双层智能优化算法求解时变网络最短路径问题

摘要

边成本为一般函数的时变网络最短路径问题(TDSP),已被证明不存在多项式时间算法.同时智能优化算法被广泛地用于求解该类问题,但多数没有考虑节点的可等待约束.提出了求解TDSP 问题的双层智能优化算法,内层遗传算法优化每条可行路径的各节点离开时间,外层蚁群算法优化构建的路径,最终搜索到从起始点到终点的最短时间路径.实验结果表明:双层智能优化算法能快速寻优,并且收敛速度和最优路径较同类算法更优秀.%It is proven there is no polynomial time algorithm for the time-dependent shortest path (TDSP)occurring when marginal cost is a general function.Also,intelligent optimization algorithms are extensively used in solving such problems,but most of them have not considered the waiting con-straint of the nodes.This paper brings out the two-layer intelligent optimization to solve out TDSP problem:at internal layer,optimize the leaving time of each node of each feasible path with genetical-gorithm;at external layer,optimize the built path with ant colony algorithm.In this way,the shor-test time path from a starting point to an end point is obtained.The experimental result shows,the two-level intelligent optimization algorithm is able to identify the optimization and the convergence speed with optimized path is better than other algorithms.