{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T05:37:27Z","timestamp":1780983447299,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T00:00:00Z","timestamp":1617062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T00:00:00Z","timestamp":1617062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper compares different solution approaches for the multi-objective shortest path problem (MSPP) on multigraphs. Multigraphs as a modelling tool are able to capture different available trade-offs between objectives for a given section of a route. For this reason, they are increasingly popular in modelling transportation problems with multiple conflicting objectives (e.g., travel time and fuel consumption), such as time-dependent vehicle routing, multi-modal transportation planning, energy-efficient driving, and airport operations. The multigraph MSPP is more complex than the NP-hard simple graph MSPP. Therefore, approximate solution methods are often needed to find a good approximation of the true Pareto front in a given time budget. Evolutionary algorithms have been successfully applied for the simple graph MSPP. However, there has been limited investigation of their applications to the multigraph MSPP. Here, we extend the most popular genetic representations to the multigraph case and compare the achieved solution qualities. Two heuristic initialisation methods are also considered to improve the convergence properties of the algorithms. The comparison is based on a diverse set of problem instances, including both bi-objective and triple objective problems. We found that the metaheuristic approach with heuristic initialisation provides good solutions in shorter running times compared to an exact algorithm. The representations were all found to be competitive. The results are encouraging for future application to the time-constrained multigraph MSPP.<\/jats:p>","DOI":"10.1007\/s42979-021-00512-z","type":"journal-article","created":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T16:02:52Z","timestamp":1617120172000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Comparison of Genetic Representations and Initialisation Methods for the Multi-objective Shortest Path Problem on Multigraphs"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1284-1080","authenticated-orcid":false,"given":"Lilla","family":"Beke","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Weiszer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,30]]},"reference":[{"issue":"12","key":"512_CR1","doi-asserted-by":"publisher","first-page":"3524","DOI":"10.1109\/TITS.2016.2587619","volume":"17","author":"J Chen","year":"2016","unstructured":"Chen J, Weiszer M, Locatelli G, Ravizza S, Atkin JA, Stewart P, Burke EK. Toward a more realistic, cost-effective, and greener ground movement through active routing: a multiobjective shortest path approach. IEEE Trans Intell Transp Syst. 2016;17(12):3524\u201340.","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"2","key":"512_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/j.ejor.2015.11.034","volume":"251","author":"JF Ehmke","year":"2016","unstructured":"Ehmke JF, Campbell AM, Thomas BW. Vehicle routing to minimize time-dependent emissions in urban areas. Eur J Oper Res. 2016;251(2):478\u201394.","journal-title":"Eur J Oper Res"},{"issue":"1","key":"512_CR3","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1080\/15472450.2014.941759","volume":"19","author":"J Hrn\u010d\u00ed\u0159","year":"2015","unstructured":"Hrn\u010d\u00ed\u0159 J, Rovatsos M, Jakob M. Ridesharing on timetabled transport services: a multiagent planning approach. J Intell Transp Syst. 2015;19(1):89\u2013105.","journal-title":"J Intell Transp Syst"},{"issue":"3","key":"512_CR4","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1016\/j.ejor.2015.09.009","volume":"248","author":"J Qian","year":"2016","unstructured":"Qian J, Eglese R. Fuel emissions optimization in vehicle routing problems with time-varying speeds. Eur J Oper Res. 2016;248(3):840\u20138.","journal-title":"Eur J Oper Res"},{"issue":"5","key":"512_CR5","doi-asserted-by":"publisher","first-page":"2786","DOI":"10.1109\/TITS.2015.2422778","volume":"16","author":"X Wu","year":"2015","unstructured":"Wu X, He X, Yu G, Harmandayan A, Wang Y. Energy-optimal speed control for electric vehicles on signalized arterials. IEEE Trans Intell Transp Syst. 2015;16(5):2786\u201396.","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"1","key":"512_CR6","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.ejor.2009.10.002","volume":"204","author":"T Garaix","year":"2010","unstructured":"Garaix T, Artigues C, Feillet D, Josselin D. Vehicle routing problems with alternative paths: an application to on-demand transportation. Eur J Oper Res. 2010;204(1):62\u201375.","journal-title":"Eur J Oper Res"},{"key":"512_CR7","doi-asserted-by":"crossref","unstructured":"Serafini P. Some considerations about computational complexity for multi objective combinatorial problems. In: Johannes J, Werner K (eds) Recent advances and historical development of vector optimization. Springer; 1987. p. 222\u201332.","DOI":"10.1007\/978-3-642-46618-2_15"},{"issue":"1","key":"512_CR8","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1016\/j.eswa.2011.08.044","volume":"39","author":"C Chitra","year":"2012","unstructured":"Chitra C, Subbaraj P. A nondominated sorting genetic algorithm solution for shortest path routing problem in computer networks. Expert Syst Appl. 2012;39(1):1518\u201325.","journal-title":"Expert Syst Appl"},{"issue":"6","key":"512_CR9","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1080\/13658816.2012.737921","volume":"27","author":"R Li","year":"2013","unstructured":"Li R, Leung Y, Huang B, Lin H. A genetic algorithm for multiobjective dangerous goods route planning. Int J Geogr Inf Sci. 2013;27(6):1073\u201389.","journal-title":"Int J Geogr Inf Sci"},{"issue":"3","key":"512_CR10","first-page":"416","volume":"128","author":"L Lin","year":"2008","unstructured":"Lin L, Gen M. An effective evolutionary approach for bicriteria shortest path routing problems. IEEJ Trans Electron Inf Syst. 2008;128(3):416\u201323.","journal-title":"IEEJ Trans Electron Inf Syst"},{"issue":"3","key":"512_CR11","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/937503.937505","volume":"35","author":"C Blum","year":"2003","unstructured":"Blum C, Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv (CSUR). 2003;35(3):268\u2013308.","journal-title":"ACM Comput Surv (CSUR)"},{"issue":"4","key":"512_CR12","doi-asserted-by":"publisher","first-page":"789","DOI":"10.2298\/CSIS090710024A","volume":"7","author":"RA Abbaspour","year":"2010","unstructured":"Abbaspour RA, Samadzadegan F. An evolutionary solution for multimodal shortest path problem in metropolises. Comput Sci Inf Syst. 2010;7(4):789\u2013811.","journal-title":"Comput Sci Inf Syst"},{"key":"512_CR13","unstructured":"Yu H, Lu F. A multi-modal route planning approach with an improved genetic algorithm. In: Wenzhong S, Michael G, Brian L, Yee L (eds) Advances in geo-spatial information science; 2012. pp 193\u2013202 ISBN 978-0-415-62093-2. https:\/\/books.google.co.uk\/books?hl=en&lr=&id=CAi6FKV00SYC&oi=fnd&pg=PA193&ots=qYwVLiIkwL&sig=JkDe3kB0m0vbasyp_X6Ch9tu4XE#v=onepage&q&f=false."},{"issue":"6","key":"512_CR14","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/TEVC.2002.804323","volume":"6","author":"CW Ahn","year":"2002","unstructured":"Ahn CW, Ramakrishna RS. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Trans Evol Comput. 2002;6(6):566\u201379.","journal-title":"IEEE Trans Evol Comput"},{"key":"512_CR15","doi-asserted-by":"crossref","unstructured":"Inagaki J, Haseyama M, Kitajima H. A genetic algorithm for determining multiple routes and its applications. In: ISCAS\u201999. Proceedings of the 1999 IEEE international symposium on circuits and systems VLSI (Cat. No. 99CH36349), vol.\u00a06. IEEE; 1999. p. 137\u201340.","DOI":"10.1109\/ISCAS.1999.780114"},{"issue":"3","key":"512_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00291-005-0029-9","volume":"28","author":"M Gen","year":"2006","unstructured":"Gen M, Altiparmak F, Lin L. A genetic algorithm for two-stage transportation problem using priority-based encoding. OR Spectr. 2006;28(3):337\u201354.","journal-title":"OR Spectr"},{"issue":"1","key":"512_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1162\/evco.1998.6.1.81","volume":"6","author":"EK Burke","year":"1998","unstructured":"Burke EK, Newall JP, Weare RF. Initialization strategies and diversity in evolutionary timetabling. Evol Comput. 1998;6(1):81\u2013103.","journal-title":"Evol Comput"},{"key":"512_CR18","doi-asserted-by":"publisher","unstructured":"Deng Y, Liu Y, Zhou D. An improved genetic algorithm with initial population strategy for symmetric tsp. Mathemat Prob Eng. 2015;1\u20136. https:\/\/doi.org\/10.1155\/2015\/212794","DOI":"10.1155\/2015\/212794"},{"key":"512_CR19","doi-asserted-by":"crossref","unstructured":"Hasan BS, Khamees MA, Mahmoud ASH. A heuristic genetic algorithm for the single source shortest path problem. In: 2007 IEEE\/ACS international conference on computer systems and applications. IEEE; 2007. p. 187\u201394.","DOI":"10.1109\/AICCSA.2007.370882"},{"key":"512_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ins.2015.11.004","volume":"332","author":"J Lee","year":"2016","unstructured":"Lee J, Kim DW. An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph. Inf Sci. 2016;332:1\u201318.","journal-title":"Inf Sci"},{"key":"512_CR21","doi-asserted-by":"crossref","unstructured":"Beke L, Weiszer M, Chen J. A comparison of genetic representations for multi-objective shortest path problems on multigraphs. In: European conference on evolutionary computation in combinatorial optimization (part of EvoStar). Springer; 2020. p. 35\u201350.","DOI":"10.1007\/978-3-030-43680-3_3"},{"key":"512_CR22","unstructured":"Munetomo M, Takai Y, Sato Y. An adaptive network routing algorithm employing path genetic operators. In: ICGA 1997."},{"issue":"3","key":"512_CR23","doi-asserted-by":"publisher","first-page":"1515","DOI":"10.1016\/j.eswa.2010.07.064","volume":"38","author":"Z Ji","year":"2011","unstructured":"Ji Z, Kim YS, Chen A. Multi-objective $$\\alpha$$-reliable path finding in stochastic networks with correlated link costs: a simulation-based multi-objective genetic algorithm approach (smoga). Expert Syst Appl. 2011;38(3):1515\u201328.","journal-title":"Expert Syst Appl"},{"key":"512_CR24","doi-asserted-by":"crossref","unstructured":"Lin L, Gen M. Priority-based genetic algorithm for shortest path routing problem in ospf. In: Intelligent and evolutionary systems. Springer; 2009. p. 91\u2013103.","DOI":"10.1007\/978-3-540-95978-6_7"},{"issue":"4","key":"512_CR25","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1016\/j.asoc.2008.01.002","volume":"8","author":"AW Mohemmed","year":"2008","unstructured":"Mohemmed AW, Sahoo NC, Geok TK. Solving shortest path problem using particle swarm optimization. Appl Soft Comput. 2008;8(4):1643\u201353.","journal-title":"Appl Soft Comput"},{"key":"512_CR26","unstructured":"Gen M, Cheng R, Wang D. Genetic algorithms for solving shortest path problems. In: Proceedings of 1997 IEEE international conference on evolutionary computation (ICEC\u201997). IEEE; 1997. p. 401\u20136."},{"key":"512_CR27","doi-asserted-by":"crossref","unstructured":"Gen M, Lin L. A new approach for shortest path routing problem by random key-based ga. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. ACM; 2006. p. 1411\u20132.","DOI":"10.1145\/1143997.1144220"},{"issue":"2","key":"512_CR28","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1287\/ijoc.6.2.154","volume":"6","author":"JC Bean","year":"1994","unstructured":"Bean JC. Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput. 1994;6(2):154\u201360.","journal-title":"ORSA J Comput"},{"issue":"2","key":"512_CR29","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, Meyarivan T. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans Evol Comput. 2002;6(2):182\u201397.","journal-title":"IEEE Trans Evol Comput"},{"key":"512_CR30","unstructured":"Seada H, Deb K. U-nsga-iii: a unified evolutionary algorithm for single, multiple, and many-objective optimization. COIN report. 2014;2014022."},{"key":"512_CR31","doi-asserted-by":"publisher","unstructured":"This research utilised queen mary\u2019s apocrita hpc facility, supported by qmul research-it. https:\/\/doi.org\/10.5281\/zenodo.438045","DOI":"10.5281\/zenodo.438045"},{"key":"512_CR32","unstructured":"Inspyred: Bio-inspired algorithms in python. https:\/\/www.pythonhosted.org\/inspyred\/. Accessed 30 Oct 2019."},{"key":"512_CR33","doi-asserted-by":"publisher","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez M, Dubois-Lacoste J, P\u00e9rez C\u00e1ceres L, St\u00fctzle T, Birattari M. The irace package: Iterated racing for automatic algorithm configuration. Oper Res Perspect. 2016;3, 43\u201358. https:\/\/doi.org\/10.1016\/j.orp.2016.09.002.","DOI":"10.1016\/j.orp.2016.09.002"},{"issue":"9","key":"512_CR34","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1109\/49.12889","volume":"6","author":"BM Waxman","year":"1988","unstructured":"Waxman BM. Routing of multipoint connections. IEEE J Sel Areas Commun. 1988;6(9):1617\u201322.","journal-title":"IEEE J Sel Areas Commun"},{"key":"512_CR35","doi-asserted-by":"crossref","unstructured":"Machuca E, Mandow L, de\u00a0la Cruz JLP, Ruiz-Sepulveda A. An empirical comparison of some multiobjective graph search algorithms. In: Annual conference on artificial intelligence. Springer; 2010. p. 238\u201345.","DOI":"10.1007\/978-3-642-16111-7_27"},{"issue":"1","key":"512_CR36","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0377-2217(91)90094-C","volume":"53","author":"J Mote","year":"1991","unstructured":"Mote J, Murthy I, Olson DL. A parametric approach to solving bicriterion shortest path problems. Eur J Oper Res. 1991;53(1):81\u201392.","journal-title":"Eur J Oper Res"},{"key":"512_CR37","unstructured":"Mandow L, De\u00a0la Cruz JP, et\u00a0al. A new approach to multiobjective a* search. In: IJCAI, vol.\u00a08. Citeseer; 2005."},{"issue":"2","key":"512_CR38","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0377-2217(92)90248-8","volume":"62","author":"CT Tung","year":"1992","unstructured":"Tung CT, Chew KL. A multicriteria pareto-optimal path algorithm. Eur J Oper Res. 1992;62(2):203\u20139.","journal-title":"Eur J Oper Res"},{"key":"512_CR39","first-page":"581","volume":"2016","author":"A Liefooghe","year":"2016","unstructured":"Liefooghe A, Derbel B. A correlation analysis of set quality indicator values in multiobjective optimization. Proc Genet Evol Comput Conf. 2016;2016:581\u20138.","journal-title":"Proc Genet Evol Comput Conf"},{"key":"512_CR40","unstructured":"Fonseca CM, Knowles JD, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. In: Third international conference on evolutionary multi-criterion optimization (EMO 2005), vol. 216; 2005. p. 240."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00512-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00512-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00512-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T04:20:57Z","timestamp":1724732457000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00512-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,30]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["512"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00512-z","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,30]]},"assertion":[{"value":"8 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2021","order":3,"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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"176"}}