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

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

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

Browse the full library · About the Tower of Babel