Paper Info
Title
Uncertain programming models for multi-objective shortest path problem with uncertain parameters
Abstract
The shortest path problem is considered as one of the essential problems in network optimization with a wide range of real-world applications. Modelling such real-world applications involves various indeterminate phenomena which can be estimated through human beliefs. The uncertainty theory proposed by Liu (Uncertain theory, 2nd edn., Springer, Berlin, 2007) is widely regarded as a legitimate tool to deal with such uncertainty. This paper presents an uncertain multi-objective shortest path problem (UMSPP) for a weighted connected directed graph (WCDG), where every edge weight is associated with two uncertain parameters: cost and time. These parameters are represented as uncertain variables. Here, we have formulated the expected value model and chance-constrained model of the proposed UMSPP, and the corresponding deterministic transformation of these models is also presented. Subsequently, the deterministic models are solved with a classical multi-objective solution method, namely the global criterion method. Furthermore, two multi-objective genetic algorithms (MOGAs): nondominated sorting genetic algorithm II (NSGA-II) and multi-objective cross-generational elitist selection, heterogeneous recombination and cataclysmic mutation (MOCHC), are employed to solve these models. A suitable example is provided to illustrate the proposed model. Finally, the performance of MOGAs is compared for five randomly generated instances of UMSPP.
Year
DOI
Venue
2020
10.1007/s00500-019-04423-3
Soft Computing
Keywords
DocType
Volume
Uncertain multi-objective shortest path problem, Expected value model, Chance-constrained model, NSGA-II, MOCHC
Journal
24
Issue
ISSN
Citations 
12
1432-7643
1
PageRank 
References 
Authors
0.35
0
4
Name
Order
Citations
PageRank
Saibal Majumder110.35
Mohuya B. Kar2254.53
Samarjit Kar360863.41
Tandra Pal48512.23