1 July 2019 in Transportation Science
Vehicle routing problems (VRPs) are among the most studied problems in operations research. Nowadays, the leading exact algorithms for solving many classes of VRPs are branch-price-and-cut algorithms. In this survey paper, we highlight the main methodological and modeling contributions made over the years on branch-and-price (branch-price-and-cut) algorithms for VRPs, whether they are generic or specific to a VRP variant. We focus on problems related to the classical VRP—that is, problems in which customers must be served by several capacitated trucks and which are not combinations of a VRP and another optimization problem.
1 February 2010 in European Journal of Operational Research
1 May 2014 in Discrete Optimization
1 December 2012 in Computers & Operations Research
In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.
1 August 2017 in INFORMS Journal on Computing
The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut (BPC). First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers.
1 February 2014 in INFORMS Journal on Computing
In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances.