基于遗传算法的K路径优化方法.pdf

: .
中国科技论文在线 http:/transportation planning and management; dynamic traffic guidance; route
30 optimization；K routes optimization

0 引言
随着机动车数量的不断增加，交通拥堵问题日益严重，特别是对于大型城市而言，交通
拥堵问题尤为突出，已成为各国交通管理部门共同面临的难题。动态交通引导系统（Dynamic
35 Traffic Guidance System，DTGS）通过对路径进行实时优化，指引出行者选择出行费用相对
较小的路径行驶，使其避开拥堵地点，从而实现调整路网交通分布的功能。
路径优化是将路段出行费用信息转化为路径推荐信息的关键环节。早期路径优化算法均
以单一路径优化为目标法[1-4]，后来发展为 K 路径算法[5-7]，以减少出行费用估计误差对最优
路径鲁棒性的影响和大量机动车同时涌向同一条路径导致的“拥堵漂移”现象。近年来，随
40 着道路网络复杂程度和交通状态时变程度的增加，提高 K 路径优化的效果与效率日益成为
研究的重点，以遗传算法为代表的启发式优化方法受到了广泛关注[8-11]。

基金项目：基金项目:高等学校博士学科点专项科研基金( 201**********)
作者简介：常安德(1984-),男,博士,智能交通
通信联系人：姜桂艳（1964-），女，教授，智能交通
- 1 -中国科技论文在线
目前，利用遗传算法求解 K 路径优化问题已取得不少成果，但在染色体编码方式、初
始种群构建、遗传算子等方面对于 K 路径的特点考虑不足，导致优化效果和效率还有较大。
的改进空间
45 本文将在已有成果的基础上，以进一步提高 K 路径优化的效果和效率为目标，通过对
编码方式、初始种群构建、遗传操作等环节进行改善，设计基于遗传算法的分层 K 路径优
化方法。
1 问题描述
遗传算法是由 Holland[12]于 1975 年提出的一种基于生物进化原理的搜索方法，包括遗
50 传编码、初始种群生成和遗传操作三个主要环节，已在优化研究领域得到广泛应用。路径优
化是典型的组合优化问题，备选路径随着节点数量的增长呈指数增加，遗传算法具备改造 K
路径优化算法的潜力。
动态 K 路径优化的目的在于快速找到起止节点间路权最小的 K 条路径，模型为：
nn
z = min ∑∑wa()()ij, a xaa ij ,
ij==11
（1）
⎧1,i = 1
nn⎪
st. . ∑∑x()aaij,,0−==− xaa() ki ⎨ ,2 i,3,,1"