Minimizing Latency in Online Pickup and Delivery Problem with Single Pickup Point
Haiyan Yu, Xianwei Luo · 2019
Motivated by the popularity of online to offline takeaway crowdsourcing delivery service, we study online pickup and delivery problem with single pickup point where the objective is to route a delivery man with a constant capacity to serve requests released over time so as to minimize the total latency. We consider online point-to-point requests with single pickup point where each request has to be picked up at the single pickup point and delivered to its destination, and each request becomes available at its release time, which is not known in advance. We prove the lower bound of this problem for various capacities of the delivery man. For a half line case we present Wait and Return online algorithms and Wait and Ignore online algorithm, and prove their competitive ratios, which are variety for various capacities. For the general metric space, we compare the performance of these two online algorithms by computational study.