Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension

DOI10.1134/S1064562420040080zbMath1476.90046OpenAlexW3104566536MaRDI QIDQ2243777

Yu. Yu. Ogorodnikov, Mikhail Yu. Khachay

Publication date: 11 November 2021

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562420040080

zbMATH Keywords

capacitated vehicle routing problemquasi-polynomial time approximation schememetric spaces of fixed doubling dimension

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Efficient approximation of the metric CVRP in spaces of fixed doubling dimension

Cites Work

• Unnamed Item
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• The Euclidean traveling salesman problem is NP-complete
• Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand
• Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows
• The Truck Dispatching Problem
• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Bypassing the embedding
• Bounds and Heuristics for Capacitated Routing Problems
• Advances in metric embedding theory

This page was built for publication: Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension