TY - CHAP
T1 - Towards Asymptotically Optimal One-to-One PDP Algorithms for Capacity 2+ Vehicles
AU - Olsen, Martin
AU - Andersen, Lars Nørvang
PY - 2018
Y1 - 2018
N2 - We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space with arbitrary dimension d, where n transportation requests are picked i.i.d. with a separate origin-destination pair for each object to be moved. First, we consider the problem from the customer perspective, where the objective is to compute a plan for transporting the objects such that the Euclidean distance traveled by the vehicles when carrying objects is minimized. We develop a polynomial time asymptotically optimal algorithm for vehicles with capacity o(2d√n) for this case including the realistic setting where the capacity of the vehicles is a fixed constant and d=2. This result also holds imposing LIFO constraints for loading and unloading objects. Secondly, we extend our algorithm to the classical single-vehicle PDP, where the objective is to minimize the total distance traveled by the vehicle and we present results indicating that the extended algorithm is asymptotically optimal for a fixed vehicle capacity, if the origins and destinations are picked i.i.d. using the same distribution.
AB - We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space with arbitrary dimension d, where n transportation requests are picked i.i.d. with a separate origin-destination pair for each object to be moved. First, we consider the problem from the customer perspective, where the objective is to compute a plan for transporting the objects such that the Euclidean distance traveled by the vehicles when carrying objects is minimized. We develop a polynomial time asymptotically optimal algorithm for vehicles with capacity o(2d√n) for this case including the realistic setting where the capacity of the vehicles is a fixed constant and d=2. This result also holds imposing LIFO constraints for loading and unloading objects. Secondly, we extend our algorithm to the classical single-vehicle PDP, where the objective is to minimize the total distance traveled by the vehicle and we present results indicating that the extended algorithm is asymptotically optimal for a fixed vehicle capacity, if the origins and destinations are picked i.i.d. using the same distribution.
UR - http://www.scopus.com/inward/record.url?scp=85057273092&partnerID=8YFLogxK
M3 - Book chapter
T3 - Lecture Notes in Computer Science
SP - 268
EP - 278
BT - Computational Logistics - 9th International Conference, ICCL 2018, Proceedings
PB - Springer
ER -