Improved approximations for capacitated vehicle routing with unsplittable client demands

DOI10.1007/978-3-031-06901-7_19MaRDI QIDQ2164702zbMATH OpenOpenAlexFDO

Authors Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, Mohammad Salavatipour

Publication date 16 August 2022

Full work available at URL https://arxiv.org/abs/2111.08138

zbMATH Keywords

approximation algorithmcapacitated vehicle routingcombinatorial optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper, we present improved approximation algorithms for the (unsplittable) Capacitated Vehicle Routing Problem (CVRP) in general metrics. In CVRP, introduced by Dantzig and Ramser (1959), we are given a set of points (clients) $V$ together with a depot $r$ in a metric space, with each $vinV$ having a demand $d_v>0$, and a vehicle of bounded capacity $Q$. The goal is to find a minimum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once and the total demands of the clients in each tour is at most $Q$. In the unsplittable variant we study, the demand of a node must be served entirely by one tour. We present two approximation algorithms for unsplittable CVRP: a combinatorial $(alpha+1.75)$-approximation, where $alpha$ is the approximation factor for the Traveling Salesman Problem, and an approximation algorithm based on LP rounding with approximation guarantee $alpha+ln(2)+deltaapprox3.194+delta$ in $n^{O(1/delta)}$ time. Both approximations can further be improved by a small amount when combined with recent work by Blauth, Traub, and Vygen (2021), who obtained an $(alpha+2cdot(1-epsilon))$-approximation for unsplittable CVRP for some constant $epsilon$ depending on $alpha$ ($epsilon>1/3000$ for $alpha=1.5$).

Recommendations

• A tight approximation algorithm for multi-vehicle CVRP with unsplittable demands on a line
• Capacitated vehicle routing problem on line with unsplittable demands
• Improving the approximation ratio for capacitated vehicle routing
• Improving the approximation ratio for capacitated vehicle routing
• A new approximation algorithm for the capacitated vehicle routing problem on a tree

Cites work

• A framework for vehicle routing approximation schemes in trees
• A PTAS for bounded-capacity vehicle routing in planar graphs
• A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• A tight 4/3 approximation for capacitated vehicle routing in trees
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension
• Bounds and Heuristics for Capacitated Routing Problems
• Capacitated arc routing problems
• Capacitated Vehicle Routing on Trees
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• scientific article; zbMATH DE number 1559543 (Why is no real title available?)
• Improving the approximation ratio for capacitated vehicle routing
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• PTAS for k-tour cover problem on the plane for moderately large values of k
• PTAS for the Euclidean capacitated vehicle routing problem in R^d
• The Traveling Salesman Problem with Distances One and Two
• The truck dispatching problem

Cited in

(19)

• Approximation algorithms for the load-balanced capacitated vehicle routing problem
• Capacitated vehicle routing problem on line with unsplittable demands
• A tight approximation algorithm for multi-vehicle CVRP with unsplittable demands on a line
• Capacitated vehicle routing with non-uniform speeds
• Improving the approximation ratio for capacitated vehicle routing
• Improving the approximation ratio for capacitated vehicle routing
• Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
• Improved approximation algorithms for multidepot capacitated vehicle routing
• Vehicle routing with time-dependent travel times: theory, practice, and benchmarks
• PTAS for Euclidean travelling salesman problem with soft time windows
• Improved approximations for the capacitated vehicle routing problem with fixed capacity
• Approximation algorithms for the airport and railway problem
• A tight (1.5+)-approximation for unsplittable capacitated vehicle routing on trees
• Multidepot capacitated vehicle routing with improved approximation guarantees
• Approximation algorithms for the airport and railway problem
• Euclidean capacitated vehicle routing in the random setting: a 1.55-approximation algorithm
• Approximation algorithms for cumulative vehicle routing with stochastic demands
• Enhanced approximation algorithms for the capacitated location routing problem
• Improved approximation algorithms for capacitated vehicle routing with fixed capacity

This page was built for publication: Improved approximations for capacitated vehicle routing with unsplittable client demands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164702)