A Comparison of Genetic Representations for Multi-objective Shortest Path Problems on Multigraphs
Volume
12102 LNCS
Pagination
35 - 50
Publisher
ISBN-13
9783030436797
DOI
10.1007/978-3-030-43680-3_3
ISSN
0302-9743
Metadata
Show full item recordAbstract
The use of multi-graphs in modelling multi-objective transportation problems is gaining popularity, necessitating the consideration of the Multi-objective Shortest Path Problem (MSPP) on multigraphs. This problem is encountered in time-dependent vehicle routing, multimodal transportation planning and in optimising airport operations. This problem is more complex than the NP-hard simple graph MSPP, and thus approximate solution methods are needed to find a good representation of the true Pareto front in a given time budget. Evolutionary algorithms have been applied with success to the simple graph MSPP, however their performances on multigraph MSPP were not systematically investigated. To this aim, we extend the most popular genetic representations to the multigraph case and compare the achieved performances. We find that the priority based encodings outperform the direct ones with purely random initialisation. We further introduce a novel heuristic initialisation technique, that is generic enough for many representations, and that further improves the convergence speed and solution quality of the algorithms. The results are encouraging for later application to the time constrained multigraph MSPP.