Trudy Instituta Matematiki i Mekhaniki UrO RAN
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2018, Volume 24, Number 3, Pages 233–246
DOI: https://doi.org/10.21538/0134-4889-2018-24-3-233-246
(Mi timm1565)
 

This article is cited in 9 scientific papers (total in 9 papers)

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

M. Yu. Khachayabc, Yu. Yu. Ogorodnikovab

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
c Omsk State Technical University
Full-text PDF (456 kB) Citations (9)
References:
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.
Funding agency Grant number
Russian Science Foundation 14-11-00109
The first author is supported by the Russian Science Foundation (project no. 14-11-00109).
Received: 29.05.2018
English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2019, Volume 307, Issue 1, Pages S51–S63
DOI: https://doi.org/10.1134/S0081543819070058
Bibliographic databases:
Document Type: Article
UDC: 519.16 + 519.85
MSC: 90C27, 90C59, 90B06
Language: Russian
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
Citation in format AMSBIB
\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:
    1. Yongyu Chen, 2023 2nd International Conference on Computational Modelling, Simulation and Optimization (ICCMSO), 2023, 277  crossref
    2. 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  crossref  mathscinet  isi  scopus
    3. 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  crossref
    4. 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  crossref  isi  scopus
    5. 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  crossref  mathscinet  isi  scopus
    6. Michael Khachay, Yuri Ogorodnikov, Daniel Khachay, Lecture Notes in Computer Science, 12095, Mathematical Optimization Theory and Operations Research, 2020, 49  crossref
    7. 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  crossref  isi  scopus
    8. 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  crossref  mathscinet  zmath  isi  scopus
    9. Michael Khachay, Yuri Ogorodnikov, Lecture Notes in Computer Science, 11832, Analysis of Images, Social Networks and Texts, 2019, 388  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Statistics & downloads:
    Abstract page:336
    Full-text PDF :96
    References:54
    First page:6
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025