A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
From MaRDI portal
(Redirected from Publication:494936)
Abstract: In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.
Recommendations
- scientific article; zbMATH DE number 6297716
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
- Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows
- A quasi-polynomial time approximation scheme for Euclidean CVRPTW
Cites work
- scientific article; zbMATH DE number 4066603 (Why is no real title available?)
- scientific article; zbMATH DE number 1223730 (Why is no real title available?)
- scientific article; zbMATH DE number 1559543 (Why is no real title available?)
- scientific article; zbMATH DE number 1775442 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 1452992 (Why is no real title available?)
- scientific article; zbMATH DE number 6297716 (Why is no real title available?)
- scientific article; zbMATH DE number 956786 (Why is no real title available?)
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- A quasi-polynomial time approximation scheme for minimum weight triangulation
- Approximation Schemes for Minimum Latency Problems
- Approximation schemes for NP-hard geometric optimization problems: a survey
- Bounds and Heuristics for Capacitated Routing Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- How Long Can a Euclidean Traveling Salesman Tour Be?
- 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
- The truck dispatching problem
- The vehicle routing problem. Latest advances and new challenges.
- Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
Cited in
(28)- Iterated tour partitioning for Euclidean capacitated vehicle routing
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k^*\)
- Polynomial capacity guarantees PTAS for the Euclidean capacitated vehicle routing problem even for non-uniform non-splittable demand
- Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows
- Makespan trade-offs for visiting triangle edges (extended abstract)
- A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
- A PTAS for Capacitated Vehicle Routing on Trees
- A polynomial-time exact algorithm for \(k\)-depot capacitated vehicle routing problem on a tree
- PTAS for the Euclidean capacitated vehicle routing problem in \(\mathbb R^d\)
- A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
- Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
- A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering
- scientific article; zbMATH DE number 6297716 (Why is no real title available?)
- Approximation schemes for Euclidean vehicle routing problems with time windows
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Improving the approximation ratio for capacitated vehicle routing
- Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
- Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
- Improved approximations for capacitated vehicle routing with unsplittable client demands
- Improving the approximation ratio for capacitated vehicle routing
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
- Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
- The Euclidean vehicle routing problem with multiple depots and time windows
This page was built for publication: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494936)
