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

By Jens Lysgaard, Adam N. Letchford, Richard W. Eglese. Mathematical programming, 2004

673 citations recorded by the source corpus.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/3455f18b21f0db1935efd82a4f550cd2093f319f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Industrial and Manufacturing Engineering

Citations in the corpus

A general heuristic for vehicle routing problems (2007, methodology): “One of the best branch-and-cut algorithms for the CVRP was developed by Lysgaard et al. [41].”
New benchmark instances for the Capacitated Vehicle Routing Problem (2017, background): “Although 90 out of its 95 instances have no more than 100 customers, several such instances were still very challenging for the branch-and-cut algorithms (like [1, 2, 3, 6, 20, 24, 34]) which prevailed at that time.”
Routing problems with loading constraints (2010, background): “of the CVRP, tightened by families of valid inequalities (see Lysgaard et al. 2004 ).”
An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts (2008, methodology): “[32] with the Set Partitioning (SP) approach.”
Bin packing and cutting stock problems: Mathematical models and exact algorithms (2016, background): “Lysgaard, included in a package, CVRPSEP, as a part of a separation routine for the Capacitated Vehicle Routing Problem (see [103]).”
New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem (2011, methodology): “The lower bound is computed by a column-and-cut generation method that uses s-cycle-free q-routes (with s up to 4) instead of feasible cvrp routes and the valid inequalities used by Lysgaard et al. (2004).”
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows (2008, methodology): “…either two or greater than or equal to four, i.e., ∑ k∈K ∑ i j ∈ + S xijk+ xjik = 2 and ∑ k∈K ∑ i j ∈ + S xijk+ xjik 4 We are using the cut library of Lysgaard (2003) to separate candidate sets for branching, which is an implementation of the heuristic methods described in Lysgaard et al. (2004).”
Combinatorial optimization and Green Logistics (2010, methodology): “Some exact methods have been tailored for this problem (e.g., Laporte and Nobert 1987; Agarwal et al. 1989; Lysgaard et al. 2004; Fukasawa et al. 2006).”
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem (2004, methodology): “Besides the well-known rounded capacity cuts (10) and bound cuts (11), we also use framed capacity, strengthened comb, multistar, partial multistar, generalized multistar and hypotour cuts, all presented in [23].”
Learning Improvement Heuristics for Solving Routing Problems (2019, methodology): “Exact methods are often designed based on the branch-and-bound framework, which have the theoretical guarantee of ﬁnding the optimal solution, but practically limited to small instances for their exponential complexity in the worst case [3], [4].”
A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty (2008, methodology): “The VRP is known to be NP-hard (Lenstra and Rinnooy Kan, 1981), but nevertheless, there has been considerable work on developing exact solution procedures, see for instance Ralphs et al. (2003), Baldacci et al. (2004), Lysgaard et al. (2004), and Fukasawa et al. (2006).”
Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints (2012, methodology): “Lysgaard et al. (2004) described a BC algorithm based on formulation F , strengthened by valid inequalities, including the rounded capacity , generalized capacity , framed capacity , strengthened comb , multistar , partial multistar , extended hypotour inequalities , and Gom-ory mixed integer cuts .”