{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T06:32:19Z","timestamp":1780986739355,"version":"3.54.1"},"reference-count":37,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2019,7,10]],"date-time":"2019-07-10T00:00:00Z","timestamp":1562716800000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,12,31]]},"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>The Time Dependent Traveling Salesman Problem (TDTSP) is a class of NP-hard combinatorial optimization problems which has many practical applications. To the best of our knowledge, developing metaheuristic algorithm for the problem has not been studied much before, even though it is a natural and general extension of the Minimum Latency Problem (MLP) or Traveling Salesman Problem (TSP). In this paper, we propose an effective two-phase metaheuristic which combines the Insertion Heuristic (IH), Variable Neighborhood Search (VNS) and the tabu search (TS) to solve the problem. In a construction phase, the IH is used to create an initial solution that is good enough. In an improvement phase, the VNS is employed to generate diverse and various neighborhoods, while the main attribute of tabu search is to prohibit our algorithm from getting trapped into cycles, and to guide the search to escape local optima. Moreover, we introduce a novel neighborhoods\u2019 structure in VNS and present a <jats:italic>O<\/jats:italic>(1) operation for calculating the cost of each neighboring solution in a special case of TDTSP where the TDTSP becomes the MLP. Extensive computational experiments on 355 benchmark instances show that our algorithm can find the optimal solutions for small instances with up to 100 vertices in a reasonable amount of time. For larger instances, our algorithm obtains the new best solutions in comparison with the state-of-the-art algorithm solutions.<\/jats:p>","DOI":"10.1051\/ro\/2019006","type":"journal-article","created":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T08:45:46Z","timestamp":1546505146000},"page":"917-935","source":"Crossref","is-referenced-by-count":9,"title":["An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem"],"prefix":"10.1051","volume":"53","author":[{"given":"Ha Bang","family":"Ban","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1137\/07068151X","volume":"37","author":"Archer","year":"2007","journal-title":"J. SIAM"},{"key":"R2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s12532-012-0047-y","volume":"5","author":"Abeledo","year":"2013","journal-title":"J. Math. Prog. Comput."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Arora S. and Karakostas G., Approximation schemes for minimum latency problems. Proc. STOC (1999) 688\u2013693.","DOI":"10.1145\/301250.301432"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Ban H.B. and Nguyen D.N., Improved genetic algorithm for minimum latency problem. Proc. SOICT (2010) 9\u201315.","DOI":"10.1145\/1852611.1852614"},{"key":"R5","doi-asserted-by":"crossref","first-page":"167","DOI":"10.2201\/NiiPi.2013.10.10","volume":"10","author":"Ban","year":"2013","journal-title":"Progr. Inform."},{"key":"R6","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0305-0548(92)90066-E","volume":"19","author":"Balakrishnan","year":"1992","journal-title":"Comput. Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Blum A., Chalasani P., Coppersmith D., Pulleyblank W., Raghavan P. and Sudan M., The minimum latency problem. Proc. STOC (1994) 163\u2013171.","DOI":"10.1145\/195058.195125"},{"key":"R8","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.disopt.2008.04.001","volume":"5","author":"Bigras","year":"2008","journal-title":"J. Dis. Optim."},{"key":"R9","unstructured":"Chaudhuri K., Goldfrey B., Rao S. and Talwar K., Path, tree and minimum latency tour. Proc. FOCS (2003) 36\u201345."},{"key":"R10","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/opre.26.1.86","volume":"26","author":"Picard","year":"1978","journal-title":"J. Oper. Res."},{"key":"R11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"Feo","year":"1995","journal-title":"J. Global Opt."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Festa P. and Resende G.M.C., Hybridizations of GRASP with path-relinking, In Vol. 434 of Hybrid Metaheuristics - Studies in Computational Intelligence, edited by Talbi E.-G.. Springer, Berlin, Heidelberg (2013) 135\u2013155.","DOI":"10.1007\/978-3-642-30671-6_5"},{"key":"R13","unstructured":"Fox K., Production scheduling on parallel lines with dependencies. Ph.D. thesis, Johns Hopkins University, Baltimore, MD (1973)."},{"key":"R14","unstructured":"Fox K., Gavish B. and Graves S., The Time Dependent Traveling Salesman Problem and Extensions. Working paper No. 7904, Graduate School of Management, University of Rochester, NY (1979)."},{"key":"R15","unstructured":"Goemans M. and Kleinberg J., An improved approximation ratio for the minimum latency problem. Proc. SIAM SODA (1996) 152\u2013158."},{"key":"R16","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","volume":"2","author":"Glover","year":"1990","journal-title":"J. INFORMS"},{"key":"R17","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1016\/j.tre.2011.11.006","volume":"48","author":"Figliozzi","year":"2012","journal-title":"J. Transp. Res. Part E Logist. Transp. Rev."},{"key":"R18","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.disopt.2007.05.004","volume":"5","author":"Hashimoto","year":"2008","journal-title":"J. Dis. Optim."},{"key":"R19","unstructured":"Dongarra J.J., Performance of various computers using standard linear equations software. Linpack Benchmark Report, University of Tennessee Computer Science Technical Report, CS-89-85 (2013)."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Li F., Golden B. and Wasil E., Solving the time dependent traveling salesman problem. The Next Wave in Computing, Optimization, and Decision Technologies. Springer (2005) 163\u2013182.","DOI":"10.1007\/0-387-23529-9_12"},{"key":"R21","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1002\/net.3230200605","volume":"20","author":"Lucena","year":"1990","journal-title":"J. Networks"},{"key":"R22","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1287\/trsc.26.3.185","volume":"26","author":"Malandraki","year":"1992","journal-title":"J. Transp. Sci."},{"key":"R23","first-page":"1097","volume":"24","author":"Mladenovic","year":"1997","journal-title":"J. Oper. Res."},{"key":"R24","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"Orda","year":"1990","journal-title":"J. ACM"},{"key":"R25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10288-011-0153-0","volume":"9","author":"Salehipour","year":"2011","journal-title":"J. Oper. Res."},{"key":"R26","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1016\/j.ejor.2012.03.044","volume":"221","author":"Silva","year":"2012","journal-title":"J. Oper. Res."},{"key":"R27","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1080\/07408179108963858","volume":"23","author":"Simchi-Levi","year":"1991","journal-title":"IEEE. Trans."},{"key":"R28","first-page":"77","volume":"7","author":"Testa","year":"1999","journal-title":"J. Comput. Inform. Technol."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Ritzinger U., Puchinger J., Hybrid metaheuristics for dynamic and stochastic vehicle routing, In Vol. 434 of Hybrid Metaheuristics \u2013 Studies in Computational Intelligence. Edited by Talbi E.G.. Springer, Berlin, Heidelberg (2003) 77\u201395.","DOI":"10.1007\/978-3-642-30671-6_2"},{"key":"R30","unstructured":"Ruland K., Polyhedral solution to the pickup and delivery problem, Ph.D. thesis, Washington University, Saint Louis, MO (1995)."},{"key":"R31","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1002\/(SICI)1520-6750(199609)43:6<797::AID-NAV2>3.0.CO;2-#","volume":"43","author":"Vander Wiel","year":"1996","journal-title":"Naval Res. Logistics (NRL)"},{"key":"R32","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1287\/trsc.29.2.167","volume":"29","author":"Vander Wiel","year":"1995","journal-title":"J Transp. Sci."},{"key":"R33","doi-asserted-by":"crossref","first-page":"36701\u20131","DOI":"10.1103\/PhysRevE.64.036701","volume":"64","author":"Bentner","year":"2001","journal-title":"Phys. Rev. E"},{"key":"R34","first-page":"215","volume":"1","author":"Johnson","year":"1997","journal-title":"Local Search Comb. Optim."},{"key":"R35","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.ipl.2004.09.009","volume":"92","author":"Wu","year":"2004","journal-title":"Inf. Proc. Lett."},{"key":"R36","unstructured":"https:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/."},{"key":"R37","unstructured":"http:\/\/liris.cnrs.fr\/christine.solnon\/TDTSP.html."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:36:54Z","timestamp":1584689814000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":37,"journal-issue":{"issue":"3"},"alternative-id":["ro170082"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2019006","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}