Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows

DOI10.1134/S0081543819070058MaRDI QIDQ2185641zbMATH OpenOpenAlexFDO

Authors Yu. Yu. Ogorodnikov, M. Yu. Khachaĭ

Publication date 5 June 2020

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0081543819070058

zbMATH Keywords

time windowscapacitated vehicle routing problemefficient polynomial-time approximation scheme

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows
• A quasi-polynomial time approximation scheme for Euclidean CVRPTW
• Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand
• Approximation schemes for Euclidean vehicle routing problems with time windows
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing

Cites work

• scientific article; zbMATH DE number 2126631 (Why is no real title available?)
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 1559543 (Why is no real title available?)
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• Approximation schemes for Euclidean vehicle routing problems with time windows
• Bounds and Heuristics for Capacitated Routing Problems
• PTAS for the Euclidean capacitated vehicle routing problem in R^d
• Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Euclidean vehicle routing problem with multiple depots and time windows
• The truck dispatching problem

Cited in

(12)

• A quasi-polynomial time approximation scheme for Euclidean CVRPTW
• Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows
• Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
• Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand
• scientific article; zbMATH DE number 6297716 (Why is no real title available?)
• Approximation schemes for Euclidean vehicle routing problems with time windows
• An optimization algorithm for a capacitated vehicle routing problem with time windows
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• 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
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
• Solving an On-Line Capacitated Vehicle Routing Problem with Structured Time Windows

Describes a project that uses

Uses Software

• VRP

This page was built for publication: Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows

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