In this paper we address the classical Vehicle Routing Problem (VRP), where (at most) $k$ minimum-cost routes through a central depot are constructed to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. We present a Local Search algorithm for VRP, based on the exploration of an exponential neighborhood by solving an Integer Linear Programming (ILP) problem. Our starting point is the following refinement heuristic procedure proposed by De Franceschi et al.: given an initial solution to be possibly improved, (a) select several customers from the current solution, and build the restricted solution obtained from the current one by extracting (i.e., short-cutting) the selected customers; (b) reallocate the extracted customers to the restricted solution by solving an ILP problem, in the attempt of finding a new improved solution. We present a generalization of the neighborhood proposed in this method, and investigate the Column Generation Problem associated with the Linear Programming (LP) relaxation of the ILP formulation corresponding to the neighborhood. In particular, we propose a two-phase approach for the neighborhood exploration, which first reduces the neighborhood size through a simple heuristic criterion, and then explores the reduced neighborhood by solving the corresponding ILP formulation through the (heuristic) solution of the Column Generation Problem associated with its LP relaxation. We report computational results on capacitated VRP instances from the literature (with/without distance constraints), which are usually used as benchmark instances for the considered problem. In several cases, the proposed algorithm is able to find the new best-known solution in the literature.

An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems

TOTH, PAOLO;
2008

Abstract

In this paper we address the classical Vehicle Routing Problem (VRP), where (at most) $k$ minimum-cost routes through a central depot are constructed to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. We present a Local Search algorithm for VRP, based on the exploration of an exponential neighborhood by solving an Integer Linear Programming (ILP) problem. Our starting point is the following refinement heuristic procedure proposed by De Franceschi et al.: given an initial solution to be possibly improved, (a) select several customers from the current solution, and build the restricted solution obtained from the current one by extracting (i.e., short-cutting) the selected customers; (b) reallocate the extracted customers to the restricted solution by solving an ILP problem, in the attempt of finding a new improved solution. We present a generalization of the neighborhood proposed in this method, and investigate the Column Generation Problem associated with the Linear Programming (LP) relaxation of the ILP formulation corresponding to the neighborhood. In particular, we propose a two-phase approach for the neighborhood exploration, which first reduces the neighborhood size through a simple heuristic criterion, and then explores the reduced neighborhood by solving the corresponding ILP formulation through the (heuristic) solution of the Column Generation Problem associated with its LP relaxation. We report computational results on capacitated VRP instances from the literature (with/without distance constraints), which are usually used as benchmark instances for the considered problem. In several cases, the proposed algorithm is able to find the new best-known solution in the literature.
2008
The Vehicle Routing Problem: latest Advances and New Challenges
275
295
P.Toth; A. Tramontani
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/63533
 Attenzione

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

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