A PTAS for Capacitated Vehicle Routing on Trees
From MaRDI portal
Abstract: We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
Cites work
- A framework for vehicle routing approximation schemes in trees
- A new approximation algorithm for the capacitated vehicle routing problem on a tree
- A PTAS for bounded-capacity vehicle routing in planar graphs
- A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- A tight 4/3 approximation for capacitated vehicle routing in trees
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated arc routing problems
- Capacitated Vehicle Routing on Trees
- scientific article; zbMATH DE number 1303035 (Why is no real title available?)
- scientific article; zbMATH DE number 1324130 (Why is no real title available?)
- scientific article; zbMATH DE number 1559543 (Why is no real title available?)
- Improved bounds for vehicle routing solutions
- Improving the approximation ratio for capacitated vehicle routing
- Models, relaxations and exact approaches for the capacitated vehicle routing problem
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- 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
- Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
- The truck dispatching problem
- The vehicle routing problem. Latest advances and new challenges.
Cited in
(11)- A PTAS for bounded-capacity vehicle routing in planar graphs
- scientific article; zbMATH DE number 1184494 (Why is no real title available?)
- Capacitated Vehicle Routing on Trees
- scientific article; zbMATH DE number 1303035 (Why is no real title available?)
- Airports and railways with unsplittable demand
- Approximation algorithms for the airport and railway problem
- A tight (1.5+)-approximation for unsplittable capacitated vehicle routing on trees
- Complexity of fixed order routing
- Approximation algorithms for the airport and railway problem
- Euclidean capacitated vehicle routing in the random setting: a 1.55-approximation algorithm
- An approximation algorithm for the pickup and delivery vehicle routing problem on trees
This page was built for publication: A PTAS for Capacitated Vehicle Routing on Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075752)
