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

DOI10.1007/s10898-020-00990-0zbMath1475.90082OpenAlexW3126514426MaRDI QIDQ2046271

Yuri Ogorodnikov, Daniel Khachay, Mikhail Yu. Khachay

Publication date: 17 August 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-020-00990-0

zbMATH Keywords

capacitated vehicle routing problemquasi-polynomial time approximation schemefixed 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 (2)

FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem

Uses Software

• VRP

Cites Work

• Unnamed Item
• A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• The Euclidean traveling salesman problem is NP-complete
• Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems
• A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
• Knowledge-guided local search for the vehicle routing problem
• A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups
• 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
• Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
• A PTAS for bounded-capacity vehicle routing in planar 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
• The Truck Dispatching Problem
• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• Vehicle Routing
• 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$$
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
• Bypassing the embedding
• Bounds and Heuristics for Capacitated Routing Problems
• Probabilistic checking of proofs
• Advances in metric embedding theory
• VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties

This page was built for publication: Efficient approximation of the metric CVRP in spaces of fixed doubling dimension