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.

Classical Exact Algorithms for the Capacitated Vehicle Routing Problem

TOTH, PAOLO;VIGO, DANIELE
2014

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.
VEHICLE ROUTING: PROBLEMS, METHODS, AND APPLICATIONS, SECOND EDITION
37
57
MOS-SIAM SERIES ON OPTIMIZATION
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: http://hdl.handle.net/11585/527551
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 21
social impact