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

By Ricardo Fukasawa, Humberto J. Longo, Jens Lysgaard, M. P. D. Aragão, Marcelo L. Reis, Eduardo Uchoa, Renato F. Werneck. Mathematical programming, 2004

621 citations recorded by the source corpus.

Subfields: Automotive Engineering, Building and Construction, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/6b1ae2c40e0e9eef4c367416053b78d2d7ebaf0d

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 Building and Construction

In Industrial and Manufacturing Engineering

Citations in the corpus

Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints (2012, methodology): “Other valid inequalities, related to k-path inequalities and called Reachability cuts, have been investigated by Lysgaard (2006). The exact algorithms for solving the resulting SP model of the VRPTW use CCG methods for computing the lower bound and either branch-and-price (BP) or BCP algorithms to f”
A new branch-and-cut algorithm for the capacitated vehicle routing problem (2004, methodology): “Future research could include the incorporation of column generation, leading to a full branch-cut-and-price algorithm along the lines of the one presented in Fukasawa et al (2006). This would no doubt lead to the solution of even more instances, especially those with small vehicle capacities and a ”
An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints (2007, background): “, some hours on a common PC) they can generally solve instances with up to 100 customers (e.g., Toth and Vigo 2002b; Fukasawa et al. 2006).”
A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty (2008, background): “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).”
Reinforcement Learning for Solving the Vehicle Routing Problem (2018, background): “This problem is computationally difficult to solve to optimality, even with only a few hundred customer nodes [12], and is classified as an NP-hard problem.”
New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem (2011, methodology): “If bmr cannot solve a problem in Step 1, we use the upper bound used by Fukasawa et al. (2006) and Baldacci et al. (2008), but, while generating the route set R3, whenever in genp F3 > 1×106, we run our implementation of the tabu search algorithm of Gendreau et al. (1994) with a time limit of 180…”
Heuristics for multi-attribute vehicle routing problems: A survey and synthesis (2013, background): “For example, the largest instances solved by Fukasawa et al. (2006) and Baldacci et al. (2008b) have a maximum of 135 customers.”
An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts (2008, methodology): “[21] and by E S P the exact set partitioning method described in Sect.”
Routing problems with loading constraints (2010, result): “We just mention here that excellent results have been recently obtained by Fukasawa, Longo, Lysgaard, Poggi de Arag̃ao, Resi, Uchoa and Werneck [49] (branch-and-cut-and-price), and by Baldacci, Christofides and Mingozzi [4] and Baldacci”
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows (2009, methodology): “For the CVRP the best results have been obtained by Fukasawa et al. (2006) and Baldacci et al. (2008), while the best results for the VRPTW have been presented by Jepsen et al. (2008) and Desaulniers et al. (2008).”
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows (2008, methodology): “To give a fair comparison between running times of our algorithm and the two most recent algorithms presented by Irnich and Villeneuve (2006) and Chabrier (2005), the CPU speed is taken into account.”
New benchmark instances for the Capacitated Vehicle Routing Problem (2017, background): “[14] solved all its instances with up to 100 customers, as well as instances M-n121-k7 and F-n135-k7 (the later was already solved since [3]).”
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, positive): “This method has been used with success in a number of vehicle routing and other graph problems [124,125].”
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).”
A Tabu Search Algorithm for a Routing and Container Loading Problem (2006, methodology): “algorithm obtained by combining branch-and-cut and branch-and-price (Fukasawa et al. 2004).”