A note on the truck and trailer routing problem

This study considers the relaxed truck and trailer routing problem (RTTRP), a relaxation of the truck and trailer routing problem (TTRP). TTRP is a variant of the well studied vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service a set of customers with known demands. Some customers may be serviced by a truck pulling a trailer, while the others may only be serviced by a single truck. This is the main difference between TTRP and VRP. The number of available trucks and available trailers is limited in the original TTRP but there are no fixed costs associated with the use of trucks or trailers. Therefore, it is reasonable to relax this fleet size constraint to see if it is possible to further reduce the total routing cost (distance). In addition, the resulting RTTRP can also be used to determine a better fleet mix. We developed a simulated annealing heuristic for solving RTTRP and tested it on 21 existing TTRP benchmark problems and 36 newly generated TTRP instances. Computational results indicate that the solutions for RTTRP are generally better than the best solutions in the literature for TTRP. The proposed SA heuristic is able to find better solutions to 18 of the 21 existing benchmark TTRP instances. The solutions for the remaining three problems are tied with the best so far solutions in the literature. For the 36 newly generated problems, the average percentage improvement of RTTRP solutions over TTRP solutions is about 5%. Considering the ever rising crude oil price, even small reduction in the route length is significant.     

Arc routing in a node routing environment

We describe a special variant of the vehicle routing problem (VRP), where there are many customers per road segment. This class of VRPs arises in, e.g. mail delivery, and is a borderline case where both arc routing and node routing techniques may be applied for modeling and solving. In a real-world setting, the problem should be modeled so as to incorporate all important constraining factors. We use a simplified node routing model and aggregate customers into supernodes to reduce problem size. A tabu search metaheuristic for the standard node routing-based VRP is then applied to the aggregated version of the problem. Our method is tested both on test instances from the literature as well as on a portfolio of new test instances especially made to fit the problem at hand. Experimental results are reported, showing that aggregation of customers can lead to substantial improvements both in solution time and solution quality in this setting, especially for larger instances.     

A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints

This paper addresses an extension of the capacitated vehicle routing problem where the client demand consists of three-dimensional weighted items (3L-CVRP). The objective is to design a set of trips for a homogeneous fleet of vehicles based at a depot node which minimizes the total transportation cost. Items in each vehicle trip must satisfy the three-dimensional orthogonal packing constraints. This problem is strongly connected to real-life transportation systems where the packing of items to be delivered by each vehicle can have a significant impact on the routes. We propose a new way to solve the packing sub-problem. It consists of a two-step procedure in which the z-constraints are first relaxed to get a (x,y) positioning of the items. Then, a compatible z-coordinate is computed to get a packing solution. Items can be rotated but additional constraints such as item fragility, support and LIFO are not considered. This method is included in a GRASP×ELS hybrid algorithm dedicated to the computation of VRP routes. The route optimization alternates between two search spaces: the space of VRP routes and the space of giant trips. The projection from one to the other is done by dedicated procedures (namely the Split and the concatenation algorithms). Moreover, a Local Search is defined on each search space. Furthermore, hash tables are used to store the result of the packing checks and thus save a substantial amount of CPU time. The effectiveness of our approach is illustrated by computational experiments on 3L-CVRP instances from the literature. A new set of realistic instances based on the 96 French districts are also proposed. They range from 19 nodes for the small instances to 255 nodes for the large instances and they can be stated as realistic since they are based on true travel distances in kilometers between French cities. The impact of the hash tables is illustrated as well.     

A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints

The capacitated vehicle routing problem with three-dimensional loading constraints combines capacitated vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, unloading operations. An efficient hybrid algorithm including a tabu search algorithm for routing and a tree search algorithm for loading is introduced. Computational results are presented for all publicly available test instances. Most of the best solutions previously reported in literature have been improved while the computational effort is drastically reduced compared to other methods.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

Vehicle routing with cross-dock selection

The vehicle routing problem with cross-dock selection is a variant of the vehicle routing problem containing spatial and load synchronization constraints by which products are transferred and processed via at least one cross-dock. This paper presents a mathematical formulation of the problem and an adaptive large neighborhood search heuristic. Computational experiments on a set of benchmark instances demonstrate the efficiency of the proposed methodology.     

A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints

This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.     

The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results

The multi-depot split delivery vehicle routing problem combines the split delivery vehicle routing problem and the multiple depot vehicle routing problem. We define this new problem and develop an integer programming-based heuristic for it. We apply our heuristic to 30 instances to determine the reduction in distance traveled that can be achieved by allowing split deliveries among vehicles based at the same depot and vehicles based at different depots. We generate new test instances with high-quality, visually estimated solutions and report results on these instances.     

An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup

In this paper we use an ant colony system (ACS) algorithm to solve the vehicle routing problem with simultaneous delivery and pickup (VRPSDP) which is a combinatorial optimization problem. ACS is an algorithmic approach inspired by the foraging behavior of real ants. Artificial ants are used to construct a solution for the problem by using the pheromone information from previously generated solutions. The proposed ACS algorithm uses a construction rule as well as two multi-route local search schemes. The algorithm can also solve the vehicle routing problem with backhaul and mixed load (VRPBM). An extensive numerical experiment is performed on benchmark problem instances available in literature. It is found that ACS gives good results compared to the existing algorithms.     

Heuristics for a multiperiod inventory routing problem with production decisions

Manufacturers who resupply a large number of retailers on a periodic basis continually struggle with the question of how to formulate a replenishment strategy. This paper presents a comparative analysis of a series of heuristics for an inventory routing problem (IRP) that arises in a manufacturing supply chain. The IRP is formulated as a mixed integer program with the objective of maximizing the net benefits associated with making deliveries in a specific time period to a widely dispersed set of customers. It is assumed that inventory can accumulate at the customer sites, but that all demand must be met without backlogging. Because optimal solutions were not within reach of exact methods, a two-step procedure was developed that first estimates daily delivery quantities and then solves a vehicle routing problem for each day of the planning horizon. As part of the methodology, a linear program is used to determine which days it is necessary to make at least some deliveries to avoid stockouts.The IRP is investigated in the context of an integrated production–inventory–distribution–routing problem (PIDRP). The full model takes into account production decisions and inventory flow balance in each period. For the computations, a previously developed branch-and-price algorithm is used that requires the solution of multiple IRPs (one in each period) to generate columns for the master problem. Testing showed that PIDRP instances with up to eight time periods and 50 customers can be solved within 1 h. This level of performance could not be matched by either CPLEX or an exact version of the branch-and-price algorithm.     

A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows

This paper presents a hybrid evolutionary algorithm (HEA) to solve heterogeneous fleet vehicle routing problems with time windows. There are two main types of such problems, namely the fleet size and mix vehicle routing problem with time windows (F) and the heterogeneous fixed fleet vehicle routing problem with time windows (H), where the latter, in contrast to the former, assumes a limited availability of vehicles. The main objective is to minimize the fixed vehicle cost and the distribution cost, where the latter can be defined with respect to en-route time (T) or distance (D). The proposed unified algorithm is able to solve the four variants of heterogeneous fleet routing problem, called FT, FD, HT and HD, where the last variant is new. The HEA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle the heterogeneous fleet dimension. Extensive computational experiments on benchmark instances have shown that the HEA is highly effective on FT, FD and HT. In particular, out of the 360 instances we obtained 75 new best solutions and matched 102 within reasonable computational times. New benchmark results on HD are also presented.     

Metaheuristic algorithms for solving two interconnected vehicle routing problems in a hospital complex

This paper addresses a real-life logistic problem arising in the hospital complex of Tours (France). The two-level vehicle routing problem has time windows, a heterogeneous fleet, and multi-depot, multi-commodity and split deliveries. The first level concerns the routing problem for a fleet of vehicles serving several hospital units that delivers medicines, clean linen, meals, various supplies, patient files and picks up waste and dirty linen. The second level concerns the problem of routing employees between buildings within a large hospital unit. Both levels are interconnected. In addition, decisions about sizing and planning the teams of drivers and warehouse employees have to be made. Two metaheuristic algorithms are proposed to solve the entire problem: a genetic algorithm and a tabu search. The algorithms are tested on 100 instances, randomly generated on the basis of real-life instances.     

Active-guided evolution strategies for large-scale capacitated vehicle routing problems

We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 70 test instances.     

The robust vehicle routing problem with time windows

This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing adjustable robust optimization. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on a test bed composed of maritime transportation instances. These results show that the solution times are similar for both formulations while being significantly faster than the solutions times of a layered formulation recently proposed for the problem.     

Parity conditions in homotopic knock-knee routing

We examine the impact ofevenness (all cuts having even free capacity) andlocal evenness (cuts that separate a single vertex having even free capacity) on homotopic knock-knee routing. Kaufmann and Mehlhorn have presented a linear-time algorithm for routing even instances. We show that routing locally even instances is NP-hard. If we are permitted to move modules slightly, however, then we can efficiently route any locally even instance in which the free capacity of every cut is nonnegative. This fact implies that locally even instances can be one-dimensionally compacted in polynomial time. But when the assumption of local evenness is dropped, routing again becomes NP-hard, whether or not modules may move.This work was supported in part by the Deutsche Forschungsgemeinschaft, Sonderforschungsbereich 124, Teilprojekt B2 (VLSI Entwurf und Parallelität), and in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant NSF-STC88-09648. Miller Maley was also supported by a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation, Grant DMS-8705835.     

A Road Timetable to aid vehicle routing and scheduling

Both within and between urban conurbations, the time of a journey and the corresponding shortest path in a road network from an origin to a destination may depend on the time of the day, the day of the week and the season of the year. Significant journey time differences occur mainly due to recurring instances and variations in levels of traffic congestion throughout the year. This paper examines the issues involved in constructing a database of road times for a road network that uses time-dependent data on the travel times for individual roads in the network to provide the expected times and distances between locations for journeys starting at different times. The benefits of time-dependent vehicle routing and scheduling systems are demonstrated by using real-world data for the road network in the north west of England.