A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing

DOI10.1007/s00453-014-9906-4zbMath1319.90055arXiv0812.1595OpenAlexW3012882765MaRDI QIDQ494936

Aparna Das, Claire Mathieu

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.1595

zbMATH Keywords

combinatorial optimizationvehicle routingapproximation algorithmsgeometric algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ Improved approximations for capacitated vehicle routing with unsplittable client demands ⋮ Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces ⋮ Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows ⋮ A PTAS for Capacitated Vehicle Routing on Trees ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Iterated tour partitioning for Euclidean capacitated vehicle routing ⋮ Randomized approximation scheme for Steiner multi cycle in the Euclidean plane ⋮ 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 ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension ⋮ A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs ⋮ Makespan trade-offs for visiting triangle edges (extended abstract) ⋮ A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The vehicle routing problem. Latest advances and new challenges.
• Approximation schemes for NP-hard geometric optimization problems: a survey
• The Truck Dispatching Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k
• Bounds and Heuristics for Capacitated Routing Problems
• Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle 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
• How Long Can a Euclidean Traveling Salesman Tour Be?
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A quasi-polynomial time approximation scheme for minimum weight triangulation

This page was built for publication: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing