In this paper we introduce a class of routing problems where pickups and deliveries need to be performed in two distinct regions, and must be synchronized by considering the presence of a first-in-first-out channel linking them. Our research is motivated by applications in the context of automated warehouses management. We formalize our problem, defining eight variants which depend on the characteristics of both the pickup and delivery vehicles, and the first-in-first-out linking channel. We show that all variants are in general NP-hard. We focus on two of these variants, proving that relevant sub-problems can be solved in polynomial-time. Our proofs are constructive, consisting of resolution algorithms. We show the applicability of our results by computational experiments on instances from the literature.

Synchronized Pickup and Delivery Problems with Connecting FIFO Stack / M. Barbato, A. Ceselli, N. Facchinetti (AIRO SPRINGER SERIES). - In: Graphs and Combinatorial Optimization: from Theory to Applications / [a cura di] C. Gentile, G. Stecca, P. Ventura. - [s.l] : Springer, 2021. - ISBN 9783030630713. - pp. 237-249 (( Intervento presentato al 18. convegno Cologne-Twente Workshop on Graphs and Combinatorial Optimization tenutosi a on-line nel 2020 [10.1007/978-3-030-63072-0_19].

Synchronized Pickup and Delivery Problems with Connecting FIFO Stack

M. Barbato
;
A. Ceselli;
2021

Abstract

In this paper we introduce a class of routing problems where pickups and deliveries need to be performed in two distinct regions, and must be synchronized by considering the presence of a first-in-first-out channel linking them. Our research is motivated by applications in the context of automated warehouses management. We formalize our problem, defining eight variants which depend on the characteristics of both the pickup and delivery vehicles, and the first-in-first-out linking channel. We show that all variants are in general NP-hard. We focus on two of these variants, proving that relevant sub-problems can be solved in polynomial-time. Our proofs are constructive, consisting of resolution algorithms. We show the applicability of our results by computational experiments on instances from the literature.
Optimization in manufacturing; Routing; FIFO loading; Dynamic programming
Settore MAT/09 - Ricerca Operativa
Advanced Cosmetic Manifacturing (AD-COM)
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Barbato2021_Chapter_SynchronizedPickupAndDeliveryP.pdf

accesso riservato

Descrizione: Articolo Principale
Tipologia: Publisher's version/PDF
Dimensione 314.97 kB
Formato Adobe PDF
314.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
CTW_2020___Double_VRP_with_FIFO_Stack.pdf

accesso aperto

Descrizione: Versione accettata dall'editore con correzioni evidenziate
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 233.49 kB
Formato Adobe PDF
233.49 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/2434/828457
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact