Enhanced Non-Dominated Sorting Genetic Algorithms for Uncertain Multi-Objective Shortest Path Problem: Application to Fire Prevention Services

This paper examines a multi-objective shortest path problem (MOSPP) under an uncertain environment for a directed graph. The zigzag uncertain variables are used to represent the uncertain parameters. The expected and optimistic value models of uncertain MOSPP (UMOSPP) have been formulated, and their correlated deterministic transformation is also provided. Moreover, using three existing multi-objective genetic algorithms (MOGAs) and two proposed aspiration level (AL) based algorithms: AL-based non-dominated sorting genetic algorithm (NSGA)-II, and AL-based NSGA-III, the deterministic models are solved. As an application, a mock fire drill problem has been considered in the context of UMOSPP. A comparison is presented between the proposed methods and several MOGAs. A sensitivity analysis of objective functions has also been carried out regarding the shape parameter and aspiration level. Finally, to show the effectiveness of the proposed methods, the performance measure coverage is calculated.