Online Food Delivery to Minimize Maximum Flow Time
Preprint
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: There is a hardness of approximation of $\Omega(n)$ for the offline problem, and a lower bound of $\Omega(n)$ on the competitive ratio of any online algorithm, where $n$ is number of points in the metric. Our main result is an $O(1)$-competitive online algorithm for the uncapaciated (i.e, $c = \infty$) food delivery problem on tree metrics. Then we consider the speed-augmentation model. We develop an exponential time $(1+\epsilon)$-speeding $O(1/\epsilon)$-competitive algorithm for any $\epsilon > 0$. A polynomial time algorithm can be obtained with a speeding factor of $\alpha_{TSP}+ \epsilon$ or $\alpha_{CVRP}+ \epsilon$, depending on whether the problem is uncapacitated. Here $\alpha_{TSP}$ and $\alpha_{CVRP}$ are the best approximation factors for the traveling salesman (TSP) and capacitated vehicle routing (CVRP) problems respectively. We complement the results with some negative ones.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Improving the approximation ratio for capacitated vehicle routingMathematical Programming, 2022
- A (2 + ε )-approximation algorithm for preemptive weighted flow time on a single machine2021
- Capacitated vehicle routing problem on line with unsplittable demandsJournal of Combinatorial Optimization, 2020
- Online scheduling with multi‐state machinesNetworks, 2017
- Dial a Ride from k-Forest2007
- SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMSInternational Journal of Foundations of Computer Science, 2004
- Capacitated Vehicle Routing on TreesOperations Research, 1991
- Heuristics for unequal weight delivery problems with a fixed error guaranteeOperations Research Letters, 1987
- Bounds and Heuristics for Capacitated Routing ProblemsMathematics of Operations Research, 1985
- Minimizing Maximum Flow-time on Related Machines