Improving the approximation ratio for capacitated vehicle routing

DOI10.1007/978-3-030-73879-2_1zbMath1482.90119arXiv2011.05235OpenAlexW3160432155MaRDI QIDQ5918417

Jannis Blauth, Vera Traub, Jens Vygen

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Integer programming (90C10) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Related Items

Improved approximations for capacitated vehicle routing with unsplittable client demands, A PTAS for Capacitated Vehicle Routing on Trees, Iterated tour partitioning for Euclidean capacitated vehicle routing, Minimizing the maximum flow time in the online food delivery problem, Improving the approximation ratio for capacitated vehicle routing, A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• Improved bounds for vehicle routing solutions
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• A PTAS for bounded-capacity vehicle routing in planar graphs
• Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
• PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
• The School Bus Problem on Trees
• PTAS for the Euclidean Capacitated Vehicle Routing Problem in $$R^d$$
• Bounds and Heuristics for Capacitated Routing Problems
• Capacitated Vehicle Routing on Trees
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• An improved approximation algorithm for TSP in the half integral case
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Improving the approximation ratio for capacitated vehicle routing
• A new approximation algorithm for the capacitated vehicle routing problem on a tree