Multi-objective alpha-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA)
Multi-objective alpha-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA)
复制标题
DOI：
10.1016/j.eswa.2010.07.064
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
Z. Ji;Y. Kim;A. Chen
中科院分区：
文献类型：
--
作者：
Z. Ji;Y. Kim;A. Chen
在这项研究中，我们提出了一种新的基于模拟的多目标遗传算法（SMOGA）的方法来找到一个组合的可靠的非主导（帕累托）路径，一组路径是同样好或更好的至少在一个目标空间相比，所有其他路径，在随机网络，同时考虑链路旅行时间的不确定性和相关性之间的链路旅行时间。我们的SMOGA模型由蒙特卡洛模拟，遗传算法，和帕累托过滤器模块找到一组帕累托路径，最大限度地减少旅行时间预算所需的旅行时间可靠性预先确定的用户的多个要求。为了我们的目的，阿尔法（和贝塔）可靠的路径寻找问题，首先制定为一个变种的机会约束多目标规划（CCMOP）模型。然后利用仿真模块对路段行程时间相关的随机网络进行仿真，并利用遗传算法和Pareto过滤模块在组合解空间中有效地搜索满足多种可靠性要求的Pareto路径。在芝加哥Sketch网络上的数值结果表明，我们精心设计的遗传表示（可变长度染色体和两种初始种群生成方式）和遗传算子（交叉和变异算子）有效地探索了解空间，并确保了后代路径的可行性和多样性。此外，我们在同一网络上的帕累托路径的图形表示表明，不考虑路段旅行时间分布之间的相关性的简化模型可能会发现帕累托路径在旅行时间预算中存在显着偏差，因此为旅行者提供次优路径。
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.