Minimizing the Maximum Flow Time in the Online Food Delivery Problem

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. The problem also has a close connection with the broadcast scheduling problem with maximum flow time objective. 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 uncapaciated (i.e, c=∞) food delivery problem on tree metrics; we also have a negative result showing that the condition c=∞ is needed. Then we consider the speed-augmentation model, in which our online algorithm is allowed to use α-speed vehicles, where α≥1 is called the speeding factor. We develop an exponential time (1+ϵ)-speeding O(1/ϵ)-competitive algorithm for any ϵ>0. A polynomial time algorithm can be obtained with a speeding factor of α_TSP+ϵ or α_CVRP+ϵ, depending on whether the problem is uncapacitated. Here α_TSP and α_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.