Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
Jingyang Zhao, Mingyu Xiao · 2026
Read Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem 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-21660.txt.
Description
Jingyang Zhao and Mingyu Xiao improve approximation algorithms for vehicle routing with capacity limits. In this classic problem, vans leave a depot to serve customers who each demand some load. Every van has a fixed capacity, and routes should be as short as possible.
The unsplittable version bars splitting one customer's demand across vans, which matches real practice. The authors give better guarantees on how close their routes come to optimal. Routing sits under delivery, repair, and transit services everywhere. Even small gains in the guarantee translate into large savings when the method runs at city scale every day.
Catalog record
| CREATOR | Jingyang Zhao, Mingyu Xiao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-21660