The online food delivery problem on stars

We introduce the Online Food Delivery Problem (OFDP) to model the delivery problem commonly encountered in online food-ordering-and-delivery platforms. In the OFDP the requests (orders) are submitted online, and the depot (restaurant) needs to decide when to send out a server to serve the submitted requests. In addition, the server has to return to the depot (to pickup foods) before serving new requests. The objective is to minimize maximum flow time, i.e., the maximum time between the submission and completion of a request. This problem can also be viewed as a variant of the Online Dial-a-Ride problem, for which however the max flow time objective is inapproximable in general. We study the OFDP on star graphs, and give both algorithmic and hardness results. We analyze a natural greedy strategy and show that it achieves the optimal competitive ratio 3 among all myopic algorithms, which are algorithms that immediately send out the server whenever there are unserved requests. Then we prove that a far-sighted (i.e., non-myopic) algorithm with proper waiting strategy can achieve 8/3-competitive ratio. On the negative side, we give a simple lower bound example that excludes the possibility of any (2−ϵ)-competitive algorithms.