Robust Queue Inference from Waiting Times

Many service systems are based on queueing models in which customers arrive at the system and join waiting lines until they are provided service in an order they arrive. These systems are everywhere in our daily lives, including car wash, grocery store, airport, restaurants, just to name a few. Given that customers’ arrival times and their service times are random, we always experience different waiting times – sometimes short, but sometimes we wait for substantial amount of time.

For this reason, characterization of customers’ waiting times, e.g., identifying the distribution of customers’ waiting time and extracting key information such as the average waiting time, has been primary objectives of operations management researchers for decades. This is based on a crucial assumption that they are given full distributional information of customers’ arrival times and service times. However, in many application areas, the problem is its inverse– we are not given any information regarding service times, and try to estimate them by leveraging waiting time records of customers. This setting is quite natural in healthcare operations and virtual waitlist management service such as Yelp.

To address this challenge, we propose a new inference approach based on the paradigm of robust optimization. In particular, we construct a set that possibly contains unknown service time records by utilizing queue dynamics and available waiting time observations of consecutive customers. These sets are computationally attractive as they are convex and can be easily described with off-the-shelf optimization solvers, but also have strong statistical guarantees without requiring parametric assumptions on the unknown primitives. Moreover, these sets naturally allow extensions to feed-forward queueing networks and temporally correlated arrival times.