2026-07-24T18:53:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17318 2024-03-06T10:59:27Z ddc:004 open_access

Minimizing the Maximum Flow Time in the Online Food Delivery Problem Guo, Xiangyu Luo, Kelin Li, Shi Zhang, Yuhao Online algorithm Capacitated Vehicle Routing Flow Time Optimization We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where k vehicles of capacity c are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings even when k = 1 and c = ∞: There is a hardness of approximation of Ω(n) for the offline problem, and a lower bound of Ω(n) on the competitive ratio of any online algorithm, where n is number of points in the metric. We circumvent the strong negative results in two directions. Our main result is an O(1)-competitive online algorithm for the uncapacitated (i.e, c = ∞) food delivery problem on tree metrics; we also have negative result showing that the condition c = ∞ is needed. Then we explore the speed-augmentation model where our online algorithm is allowed to use vehicles with faster speed. We show that a moderate speeding factor leads to a constant competitive ratio, and we prove a tight trade-off between the speeding factor and the competitive ratio. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiangyu Guo and Kelin Luo and Shi Li and Yuhao Zhang 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.33 urn:nbn:de:0030-drops-173181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.33 eng https://creativecommons.org/licenses/by/4.0/legalcode