Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
DOI10.1134/S0965542521070149zbMath1494.90099OpenAlexW3195882325MaRDI QIDQ2048811
Yu. Yu. Ogorodnikov, Mikhail Yu. Khachay
Publication date: 24 August 2021
Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0965542521070149
metric spacedoubling dimensioncapacitated vehicle routing problem (CVRP)quasi-polynomial time approximation scheme (QPTAS)
Combinatorial optimization (90C27) Traffic problems in operations research (90B20) Approximation algorithms (68W25)
Uses Software
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
- A PTAS for bounded-capacity vehicle routing in planar graphs
- Improved branch-cut-and-price for capacitated vehicle routing
- The Truck Dispatching Problem
- Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments
- 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
- 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: Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
