In this chapter we present an overview of the early exact methods used for the solution of the Capacitated Vehicle Routing Problem (CVRP). The CVRP is an extension of the well-known Traveling Salesman Problem (TSP), calling for the determination of a Hamiltonian circuit with minimum cost visiting exactly once a given set of points. Therefore, the foundation of many exact approaches for the CVRP were derived from the extensive and successful work done for the exact solution of the TSP. However, even if tremendous progress has been made with respect to the first algorithms, such as the tree search method by Christofides and Eilon [17], the CVRP is still far from being satisfactorily solved. Our analysis encompasses more than three decades of research and examines the main families of approaches, from direct tree search methods based on Branch-and-Bound to column generation and Branch-and-Cut algorithms presented around the year 2000. The wide variety and richness of methods proposed in these early decades of CVRP history is witnessed by the good number of survey works that analyzed the relevant literature. Following the first comprehensive work of Laporte and Nobert [39], several review papers were devoted to the analysis of exact algorithms for the VRP as those of Laporte [36], Toth and Vigo [52, 53], Bramel and Simchi-Levi [15], Naddef and Rinaldi [47], Cordeau et al. [20], and Baldacci, Toth, and Vigo [10,11]. More recent Branch-and-Cut-and-Price algorithms, which have successfully combined and enhanced those described in the following, will be covered in detail in Chapter 3.

Frederic, S., Paolo, T., Daniele, V. (2014). Classical Exact Algorithms for the Capacitated Vehicle Routing Problem. Philadelpia : Society for Industrial and Applied Mathematics [10.1137/1.9781611973594.ch2].

### Classical Exact Algorithms for the Capacitated Vehicle Routing Problem

#### Abstract

In this chapter we present an overview of the early exact methods used for the solution of the Capacitated Vehicle Routing Problem (CVRP). The CVRP is an extension of the well-known Traveling Salesman Problem (TSP), calling for the determination of a Hamiltonian circuit with minimum cost visiting exactly once a given set of points. Therefore, the foundation of many exact approaches for the CVRP were derived from the extensive and successful work done for the exact solution of the TSP. However, even if tremendous progress has been made with respect to the first algorithms, such as the tree search method by Christofides and Eilon [17], the CVRP is still far from being satisfactorily solved. Our analysis encompasses more than three decades of research and examines the main families of approaches, from direct tree search methods based on Branch-and-Bound to column generation and Branch-and-Cut algorithms presented around the year 2000. The wide variety and richness of methods proposed in these early decades of CVRP history is witnessed by the good number of survey works that analyzed the relevant literature. Following the first comprehensive work of Laporte and Nobert [39], several review papers were devoted to the analysis of exact algorithms for the VRP as those of Laporte [36], Toth and Vigo [52, 53], Bramel and Simchi-Levi [15], Naddef and Rinaldi [47], Cordeau et al. [20], and Baldacci, Toth, and Vigo [10,11]. More recent Branch-and-Cut-and-Price algorithms, which have successfully combined and enhanced those described in the following, will be covered in detail in Chapter 3.
##### Scheda breve Scheda completa Scheda completa (DC)
2014
VEHICLE ROUTING: PROBLEMS, METHODS, AND APPLICATIONS, SECOND EDITION
37
57
Frederic, S., Paolo, T., Daniele, V. (2014). Classical Exact Algorithms for the Capacitated Vehicle Routing Problem. Philadelpia : Society for Industrial and Applied Mathematics [10.1137/1.9781611973594.ch2].
Frederic, Semet; Paolo, Toth; Daniele, Vigo
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11585/527551`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• 25