Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Improved Polynomial Time Approximation Scheme for Capacitated Vehicle Routing Problem with Time Windows
verfasst von : Michael Khachay, Yuri Ogorodnikov
Erschienen in: Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The Capacitated Vehicle Routing Problem with Time Windows is the well-known combinatorial optimization problem having numerous valuable applications in operations research. In this paper, following the famous framework by M. Haimovich and A. Rinnooy Kan and technique by T. Asano et al., we propose a novel approximation scheme for the planar Euclidean CVRPTW. For any fixed \(\varepsilon >0\), the proposed scheme finds a \((1+\varepsilon )\)-approximate solution of CVRPTW in time where q is the given vehicle capacity bound, p is the number of time windows for servicing the customers, and \(TIME(\mathrm {TSP},\rho ,n)\) is the time needed to find a \(\rho \)-approximate solution for an auxiliary instance of the metric TSP.
$$TIME(\mathrm {TSP},\rho ,n)+O(n^2)+O\left( e^{O\left( q\,\left( \frac{q}{\varepsilon }\right) ^3(p\rho )^2\log (p\rho )\right) }\right) ,$$