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

By Paolo Toth, Daniele Vigo. Discrete Applied Mathematics, 2002

1,029 citations recorded by the source corpus.

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 different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/b2de7e58521b308415865fda246fe5a4245327e9

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

Location-routing: Issues, models and methods (2007, methodology): “For vehicle routing, we can recommend Christofides et al. (1979), Laporte (2000) and Toth and Vigo (2002a, 2002b).”
Search and pursuit-evasion in mobile robotics (2011, background): “Relation to the vehicle routing problem (e.g., see Lenstra and Kan (1981); Toth and Vigo (2002)) in operations research o ﬀ ers numerous approximation algorithms, often relying on customized branch-and-bound approaches (Washburn, 1998).”
When immediate interactive feedback boosts optimization problem solving: A 'human-in-the-loop' approach for solving Capacitated Vehicle Routing Problems (2017, background): “…solving constitutes a cognitive process that relates strongly to everyday applied tasks (e.g. finding the best and most efficient route between two locations) and has strong applications in the field of Operational Research (OR) and Transport Logistics (Danzig & Ramser, 1959; Toth & Vigo, 2002).”
Inverse optimization with endogenous arrival time constraints to calibrate the household activity pattern problem (2012, background): “Vehicle routing problems (VRPs) (reviewed by Toth and Vigo (2002)) represent a broad field of prescriptive models that provide optimal solutions to fulfill an objective subject to constraints through the use of mixed integer linear programming (MILP).”
The vehicle routing problem: State of the art classification and review (2016, background): “A number of books (e.g. Golden, Raghavan, & Wasil, 2008; Toth & Vigo, 2002, 2014) and a considerable amount of proceedings have also contributed to the VRP literature that exists today.”
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows (2009, background): “The CVRP and VRPTW are well known combinatorial optimization problems which have received a lot of attention (see, e.g., Toth and Vigo, 2002).”