Order Now, Pickup in 30 Minutes: Managing Queues with Static Delivery Guarantees

We study the problem of managing queues in online food-ordering services where customers, who place orders online and pick up at the store, are offered a common quote time, that is, the promised pick-up time minus the time the order is placed. The objective is to minimize the long-run average expected earliness and tardiness cost incurred by the customers. We introduce the family of static threshold policies for managing such queues. A static threshold policy is one that starts serving the first customer in the queue as soon as the server is free and the time remaining until the promised pick-up time of that customer falls below a fixed threshold. In important technical contributions for establishing the attractiveness of the optimal static threshold policy, we develop two sets of lower bounds on the optimal cost. The first set of lower bounds uses the idea of a clairvoyant optimal policy by considering a decision maker who has either full or partial knowledge of the outcomes of future uncertainties. To obtain our second set of lower bounds, we develop bounds on the optimal earliness and tardiness costs by establishing lower and upper bounds on the steady-state waiting time under an optimal policy. The optimal static threshold policy is asymptotically optimal in several cases, including the heavy traffic and the light traffic regimes. We also develop a dynamic threshold policy in which the threshold depends on the queue length. Finally, through a comprehensive numerical study, we demonstrate the excellent performance of both the static and the dynamic threshold policies.