Multi-objective α-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA)

Zhaowang Ji, Yong Seog Kim, Anthony Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

56 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1515-1528
Number of pages14
JournalExpert Systems with Applications
Volume38
Issue number3
DOIs
Publication statusPublished - 1 Mar 2011
Externally publishedYes

Keywords

  • Chance constrained model
  • Genetic algorithm
  • Multi-objective path finding
  • Pareto paths
  • Travel time reliability

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Engineering(all)

Cite this