Autonomous Vehicles Delivery Systems Classification: Introducing a TSP With a Moving Depot

Abstract

The vast growth in the e-commerce market has increased the attention to resolving the problem of conveying goods from distribution hubs to final destinations (customers) in the supply chain. The process known as the Last Mile Delivery (LMD) problem has significant challenges such as reducing operational cost or ecological impact and increasing supply chain performance. The inclusion of new technologies such as drones, robots, and the internet of things help tackle these challenges by developing new distribution systems to improve from traditional deliveries methods (delivery person, postal/delivery boxes). However, the use of these technologies brings new operational challenges. For instance, in a combined truck-drone delivery system, the truck serves as a depot from where we load the product to the drone for final delivery to the customers. The depot is now moving unlike in a traditional Vehicle Routing Problem (VRP) for which we always assume a fixed depot. This research paper deals with the impact of using Autonomous Vehicles (AV) on the logistics of the LMD. We first present a technological review of the use of AVs in logistics and use it to introduce a classification of the delivery systems based on the parcel/product handover at the time of the last handling before delivery to customers. We describe three categories of handovers, namely, machine-to-person, machine-to-machine, and person-to-machine. We present a new class of vehicle routing problems with a moving depot and formulate two variants of a Discrete Traveling Salesman Problem (TSP) with a Moving Depot (TSP-MD). We solve the problem using the General Algebraic Modeling System (GAMS) software and discuss some of the problem characteristics.