This article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensivecomputational experiments.

A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints / M., Gendreau; Iori, Manuel; G., Laporte; S., Martello. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 51:1(2008), pp. 4-18. [10.1002/net.20192]

A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints

IORI, MANUEL;
2008

Abstract

This article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensivecomputational experiments.
2008
51
1
4
18
A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints / M., Gendreau; Iori, Manuel; G., Laporte; S., Martello. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 51:1(2008), pp. 4-18. [10.1002/net.20192]
M., Gendreau; Iori, Manuel; G., Laporte; S., Martello
File in questo prodotto:
File Dimensione Formato  
PaperNetworks.pdf

Accesso riservato

Descrizione: Articolo principale
Tipologia: Versione pubblicata dall'editore
Dimensione 248 kB
Formato Adobe PDF
248 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
GILM_JAN_07.pdf

Open access

Descrizione: versione post-print
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 230.54 kB
Formato Adobe PDF
230.54 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/585510
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 185
  • ???jsp.display-item.citation.isi??? 148
social impact