An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems

This paper investigates an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP). By encoding a path as an OST, in contrast with the existing evolutionary algorithms (EA) for shortest path problem (SPP), the designed GA provides a “search from a paths set to another paths set” mutation mechanism such that both of its local search and global search capabilities are greatly improved. Because the possibility to find a feasible path in a paths set is usually larger than that of only one path is feasible, the designed GA has more predominance for solving MCSPPs. Some computational tests are presented and the test results are compared with those obtained by a recent EA of which the encoding approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for shortest path problems. The test results indicate that the new algorithm is available for both of MSPP and MCSPP.

The proposed PS-ABC algorithm inherits the bright sides of other relevant methods, and simultaneously has the abilities of prediction and selection. Results show that PS-ABC has an extremely fast convergence speed like I-ABC and good search ability.Figure optionsDownload as PowerPoint slideHighlights
► We design an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (SPP).
► By encoding a path as an OST, the designed GA provides a search from a paths set to another paths set ± mutation mechanism such that both of its local search and global search capabilities are greatly improved.
► The designed GA has more predominance for solving multi-criteria constrained SPPs as well as the non-additive SPPs.