Paper Info
Title
Multi-objective α-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA)
Abstract
In this study, we propose a new simulation-based multi-objective genetic algorithm (SMOGA) approach to find a portfolio of reliable nondominant (Pareto) paths, a set of paths that is equally good or better at least in one objective space compared to all other paths, in stochastic networks while considering link travel time uncertainties and correlations among link travel times. Our SMOGA model consists of a Monte Carlo simulation, a genetic algorithm, and a Pareto filter module to find a set of Pareto paths that minimize the travel time budgets required to satisfy multiple requirements of travel time reliability pre-determined by users. For our purposes, an alpha (and beta) reliable path finding problem is first formulated as a variant of Chance Constrained Multi-objective Programming (CCMOP) model. Then the simulation module is used to simulate stochastic networks with correlations among link travel times, and genetic algorithm and Pareto filter module are used to effectively search for Pareto paths that satisfy multiple reliability requirements in combinatorial solution space. Numerical results on the Chicago Sketch network demonstrate that our carefully designed genetic representation (a variable-length chromosome and two ways of generating initial population) and genetic operators (a crossover and a mutation operator) effectively explore solution space and ensure the feasibility and diversity of offspring paths. Further, our graphical representations of Pareto paths on the same network indicate that simplified models that do not consider correlations among link travel time distributions may find Pareto paths with a significant bias in travel time budgets and hence provide travelers sub-optimal paths.
Year
DOI
Venue
2011
10.1016/j.eswa.2010.07.064
Expert Systems with Applications: An International Journal
Keywords
Field
DocType
stochastic network,pareto filter module,genetic algorithm,link travel time,multi-objective path finding,reliable path finding,pareto paths,travel time reliability,pareto path,simulation-based multi-objective genetic algorithm,genetic operator,travel time budget,chance constrained model,correlated link cost,link travel time distribution,link travel time uncertainty,path finding,genetics,monte carlo simulation,satisfiability
Population,Monte Carlo method,Mathematical optimization,Crossover,Computer science,Genetic representation,Artificial intelligence,Operator (computer programming),Genetic algorithm,Machine learning,Pareto principle,Sketch
Journal
Volume
Issue
ISSN
38
3
Expert Systems With Applications
Citations 
PageRank 
References 
9
0.89
17
Authors
3
Name
Order
Citations
PageRank
Zhaowang Ji1161.47
Yong Seog Kim211211.11
Anthony Chen320918.25