{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:42:17Z","timestamp":1740145337934,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["688117"],"award-info":[{"award-number":["688117"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Rob4Ind4.0","award":["CZ.02.1.01\/0.0\/0.0\/15_003\/0000470"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/15_003\/0000470"]}]},{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grant Agency of the Czech Technical University in Prague","award":["SGS21\/185\/OHK3\/3T\/37"],"award-info":[{"award-number":["SGS21\/185\/OHK3\/3T\/37"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10100-021-00793-y","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T19:03:36Z","timestamp":1642705416000},"page":"1451-1481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Solving the traveling delivery person problem with limited computational time"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3404-8742","authenticated-orcid":false,"given":"Jan","family":"Mikula","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0997-5889","authenticated-orcid":false,"given":"Miroslav","family":"Kulich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"key":"793_CR1","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-642-13193-6_18","volume-title":"Experimental algorithms","author":"H Abeledo","year":"2010","unstructured":"Abeledo H, Fukasawa R, Pessoa A, Uchoa E (2010) The time dependent traveling salesman problem: Polyhedra and branch-cut-and-price algorithm. In: Festa P (ed) Experimental algorithms. Springer, Berlin, pp 202\u2013213"},{"issue":"1","key":"793_CR2","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s12532-012-0047-y","volume":"5","author":"H Abeledo","year":"2013","unstructured":"Abeledo H, Fukasawa R, Pessoa A, Uchoa E (2013) The time dependent traveling salesman problem: polyhedra and algorithm. Math Program Comput 5(1):27\u201355","journal-title":"Math Program Comput"},{"issue":"3","key":"793_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1023\/A:1015061802659","volume":"8","author":"RM Aiex","year":"2002","unstructured":"Aiex RM, Resende MG, Ribeiro CC (2002) Probability distribution of solution time in GRASP: an experimental investigation. J Heuristics 8(3):343\u2013373","journal-title":"J Heuristics"},{"key":"793_CR4","doi-asserted-by":"crossref","unstructured":"Archer A, Blasiak A (2010) Improved approximation algorithms for the minimum latency problem via prize-collecting strolls. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp 429\u2013447","DOI":"10.1137\/1.9781611973075.36"},{"key":"793_CR5","unstructured":"Archer A, Williamson DP (2003) Faster approximation algorithms for the minimum latency problem. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 88\u201396"},{"issue":"5","key":"793_CR6","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1137\/07068151X","volume":"37","author":"A Archer","year":"2008","unstructured":"Archer A, Levin A, Williamson DP (2008) A faster, better approximation algorithm for the minimum latency problem. SIAM J Comput 37(5):1472\u20131498","journal-title":"SIAM J Comput"},{"key":"793_CR7","doi-asserted-by":"crossref","unstructured":"Ausiello G, Leonardi S, Marchetti-Spaccamela A (2000) On Salesmen, Repairmen, Spiders, and Other Traveling Agents. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp 1\u201316","DOI":"10.1007\/3-540-46521-9_1"},{"key":"793_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.2201\/NiiPi.2013.10.10","volume":"10","author":"HB Ban","year":"2013","unstructured":"Ban HB, Nguyen K, Ngo MC, Nguyen DN (2013) An efficient exact algorithm for the Minimum Latency Problem. Progress Inf 10:167","journal-title":"Progress Inf"},{"issue":"2","key":"793_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1002\/net.3230230202","volume":"23","author":"L Bianco","year":"1993","unstructured":"Bianco L, Mingozzi A, Ricciardelli S (1993) The traveling salesman problem with cumulative costs. Networks 23(2):81\u201391","journal-title":"Networks"},{"key":"793_CR10","doi-asserted-by":"crossref","unstructured":"Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC \u201994, ACM Press, New York, New York, USA, pp 163\u2013171","DOI":"10.1145\/195058.195125"},{"key":"793_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.cor.2018.01.016","volume":"93","author":"T Bulh\u00f5es","year":"2018","unstructured":"Bulh\u00f5es T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the Minimum Latency Problem. Comput Oper Res 93:66\u201378","journal-title":"Comput Oper Res"},{"issue":"2","key":"793_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/trsc.1070.0209","volume":"42","author":"AM Campbell","year":"2008","unstructured":"Campbell AM, Vandenbussche D, Hermann W (2008) Routing for relief efforts. Transp Sci 42(2):127\u2013145","journal-title":"Transp Sci"},{"key":"793_CR13","unstructured":"Ceallaigh DO, Ruml W (2015) Metareasoning for Concurrent Planning and Execution. In: Proceedings of the Symposium on Combinatoral Search"},{"key":"793_CR14","doi-asserted-by":"crossref","unstructured":"Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., IEEE Computer. Soc, pp 36\u201345","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"793_CR15","volume-title":"In pursuit of the traveling salesman: mathematics at the limits of computation","author":"WJ Cook","year":"2012","unstructured":"Cook WJ (2012) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton Princeton"},{"key":"793_CR16","doi-asserted-by":"crossref","unstructured":"Faigl J, Hollinger GA (2014) Unifying multi-goal path planning for autonomous data collection. In: 2014 IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, pp 2937\u20132942","DOI":"10.1109\/IROS.2014.6942967"},{"key":"793_CR17","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Harrelson C, Rao S (2007) The k -traveling repairmen problem. ACM Transactions on Algorithms 3(4):40\u2013es","DOI":"10.1145\/1290672.1290677"},{"issue":"2","key":"793_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"TA Feo","year":"1989","unstructured":"Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8(2):67\u201371","journal-title":"Oper Res Lett"},{"issue":"5","key":"793_CR19","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1287\/opre.42.5.860","volume":"42","author":"TA Feo","year":"1994","unstructured":"Feo TA, Resende MGC, Smith SH (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 42(5):860\u2013878","journal-title":"Oper Res"},{"issue":"6","key":"793_CR20","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M Fischetti","year":"1993","unstructured":"Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper Res 41(6):1055\u20131064","journal-title":"Oper Res"},{"issue":"3\u20134","key":"793_CR21","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1007\/s00453-011-9515-4","volume":"62","author":"GN Frederickson","year":"2012","unstructured":"Frederickson GN, Wittman B (2012) Approximation algorithms for the traveling repairman and speeding deliveryman problems. Algorithmica 62(3\u20134):1198\u20131221","journal-title":"Algorithmica"},{"issue":"2","key":"793_CR22","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1080\/10556788.2011.648932","volume":"28","author":"I Gentilini","year":"2013","unstructured":"Gentilini I, Margot F, Shimada K (2013) The travelling salesman problem with neighbourhoods: MINLP solution. Optim Methods Softw 28(2):364\u2013378","journal-title":"Optim Methods Softw"},{"key":"793_CR23","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.dam.2011.11.019","volume":"164","author":"MT Godinho","year":"2014","unstructured":"Godinho MT, Gouveia L, Pesneau P (2014) Natural and extended formulations for the time-dependent traveling salesman problem. Discrete Appl Math 164:138\u2013153","journal-title":"Discrete Appl Math"},{"issue":"1","key":"793_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia L, Vo\u00df S (1995) A classification of formulations for the (time-dependent) traveling salesman problem. Eur J Oper Res 83(1):69\u201382","journal-title":"Eur J Oper Res"},{"issue":"2","key":"793_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","volume":"255","author":"A Gunawan","year":"2016","unstructured":"Gunawan A, Lau HC, Vansteenwegen P (2016) Orienteering problem: a survey of recent variants, solution approaches and applications. Eur J Oper Res 255(2):315\u2013332","journal-title":"Eur J Oper Res"},{"issue":"3","key":"793_CR26","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(87)90021-6","volume":"6","author":"JP Hart","year":"1987","unstructured":"Hart JP, Shogan AW (1987) Semi-greedy heuristics: an empirical study. Oper Res Lett 6(3):107\u2013114","journal-title":"Oper Res Lett"},{"key":"793_CR27","doi-asserted-by":"crossref","unstructured":"Hoos HH, St\u00fctzle T (1998) Evaluating Las Vegas Algorithms\u2014Pitfalls and Remedies. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence pp 238\u2013245, 1301.7383","DOI":"10.1007\/978-3-7091-6492-1_54"},{"key":"793_CR28","doi-asserted-by":"crossref","unstructured":"Kulich M, P\u0159eu\u010dil L, Miranda-Bront JJ (2014) Single robot search for a stationary object in an unknown environment. In: 2014 IEEE International Conference on Robotics and Automation (ICRA), IEEE, pp 5830\u20135835","DOI":"10.1109\/ICRA.2014.6907716"},{"key":"793_CR29","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.cor.2016.04.029","volume":"84","author":"M Kulich","year":"2017","unstructured":"Kulich M, Miranda-Bront JJ, P\u0159eu\u010dil L (2017) A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment. Comput Oper Res 84:178\u2013187","journal-title":"Comput Oper Res"},{"issue":"6","key":"793_CR30","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1002\/net.3230200605","volume":"20","author":"A Lucena","year":"1990","unstructured":"Lucena A (1990) Time-dependent traveling salesman problem\u2014the deliveryman case. Networks 20(6):753\u2013763","journal-title":"Networks"},{"key":"793_CR31","first-page":"219","volume":"5","author":"O Martin","year":"1991","unstructured":"Martin O, Otto SW, Felten EW (1991) Large-step Markov chains for the traveling salesman problem. Complex Syst 5:219\u2013224","journal-title":"Complex Syst"},{"issue":"17","key":"793_CR32","doi-asserted-by":"publisher","first-page":"3223","DOI":"10.1016\/j.dam.2008.05.009","volume":"156","author":"I M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz I, Zabala P, Lucena A (2008) A new formulation for the Traveling Deliveryman Problem. Discrete Appl Math 156(17):3223\u20133237","journal-title":"Discrete Appl Math"},{"key":"793_CR33","unstructured":"Mikula J (2021) Search for a static object in a known environment. Master\u2019s thesis, Czech Technical University in Prague, Faculty of Electrical Engineering"},{"issue":"3","key":"793_CR34","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1016\/j.ejor.2013.05.022","volume":"236","author":"JJ Miranda-Bront","year":"2014","unstructured":"Miranda-Bront JJ, M\u00e9ndez-D\u00edaz I, Zabala P (2014) Facets and valid inequalities for the time-dependent travelling salesman problem. Eur J Oper Res 236(3):891\u2013902","journal-title":"Eur J Oper Res"},{"key":"793_CR35","doi-asserted-by":"crossref","unstructured":"Mjirda A, Todosijevi\u0107 R, Hanafi S, Hansen P, Mladenovi\u0107 N (2017) Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. International Transactions in Operational Research","DOI":"10.1111\/itor.12282"},{"issue":"11","key":"793_CR36","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107 N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097\u20131100","journal-title":"Comput Oper Res"},{"issue":"1","key":"793_CR37","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10288-012-0212-1","volume":"11","author":"N Mladenovi\u0107","year":"2013","unstructured":"Mladenovi\u0107 N, Uro\u0161evi\u0107 D, Hanafi S (2013) Variable neighborhood search for the travelling deliveryman problem. 4OR 11(1):57\u201373","journal-title":"4OR"},{"key":"793_CR38","doi-asserted-by":"crossref","unstructured":"Naeni LM, Salehipour A (2019) A New Mathematical Model for the Traveling Repairman Problem. In: 2019 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), IEEE, pp 1384\u20131387","DOI":"10.1109\/IEEM44572.2019.8978898"},{"issue":"4","key":"793_CR39","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G (1991) TSPLIB\u2014a traveling salesman problem library. ORSA J Comput 3(4):376\u2013384","journal-title":"ORSA J Comput"},{"key":"793_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-6530-4","volume-title":"Optimization by GRASP","author":"MGC Resende","year":"2016","unstructured":"Resende MGC, Ribeiro CC (2016) Optimization by GRASP. Springer, New York"},{"issue":"3","key":"793_CR41","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s11590-014-0760-8","volume":"9","author":"CC Ribeiro","year":"2015","unstructured":"Ribeiro CC, Rosseti I (2015) tttplots-compare: a perl program to compare time-to-target plots or general runtime distributions of randomized algorithms. Optim Lett 9(3):601\u2013614","journal-title":"Optim Lett"},{"key":"793_CR42","doi-asserted-by":"crossref","unstructured":"Ribeiro CC, Rosseti I, Vallejos R (2009) On the use of run time distributions to evaluate and compare stochastic local search algorithms. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","DOI":"10.1007\/978-3-642-03751-1_2"},{"key":"793_CR43","unstructured":"Rios EFS (2016) Explora\u00e7\u00e3o de estrat\u00e9gias de busca local em ambientes cpu\/gpu. PhD thesis, Universidade Federal Fluminense"},{"issue":"3","key":"793_CR44","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1287\/trsc.2013.0474","volume":"48","author":"R Roberti","year":"2014","unstructured":"Roberti R, Mingozzi A (2014) Dynamic ng-path relaxation for the delivery man problem. Transp Sci 48(3):413\u2013424","journal-title":"Transp Sci"},{"issue":"3","key":"793_CR45","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T (1976) P-Complete approximation problems. J ACM (JACM) 23(3):555\u2013565","journal-title":"J ACM (JACM)"},{"key":"793_CR46","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10288-011-0153-0","volume":"9","author":"A Salehipour","year":"2011","unstructured":"Salehipour A, S\u00f6rensen K, Goos P, Br\u00e4ysy O (2011) Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem. 4OR 9:189\u2013209","journal-title":"4OR"},{"key":"793_CR47","doi-asserted-by":"crossref","unstructured":"Santana \u00cd, Plastino A, Rosseti I (2020) Improving a state-of-the-art heuristic for the minimum latency problem with data mining. International Transactions in Operational Research 00:itor.12774,","DOI":"10.1111\/itor.12774"},{"key":"793_CR48","doi-asserted-by":"crossref","unstructured":"Sarmiento A, Murrieta-Cid R, Hutchinson S (2004) A multi-robot strategy for rapidly searching a polygonal environment. In: Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) vol3315, pp 484\u2013493","DOI":"10.1007\/978-3-540-30498-2_48"},{"issue":"2","key":"793_CR49","doi-asserted-by":"publisher","first-page":"801","DOI":"10.12928\/telkomnika.v17i2.11789","volume":"17","author":"D Satyananda","year":"2019","unstructured":"Satyananda D, Wahyuningsih S (2019) Sequential order vs random order in operators of variable neighborhood descent method. Telkomnika (Telecommunication Computing Electronics and Control) 17(2):801\u2013808","journal-title":"Telkomnika (Telecommunication Computing Electronics and Control)"},{"issue":"3","key":"793_CR50","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.ejor.2012.03.044","volume":"221","author":"MM Silva","year":"2012","unstructured":"Silva MM, Subramanian A, Vidal T, Ochi LS (2012) A simple and effective metaheuristic for the Minimum Latency Problem. Eur J Oper Res 221(3):513\u2013520","journal-title":"Eur J Oper Res"},{"key":"793_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cor.2017.05.010","volume":"87","author":"SL Smith","year":"2017","unstructured":"Smith SL, Imeson F (2017) GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Comput Oper Res 87:1\u201319","journal-title":"Comput Oper Res"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00793-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-021-00793-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00793-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T17:15:49Z","timestamp":1666026949000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-021-00793-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["793"],"URL":"https:\/\/doi.org\/10.1007\/s10100-021-00793-y","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"type":"print","value":"1435-246X"},{"type":"electronic","value":"1613-9178"}],"subject":[],"published":{"date-parts":[[2022,1,20]]},"assertion":[{"value":"5 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}