PTAS for the Euclidean capacitated vehicle routing problem in R^d

DOI10.1007/978-3-319-44914-2_16MaRDI QIDQ3133213zbMATH OpenOpenAlexFDO

Authors Roman D. Dubinin, M. Yu. Khachaĭ

Publication date 13 February 2018

Published in Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-44914-2_16

zbMATH Keywords

vehicle routingEuclidean spacecapacitated vehicle routing problemEPTAS

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)

Recommendations

• Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
• Polynomial capacity guarantees PTAS for the Euclidean capacitated vehicle routing problem even for non-uniform non-splittable demand
• An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing

Cited in

(21)

• 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
• Minimizing the maximum flow time in the online food delivery problem
• Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows
• 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 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
• A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering
• A PTAS for bounded-capacity vehicle routing in planar graphs
• 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
• An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension
• 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
• Multi-shuttle crane scheduling in automated storage and retrieval systems
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces

This page was built for publication: PTAS for the Euclidean capacitated vehicle routing problem in \(\mathbb R^d\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133213)