Abstract:
The capacitated vehicle routing problem with time windows (CVRPTW) is a well-known NP-hard combinatorial optimization problem. We present a further development of the approach first proposed by M. Haimovich and A.H.G. Rinnooy Kan and propose an algorithm that finds for arbitrary ε>0 a (1+ε)-approximate solution for Eucidean CVRPTW in TIME(TSP,ρ,n)+O(n2)+O(eO(q(qε)3(pρ)2log(pρ))), where q is an upper bound for the capacities of the vehicles, p is the number of time windows, and TIME(TSP,ρ,n) is the complexity of finding a ρ-approximation solution of an auxiliary instance of Euclidean TSP. Thus, the algorithm is a polynomial time approximation scheme for CVRPTW with p3q4=O(logn) and an efficient polynomial time approximation scheme (EPTAS) for arbitrary fixed values of p and q.
Keywords:
capacitated vehicle routing problem, time windows, efficient polynomial time approximation scheme.
Citation:
M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows”, Trudy Inst. Mat. i Mekh. UrO RAN, 24, no. 3, 2018, 233–246; Proc. Steklov Inst. Math. (Suppl.), 307, suppl. 1 (2019), S51–S63
\Bibitem{KhaOgo18}
\by M.~Yu.~Khachay, Yu.~Yu.~Ogorodnikov
\paper Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2018
\vol 24
\issue 3
\pages 233--246
\mathnet{http://mi.mathnet.ru/timm1565}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-3-233-246}
\elib{https://elibrary.ru/item.asp?id=35511290}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2019
\vol 307
\issue , suppl. 1
\pages S51--S63
\crossref{https://doi.org/10.1134/S0081543819070058}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000451634900021}
Linking options:
https://www.mathnet.ru/eng/timm1565
https://www.mathnet.ru/eng/timm/v24/i3/p233
This publication is cited in the following 9 articles:
Yongyu Chen, 2023 2nd International Conference on Computational Modelling, Simulation and Optimization (ICCMSO), 2023, 277
M. Khachay, Yu. Ogorodnikov, D. Khachay, “Efficient approximation of the metric CVRP in spaces of fixed doubling dimension”, J. Glob. Optim., 80:3 (2021), 679–710
Y Christopher, S Wahyuningsih, D Satyananda, “Study of variable neighborhood descent and tabu search algorithm in VRPSDP”, J. Phys.: Conf. Ser., 1872:1 (2021), 012002
M. Khachay, Yu. Ogorodnikov, “Ptas for the euclidean capacitated vehicle routing problem with time windows”, Learning and Intelligent Optimization, Lion, Lecture Notes in Computer Science, 11968, ed. N. Matsatsinis, Y. Marinakis, P. Pardalos, Springer, 2020, 224–230
M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension”, Dokl. Math., 102:1 (2020), 324–329
Michael Khachay, Yuri Ogorodnikov, Daniel Khachay, Lecture Notes in Computer Science, 12095, Mathematical Optimization Theory and Operations Research, 2020, 49
M. Khachay, Yu. Ogorodnikov, “Towards an efficient approximability for the euclidean capacitated vehicle routing problem with time windows and multiple depots”, IFAC PAPERSONLINE, 52:13 (2019), 2644–2649
M. Khachay, Yu. Ogorodnikov, “Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. M. Khachay, Y. Kochetov, P. Pardalos, Springer, 2019, 309–327
Michael Khachay, Yuri Ogorodnikov, Lecture Notes in Computer Science, 11832, Analysis of Images, Social Networks and Texts, 2019, 388