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.
Licence information
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/.
Attribution 3.0 United States