A Comparison of Genetic Representations and Initialisation Methods for the Multi-objective Shortest Path Problem on Multigraphs
dc.contributor.author | Beke, L | |
dc.contributor.author | Weiszer, M | |
dc.contributor.author | Chen, J | |
dc.contributor.editor | Ekárt, A | |
dc.contributor.editor | Esparcia-Alcázar, AI | |
dc.date.accessioned | 2021-05-05T10:26:36Z | |
dc.date.available | 2021-02-08 | |
dc.date.available | 2021-05-05T10:26:36Z | |
dc.date.issued | 2021-05 | |
dc.identifier.citation | Beke, Lilla et al. "A Comparison Of Genetic Representations And Initialisation Methods For The Multi-Objective Shortest Path Problem On Multigraphs". SN Computer Science, vol 2, no. 3, 2021. Springer Science And Business Media LLC, doi:10.1007/s42979-021-00512-z. Accessed 5 May 2021. | en_US |
dc.identifier.issn | 2662-995X | |
dc.identifier.other | 176 | |
dc.identifier.other | 176 | |
dc.identifier.uri | https://qmro.qmul.ac.uk/xmlui/handle/123456789/71621 | |
dc.description.abstract | 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. | en_US |
dc.language | en | |
dc.publisher | Springer Science and Business Media LLC | en_US |
dc.relation.ispartof | SN Computer Science | |
dc.rights | This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. | |
dc.rights | Attribution 3.0 United States | * |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/us/ | * |
dc.subject | Multi-objective shortest path problems | en_US |
dc.subject | Heuristic initialisation | en_US |
dc.subject | Genetic representation techniques | en_US |
dc.subject | Multigraphs | en_US |
dc.title | A Comparison of Genetic Representations and Initialisation Methods for the Multi-objective Shortest Path Problem on Multigraphs | en_US |
dc.type | Article | en_US |
dc.rights.holder | © 2021, The Author(s) | |
dc.identifier.doi | 10.1007/s42979-021-00512-z | |
pubs.issue | 3 | en_US |
pubs.notes | Not known | en_US |
pubs.publication-status | Published online | en_US |
pubs.volume | 2 | en_US |
dcterms.dateAccepted | 2021-02-08 | |
rioxxterms.funder | Default funder | en_US |
rioxxterms.identifier.project | Default project | en_US |
qmul.funder | TRANSIT: Towards a Robust Airport Decision Support System for Intelligent Taxiing::Engineering and Physical Sciences Research Council | en_US |
qmul.funder | TRANSIT: Towards a Robust Airport Decision Support System for Intelligent Taxiing::Engineering and Physical Sciences Research Council | en_US |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.