Synchronized Pickup and Delivery Problems with Connecting FIFO Stack

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.