A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
From MaRDI portal
Publication:494936
DOI10.1007/S00453-014-9906-4zbMATH Open1319.90055arXiv0812.1595OpenAlexW3012882765MaRDI QIDQ494936FDOQ494936
Authors: Aparna Das, Claire Mathieu 
Publication date: 3 September 2015
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0812.1595
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
- The truck dispatching problem
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- The vehicle routing problem. Latest advances and new challenges.
- 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
- Approximation Schemes for Minimum Latency Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation schemes for NP-hard geometric optimization problems: a survey
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Title not available (Why is that?)
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
- Title not available (Why is that?)
- How Long Can a Euclidean Traveling Salesman Tour Be?
- Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
- Title not available (Why is that?)
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- A quasi-polynomial time approximation scheme for minimum weight triangulation
Cited In (28)
- 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
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
- Makespan trade-offs for visiting triangle edges (extended abstract)
- A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
- 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
- Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
- A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering
- Title not available (Why is that?)
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- Improving the approximation ratio for capacitated vehicle routing
- Approximation schemes for Euclidean vehicle routing problems with time windows
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
- Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
- Improving the approximation ratio for capacitated vehicle routing
- Improved approximations for capacitated vehicle routing with unsplittable client demands
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
- Iterated tour partitioning for Euclidean capacitated vehicle routing
- Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
- The Euclidean vehicle routing problem with multiple depots and time windows
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k^*\)
Uses Software
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)
