2016/10/28 by Martin Olsen, Olsen, Martin
Engineering · #Advanced Manufacturing and Logistics Optimization #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Smart Parking Systems Research #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1610.09132
openalex publication_date 2016/10/28 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean\nSpace with arbitrary dimension d where n transportation requests are picked\ni.i.d. with a separate origin-destination pair for each object to be moved.\nFirst, we consider the problem from the customer perspective where the\nobjective is to compute a plan for transporting the objects such that the\nEuclidean distance traveled by the vehicles when carrying objects is minimized.\nWe develop a polynomial time asymptotically optimal algorithm for vehicles with\ncapacity o(\√[2d]n) for this case. This result also holds imposing LIFO\nconstraints for loading and unloading objects. Secondly, we extend our\nalgorithm to the classical single-vehicle PDP where the objective is to\nminimize the total distance traveled by the vehicle and present results\nindicating that the extended algorithm is asymptotically optimal for a fixed\nvehicle capacity if the origins and destinations are picked i.i.d. using the\nsame distribution.\n