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

By Roberto Baldacci, Nicos Christofides, Aristide Mingozzi. Mathematical programming, 2008

414 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/58dec1845f30840d702a4b5111afbc8e72563cf9

How researchers see this paper

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

In Building and Construction

In Industrial and Manufacturing Engineering

In Transportation

Citations in the corpus

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.”
What you should know about the vehicle routing problem (2007, background): “Thus, Baldacci, Christofides and Mingozzi [5] use the clique inequalities.”
New benchmark instances for the Capacitated Vehicle Routing Problem (2017, background): “[4, 5] significantly reduced the CPU time required to solve many ABEFMP instances, but could not solve the three larger M instances.”
Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints (2012, methodology): “The optimal solution cost of the LP-relaxation of SP, called LSP, dominates the lower bounds provided by the LP-relaxation of formulation F when k(S) = q(S)/Q (see Baldacci et al., 2004) because any LSP solution implicitly satisfies a variety of valid inequalities that are not implied by the LP-rela”
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…”
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, result): “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).”