In this work we formalize a new complex variant of the classical vehicle routing problem arising from a real-world application. Our formulation includes a heterogeneous fleet, a multi-day planning horizon, a complex carrier-dependent cost for vehicles, and the possibility of leaving orders unscheduled. For tackling this problem we propose a metaheuristic approach based on Tabu Search and on a combination of neighborhood relations. We perform an experimental analysis to tune and compare different combinations, highlighting the most important features of the algorithm. The outcome is that a significant improvement is obtained by a complex combination of neighborhood relations. In addition, we compare our solver with previous work on public benchmarks of a similar version of the problem, namely the Vehicle Routing Problem with Private fleet and Common carrier. The conclusion is that our results are competitive with the best ones in literature.

Tabu search techniques for the heterogeneous vehicle routing problem with time windows and carrier-dependent costs

CESCHIA, Sara;DI GASPERO, Luca;SCHAERF, Andrea
2011-01-01

Abstract

In this work we formalize a new complex variant of the classical vehicle routing problem arising from a real-world application. Our formulation includes a heterogeneous fleet, a multi-day planning horizon, a complex carrier-dependent cost for vehicles, and the possibility of leaving orders unscheduled. For tackling this problem we propose a metaheuristic approach based on Tabu Search and on a combination of neighborhood relations. We perform an experimental analysis to tune and compare different combinations, highlighting the most important features of the algorithm. The outcome is that a significant improvement is obtained by a complex combination of neighborhood relations. In addition, we compare our solver with previous work on public benchmarks of a similar version of the problem, namely the Vehicle Routing Problem with Private fleet and Common carrier. The conclusion is that our results are competitive with the best ones in literature.
File in questo prodotto:
File Dimensione Formato  
fulltext.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 636.61 kB
Formato Adobe PDF
636.61 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
art10.1007s10951-010-0213-x.pdf

non disponibili

Dimensione 636.61 kB
Formato Unknown
636.61 kB Unknown   Visualizza/Apri   Richiedi una copia
jsched2011.pdf

non disponibili

Dimensione 636.61 kB
Formato Unknown
636.61 kB Unknown   Visualizza/Apri   Richiedi una copia

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/11390/697537
 Attenzione

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

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