CS Paper Radar

Improved Approximations for Vehicle Routing with Nonuniform Speeds

Hong Li

cs.DS ·submitted 2026-10-08 15:51 UTC · v1

Abstract

We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+δ)$-approximation for any fixed $δ>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+δ)$-approximation for any fixed $δ>0$.

Comment
21 pages, no figures

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Approximation for Unsplittable Capacitated Vehicle Routing Using Quota Trees

cs.DS ·2026-10-20 ·Zhenyu Wang
similarity 0.76
Abstract

In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set $V$ of $n$ clients with normalized demands $d_v \in (0,1]$, a depot $r$, a unit vehicle capacity, and symmetric metric travel costs $c$ on $V \cup \{r\}$. We seek a collection of routes of minimum total cost that start and end at $r$, serve each client's entire demand on a single route, and respect the unit capacity constraint $\sum_{v \in V(R)} d_v \le 1$ on every route $R$, where $V(R)$ denotes the clients served by $R$. 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/2$ unless $\textbf{P=NP}$ (Grandoni, Mathieu, and Zhou, 2023). The classical $3.5$-approximation has been improved; Zhao and Xiao recently obtained a $(2+\ln 2+\varepsilon)$-approximation. In this paper, we give a deterministic polynomial algorithm with approximation ratio $5/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/2$-approximation algorithm for the undirected capacitated arc routing problem (CARP) with arbitrary positive edge demands.

0.16

Improved Approximation for Unsplittable CVRP via a Greedy Approach

cs.DS math.CO ·2026-09-15 ·Daniel Ebert, Leonard Weismantel
similarity 0.74
Abstract · 26 pages, 1 figure

We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.

0.55

Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands

cs.DS ·2026-10-12 ·Jingyang Zhao, Mingyu Xiao
similarity 0.72
Abstract

We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only on the first visit. We consider a priori and restocking policies that fix the client order before observing demands and serve each client's entire demand before first visiting the next. Gupta, Nagarajan, and Ravi (Oper. Res., 2012) developed randomized a priori $(α+1)$-approximation and $(α+2)$-approximation algorithms for splittable and unsplittable deliveries, respectively, where $α$ is the approximation ratio of a metric traveling salesman problem (TSP) algorithm. We improve these approximation ratios to $2$ and $3$ by using their replenishment rules with a TSP tour constructed via matroid parity. We also obtain deterministic a priori $(2+\varepsilon)$-approximation and $(3+\varepsilon)$-approximation algorithms by compressing the distributions of cumulative demands to select an initial stock in polynomial time. All guarantees are relative to the general adaptive optimum. We then establish matching lower bounds of $2$ and $3$ that hold even for the more general class of randomized restocking policies. Finally, we apply our matroid-parity construction to improve approximation ratios for several VRP variants with deterministic demands.

0.34

A PTAS for Euclidean Capacitated Vehicle Routing

cs.DS ·2026-11-13 ·Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
top venuehot direction similarity 0.71
Abstract

In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an $n$-node graph $G=(V,E)$ with metric edges costs $c(e)$, a depot $r\in V$, and an integer vehicle capacity $Q$. The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other $Q$ nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on $\mathbb{R}^2$, and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with $Q=n-1$), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time $(2+ε)$-approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time $n^{\log^{O(1/ε)}n}$), Jayaprakash and Salavatipour [SODA'22] (time $n^{O_ε(\log^6 n)}$), and recently Sitters [ArXiV'25] (time $n^{O_ε(\log\log n)}$). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.

0.46

Polynomial $(2α+\varepsilon)$- and Quadratic $4$-Approximation Algorithms for the Biased Traveling Salesman Problem in Bipartitioned Networks

cs.DS ·2026-11-04 ·Jingyang Zhao, Trung Q. Duong, Een-Kee Hong, Hyundong Shin
similarity 0.67
Abstract

The traveling salesman problem (TSP) is one of the fundamental problems in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices. For the metric TSP, where edge costs satisfy the triangle inequality, a long line of work has produced constant-factor approximation algorithms, culminating in the best-known approximation ratio $α<3/2-10^{-36}$. The biased TSP (BTSP) generalizes the metric TSP to bipartitioned networks: the vertex set is partitioned into two subsets, edge costs satisfy the triangle inequality within each subset, while edges crossing the partition may violate it by a certain bias factor. This model captures heterogeneous routing scenarios in which distances are metric only locally but may be distorted across different regions or vertex types. Previously, the only known result for the BTSP was a $7/2$-approximation algorithm with running time $O(N^3)$. In this paper, we present two new approximation algorithms that significantly improve the state of the art. The first achieves an approximation ratio of $2α+\varepsilon$ (strictly less than $3$) in polynomial time $N^{O(1)}$ for any constant $\varepsilon>0$, where the exponent grows at least linearly with $1/\varepsilon$. The second achieves a $4$-approximation in only $O(N^2)$ running time, reducing the previous cubic-time bound by a full polynomial factor. These advances directly support emerging networked systems---including multi-tier 6G architectures and hybrid quantum-classical networks---where cross-region transitions incur biased and non-metric overheads.

0.25

A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem

cs.DS ·2026-09-17 ·Jingyang Zhao, Yuxi Liu, Mingyu Xiao
similarity 0.67
Abstract

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The metric multiple-depot TSP (MD-TSP) is a natural extension, where the graph contains depots and clients, and the objective is to compute a minimum-cost set of tours covering all clients, with each tour starting and ending at the same depot. When the number of depots is part of the input, an adaptation of the Christofides--Serdyukov heuristic yields an approximation ratio of $2$. In this paper, we introduce a $(1+1/\sqrt{2})$-approximation algorithm. Like the Christofides--Serdyukov heuristic, our algorithm first computes a rooted spanning forest (RSF), then a matching to correct its odd degrees, and finally obtains a solution by shortcutting. However, instead of using a minimum-cost RSF, we construct an RSF by a primal-dual algorithm for a natural cut relaxation. The algorithm grows rootless components and the component containing all depots at different rates, adding an edge when its dual constraint becomes tight. Vertex labels record the times at which clients first become connected to a depot. The two-speed growth provides a joint bound on the forest cost and two label-dependent terms that also arise in bounding the parity-correction cost. Balancing the coefficients of these two terms by setting both to $\sqrt{2}-1$ yields the claimed approximation ratio.

0.14

Reducing Asymmetric Path TSP to Asymmetric TSP

cs.DS ·2026-11-16 ·Hong Li
similarity 0.65
Abstract · 20 pages, 3 figures

In the Asymmetric Traveling Salesman Problem (Asymmetric TSP), we are given distances between $n$ vertices that satisfy the triangle inequality but need not be symmetric, and we seek a shortest tour through all vertices. In its path version, Asymmetric Path TSP, two vertices $s$ and $t$ are prescribed, and we seek a shortest path from $s$ to $t$ through all vertices. Both problems are equivalent to their versions with arbitrary nonnegative edge costs on a directed graph, in which vertices may be visited more than once. We show that for all constants $α\ge1$ and $\varepsilon>0$, any $α$-approximation algorithm for Asymmetric TSP yields an $(α+\varepsilon)$-approximation algorithm for Asymmetric Path TSP. The best previous reduction of this kind, due to Feige and Singh, yields an $α(2+\varepsilon)$-approximation algorithm. Our result answers an open question of Traub and Vygen. Consequently, every constant-factor approximation guarantee for Asymmetric TSP carries over to Asymmetric Path TSP up to an arbitrarily small additive error.

0.12

A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem

cs.AI ·2026-11-17 ·The Dung Bui, Ha Thu Nguyen
code/data similarity 0.64
Abstract · 5 pages, 1 figure, 2 tables. Technical Report for the SOICT 2026 Student Contest. Code: https://github.com/25023189-bit/Integrated-Passenger…

We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.

0.37