The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
For autonomous ride-hailing platforms, this work provides theoretical foundations and practical insights for idle robotaxi positioning to reduce rider wait times.
The paper formalizes the robotaxi placement problem (k-RP) to minimize expected wait times for riders, provides a 2-approximation algorithm, an inapproximability bound, an exact DP for tree metrics, and shows empirically that a variance-reduced random placement achieves near-optimal wait times on real data.
Autonomous ride-hailing platforms must strategically position idle robotaxis to minimize the wait times of prospective riders. We formalize this as the \emph{robotaxi placement problem} ($k$-RP). Given a finite metric space and a demand distribution over its points, the goal is to position $k$ robotaxis to minimize the expected total distance in a perfect matching between the robotaxis and $k$ random riders. We present several theoretical results for this stochastic optimization problem. First, we observe that sampling robotaxi locations independently according to the demand distribution yields a randomized $2$-approximation algorithm. Second, we present an explicit inapproximability bound via a novel gap-preserving reduction from the maximum coverage problem. Furthermore, while it is not even clear whether the exact expected cost of a placement can be computed efficiently on general metrics, we design an exact polynomial-time dynamic programming algorithm for $k$-RP in tree metrics by decoupling the stochastic matching dependencies. Finally, empirical evaluations on real-world ride-hailing data reveal that a variance-reduced random placement strategy is highly effective in practice, yielding expected wait times that are very close to those obtained by computationally heavy exact algorithms for the uniform capacitated $k$-median problem.