A heuristic algorithm for the asymmetric capacitated vehicle routing problem

We consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP[, a particular case of the standard asymmetric Vehicle Routing Problem arising when only the vehicle capacity constraints are imposed. ACVRP is known to be NP-hard and finds practical applications, e.g. in distribution and scheduling. In this paper we describe the extension to ACVRP of the two well-known Clarke-Wright and Fisher-Jaikumar heuristic algorithms. We also propose a new heuristic algorithm for ACVRP that, starting with an initial infeasible solution, determines the final set of vehicle routes through an insertion procedure as well as intea-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described by Fischetti, Toth and Vigo in 1992. Extensive computational results on several classes of randomly generated test problems involving up to 300 customers and on some real instances of distribution problems in urban areas, are presented. The results obtained show that the proposed approach favourably compares with previous algorithms from the literature.     

A new branch-and-cut algorithm for the capacitated vehicle routing problem

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

On the tour partitioning heuristic for the unit demand capacitated vehicle routing problem

The tour partitioning heuristic for the vehicle routing problem assumes an unlimited supply of vehicles. If the number of vehicles is fixed, this heuristic may produce infeasible solutions. We modify the heuristic to guarantee feasibility in this situation and we analyze the worst-case performance of the modified heuristic.     

A new tabu search heuristic for the open vehicle routing problem

In this paper, another version of the vehicle routing problem (VRP)—the open vehicle routing problem (OVRP) is studied, in which the vehicles are not required to return to the depot, but if they do, it must be by revisiting the customers assigned to them in the reverse order. By exploiting the special structure of this type of problem, we present a new tabu search heuristic for finding the routes that minimize two objectives while satisfying three constraints. The computational results are provided and compared with two other methods in the literature.     

A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times

This paper describes a generalized variable neighborhood search heuristic for the Capacitated Vehicle Routing Problem with Stochastic Service Times, in which the service times at vertices are stochastic. The heuristic is tested on randomly generated instances and compared with two other heuristics and with an alternative solution strategy. Computational results show the superiority and effectiveness of the proposed heuristic.     

On the capacitated vehicle routing problem

 We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002 Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

A branch-and-cut algorithm for the capacitated open vehicle routing problem

In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch-and-cut. We show that, even though the open CVRP initially looks like a minor variation of the standard CVRP, the integer programming formulation and cutting planes need to be modified in subtle ways. Computational results are given for several standard test instances, which enables us for the first time to assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.     

A heuristic method for the open vehicle routing problem

The open vehicle routing problem (OVRP) differs from the classic vehicle routing problem (VRP) because the vehicles either are not required to return to the depot, or they have to return by revisiting the customers assigned to them in the reverse order. Therefore, the vehicle routes are not closed paths but open ones. A heuristic method for solving this new problem, based on a minimum spanning tree with penalties procedure, is presented. Computational results are provided.     

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available.     

The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index.     

The savings algorithm for the vehicle routing problem

Survey is given concerning the savings method for the vehicle routing problem. Results for several methods and data sets are compared. Furthermore, modifications of the savings method are presented which show less CPU time and reduced storage requirements. Therefore, the savings method can be implemented on microcomputers.     

Erratum: A new tabu search heuristic for the open vehicle routing problem

Correction to: Journal of the Operational Research Society (2005) 56, 267–274. doi:10.1057/palgrave.jors.2601817     

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.     

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 branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

This article introduces a new exact algorithm for the capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSD can be formulated as a set partitioning problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme. Computational experiments show promising results.     

A brain storm optimization approach for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a combinatorial optimization problem which aims to minimize the sum of arrival times at customers. This paper presents a brain storm optimization algorithm to solve the CCVRP. Based on the characteristics of the CCVRP, we design new convergent and divergent operations. The convergent operation picks up and perturbs the best-so-far solution. It decomposes the resulting solution into a set of independent partial solutions and then determines a set of subproblems which are smaller CCVRPs. Instead of directly generating solutions for the original problem, the divergent operation selects one of three operators to generate new solutions for subproblems and then assembles a solution to the original problem by using those new solutions to the subproblems. The proposed algorithm was tested on benchmark instances, some of which have more than 560 nodes. The results show that our algorithm is very effective in contrast to the existing algorithms. Most notably, the proposed algorithm can find new best solutions for 8 medium instances and 7 large instances within short time.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

A bi-criteria heuristic for the vehicle routing problem with time windows

This paper describes a heuristic for the Vehicle Routing and Scheduling Problem with Time Windows (VRSPTW). Unique to this problem are the so-called time windows, i.e. time slots during which the vehicle must arrive at the customer to deliver the goods. The heuristic builds on the well-known Clarke and Wright Savings method with an additional criterion that models an intuitive view of time influence on route building. Experiments show that this added criterion yields significantly better solutions to the VRSPTW than pure routing heuristics, and also compares favorably to other new heuristics, developed specifically for the VRSPTW.