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

CREATORJingyang Zhao, Mingyu Xiao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21652

Browse the full library · About the Tower of Babel