Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.15745 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913132050382848 |
|---|---|
| author | Caragiannis, Ioannis Kollias, Kostas Roghani, Mohammad Schild, Aaron Sinop, Ali Kemal |
| author_facet | Caragiannis, Ioannis Kollias, Kostas Roghani, Mohammad Schild, Aaron Sinop, Ali Kemal |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15745 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand Caragiannis, Ioannis Kollias, Kostas Roghani, Mohammad Schild, Aaron Sinop, Ali Kemal Data Structures and Algorithms Computational Complexity 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. |
| title | The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2605.15745 |