betaFeedback

Reading v1View latest version

WorksComputer Science

Improved Approximation for Unsplittable Capacitated Vehicle Routing Using Quota Trees

Abstract

In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set VV of nn clients with normalized demands dv∈(0,1]d_v \in (0,1], a depot rr, a unit vehicle capacity, and symmetric metric travel costs cc on V∪{r}V \cup \{r\}. We seek a collection of routes of minimum total cost that start and end at rr, serve each client's entire demand on a single route, and respect the unit capacity constraint ∑v∈V(R)dv≤1\sum_{v \in V(R)} d_v \le 1 on every route RR, where V(R)V(R) denotes the clients served by RR. This models deliveries from a common depot in which each customer's order must be delivered in a single trip. UCVRP generalizes the metric traveling salesman problem (TSP) and is therefore NP-hard. Capacity constraints add a packing difficulty: when all clients are colocated away from the depot, minimizing the route cost is equivalent to minimizing the number of bins in bin packing. Consequently, UCVRP admits no polynomial-time approximation ratio below 3/23/2 unless P=NP\textbf{P=NP} (Grandoni, Mathieu, and Zhou, 2023). The classical 3.53.5-approximation has been improved through several recent advances; in particular, Zhao and Xiao (2026) recently obtained a (2+ln⁡2+ε)(2+\ln 2+\varepsilon)-approximation. In this paper, we give a deterministic (5/2+ε)(5/2+\varepsilon)-approximation algorithm running in nO(1/ε)n^{O(1/\varepsilon)} time for every rational 0<ε≤1/90<\varepsilon\le1/9, applicable to general capacity and arbitrary positive demands. Our algorithm uses local search to select routes through one client with large demand and clients with small demands. It constructs candidate routes using endpoint quota trees after rounding demands and creating vertex copies. We combine these routes with those obtained by matching and set packing, keeping their client sets disjoint. The remaining clients are served by partitioning a tour constructed using weighted graphic matroid parity.

Paper details

vlnc:W_3agwdwg5
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…