{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:58:44Z","timestamp":1775732324483,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,19]],"date-time":"2022-08-19T00:00:00Z","timestamp":1660867200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,19]],"date-time":"2022-08-19T00:00:00Z","timestamp":1660867200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["01IS18070B"],"award-info":[{"award-number":["01IS18070B"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Pathfinding, also known as route planning, is one of the most important aspects of logistics, robotics, and other applications where engineers must balance many competing interests. There is a significant challenge in pathfinding problems with multiple objectives because many paths can map to the same objective value. Such multi-modal solutions cannot easily be found in multi-objective optimisation algorithms, which are typically geared towards selection mechanisms in the objective space. A niching approach for preserving good diverse solutions in the decision space is proposed in this paper, which is tailored for pathfinding problems. The criteria used to compare the solutions within the decision space are path similarity metrics, which we extend from a previous study, and are used instead of the well-established crowding distance. In two variations, we investigate the proposed meta-heuristic approach on a range of benchmark instances and compare the methodology to a deterministic optimisation approach.<\/jats:p>","DOI":"10.1007\/s11047-022-09908-z","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T23:02:45Z","timestamp":1660863765000},"page":"315-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A comparison of distance metrics for the multi-objective pathfinding problem"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8828-8752","authenticated-orcid":false,"given":"Jens","family":"Weise","sequence":"first","affiliation":[]},{"given":"Sanaz","family":"Mostaghim","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,19]]},"reference":[{"issue":"7","key":"9908_CR1","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s00500-012-0964-8","volume":"17","author":"F Ahmed","year":"2013","unstructured":"Ahmed F, Deb K (2013) Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Comput 17(7):1283\u20131299","journal-title":"Soft Comput"},{"issue":"5","key":"9908_CR2","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1109\/TEVC.2009.2021467","volume":"13","author":"Aimin Zhou","year":"2009","unstructured":"Zhou Aimin, Zhang Qingfu, Jin Yaochu (2009) Approximating the set of pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm. IEEE Trans Evol Comput 13(5):1167\u20131189","journal-title":"IEEE Trans Evol Comput"},{"key":"9908_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1142\/S0218195995000064","volume":"05","author":"H Alt","year":"1995","unstructured":"Alt H, Godau M (1995) Computing the Fr\u00e9chet distance between two polygonal curves. Int J Comput Geom Appl (01n02) 05:75\u201391","journal-title":"Int J Comput Geom Appl (01n02)"},{"issue":"2","key":"9908_CR4","doi-asserted-by":"publisher","first-page":"51","DOI":"10.5121\/acij.2013.4205","volume":"4","author":"R Anbuselvi","year":"2013","unstructured":"Anbuselvi R (2013) Path finding solutions for grid based graph. Adv Comput Int J 4(2):51\u201360","journal-title":"Adv Comput Int J"},{"key":"9908_CR5","unstructured":"Anguelov B (2011) Video game pathfinding and improvements to discrete search on grid-based maps. PhD thesis. University of Pretoria"},{"key":"9908_CR6","first-page":"35","volume-title":"A comparison of genetic representations for multi-objective shortest path problems on multigraphs","author":"L Beke","year":"2020","unstructured":"Beke L, Weiszer M, Chen J (2020) A comparison of genetic representations for multi-objective shortest path problems on multigraphs, vol 8. Springer International Publishing, Berlin, pp 35\u201350"},{"key":"9908_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.ins.2013.02.022","volume":"238","author":"E Besada-Portas","year":"2013","unstructured":"Besada-Portas E, de la Torre L, Moreno A et al (2013) On the performance comparison of multi-objective evolutionary UAV path planners. Inf Sci 238:111\u2013125","journal-title":"Inf Sci"},{"issue":"2","key":"9908_CR8","first-page":"46","volume":"7","author":"K Bringmann","year":"2016","unstructured":"Bringmann K, Mulzer W (2016) Approximability of the discrete Fr\u00e9chet distance. J Comput Geom 7(2):46\u201376","journal-title":"J Comput Geom"},{"key":"9908_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.ins.2017.11.051","volume":"430\u2013431","author":"X Cai","year":"2018","unstructured":"Cai X, Sun H, Fan Z (2018) A diversity indicator based on reference vectors for many-objective optimization. Inf Sci 430\u2013431:467\u2013486","journal-title":"Inf Sci"},{"key":"9908_CR10","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.ipl.2018.06.011","volume":"138","author":"TM Chan","year":"2018","unstructured":"Chan TM, Rahmati Z (2018) An improved approximation algorithm for the discrete Fr\u00e9chet distance. Inf Process Lett 138:72\u201374","journal-title":"Inf Process Lett"},{"issue":"4","key":"9908_CR11","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1109\/TEVC.2013.2281535","volume":"18","author":"K Deb","year":"2014","unstructured":"Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput 18(4):577\u2013601","journal-title":"IEEE Trans Evol Comput"},{"key":"9908_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-31880-4_4","volume":"3410","author":"K Deb","year":"2005","unstructured":"Deb K, Tiwari S (2005) Omni-optimizer: a procedure for single and multi-objective optimization. Lect Notes Comput Sci 3410:47\u201361","journal-title":"Lect Notes Comput Sci"},{"issue":"2","key":"9908_CR13","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","volume":"6","author":"K Deb","year":"2002","unstructured":"Deb K, Pratap A, Agarwal S et al (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182\u2013197","journal-title":"IEEE Trans Evol Comput"},{"issue":"4","key":"9908_CR14","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00454-002-2886-1","volume":"28","author":"A Efrat","year":"2002","unstructured":"Efrat A, Guibas LJ, Har-Peled S et al (2002) New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete Comput Geom 28(4):535\u2013569","journal-title":"Discrete Comput Geom"},{"key":"9908_CR15","unstructured":"Eiter T, Mannila H (1994) Computing discrete Fr\u00e9chet distance. Tech. Report CD-TR 94\/64, Christian Doppler Lab. Expert Sys., TU Vienna, Austria"},{"key":"9908_CR16","doi-asserted-by":"publisher","unstructured":"Fan C, Luo J, Zhu B (2011) Fr\u00e9chet-distance on road networks. In: Akiyama J, Bo J, Kano M, Tan X (eds) Computational geometry, graphs and applications. CGGA 2010. Lecture Notes in Computer Science, vol 7033. Springer, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-24983-9_7","DOI":"10.1007\/978-3-642-24983-9_7"},{"issue":"1","key":"9908_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF03018603","volume":"22","author":"MM Fr\u00e9chet","year":"1906","unstructured":"Fr\u00e9chet MM (1906) Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo (1884\u20131940) 22(1):1\u201372","journal-title":"Rendiconti del Circolo Matematico di Palermo (1884\u20131940)"},{"issue":"1","key":"9908_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10288-005-0074-x","volume":"4","author":"X Gandibleux","year":"2006","unstructured":"Gandibleux X, Beugnies F, Randriamasy S (2006) Martins\u2019 algorithm revisited for multi-objective shortest path problems with a MaxMin cost function. 4OR 4(1):47\u201359","journal-title":"4OR"},{"issue":"2","key":"9908_CR19","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100\u2013107","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"9908_CR20","doi-asserted-by":"crossref","unstructured":"Ishibuchi H, Masuda H, Nojima Y (2015) A study on performance evaluation ability of a modified inverted generational distance indicator. In: Proceedings of the 2015 on genetic and evolutionary computation conference\u2014GECCO \u201915. ACM Press, New York, pp 695\u2013702","DOI":"10.1145\/2739480.2754792"},{"key":"9908_CR21","doi-asserted-by":"publisher","unstructured":"Javadi M, Mostaghim S (2021) Using neighborhood-based density measures for multimodal multi-objective optimization. In: Evolutionary multi-criterion optimization. EMO 2021. Lecture Notes in Computer Science, vol 12654. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-72062-9_27","DOI":"10.1007\/978-3-030-72062-9_27"},{"key":"9908_CR22","doi-asserted-by":"crossref","unstructured":"Javadi M, Zille H, Mostaghim S (2019) Modified crowding distance and mutation for multimodal multi-objective optimization. In: Proceedings of the genetic and evolutionary computation conference companion. ACM, New York, pp 211\u2013212","DOI":"10.1145\/3319619.3321970"},{"key":"9908_CR23","series-title":"Springer ECCOMAS book series on computational methods in applied sciences","volume-title":"Combining Manhattan and crowding distances in decision space for multimodal multi-objective optimization problems","author":"M Javadi","year":"2020","unstructured":"Javadi M, Ramirez-Atencia C, Mostaghim S (2020) Combining Manhattan and crowding distances in decision space for multimodal multi-objective optimization problems. Springer ECCOMAS book series on computational methods in applied sciences. ACM, Guimar\u00e3es"},{"issue":"01","key":"9908_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1142\/S0219720008003278","volume":"06","author":"M Jiang","year":"2008","unstructured":"Jiang M, Xu Y, Zhu B (2008) Protein structure\u2013structure alignment with discrete Fr\u00e9chet distance. J Bioinform Comput Biol 06(01):51\u201364","journal-title":"J Bioinform Comput Biol"},{"key":"9908_CR25","doi-asserted-by":"crossref","unstructured":"Jun H, Qingbao Z (2010) Multi-objective mobile robot path planning based on improved genetic algorithm. In: 2010 International conference on intelligent computation technology and automation, vol 2. IEEE, Changsha, pp 752\u2013756","DOI":"10.1109\/ICICTA.2010.300"},{"issue":"3","key":"9908_CR26","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/TRO.2004.838026","volume":"21","author":"S Koenig","year":"2005","unstructured":"Koenig S, Likhachev M (2005) Fast replanning for navigation in unknown terrain. IEEE Trans Robot 21(3):354\u2013363","journal-title":"IEEE Trans Robot"},{"key":"9908_CR27","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/978-3-540-70928-2_55","volume-title":"Evolutionary multi-criterion optimization","author":"M K\u00f6ppen","year":"2007","unstructured":"K\u00f6ppen M, Yoshida K (2007) Substitute distance assignments in NSGA-II for handling many-objective optimization problems. LNCS. Evolutionary multi-criterion optimization, vol 4403. Springer, Berlin, pp 727\u2013741"},{"issue":"2","key":"9908_CR28","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.comgeo.2010.09.008","volume":"44","author":"A Maheshwari","year":"2011","unstructured":"Maheshwari A, Sack JR, Shahbaz K et al (2011) Fr\u00e9chet distance with speed limits. Comput Geom 44(2):110\u2013120","journal-title":"Comput Geom"},{"issue":"5","key":"9908_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1754399.1754400","volume":"57","author":"L Mandow","year":"2010","unstructured":"Mandow L, De La Cruz JLP (2010) Multiobjective A* search with consistent heuristics. J ACM 57(5):1\u201325","journal-title":"J ACM"},{"issue":"2","key":"9908_CR30","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","volume":"16","author":"EQV Martins","year":"1984","unstructured":"Martins EQV (1984) On a multicriteria shortest path problem. Eur J Oper Res 16(2):236\u2013245","journal-title":"Eur J Oper Res"},{"key":"9908_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-540-74048-3_4","volume-title":"Information retrieval for music and motion","author":"M M\u00fcller","year":"2007","unstructured":"M\u00fcller M (2007) Dynamic time warping. Information retrieval for music and motion. Springer, Berlin, pp 69\u201384"},{"key":"9908_CR32","volume-title":"Topology. Featured titles for topology","author":"JR Munkres","year":"2000","unstructured":"Munkres JR (2000) Topology. Featured titles for topology. Prentice Hall, Incorporated, New York"},{"issue":"4","key":"9908_CR33","doi-asserted-by":"publisher","first-page":"357","DOI":"10.12720\/joace.2.4.357-362","volume":"2","author":"BK Oleiwi","year":"2014","unstructured":"Oleiwi BK, Roth H, Kazem BI (2014) Modified genetic algorithm based on A* algorithm of multi objective optimization for path planning. J Autom Control Eng 2(4):357\u2013362","journal-title":"J Autom Control Eng"},{"key":"9908_CR34","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.cor.2015.05.007","volume":"64","author":"FJJ Pulido","year":"2015","unstructured":"Pulido FJJ, Mandow L, P\u00e9rez-De-La-Cruz JLL (2015) Dimensionality reduction in multiobjective shortest path search. Comput Oper Res 64:60\u201370","journal-title":"Comput Oper Res"},{"issue":"6","key":"9908_CR35","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/bult.2010.1720360610","volume":"36","author":"MA Rodriguez","year":"2010","unstructured":"Rodriguez MA, Neubauer P (2010) Constructions from dots and lines. Bull Am Soc Inf Sci Technol 36(6):35\u201341","journal-title":"Bull Am Soc Inf Sci Technol"},{"key":"9908_CR36","doi-asserted-by":"crossref","unstructured":"Shir OM (2012) Niching in evolutionary algorithms. In: Handbook of natural computing, vol 1\u20134. Springer, Berlin, pp 1035\u20131069","DOI":"10.1007\/978-3-540-92910-9_32"},{"key":"9908_CR37","doi-asserted-by":"crossref","unstructured":"Shir OM, Preuss M, Naujoks B et al (2009) Enhancing decision space diversity in evolutionary multiobjective algorithms. Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) LNCS, vol 5467, pp 95\u2013109","DOI":"10.1007\/978-3-642-01020-0_12"},{"key":"9908_CR38","doi-asserted-by":"crossref","unstructured":"Sriraghavendra E, Karthik K, Bhattacharyya C (2007) Fr\u00e9chet distance based approach for searching online handwritten documents. In: Ninth international conference on document analysis and recognition (ICDAR 2007), vol 1. IEEE, Curitiba, Paran\u00e1, pp 461\u2013465","DOI":"10.1109\/ICDAR.2007.4378752"},{"issue":"2","key":"9908_CR39","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1109\/TCIAIG.2012.2197681","volume":"4","author":"NR Sturtevant","year":"2012","unstructured":"Sturtevant NR (2012) Benchmarks for grid-based pathfinding. IEEE Trans Comput Intell AI Games 4(2):144\u2013148","journal-title":"IEEE Trans Comput Intell AI Games"},{"key":"9908_CR40","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.eswa.2016.10.045","volume":"72","author":"B Tozer","year":"2017","unstructured":"Tozer B, Mazzuchi T, Sarkani S (2017) Many-objective stochastic path finding using reinforcement learning. Expert Syst Appl 72:371\u2013382","journal-title":"Expert Syst Appl"},{"key":"9908_CR41","doi-asserted-by":"crossref","unstructured":"Ulrich T, Bader J, Zitzler E (2010) Integrating decision space diversity into hypervolume-based multiobjective search. In: Proceedings of the 12th annual conference on genetic and evolutionary computation\u2014GECCO \u201910. ACM Press, New York, p 455","DOI":"10.1145\/1830483.1830569"},{"key":"9908_CR42","doi-asserted-by":"crossref","unstructured":"Weise J, Mostaghim S (2020) A many-objective route planning benchmark problem for navigation. In: Proceedings of the 2020 genetic and evolutionary computation conference companion, GECCO \u201920. ACM, New York, pp 183\u2013184","DOI":"10.1145\/3377929.3389996"},{"key":"9908_CR43","doi-asserted-by":"crossref","unstructured":"Weise J, Mostaghim S (2021) A customized Niching methodology for the many-objective pathfinding problem. In: 2021 IEEE symposium series on computational intelligence (SSCI). IEEE, Orlando, pp 1\u20138","DOI":"10.1109\/SSCI50451.2021.9659956"},{"key":"9908_CR44","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1109\/TEVC.2021.3089050","volume":"26","author":"J Weise","year":"2021","unstructured":"Weise J, Mostaghim S (2021) A scalable many-objective pathfinding benchmark suite. IEEE Trans Evol Comput 26:188\u2013194","journal-title":"IEEE Trans Evol Comput"},{"key":"9908_CR45","doi-asserted-by":"crossref","unstructured":"Weise J, Mostaghim S (2021c) Many-objective pathfinding based on Fr\u00e9chet similarity metric. In: 11th International conference, EMO 2021, Shenzhen, China, 28\u201331 Mar 2021, proceedings. 01, pp 375\u2013386","DOI":"10.1007\/978-3-030-72062-9_30"},{"key":"9908_CR46","doi-asserted-by":"crossref","unstructured":"Weise J, Mai S, Zille H et\u00a0al (2020) On the scalable multi-objective multi-agent pathfinding problem. In: 2020 IEEE congress on evolutionary computation (CEC). IEEE, pp 1\u20138","DOI":"10.1109\/CEC48606.2020.9185585"},{"key":"9908_CR47","doi-asserted-by":"crossref","unstructured":"Weise J, Zille H, Mostaghim S (2021) A comparative study of different encodings on the multi-objective pathfinding problem. In: 2021 IEEE symposium series on computational intelligence (SSCI). IEEE, Orlando, pp 1\u20138","DOI":"10.1109\/SSCI50451.2021.9660055"},{"key":"9908_CR48","first-page":"117","volume":"32","author":"J Xiao","year":"1999","unstructured":"Xiao J, Michalewicz Z (1999) An evolutionary computation approach to robot planning and navigation. Soft Comput Mechatron 32:117\u2013141","journal-title":"Soft Comput Mechatron"},{"key":"9908_CR49","doi-asserted-by":"crossref","unstructured":"Yap P (2002) Grid-based path-finding. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics), vol 2338, pp 44\u201355","DOI":"10.1007\/3-540-47922-8_4"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09908-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-022-09908-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09908-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T08:17:08Z","timestamp":1686125828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-022-09908-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,19]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9908"],"URL":"https:\/\/doi.org\/10.1007\/s11047-022-09908-z","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,19]]},"assertion":[{"value":"25 July 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}