The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a one-to-one pickup-and-delivery single-vehicle routing problem with backhaul deliveries. The vehicle carries a container divided into stacks of fixed height, each following a Last-In-First-Out policy, and the aim is to perform pickups and deliveries by minimizing the total routing cost and ensuring a feasible loading/unloading of the vehicle. A realistic generalization of the DTSPMS arises when a single vehicle is not enough to collect all products, and therefore multiple, and possibly heterogeneous vehicles are needed to perform the transportation operations. This paper introduces and formulates this generalization, that we refer as the Double Vehicle Routing Problem with Multiple Stacks. It proposes three models, the first one based on a three-index formulation and solved by a branch-and-cut algorithm, and the other two based on two set partitioning formulations using different families of columns and solved by a branch-and-price and a branch-and-price-and-cut algorithm, respectively. The performance of these algorithms has been studied on a wide family of benchmark test instances, observing that, although the branch-and-cut algorithm shows a better performance on instances with a small number of vehicles, the performance of the branch-and-price and the branch-and-price-and-cut algorithms improves as the number of vehicles grows. Additionally, the first set partitioning formulation yields tighter lower bounds, but the second formulation, because of its simplicity, provides better convergence properties, solving instances with up to fifty vertices to proven optimality.

Exact algorithms for the double vehicle routing problem with multiple stacks / Iori, Manuel; Riera Ledesma, Jorge. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 63:(2015), pp. 83-101. [10.1016/j.cor.2015.04.016]

Exact algorithms for the double vehicle routing problem with multiple stacks

IORI, MANUEL;
2015

Abstract

The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a one-to-one pickup-and-delivery single-vehicle routing problem with backhaul deliveries. The vehicle carries a container divided into stacks of fixed height, each following a Last-In-First-Out policy, and the aim is to perform pickups and deliveries by minimizing the total routing cost and ensuring a feasible loading/unloading of the vehicle. A realistic generalization of the DTSPMS arises when a single vehicle is not enough to collect all products, and therefore multiple, and possibly heterogeneous vehicles are needed to perform the transportation operations. This paper introduces and formulates this generalization, that we refer as the Double Vehicle Routing Problem with Multiple Stacks. It proposes three models, the first one based on a three-index formulation and solved by a branch-and-cut algorithm, and the other two based on two set partitioning formulations using different families of columns and solved by a branch-and-price and a branch-and-price-and-cut algorithm, respectively. The performance of these algorithms has been studied on a wide family of benchmark test instances, observing that, although the branch-and-cut algorithm shows a better performance on instances with a small number of vehicles, the performance of the branch-and-price and the branch-and-price-and-cut algorithms improves as the number of vehicles grows. Additionally, the first set partitioning formulation yields tighter lower bounds, but the second formulation, because of its simplicity, provides better convergence properties, solving instances with up to fifty vertices to proven optimality.
7-mag-2015
63
83
101
Exact algorithms for the double vehicle routing problem with multiple stacks / Iori, Manuel; Riera Ledesma, Jorge. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 63:(2015), pp. 83-101. [10.1016/j.cor.2015.04.016]
Iori, Manuel; Riera Ledesma, Jorge
File in questo prodotto:
File Dimensione Formato  
DVRPMS-CandOR-2015-Appeared.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 673.29 kB
Formato Adobe PDF
673.29 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/1067372
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 27
social impact