Improved Approximations for Dial-a-Ride Problems
Jingyang Zhao, Mingyu Xiao · 2026
Read Improved Approximations for Dial-a-Ride Problems by Jingyang Zhao, Mingyu Xiao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21652.txt.
Description
Jingyang Zhao and Mingyu Xiao improve approximation algorithms for dial-a-ride problems. In this routing family, each request has a pickup point and a drop-off point. Several vehicles of fixed capacity, based at depots, must serve every request without splitting a ride.
The goal is to plan routes that cover all requests with the least total travel. The authors give improved guarantees on how near their routes come to the best possible. Dial-a-ride models real services, from paratransit vans to ride sharing. Better guarantees mean operators can promise service levels with math behind them, not just hope.
Catalog record
| CREATOR | Jingyang Zhao, Mingyu Xiao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-21652