A Relax and Cut Algorithm for the Vehicle Routing Problem (2026)

An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

Mathematical Programming, 2008

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.

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

Computational Management Science, 2010

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, 123 230 R. Baldacci et al. 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.

Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows

Operations Research, 2008

This paper presents a branch-and-cut-and-price algorithm for the vehicle-routing problem with time windows. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set-partitioning problem as the master problem and an elementary shortest-path problem with resource constraints as the pricing problem. We introduce the subset-row inequalities, which are Chvatal-Gomory rank-1 cuts based on a subset of the constraints in the master problem. Applying a subset-row inequality in the master problem increases the complexity of the label-setting algorithm used to solve the pricing problem because an additional resource is added for each inequality. We propose a modified dominance criterion that makes it possible to dominate more labels by exploiting the step-like structure of the objective function of the pricing problem. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying ...

A unified exact method for solving different classes of vehicle routing problems

Mathematical Programming, 2009

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.

Computational results with a branch and cut code for the capacitated vehicle routing problem

1995

In this paper, we present a branch-and-cut algorithm to solve the Capacitated Vehicle Routing Problem (CVRP) to optimality, which is based on the partial polyhedral description of the corresponding polytope. The valid inequalities used in the algorithm are proposed and described in Harche (1993), De Vitis, Harche, and, and in where also unpublished inequalities of Augerat and Pochet can be found. We concentrated mainly on the design of separation procedures for several classes of valid inequalities.

A Branch-and-Price-and-Cut Algorithm for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

Transportation Science

The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) is a practical variant of the classic capacitated vehicle routing problem. A number of algorithms have been developed for the problem, but it is very difficult for the existing exact methods to optimally solve instances featuring with large rectangular items. To address this issue, a branch-and-price-and-cut (BPC) algorithm is proposed in this study. A novel data structure and a new dominance rule are developed to build an exact pricing algorithm that takes the loading constraints into account. Several valid inequalities are used to strengthen the linear relaxation. Extensive computational experiments were conducted on the benchmark instances of the 2L-CVRP, showing that the BPC algorithm outperforms all the existing exact methods for the problem in terms of the solution quality. Fourteen instances are solved to optimality for the first time. In particular, the size of solvable instances with large items ...

Recent advances in vehicle routing exact algorithms

4OR: A Quarterly Journal of Operations …, 2007

5 Comparison of various VRP relaxations 6 Branch-and-cut methods Separation algorithms Branching strategies 7 Branch-and-cut-and-price method R. Baldacci (DEIS) Exact Algorithms for the VRP May 12, 2008 2 / 66 Outline (2) Pricing and cut generation 8 Set partitioning with additional cuts Finding an optimal VRP solution Bounding procedure Route generation algorithm 9 Summary of the computational experiments 10 Appendix 11 References R. Baldacci (DEIS) Exact Algorithms for the VRP May 12, 2008 3 / 66 Problem description

Models, relaxations and exact approaches for the capacitated vehicle routing problem

Discrete Applied Mathematics, 2002

In this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of di erent relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this ÿeld.

A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem

Transportation Science, 2013

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms.

Exact algorithms for different classes of vehicle routing problems

4OR, 2012

Chapter 1 Introduction vehicles, especially freight vehicles, in city centers and want to switch from large to smaller vehicles. In Chapter 6, we introduce a new mathematical formulation of the 2E-CVRP that is used to derive both integer and continuous relaxations. We present a new bounding procedure based on dynamic programming and an exact algorithm that decomposes the 2E-CVRP into a set of CVRPs with multiple depots and side constraints. The new algorithm is tested on five sets of instances from the literature and a new set of instances with up to 100 customers and 6 satellites. Computational results show that 144 out of 153 instances from the literature were solved, 97 of which for the first time. The comparisons with the state-of-the-art exact methods show that new exact method compares favorably with the other exact methods from the literature.

Introducing Subset Row Inequalities in a Branch-and-Cut-and-Price Algorithm for the Vehicle Routing Problem with Time Windows

Chvatal rank-1 cuts based on a subset of the constraints in the master problem. The use of Subset Row Inequalities results in a weak dominance criteria when using label-setting algorithms to solve the pricing problem. This paper presents an improved dominance criteria making it possible to handle the step-like objective function of the pricing problem in a reasonable way. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying Subset Row Inequalities in the master problem significantly improves the lower bound and in many cases makes it possible to prove optimality in the root node. Operations Research 00(0), pp. 000-000, c 0000 INFORMS Constraints (SPPRC) and can be solved in pseudopolynomial time using label-setting algorithms. To improve lower bounds of the master problem Desrochers et al. (1992) used 2-cycle elimination which was later extended by Irnich and Villeneuve (2006) to k-cycle elimination (k-cyc-SPPRC) where cycles containing k or less nodes are not permitted. Beasley and Christofides (1989) proposed to solve the ESPPRC using Lagrangian relaxation. However, recently label-setting algorithms have become the most popular approach to solve the ESPPRC, see e.g. Dumitrescu (2002) and Feillet et al. (2004). Righini and Salani (2004) developed a label-setting algorithm using the idea of Dijkstra's bidirectional shortest path algorithm that expands both forward and backward from the depot and connects routes in the middle, thereby potentially reducing the running time of the algorithm. Furthermore Righini and Salani (2005) and Boland et al. (2006) proposed a decremental state space algorithm that iteratively solves a SPPRC by applying resources forcing nodes to be visited at most once. In Petersen and Spoorendonk (2006) both of the above results have been extended to the label-setting algorithms for the k-cyc-SPPRC, however we only consider the traditional elementary algorithm in this paper. Recently Chabrier (2005), Danna and Pape (2005), and Salani (2005) successfully solved several previously unsolved instances of the VRPTW from the benchmarks of Solomon (1987) using a label-setting algorithm for the ESPPRC. In this paper we extend the BCP framework to include valid inequalities for the master problem, more specifically by applying the subset row (SR) inequalities to the Set Partition master problem. This leads to an increased complexity of the pricing problem since each SR-inequality is represented by an additional resource. Moreover, the additional resources seriously weaken the dominance rules when extending labels due to a step-like function in the reduced cost. However, the SRinequalities will potentially provide better lower bounds and smaller branch trees. To improve the performance of the label-setting algorithm we introduce an extended dominance criteria that handles the reduced cost calculation in a reasonable way. Nemhauser and Park (1991) developed a similar BCP algorithm for the Edge Coloring Problem, but to our knowledge no such algorithms for VRPTW have been presented.

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

Mathematical Programming, 2006

During the eigthies and early nineties, the best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) utilized lower bounds obtained by Lagrangean relaxation or column generation. Next, the advances in the polyhedral description of the CVRP yielded branch-andcut algorithms giving better results. However, several instances in the range of 50-80 vertices, some proposed more than 30 years ago, can not be solved with current known techniques. This paper presents an algorithm utilizing a lower bound obtained by minimizing over the intersection of the polytopes associated to a traditional Lagrangean relaxation over q-routes and the one defined by bounds, degree and the capacity constraints. This is equivalent to a linear program with an exponential number of both variables and constraints. Computational experiments show the new lower bound to be superior to the previous ones, specially when the number of vehicles is large. The resulting branch-and-cut-and-price could solve to optimality almost all instances from the literature up to 100 vertices, nearly doubling the size of the instances that can be consistently solved. Further progress in this algorithm may be soon obtained by also using other known families of inequalities. A landmark exact algorithm for the CVRP was presented in 1981 by Christofides, Mingozzi and Toth [16] using a Lagrangean bound obtained by solving minimum q-route problems. A q-route starts at the depot and traverses a sequence of clients limiting the demand accumulated to at most C and returns to the depot. It is not necessarily a simple path, for some clients may be visited more than once. Therefore, the set of valid CVRP routes is contained in the set of q-routes. The resulting branch-and-bound could solve instances up to 25 vertices, a quite respectful size at that time. Several other branch-and-bound algorithms using Lagrangean bounds appear in the literature. This same article [16] also describes a lower bound based on k-degree center trees, minimum spanning trees having degree K ≤ k ≤ 2K on the depot, plus 2K − k least cost edges. Other authors propose Lagrangean bounds based on K-trees, which are sets of n + K edges spanning G, like Fisher [21] and Martinhon, Lucena and Maculan [29]. There is also an algorithm based on minimum b-matchings having degree 2K at the depot and 2 on the remaining vertices by Miller [30]. The Lagrangean bounds can be improved by dualizing capacity inequalities [21, 30] and also combs and multistar inequalities [29]. Another kind of exact algorithms have its stem on the formulation of the CVRP as a set partition problem by Balinsky and Quandt [9]. In that formulation, a column covers a set of vertices S with total demand not exceeding C and have the cost of a minimum route over {0} ∪ S. Bramel and Simchi-Levi [13] proved that for certain natural classes of instances, the ratio between the lower bounds given by that formulation and the optimal solution values asymptotically approaches 1 as the number of clients grows. However, that formulation in itself is not practical because pricing over the exponential number of columns require the solution of capacitated prize-collecting TSPs, a problem almost as difficult as the CVRP itself. Agarwal, Marthur and Salkin [3] proposed a column generation algorithm on a modified set partition where column costs are given by a linear function over the vertices yielding a lower bound on the actual route cost. Columns with the modified cost can be priced by solving easy knapsack problems. Hadjconstantinou et al. [23] derive lower bounds from heuristic solutions to the dual of the set partitioning formulation. Those dual solutions are obtained by the so-called additive approach, combining the q-path with the K-shortest path relaxations. For further information and some comparative results on the above mentioned algorithms, we refer the reader to the survey by Toth and Vigo [37]. Starting in the 90's, most of the research effort on the CVRP is now concentrated on the polyhedral description of convex hull of the edge incidence vectors that correspond to K feasible routes and on the development of effective separation algorithms for the families of valid inequalities identified (for instance, [4, 14, 18, 6, 7, 2, 31, 27]). In particular, Araque et al. [5], Augerat et al. [8], Blasum and Hochstattler [12], Ralphs et al. [36], Achutan, Caccetta and Hill [1] and Lysgard, Letchford and Eglese [28] describe complete branch-and-cut algorithms, some including sophisticated inequalities such as framed capacity, strengthened combs, multistar, among others. (The taxonomy and nomenclature of valid inequalities for the CVRP is not uniform in the literature, we are following [28] in this article.) Although those are the best exact algorithms currently available for the CVRP, the lower bounds obtained at the root nodes, even after adding all those cuts, are not very tight for many instances with as little as 40 vertices. The quality of those bounds is specially problematic for larger values of K, say K ≥ 7. Many nodes in a branch-and-cut tree may have to be explored in order to close the resulting duality gaps. Even resorting to massive computational power (up to 80 processors running in parallel in a recent work by Ralphs [36, 35]) several instances with less than 80 vertices, including some proposed more than 30 years ago by Christofides and Eilon [15], can not be solved at all. In fact, it seems that branch-and-cut algorithms for the CVRP are experimenting a "diminishing returns" phenomenon, where substantial theoretical and implementation efforts leads to practical results that are only marginally better than those of previous works. This work presents a new exact algorithm for the CVRP that seems to break through this situation. The main idea is to combine the branch-and-cut approach with the old q-routes approach (which we interpret as a column generation instead of the original Lagrangean relaxation)

Lower Bounds and an Exact Method for the Capacitated Vehicle Routing Problem

2006 International Conference on Service Systems and Service Management, 2006

In this paper we consider the problem in which a fleet of M vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. This problem is referred as the Capacitated Vehicle Routing Problem (CVRP). We present an exact algorithm for solving the CVRP based on a Set Partitioning formulation of the problem. We describe a procedure for computing a valid lower bound to the cost of the optimal CVRP solution that finds a feasible solution of the dual of the LP-relaxation of the set partitioning formulation without generating the entire set partitioning matrix. The dual solution obtained is then used to limit the set of the feasible routes containing the optimal CVRP solutions. The resulting Set Partitioning problem is solved by using a branch and bound algorithm. Computational results are presented for a number of problems derived from the literature. The results show the effectiveness of the proposed method in solving problems up to about 100 customers.

Lifted and Local Reachability Cuts for the Vehicle Routing Problem with Time Windows

Computers & Operations Research, 2013

The Vehicle Routing Problem with Time Windows (VRPTW) requires to design minimum cost routes for a fleet of vehicles with identical capacities to serve a set of customers within given time windows. Each customer must be visited exactly once and the load of a vehicle must not exceed its capacity. In this paper we introduce two new basic families of valid inequalities, called Lifted and Local Reachability Cuts, respectively, which extend the Reachability Cuts introduced by J. Lysgaard. Separation procedures for Lifted and Local Reachability Cuts have been implemented and embedded into a Branch-and-Cut framework to validate their computational effectiveness. They were tested on the Solomon and on the Gehring-Homberger benchmark instances (also known as the "Extended Solomon" instances) with 200 customers. Computational experiments show that the new cutting plane families can substantially improve the lower bounds returned by Lysgaard's Reachability Cuts. The Branch-and-Cut algorithm could also provide the optimal solution of three previously unsolved instances-C222, C225 and C226with large capacities and wide time windows and therefore difficult for exact algorithms.

Branch-cut-and-price algorithms for the vehicle routing problem with backhauls

HAL (Le Centre pour la Communication Scientifique Directe), 2019

New Valid Inequalities for the Two-Echelon Capacitated Vehicle Routing Problem

Electronic Notes in Discrete Mathematics

We introduce new valid inequalities for the two-echelon variant of the Capacitated Vehicle Routing Problem (CVRP)In particular, a first group of inequalities is obtained by extending to 2E-CVRP some of the most effective among the existing CVRP valid inequalities. A second group of inequalities is explicitly derived for the 2E-CVRP and concerns the flow feasibility at customer nodes and the satellitecustomer route connectivity. The inequalities are then introduced in a Branch & Cut algorithm. Computational results show that the proposed algorithm is able both to solve to optimality many open literature instances and significantly reduce the optimality gap for the remaining instances.

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

Mathematical Programming, 1981

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 spanning k-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 the q-routes are superior to those from k-DCT and that VRPs of up to about 25 customers can be solved exactly.

New Lower Bounds for the Split Delivery Vehicle Routing Problem

This paper presents an algorithm to obtain lower bounds for the Split Delivery Vehicle Routing Problem. An extended formulation over a large set of variables is provided and valid inequalities are identified. The algorithm combines column and cut generation and was able to improve the lower bound for almost all instances tested.

On the capacitated vehicle routing problem

Mathematical …, 2003

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. *

Limited memory Rank-1 Cuts for Vehicle Routing Problems

Operations Research Letters

Pecin et al. (2016) introduced a "limited memory" technique that allows an efficient use of Rank-1 cuts in the Set Partitioning Formulation of Vehicle Routing Problems, motivating a deeper investigation of those cuts. This work presents a computational polyhedral study that determines the best possible sets of multipliers for cuts with up to 5 rows. Experiments with CVRP instances show that the new multipliers lead to significantly improved dual bounds and contributes decisively for solving an open instance with 420 customers.