License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.33
URN: urn:nbn:de:0030-drops-173181
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17318/
Guo, Xiangyu ;
Luo, Kelin ;
Li, Shi ;
Zhang, Yuhao
Minimizing the Maximum Flow Time in the Online Food Delivery Problem
Abstract
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.
BibTeX - Entry
@InProceedings{guo_et_al:LIPIcs.ISAAC.2022.33,
author = {Guo, Xiangyu and Luo, Kelin and Li, Shi and Zhang, Yuhao},
title = {{Minimizing the Maximum Flow Time in the Online Food Delivery Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {33:1--33:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17318},
URN = {urn:nbn:de:0030-drops-173181},
doi = {10.4230/LIPIcs.ISAAC.2022.33},
annote = {Keywords: Online algorithm, Capacitated Vehicle Routing, Flow Time Optimization}
}
|
Keywords: |
|
Online algorithm, Capacitated Vehicle Routing, Flow Time Optimization |
|
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
