Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand

We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach.     

Exact algorithms for the vehicle routing problem,based on spanning tree and shortest path relaxations

We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications. We present tree search algorithms for the exact solution of the VRP incorporating lower bounds computed from (i) shortest spanningk-degree centre tree (k-DCT), and (ii)q-routes. The final algorithms also include problem reduction and dominance tests. Computational results are presented for a number of problems derived from the literature. The results show that the bounds derived from theq-routes are superior to those fromk-DCT and that VRPs of up to about 25 customers can be solved exactly.     

A self-tuning heuristic for a multi-objective vehicle routing problem

In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.     

Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs

Metaheuristic algorithms, such as simulated annealing and tabu search, are popular solution techniques for vehicle routing problems (VRPs). These approaches rely on iterative improvements to a starting solution, involving slight alterations to the routes (ie, neighbourhood moves), moving a node to a different part of a solution, swapping nodes or inverting sections of a tour, for example. When working with standard VRPs, where the costs of the arcs do not vary with advancing time, evaluating changes to the total cost following a neighbourhood move is a simple process: simply subtract the cost of the links removed from the solution and add the costs for the new links. When a time-varying aspect (eg, congestion) is included in the costs, these calculations become estimations rather than exact values. This paper focuses on a single vehicle routing problem, similar to the Travelling Salesman Problem, and investigates the potential for using estimation methods on simple models with time-variant costs, mimicking the effects of road congestion.     

Vehicle routing with stochastic demands and restricted failures

This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

Research on the vehicle routing problem with interval demands

In this paper, a vehicle routing problem with interval demands is investigated based on the motivation of dispatching vehicles to deliver perishable products in practice. A nonlinear interval-based programming method is used to build a model for the vehicle routing problem with interval demands, which assumes that demands of customers are uncertain but fall in given intervals and actual demand of a customer becomes known only when the vehicle visited the customer. A vehicle-coordinated strategy was designed to solve the service failure problem. A hybrid algorithm based on the artificial immune system is also proposed to solve the model for vehicle routing problem with interval demands. The validity of methods and sensitivity analysis are illustrated by conducting some numerical examples. We find that the tolerant possibility degree of interval number has significant impacts on the distances. The planned distance strictly increased, while the additional distance strictly decreased and the total distance after coordinated transport has a U-typed relationship with the tolerant possibility degree of interval number.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

Improved bounds for vehicle routing solutions

We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.     

New mathematical models of the generalized vehicle routing problem and extensions

The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta [1]. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bekta? formulation [2], but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case.     

A tabu search algorithm for the single vehicle routing allocation problem

In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows

We propose lifted versions of the Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows (TW). The constraints are valid for problems such as the travelling salesman problem with TW, the vehicle routing problem with TW, the generalized travelling salesman problem with TW, and the general vehicle routing problem with TW. They are corrected versions of the constraints proposed by Desrochers and Laporte (1991).     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem

Surveillance applications require a collection of heterogeneous vehicles to visit a set of targets. We consider a fundamental routing problem that arises in these applications involving two vehicles. Specifically, we consider a routing problem where there are two heterogeneous vehicles that start from distinct initial locations and a set of targets. The objective is to find a tour for each vehicle such that each of the targets is visited at least once by a vehicle and the sum of the distances traveled by the vehicles is minimal. We consider an important special case of this routing problem where the travel costs satisfy the triangle inequality and the following monotonicity property: the first vehicle’s cost of traveling between any two targets is at most equal to the second vehicle’s cost of traveling between the same targets. We present a primal-dual algorithm for this case that provides an approximation ratio of 2.     

A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

Polyhedral study of the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495.     

A column generation-based heuristic algorithm for an inventory routing problem with perishable goods

An inventory routing problem is a variation of the vehicle routing problem in which inventory and routing decisions are determined simultaneously over a given time horizon. The objective is to minimize the sum of transportation and inventory costs. In this paper, we study a specific inventory routing problem in which goods are perishable (PIRP). We develop a mathematical model for PIRP and exploit its structure to develop a column generation-based solution approach. Cutting planes are added to improve the formulation. We present computational experiments to demonstrate that our methodology is effective, and that the integration of routing and inventory can yield significant cost savings.