We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-Dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is -hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.

An exact approach for the vehicle routing problem with two-dimensional loading constraints / Iori, Manuel; J. J., SALAZAR GONZALEZ; D., Vigo. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 41:2(2007), pp. 253-264. [10.1287/trsc.1060.0165]

An exact approach for the vehicle routing problem with two-dimensional loading constraints

IORI, MANUEL;
2007

Abstract

We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-Dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is -hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.
41
2
253
264
An exact approach for the vehicle routing problem with two-dimensional loading constraints / Iori, Manuel; J. J., SALAZAR GONZALEZ; D., Vigo. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 41:2(2007), pp. 253-264. [10.1287/trsc.1060.0165]
Iori, Manuel; J. J., SALAZAR GONZALEZ; D., Vigo
File in questo prodotto:
File Dimensione Formato  
1526-5447-2007-41-02-0253.pdf

non disponibili

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 158.65 kB
Formato Adobe PDF
158.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2LCVRP-TS06.pdf

accesso aperto

Descrizione: Versione post print
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 207.33 kB
Formato Adobe PDF
207.33 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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/585504
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 206
  • ???jsp.display-item.citation.isi??? 166
social impact