9512.net
甜梦文库
当前位置:首页 >> >>

多约束最短路径模型与求解


第 25 卷第 1 期 2010 年 3月

湖南科技大学学报 (自然科学版 )

J ournal of Hunan Univers ity of S cience & Technology (Natural S cience Edition)

Vol.25 No.1 Mar. 2010

多约束最短路径模型与求解
2 胡耀民1,,刘伟铭2 (1.广州番禺职业技术学院 信息工程学院, 广东 广州 511483; 2.华南理工大学 土木与交通学院, 广东 广州 510640 )



要: 提供满足驾驶员多个心理期望的路径是导航系统该解决的关键问题, 其本质是资源约束最短路径问题, 属于 NP 难问

题, 无法使用传统的最短路径算法解决.提供了多约束路径规划的数学模型, 并使用了蚁群算法对其求解, 在算法中针对问题重新设 计了信息素更新规则和启发因子.实验证明算法具备良好的寻优能力, 能准确找出路网中满足多种属性约束的路径. 关键词: 多约束; 路径规划; 蚁群算法 中图分类号: TP311 文献标识码: A 文章编号: 1672- 9102 (2010 01- 0087- 04 )

驾驶员在使用导航系统进行路径规划时都希望 得到的路径最短以达到节省时间和费用, 但同时又希 望路径是容易驾驶、 安全性很高、 风景迷人的, 这就要 求路径满足多种路径质量的约束条件.这个问题的实质 就是在最短路径 (shortest path: ) SP 的基础上添加另外 的约束条件而构成带约束最短路径问题 (constrained shortest path: ) CSP .CSP 问题有多种形式, 如要求路径必 必须经过某条弧、 路径资源限制等, 须经过某个节点、 求解满足路径 文中使用的是资源约束的 CSP 定义 :
[1- 5]

多约束最短路径, 并在基本蚁群算法的基础上重新设 计信息素更新规则, 引入信息素更新算子, 动态增加 负荷约束的路径上信息素; 为提高算法效率, 算法中 改进能见度启发因子.

1

数学模型
多约束最短路径是求解路网中能够同时满足多

个路径属性约束 (如到达时间限制、 安全性限制、 距离 费用限制、 路的等级限制等) 且距离最短的路 , 限制、 径, 下面对多约束最短路径建模. 交叉口对应结点,两交叉口之间的路段对应弧, 路段的属性使用多元组来表示. 有向图满足了导航需 要的路网表达方法和存储结构应满足的要求, 如存储 量小, 便于路线优化算法对其进行操作, 充分考虑路 网作为网络的特殊性,能够表达路网要素及拓扑结 交叉口转向限制等交通管制 构, 能够表达单向交通、 措施, 能够表达路网的各种特殊结构, 要考虑结点权 重如何存储.路网有向图的可以表示为式 ) (1 :
! # # # # " # # # # $

上某种或某几种属性之和小于设定的上限值的最短 路径.众所周知, 问题的时间复杂度为 n (n 为节点 SP
2

个数 , ) 然而不幸的是 CSP 问题已经被证明为 NP 难问 题
[6- 7]

, 无法采用 dijstra 或 A* 来解决.对于 CSP 问题的

求解,也是学术界一直在探讨的问题, Handler, G.Y., Zang 中使用了 K- 最短路径和拉格朗日松弛的方式
[6]

但求解的时间 进行求解, 成为 CSP 问题的经典解法, 复杂度并不令人满意. 蚁群算法模拟生物界群体觅食 的能力, 能够在实际的路径搜索过程中对外界的影响 做出动态的响应, 是一种具有分布计算、 信息正反馈 和启发式搜索等特征的优化工具 , 因而在交通最优
[8]

NR= (V,) E , V={1, 3, …}, 2, 4, E={ u, Quν u, ( ν, ) ν∈V}. (1 )

路径选择中具有极大的可能性和适应性. 作者先给出 多约束路径的数学模型, 采用改进型蚁群算法来寻找

式中, uν 是道路的属性集用多元组表示, (长度、 Q 如 平

收稿日期: 2009-10-22 基金项目: 国家自然科学基金资助项目 (50978106 ) 通信作者: 胡耀民 (1975-) 男, , 湖南宁乡人, 博士生, 讲师, 主要从事智能交通及数据挖掘研究.E- mail: hymscut@163.com

87

均时速、 收费金额、 道路等级 等. ) 为了表示方便本文引入了其他一些符号定义: C: 路网有向图矩阵; o: 表示起始点; d: 表示终点; cij: 从节点 i 到节点 j 的弧,ij∈C; c dij: 路段 cij 的长度; fij: 路段 cij 的通行费金额 (不包括燃油耗费 , ) 按不 同车辆类型有不同数据; tij: 行驶在 cij 时每公里的耗时, 参考历史的平均时 段统计数据; sij: 发生在 cij 上的交通事故率, 参考历史的平均时 段统计数据. 在行车时间、 通行费、 安全性等方面施加了质量 约束的多约束最短路径数学模型: Min ) (G =min(ΣΣ ij dij , (X )
i∈V j∈V
0 0 0 0 0 0i∈V j∈V 0 0 0 0 0 0 0 i∈V j∈V 0 0 0 0 0 0 0 0 i∈V, j∈V 0 0 0 0 ij

蚁模拟真实蚂蚁行为来求解组合优化问题的方法.在 20 世纪 90 年代初期, 由意大利学者 Dorigo Macro 等首 蚂蚁在所经过的路径上留下 先提出[9].其原理在于[10- 13], 一种称为信息素的挥发性分泌物, 在觅食过程中蚂蚁 能够感知这种物质的存在及其强度, 并以此来指导己 的运动方向, 同时它们倾向于朝着信息素浓度高的方 向移动. 信息素浓度越高的路径,被选择的机会就越 多, 蚂蚁在其上留下的信息素就更多, 而更多的信息 素又能吸引更多的蚂蚁, 从而形成一种正反馈.通过这 种正反馈, 大部分的蚂蚁最终都会走上同一条最优路 径.为了求解多约束高质量路径模型 号模型) 要改 (I , 进解决 TSP 问题的基本蚁群算法[7]. 2.1 蚂蚁转移规则 设 为模拟蚂蚁的行为引入如下记号 [7]: m 是蚁群 中蚂蚁的数量,(i, …, 表示节点 i 和节点 j 之间的 dij j, n ) (2 ) τij ) 距离,(t 表示 t 时刻在节点 i 和节点 j 连线信息素.初 始时刻, 各条 路 径 上 信 息 素 的 浓 度 相 同 , τij ) 设 (0 = C 为常数) (C .蚂蚁 k (k=1, …, 在运动过程中, 2, n ) 根 k 据各条路径上的信息素的浓度决定转移方向,p ij(t ) 表示在 t 时刻蚂蚁 k 从节点 i 转移到节点 j 的概率; ij η 为能见度启发因子, 表示目标点的能见度; 为信息启 α 发因子, 表示轨迹的相对重要性, 反映了蚂蚁在运动 过程中所积累的信息在蚂蚁运动时所起的作用, 其值 越大,该蚂蚁越倾向于选择其它蚂蚁经过的路径, 蚂 蚁之间协作性越强; 为期望启发因子, β 表示能见度的 相对重要性, 反映了蚂蚁在运动过程中启发式因子在 (3 ) 蚂蚁选择路径中的受重视程度, 其值越大, 则该转移 概率越接近于贪心规则. 蚂蚁 k 从 i 节点转移至节点 j 转移规则按如下公式进行: 如果: ij ) 0, p (t <p 转移概率按式 ) (7 来求解, 其中 p0 是转移概率门槛值, (7 可加速算法收敛: 式 )
k k

(X ΣΣ dt )≤D ,
ij ij ij p

s.t.

(X ΣΣ f )<F ,
ij ij p

仪 (1-Xs )≥S ,
ij ij p

X ∈{0, i, . 1}, j∈V

如果 cij 弧在连接 o 和 d 的出行路径 p 上为 1, Xij, 否则为 0; 表示路径 p 上的距离: G G=ΣΣ ij dij . (X )
i∈V j∈V

到达时间约束: (X ΣΣ dt )≤D .
ij ij ij p i∈V j∈V

(4 )

安全性约束:

i∈V, j∈V

仪 (1-Xs )≥S .
ij ij p

(5 )

pij ) (t =

max τ(t ) j∈allowed , ( Σ 否则. ) , 0,
ij k

(7 )

通行费用约束: (X ΣΣ f )<F .
ij ij p i∈V j∈V

否则按式 ) (8 来求解: (6 ) pij ) (t =
k
0 0 0 0 0 0 0 0 0 0 0 0 0

[τ(t ]α [η(t ]β ij ) ij )

, j∈allowedk,
β

Σ[τ(t)][η(t)]
ij α ij j

(8 )

式中 Dp 为所选路径 p 上的允许时间开销上限,p 为所 S 选路径 p 上安全系数下限, p 为所选路径上的通行费 F 用上限.

0, . 否则

式 ) ηij 不能使用基本蚁群算法中的 1/dij, (8 中 因为这 样会导致蚂蚁贪图单步快捷而偏离行进方向. 为了改 进算法的收敛速度, ij 的取值按照式 ) η (9 规则: ηij= 1/dis , Σ 否则dis 不等于 0, 1, .
jd jd

2 算法设计
蚁群算法就是受蚂蚁觅食行为的启发, 以人工蚂 88

(9 )

式 ) disjd 为 j 点到目标点 d 的直线距离, (9 中 这样可以 启发蚂蚁以较高概率向最终目标点行进, 而不贪婪当 前最小一步. 2.2 信息素更新规则 为了诱导蚂蚁以较大几率向满足条件的路径靠 拢, 在所有蚂蚁都找到一条路径后 (也即一个循环结 束 后, ) 要对路网上信息素按照式 ) (10 更新: τ(t+1 = ) ij (1-ρ τ(t , ij 不是路径 p 上的边, ) ij ) C (10 ) ) ij ) C (1-ρ τ(t +ρ F, ij 是路径 p 上的边.

该蚂蚁所选路径上各边的信息素根据信息素更新规 则进行更新; 3 对所有蚂蚁重复第 2 步, ) ) 直到 m 只蚂蚁都完成 了第 2 步; ) 4 选择在本次循环中费用最小, ) 且满足时间限 制、 安全性限制的路由的蚂蚁, 然后使用全局更新规 则对该蚂蚁所选的路径各边上的信息素进行更新; 5 重复第 2 -4 步, ) ) ) 直到获得满意的结果.

3 算例
3.1 试验 为了验证算法的寻优能力,作者在 windows XP 下, 使用 Jbuilder2006 编程实现了算法, 对多约束最短 路径模型进行求解.图 1 是是仿真所用的网络拓扑, 假 定所仿真路网上边的两个方向的属性一致, 所以可以 用把有向图转换为无向图表示, 每一条无向边表示正 坐标值 (X, 反两条弧.顶点用编号带坐标的方法表示, Y 如果在真实地图中则换成 ) (经度, 纬度) 元组; 每条 边用一个四元组 (length, Speed, Tolls, Accident-rate ) 允许车速、 通行费 来表示, 其中元素分别表示距离、 事故发生统计概率. 用、

p 式 ) ρ 为全局信息素挥发因子, 为本轮循环找 (10 中 到的最优路径, 是一个函数, F 可表示为 F=-A F1+B F2+C F3+D F4. (11 ) F 式 ) F1 表示路径 p 上的距离; 2 表示路径能够 (11 中, F F 满足时间限制; 3 表示路径期望满足安全性限制; 4 表示路径期望满足通行费限制.F1, 2, 3, 4 可分别用 F F F 式 )式 )式 )式 ) (12 , (13 , (14 , (15 来表示: F1=ΣΣ ij dij . (X )
i∈V j∈V
Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ

(12 )

Dp- ΣΣ ij dij tij , Dp> ΣΣ ij dij tij 时, (X ) 当 (X ) i∈V j∈V i∈V j∈V F2= (13 ) 0, Dp< ΣΣ ij dij tij 时. 当 (X )
i∈V j∈V

F3=

Σ Σ Σ Σ Σ Σ Σ 仪 Σ Σ Σ Σ Σ Σ Σ

Sp-

i∈V, j∈V

当 仪 (1-Xs ), S > 仪 (1-Xs )时,
ij ij p ij ij i∈V, j∈V

(14 )

0, Sp< 当

i∈V, j∈V

仪 (1-Xs )时.
ij ij i∈V j∈V

F4=

仪 Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ

Fp-ΣΣ ij fij , Sp>ΣΣ ij fij 时, (X ) 当 (X )
i∈V j∈V

(15 )

0, Fp<ΣΣ ij fij 时. 当 (X )
i∈V j∈V

式 ) A, C, 是 4 个系数, (11 中, B, D 都是正实数, 分别表 示距离限制、 时间限制、 安全性限制、 通行费限制的相 对重要性,在如果算法中要强调哪个因素的限制, 就 可以把系数取一个较大正实数. 通过上述定义可知, 如果所选路径的总路径距离越短, 同时又满足时间限 安全性限制要求、 通行费限制要求, 则该路径 制要求、 上信息素相应要增加更多, 这就启发更多蚂蚁向这些 路径上的边汇聚. 多约束高质量路径的蚁群算法具体步骤如下: 1 初始化网络拓扑中各边的信息素; ) 2 放置 m 只蚂蚁在出发节点, ) 各蚂蚁通过转移规 则来选择各自路径,当某只成功完成路由选择之后, 试验 1: 让算法尝试规划 1-14 之间最优路径.规定 允许的事故发生率 路径质量: 允许的行车时间 Dp<4 h, (1-Sp <=10-5, ) 通行费用 <100.设置蚂蚁个数 m=10, 信 息素启发因子 α=1, 距离期望启发因子 β=5, 信息素初 值 =100,信息素挥发因子 ρ=0.55,系数 A=10, B=15, C=200, D=15, 迭代次数设定为 100 次.经过 300 次实 验得到如表 1 所示结果. 试验 2:为了考查算法在无法给出驾驶员期望质 量的路径时行为,作者尝试使程序规划 1-9 之间的路 径, 且规定路径质量: 允许的行车时间 Dp<3 h, 允许的 89

事故发生率 (1-Sp <=10-5, ) 通行费用 <5.设置蚂蚁个数 m=10, 信息启发因子 α=1, 期望启发因子 β=5, 信息素 信息素挥发因子 ρ=0.55, 系数 A=10, B=15, 初值 =100, C=200, D=15, 迭代次数设定为 100 次.经过 300 次实 验得到如表 2 所示结果.
表 1 路径规划结果表 1 Tab.1 Table of path planning results 1
路径请 求(o-d) 1- 14 通行 耗时 事故率 结果 所占比 所得路径 距离 费用 估计 (数量级) 次数 率 /% 1- 6- 7- 11- 14 80 300 3.265 10- 5 266 88.67 1- 6- 7- 12- 14 95 340 3.625 10- 5 34 11.33

必须对其进行修改,文中重新设计了信息素更新算 子,把路径质量约束添加到了信息素更新算子中, 改 进了能见度启发因子,从而增强了算法的正反馈作 在驾驶员 用, 提高了算法的收敛速度.仿真试验表明: 规定的路径质量能够满足时, 算法能够快速有效的求 得满足质量约束的最优路径或次优路径; 在驾驶员规 定的路径质量不能满足时, 算法能够求出最短路径或 次短路径. 这对导航系统的路径规划问题的研究有一 定的参考价值. 参考文献:
[1] [2] [3] [4] Aneja Y, Aggarwal V, K.Shortest chain subject to side conditions[J]. Nair 1983,(1 : 13 ) 295-302. Networks, Christofides N. An algorithm for the resource constrained Beasley J, shortest path problem[J]. Networks, 1989, (2 : 19 ) 379-394. Dumas Y, Solomon M, al.Time constrained routing and et Desrosiers J, 1995, ) 35-139. 8 : (1 scheduling[J]. Network Routing, Dumitrescu I, Boland N. The weight-constrained shortest path problem: preprocessing, scaling and dynamic programming algorithms with numerical comparisons[C]//International Symposium on Mathematical Programming(ISMP , ) Springer LNCS, 2000: 453-461. SellmannM.Cost-basedfilteringforshorterpathconstraints[M].Principles (CP , ) Springer LNCS, 2003: and Practice of Constraint Programming 679-693. Handler G Y, Zang I. A dual algorithm for the constrained shortest path 1980,(4 : 10 ) 293-310. problem[J]. Networks, Wang Z, Crowcroft J. Qualityof service routing for supporting multimedia applications [J]. IEEE Journal on Selected Areas in Communications, 1996,()1228-1234. 14 7 : Monekosso D, Barman S, al. A review of ant algorithms[J]. et Mullen R J, 2009,(2 : 36 ) 9608-9617. Expert Systems with Applications, Colorm A, Dorigo M, Miniezzo V. Distributed optimization by ant colonies[C]//Proceeding of the First European Conference on Artificial Life, Elsevier Publishing, 1991: -142. 134 Dorigo M, Cambardella L M.A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary 1997, ) 53-66. 1 : (1 Computation, Yang J H, X H.An ant colony optimization method for generalized Shi TSP problem[J].Progress in Natural Science, 2008, (1 : 18 ) 1417-1422. Robert Babus ka.Novel ant colony optimization Jelmer Marinus van Ast, approach to optimal control[J]. International Journal of Intelligent Computing and Cybernetics, 2009, 3 : 2 ) 414-434. ( Sara Morin, Caroline Gagné, Marc Gravel.Ant colonyoptimization with a specialized pheromone trail for the car-sequencing problem[J]. 2009, 197(1 : ) 1185-1191. European Journal of Operational Research,

表 2 路径规划结果表 2 Tab.2 Table of path planning results 2
路径请 求(o-d) 1- 9 所得路径 1- 4- 8- 9 1- 2- 3- 9 耗时 事故率 结果 所占比 通行 距离 估计 (数量级) 次数 率 /% 费用 20 220 4.167 10- 4 282 94 70 270 3.43 10- 5 18 6

3.2

结果分析 试验 1 可以看出, 发现最优解率为 88.67%; 发现
[5]

没有无效解, 说明改进后蚁群算法 次优解率为 11.3%, 具备良好的寻优能力. 从图中可以看出 1-14 的路由中 存在 1-4-8-11-14, 虽然通行费用只要 25, 距离 290, 但 耗时达到 5.55 h, 且事故率达到 10-4 数量级, 路径质量 没达到要求, 算法没选择它. 试验 2 可以看出, 当驾驶员给出的路径质量约束 不能满足时,算法还是能够规划出路线 1-4-8-9 和 1-2-3-9, 此时算法已经退化为求距离最短的路径规划 算法, 保证了路径规划结果, 体现了算法的鲁棒性.
[8] [9] [6] [7]

[10]

4 结论
针对导航系统中多约束路径规划问题, 引入蚁群 算法求解,为求解属于 NP- C 的带约束最短路径问题 提供了一个可行方案. 基本蚁群算法式是求解 TSP 问 题的,要使之能够应用于求解多约束最短路径问题,

[11] [12]

[13]

Multi- constrained shortest path model and solving
2 HU Yao- min1,, LIU Wei- ming2 (1.Guangzhou Panyu Polytechnic, Guangzhou 511483, China; 2.South China University of Technology, Guangzhou 510640, China )

Abstr act: How to provide route to meet the driver's multiple psychological expectations is the key problem of navigation system. The essence of this problem is resource constrained shortest path problem (RCSP ,which belongs to ) NP- C problems and can not be solved with the traditional shortest path algorithm. Multi- constrained shortest path mathematical model was presented,and ant colony algorithm was used to solve it. Aimed at the problem,pheromone update rule and heuristic factor were redesigned in the algorithm. Experiments show that the improved optimization algorithm have a good ability to accurately find multi- constrained shortest path in road network. Key wor ds: multi- constrained; route plan; improved ant colony algorithm 90


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图