betaFeedback

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. 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; Zhao and Xiao recently obtained a (2+ln⁡2+ε)(2+\ln 2+\varepsilon)-approximation. In this paper, we give a deterministic polynomial algorithm with approximation ratio 5/25/2 for 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 replace selected routes using sets of two to four clients and a squared-weight local search, keeping their client sets disjoint. The remaining clients are served by partitioning a tour constructed using weighted graphic matroid parity. We also give a deterministic polynomial 5/25/2-approximation algorithm for the undirected capacitated arc routing problem (CARP) with arbitrary positive edge demands.

Paper details

vlnc:W_3agwdwg5
Version
v2 · latest
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…