{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:31:45Z","timestamp":1762299105614,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T00:00:00Z","timestamp":1569024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T00:00:00Z","timestamp":1569024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472192"],"award-info":[{"award-number":["61472192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>The dynamic travelling salesman problem (DTSP) is a natural extension of the standard travelling salesman problem, and it has attracted significant interest in recent years due to is practical applications. In this article, we propose an efficient solution for DTSP, based on a genetic algorithm (GA), and on the one-by-one revision of two sides (GORTS). More specifically, GORTS combines the global search ability of GA with the fast convergence feature of the method of one-by-one revision of two sides, in order to find the optimal solution in a short time. An experimental platform was designed to evaluate the performance of GORTS with TSPLIB. The experimental results show that the efficiency of GORTS compares favourably against other popular heuristic algorithms for DTSP. In particular, a prototype logistics system based on GORTS for a supermarket with an online map was designed and implemented. It was shown that this can provide optimised goods distribution routes for delivery staff, while considering real-time traffic information.<\/jats:p>","DOI":"10.1007\/s00500-019-04335-2","type":"journal-article","created":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T04:05:56Z","timestamp":1569038756000},"page":"7197-7210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["GORTS: genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2189-750X","authenticated-orcid":false,"given":"Xiaolong","family":"Xu","sequence":"first","affiliation":[]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8363-0715","authenticated-orcid":false,"given":"Peter","family":"Matthew","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7469-6694","authenticated-orcid":false,"given":"Jeffrey","family":"Ray","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4193-9842","authenticated-orcid":false,"given":"Ovidiu","family":"Bagdasar","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6607-422X","authenticated-orcid":false,"given":"Marcello","family":"Trovati","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,21]]},"reference":[{"key":"4335_CR1","unstructured":"Alves RMF, Lopes CR (2015) Using genetic algorithms to minimize the distance and balance the routes for the multiple traveling salesman problem. In: in Proceedings of CEC, Sendai. 1\u20138"},{"issue":"11","key":"4335_CR2","first-page":"256","volume":"12","author":"R Avin","year":"2012","unstructured":"Avin R, Agin D, Adnan M (2012) Solving tsp using genetic algorithms\u2014case of Kosovo, advances in. Computer Sci 12(11):256\u2013260","journal-title":"Computer Sci"},{"key":"4335_CR3","doi-asserted-by":"publisher","unstructured":"Bessis N, Sotiriadis S, Pop F, Cristea V (2012) Optimizing the energy efficiency of message exchanging for service distribution in interoperable infrastructures. pp 105\u2013112. \nhttps:\/\/doi.org\/10.1109\/iNCoS.2012.16","DOI":"10.1109\/iNCoS.2012.16"},{"key":"4335_CR4","unstructured":"Blackwell BT, Branke J (2004) Multi-swarm optimization in dynamic environments. Applications of Evolutionary Computing, Evoworkshops 3005"},{"key":"4335_CR5","doi-asserted-by":"crossref","unstructured":"Boryczka, U, Strak \u0141 (2012) A hybrid discrete particle swarm optimization with pheromone for dynamic traveling salesman problem. In: Computational Collective Intelligence. Technologies and Applications, LNCS pp 503\u2013512","DOI":"10.1007\/978-3-642-34707-8_51"},{"issue":"14","key":"4335_CR6","first-page":"7","volume":"2009","author":"H Cheng","year":"2009","unstructured":"Cheng H, Yang SX (2009) Genetic algorithms with elitism-based immigrants for dynamic shortest path problem in mobile ad hoc networks. IEEE Congress Evolut Comput (CEC) 2009(14):7\u20133135","journal-title":"IEEE Congress Evolut Comput (CEC)"},{"issue":"5","key":"4335_CR7","first-page":"19","volume":"12","author":"WJ Cook","year":"2011","unstructured":"Cook WJ (2011) In pursuit of the traveling salesman: mathematics at the limits of computation. J Classif 12(5):19\u201321","journal-title":"J Classif"},{"key":"4335_CR8","doi-asserted-by":"crossref","unstructured":"Falcon R, Nayak A (2010) The one-commodity traveling salesman problem with selective pickup and delivery: an ant colony approach. In: in Proceedings of CEC. pp 4326\u20134333. Barcelona, Spain","DOI":"10.1109\/CEC.2010.5586036"},{"key":"4335_CR9","volume-title":"Computers and intractability: a guide to the theory of np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness. Wh Freeman & Company, New York"},{"key":"4335_CR10","unstructured":"Gerhard R (2013) Tsplib. Website \nhttps:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/"},{"key":"4335_CR11","unstructured":"Ghadle KP, Muley YM (2014) An application of assignment problem in traveling salesman problem (tsp. Journal of Engineering Research and Applications pp 169\u2013172"},{"issue":"1","key":"4335_CR12","first-page":"0975","volume":"53","author":"FS Gharehchopogh","year":"2012","unstructured":"Gharehchopogh FS, Farahmandian IMM (2012) New approach for solving dynamic travelling salesman problem with hybrid genetic algorithms and ant colony optimization. Int J Comput Appl 53(1):0975\u20138887","journal-title":"Int J Comput Appl"},{"key":"4335_CR13","doi-asserted-by":"crossref","unstructured":"Guntsch M, Middendorf M (2002) Applying population based aco to dynamic optimization problems. In: in Ant Algorithms, LNCS. pp 111\u2013122","DOI":"10.1007\/3-540-45724-0_10"},{"key":"4335_CR14","doi-asserted-by":"crossref","unstructured":"Kang L, Zhou A, McKay B, Li Y, Kang Z (2004) Bench-marking algorithms for dynamic travelling salesman problems. In: in proceedings of 2004. IEEE Congr Evol Comput 2(2), 1286\u20131292","DOI":"10.1109\/CEC.2004.1331045"},{"issue":"6","key":"4335_CR15","first-page":"24","volume":"15","author":"J Li","year":"2013","unstructured":"Li J (2013) An improved dynamic programming algorithm for bitonic tsp, j. Classification 15(6):24\u201327","journal-title":"Classification"},{"key":"4335_CR16","doi-asserted-by":"crossref","unstructured":"Li C, Yang M, Kang L (2006) A new approach to solving dynamic taveling salesman problem. In: in Proceedings of 6th International Conference on Simulated Evolution and Learning. pp 236\u2013243","DOI":"10.1007\/11903697_31"},{"issue":"2","key":"4335_CR17","first-page":"356","volume":"32","author":"ZY Li","year":"2015","unstructured":"Li ZY, Ma L, Zhang HZ (2015) Discrete bat algorithm for solving minimum ratio traveling salesman problem. J Clas-sif Appl Res Comput 32(2):356\u2013359","journal-title":"J Clas-sif Appl Res Comput"},{"key":"4335_CR18","doi-asserted-by":"crossref","unstructured":"Liu Y, Shen, X, Chen H (2012) An adaptive ant colony algorithm based on common information for solving the traveling salesman problem. In: in Proceedings of ICSAI, Shandong ,pp 763-766","DOI":"10.1109\/ICSAI.2012.6223122"},{"key":"4335_CR19","doi-asserted-by":"crossref","unstructured":"Mahfoudh, SS, Khaznaji W, Bellalouna M (2015) A branch and bound algorithm for the porbabilistic traveling salesman problem. In: in Proceedinfs of SNPD, Takamatsu. pp 1\u20136","DOI":"10.1109\/SNPD.2015.7176284"},{"issue":"4","key":"4335_CR20","first-page":"1","volume":"13","author":"M Mavrovouniotis","year":"2016","unstructured":"Mavrovouniotis M, M\u00fcller FM, Yang S (2016) Ant colony optimization with local search for dynamic traveling salesman problems. IEEE Trans Cybern 13(4):1\u201314","journal-title":"IEEE Trans Cybern"},{"issue":"10","key":"4335_CR21","first-page":"4023","volume":"13","author":"M Mavrovouniotis","year":"2013","unstructured":"Mavrovouniotis M, Yang S (2013) Ant colony optimization with immigrants schemes for the dynamic travelling sales-man problem with traffic factors. J Classif Appl 13(10):4023\u20134037","journal-title":"J Classif Appl"},{"key":"4335_CR22","doi-asserted-by":"crossref","unstructured":"Melo L, Pereira F, Costa E (2013) ser LNCS: Multi-caste ant colony algorithm for the dynamic traveling salesperson problem. In: in Adaptive and Natural Computing Algorithms. pp 179\u2013188","DOI":"10.1007\/978-3-642-37213-1_19"},{"issue":"1","key":"4335_CR23","first-page":"974","volume":"12","author":"M Niendorf","year":"2015","unstructured":"Niendorf M, Kabamba PT (2015) Girard a r. stability of solutions to classes of traveling salesman problems. Cybernetics IEEE Trans 12(1):974\u2013985","journal-title":"Cybernetics IEEE Trans"},{"issue":"4","key":"4335_CR24","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1109\/TCYB.2015.2418737","volume":"46","author":"M Niendorf","year":"2016","unstructured":"Niendorf M, Kabamba PT, Girard AR (2016) Stability of solutions to classes of traveling salesman problems. IEEE Trans Cybern 46(4):973\u2013985","journal-title":"IEEE Trans Cybern"},{"issue":"9","key":"4335_CR25","doi-asserted-by":"publisher","first-page":"1745","DOI":"10.1007\/s00500-013-1207-3","volume":"18","author":"DG Reina","year":"2014","unstructured":"Reina DG, Le\u00f3n-Coca JM, Toral SL, Asimakopoulou E, Barrero F, Norrington P, Bessis N (2014) Multi-objective performance optimization of a probabilistic similarity\/dissimilarity-based broadcasting scheme for mobile ad hoc networks in disaster response scenarios. Soft Comput 18(9):1745\u20131756. \nhttps:\/\/doi.org\/10.1007\/s00500-013-1207-3","journal-title":"Soft Comput"},{"issue":"3","key":"4335_CR26","first-page":"385","volume":"6","author":"G Singh","year":"2014","unstructured":"Singh G, Mehta R (2014) Implementation of travelling salesman problem using ant colony optimization. J Eng Res Appl 6(3):385\u2013389","journal-title":"J Eng Res Appl"},{"key":"4335_CR27","doi-asserted-by":"crossref","unstructured":"Stutzle T, Hoos H (1997) Max-min ant system and local search for the traveling salesman problem. IEEE Int Conf Evol Comput 309\u2013314","DOI":"10.1109\/ICEC.1997.592327"},{"key":"4335_CR28","doi-asserted-by":"crossref","unstructured":"Tinos R, Whitley D, Howe A (2014) Use of explicit memory in the dynamic traveling salesman problem. In: in Proceedings of 2014 Annual Conference Genetic","DOI":"10.1145\/2576768.2598247"},{"key":"4335_CR29","doi-asserted-by":"crossref","unstructured":"Wang Y (2014) A nearest neighbor method with a frequency graph for traveling salesman problem. In: in Proceedings of IHMSC. Hangzhou. pp 335\u2013338","DOI":"10.1109\/IHMSC.2014.88"},{"key":"4335_CR30","doi-asserted-by":"publisher","unstructured":"Xu X, Bessis N, Cao J (2013) An autonomic agent trust model for iot systems. Procedia Computer Science 21, 107 \u2013 113. \nhttps:\/\/doi.org\/10.1016\/j.procs.2013.09.016\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S1877050913008090\n\n, the 4th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN-2013) and the 3rd International Conference on Current and Future Trends of Information and Communication Technologies in Healthcare (ICTH)","DOI":"10.1016\/j.procs.2013.09.016"},{"issue":"1","key":"4335_CR31","first-page":"102","volume":"24","author":"XW Yang","year":"2009","unstructured":"Yang XW, Chen ZJ (2009) Li: A l, seeking the best hamilton cycle through matrix tuning. J Logistical Eng Univ 24(1):102\u2013106","journal-title":"J Logistical Eng Univ"},{"issue":"1","key":"4335_CR32","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.ejor.2013.01.043","volume":"228","author":"S Yuan","year":"2013","unstructured":"Yuan S, Skinner B, Huang S, Liu D (2013) A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. Eur J Oper Res 228(1):72\u201382","journal-title":"Eur J Oper Res"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-019-04335-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00500-019-04335-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-019-04335-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T23:34:35Z","timestamp":1600558475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00500-019-04335-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,21]]},"references-count":32,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["4335"],"URL":"https:\/\/doi.org\/10.1007\/s00500-019-04335-2","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"type":"print","value":"1432-7643"},{"type":"electronic","value":"1433-7479"}],"subject":[],"published":{"date-parts":[[2019,9,21]]},"assertion":[{"value":"21 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}