您好,欢迎来到小侦探旅游网。
搜索
您的当前位置:首页运输路径优化蚁群算法问题研究

运输路径优化蚁群算法问题研究

来源:小侦探旅游网
文章编号:1003—1421(2010)09--0068—05 中图分类号:0229;Ul16.2 文献标识码:A 运输路径优化蚁群算法问题研究 Research on ant colony atg0dthm for transport route optimization 陈钢铁,帅斌 CHEN Gans"-tie,SHUAI Bin (西南交通大学交通运输学院,四川成都 6f 0051) (School of Traffic and Transportation,Southwest Jiaotong University,Chengdu,Sichuan 6 1 003 1,China) Abstract:First.the route optimization model based on 摘要:对于某一特定源点和目的地之间 risk and taking account of cost and time—varying conditions 的车辆运输调度问题,建立基于风险、考 was established for the train traffic dispatching problems between certain origin and destination.In this paper, 虑成本和时变条件下的路径优化模型,采 pheromone update strategy of ant colony algorithm is used, 用蚁群算法的信息素更新策略,使边上残 so that the margin residual pheromone could accurately 留信息素能够正确反映时变网络中边上权 reflect the change of the margin value in time—varying 值的变化,并结合遗传算法,采取最优个 network.Then,by combining with Genetic algorithms, the ant colony formed after each traversal solution as the 体交叉策略将蚁群每次遍历后形成的解作 initial species in terms of single—point crossover,in order 为初始群种进行单点交叉计算,以避免陷 to avoid getting in local optimal solution and improve the 入局部最优解,提高算法的收敛性。通过 convergence of the algorithm.The validity of the algorithm 算例分析验证算法的有效性。 is proved by the example. 关键词:时变网络;路径优化;蚁群算法 Key words:Time-varying Network;Route Optimization; Ant Colony Algorithm 一 第32卷第9期 运输路径优化蚁群算法问题研究陈钢铁等  f—N;E一(g )为弧集, 石雨时间窗的车辆路径问题(Vehic e R。u ing 顶点集,f是众多车辆路径问题(Vechicle Routing Problem, = 。P( )表 Problem with Hard Time Window.VRPHTW) 示顶点v 的前点集;s(i)表示顶点v 的后点集; 表 示完成运输的总时间上界;c表示完成运输的总费 VRP)中的一种。该问题既考虑车辆容量约束,也 用上界; 表示在顶点v,的等待时间上界; 表示 考虑客户对货物送达的时间要求,并且每个客户 在顶点v 等待的单位时间风险;c 表示在顶点v 等 都要求将货物在指定的时间窗内送达,既不能提 待的单位时间费用;a 表示在顶点v 的到达时间; 前,也不能延后。VRPHTW问题的求解方法分为 『j,表示弧e0.的距离;w 表示在顶点v 的等待时间; 精确算法和启发式方法。精确算法由于引入严格的 c ( 表示t时刻进入弧P 的单位运费;t ,( 表示t时 数学方法,无法避免指数爆炸问题,只能有效求 刻进入弧P 所需的时间; ,(f)===1表示t时刻进入 解小规模VRPHTW问题 之]。而VRPHTw问题是强 弧e , ,( )一0表示tN刻没有进入弧e 。 NP(Nonlinear Programming)难题,只能寻找近似 2.2建立模型 算法。因此,构造高质量的启发式算法显得尤其重 主要有遗传算法 、禁忌搜索算法 ]。对基于风 险考虑成本和时变条件下的问题建立模型,采用蚁 选取顶点1为源点,Ⅳ为目的地,建立混合整 要。目前,用于求解VRPHTWI'if]题的启发式算法 数规划: min∑∑r ( × ( +∑ xw …1 ∈E ∈V (1) (2) 群算法的信息素更新策略,使边上残留信息素能够 正确反映时变网络中边上权值的变化,结合蚁群算 法和遗传算法,将蚁群每次遍历后形成的解作为初 始群种进行单点交叉计算,可以避免陷入局部最优 s.t. ∑∑ F 1 ∈ I) (f)一1 ∑∑ ,(,)一∑∑ ( ===0 i=1,2,…,JV一1 (3) 解,提高算法的收敛性。 圭∑ (f)一1 1 问题描述 交通网络中特定源点与目的地之间的车辆运 输调度问题的运输风险依赖于时间,而且主要取 决于入弧的时间,但当车辆进入某一弧时,风险 由进入弧的时间决定。为操作方便,假定时间是 F1 f∈,(Ⅳ) (4) i=1,…,Ⅳ一1 =2,…,Ⅳ (5) (6) ∑∑ ,( ≤1 F1}E ' 1 ic尸(f1 ∑∑O+ ( )× ( 一日,一0 ∑∑tx ( 一日,一w,一0 t-1/eS(i) 一1,…,Ⅳ_l(7) 离散化的小单位(如1 h或更小的10 min)。允许 ∑c ( X (f)X1u+∑c ,XW ≤C Fl e ∈F f∈P (8) (9) (1o) 车辆在每一顶点停靠等待,但不允许顶点间的停 靠,其中考虑了等待时间和驾驶时间的不同 情况,但考虑到允许等待和在现实中长途运输中 多个司机随车的现象,研究只考虑等待时间 的情况,即顶点上的等待时间必须在0和上界之 aj一0,aⅣ≤T 0≤wf≤ ,a ≥0 i 1,2,…,Ⅳ (f)一0或1, ∈ f—l,2,‘。。, (11) 间。在此基础上,考虑企业的实际运作情况,研 其中:约束条件(2)~(4)是留守恒的; 5)保证只有1条路径;约束条件(6)~(7) 究基于风险考虑成本和时变条件下物品运输的路 约束条件(径动态优化问题,以及在选定路径顶点上决定的 保证途经弧e 时,弧e 的后节点到达时间为前节 出发和等待时间的综合问题。 点的到达时间、等待时间和弧的旅行时间之和; 约束条件(8)满足在一定成本下进行运输活动的条 2模型和算法 2.1 定义变量 件;约束条件(9)定义了整个运输活动的开始时间 和最迟结束时间;约束条件(10)~【11)表示变量的取 G一( ,  表示交通网络图,其中, 一( )为 值范围。圈 运输路径优化蚁群算法问题研究陈钢铁等 2.3模型算法 Algorithm,ACO)是新的仿生类进化算法,也是新 在公式㈦中,△Jr 表示第k只蚂蚁在本次循环 般设置周游次数计数器 ,当达到设定值时  Dorigo首先提出的蚁群算法(Ant COlony 中留在路径卜,上的信息量。一的启发式算法。该算法模仿蚂蚁觅食行为,按照启 结束,最短路径为: 发式思想,通过外激素的诱发作用逐渐收敛到问题 的全局最优解。 假设m为蚁群中蚂蚁的数量,d ,(i,J— L i 一min( In(,1) ,一1,2,…,J7v (16j 2.4最优个体交叉策略 基本的蚁群算法容易过早收敛,使搜索陷入局 l,2,…,,z)表示节点i和节点./之间的距离;r ,( ) 部最优解。为了避免这一情况,结合遗传算法,将 表示t时刻在节点i、J之间的径路f一,上残留的 蚁群算法每次遍历后形成的解作为初始群种,然后 信息量。在初始时刻,各条路径上信息量相等, 扫描双亲,检查双亲是否有相同的基因。在所有相 设 (0)=C(c为常数),蚂蚁k(足一1,2,…, )在 同基因对中,挑选出单点交叉后得到的后代最优基 运动过程中,根据各条路径上的信息量决定转移 因对进行单点交叉。采用这种方法进行交叉,不会 方向, ( )表示在t时刻蚂蚁k由节点i转移到节 产生非可行解,同时使交叉操作具有方向性,不仅 能够加速收敛到全局最优解,而且能在一定程度上 点,的概率: (明“f叩 p ( )= 避免陷入局部最优解。 j睡Uk (121 X 2.5改进的蚁群算法步骤 根据以上改进策略,给出适合于时变网络的蚁 群算法TDNACO,其算法步骤如下。 ∑[ (明 [ 仉 0 步骤1:当算法开始运行时,初始化每条边上 式中: 为先验知识或称为能见度,在最优路径问 的信息量 ,(0)一C(C为常数),同时设置迭代次数。 题中是节点辟专移到节点,的启发信息,一般取叩 === .步骤2:将 只蚂蚁放在初始节点S,计算蚂 . 1/ ;o【为路径 _,上残留信息的重要程度; 为启 蚁转移概率: 发信息的重要程度;Uk(k=1,2,…, )是禁忌表, 用以记录蚂蚁k当前所走过的节点,下一步不再允 【 (,)] [ J∈ 许选择,集合 随着进化过程作动态调整。 经过 个时刻,所有蚂蚁都完成了1次周游, 其本次周游的禁忌表将满,此时应清空,将当前蚂 p (力 , 0 否则 蚁所在节点置入 ,准备下一次周游。这时,计算 式中: 每只蚂蚁所走过的路径厶,并保存最优路径: Lkmi 一min(Lk) 七一1,2,…,/7/ (后一1,2,…, )用以记录蚂蚁k当前所走 一{与i相连的节点一 }; 过的节点; (13) 叩 一g (f)~,g (t)为t时刻出发时边(v ,vj)的行走 随着时间的推移,以前留下的信息逐渐消失, 时间; 、 体现信息素和启发信息对蚂蚁决策。 步骤3:如果,是目的节点,保存路径及其花 用参数1一p表示信息消失程度,蚂蚁完成1次循环 以后,路径上的信息量要根据公式(14)作调整: ru(t+1)一(1--p)ro.(t)+ △ (14) 费时间 ;如果,不是目的节点,继续查找下一个 节点,转到步骤2。 步骤4:当m只蚂蚁搜索完后,则求得m条路 △ 一盏△ 时,△ 一 (15) 径,全局更新边上的信息量: ru(t+1)一[(1 p) (f)+pro.]2 (18) 当k只蚂蚁在时刻 和,+1之间经过路径卜 式中:P表示信息素的消失程度,0<p<1。 一 ;否则,ArO.:0。其中,9为常数; 表示第k只蚂蚁在本次循环中走过的路径长度。 d/ (19) _ 9期 运输路径优化蚁群算法问题研究陈钢铁等 式中:岛o 和gfn/ 分别表示 上的原行走时间及 择相应节点进行了分析。 更新后的行走时间。 △ 一 A 七=l 盯 当k只蚂蚁在时刻t和t+l之间经过路径i一, 时,△ 一Q/L ;否则,△r,,一0。其中,Q为常数; 厶为蚂蚁k从出发点到目的地所经历的时间。 图1运输网络 在公式【20)中,△ 是蚂蚁k在边(1, , ,)上的信 表1 各条有向边在不同时间条件下的运输时间、成本和风险 息素增量。 及相应概率 步骤5:扫描得到 个解,进行交叉计算。杂 目标值 交后的路径时间若小于杂交前的路径时间,则用新 有向边 0,12 12,24 路径取代原路径,同时更新相应路径上每条边的信 息素;否则,不进行更新。 时间 成本 风险 时间 成本 风险 步骤6:在m个解中求取局部最优解。 1.0/0.7 5/0.4 5/0.5 5.0/0.8 5/0.6 10/0.6 (1,2) 厶 i 一min(L ) 一1,2,…,m (21) 1.5/0.3 l0/0.6 8/0.5 7.0/0.2 15/0.4 35/0.2 步骤7:到当前迭代次数为止,将建立的所有 1.o/0.7 10/0.6 15/0.3 1.0/1 l0/0.6 25,0.3 局部最优解中最小值的解作为当前迭代次数的全局 (1,3) 1.5/0.3 l2/0.4 18/0.7 15/0.4 30/0.7 最优解。 1/0.6 l0/0.5 8/0.6 0.5/1 15/1 8/1 L i ===min(L in(/)) ,=1,2,…,当前迭代 (2,3) 次数 (22) 1.2/0.4 15/0.5 14/0.4 步骤8:如果到达设置的迭代次数,则退出程 2.5/0.3 55/0.3 20/0.6 3/0.5 60/0.4 2o/0.5 序;否则,迭代次数加1,转步骤2。 (2,4) 3/0.3 50/0.2 25/0.4 3.5/0.5 75/0.6 35/0.5 3算例分析 3.5/0.4 65/0.5 2.o/0.5 20/0.6 50/0.5 3.5/0.5 30/0.6 60/0.3 为验证算法,建立4个节点的拓扑网络,采 用TDNACO算法进行计算。为模拟实际时变网络 (3,4) 2.5/0.5 25/0.4 65/0.5 4/0.5 25/0.4 75,0.4 中权值的变化情况,在计算过程根据设定的权值变 85/0.3 化频率和权值变化系数用程序来随机挑选。设3只 蚂蚁同时进行计算,取系数oc一2, 一2,P一0.3, 表2违反规定等待惩罚和违规惩罚 一1,用TDNACO算法进行计算。 惩罚 成本 风险 运输网络如图1所示。表1给出在运输过程 等待惩罚 5 2 中,各节点之间不同时间条件下,运输过程中的 违规惩罚 10 5 运输成本、运输时间和风险。节点2和节点3的 时间范围为12:OO一14:00和17:O0—19:00。 表3各个状态和阶段 阶段 表2给出到达某节点时违反规定时,给予的等待惩 O 1 2 3 罚和违反惩罚。假设车辆可以在0:00从起始点出 l 2 3 4 发,并每隔2 h整点出发1次,在24:00之前到达 状态 3 4 终点的最优路径。在表3中,分别对0~3阶段,选 第卷第第32 9期—一 一 运输路径优化蚁群算法问题研究陈钢铁等 ping,CHAI Yueting,CAO Rui.Improved 计算结果为仅当出发时间在16:00和18:O0 【3]ZHANG Li时,在硬性规定的条件下才能通行,此时存在可行 路径为l一3—4。 genetica 1 gorithm for vehicle routing problem with time windows[JJ.Computer Integrated Manufacturing Systems, 2002,8(6):451—454. 4结束语 在基于风险考虑成本和时变的运输路径优化 过程中,采用时变网络中蚁群算法的信息素更新策 略,正确反映时变条件下的成本和风险的变化。同 时,改进传统蚁群算法的相邻节点选择策略,使蚂 蚁只需计算与当前节点存在直接路径的节点转移概 率,从而降低计算量。将蚁群算法和遗传算法结 [4]ZHANG Jiong,LANG Maoxiang.The tabu search algorithm of distribution vehicle scheduling problem with time windows[J].Journal of Northern Jiaotong University, 2004,28(2):103-106. [5】孟庆春,张江华.基于风险的考虑成本和允许等待的车辆 运输调度问题研究[J].中国管理科学,2009(6):87—91. [6】肖美华,王命延.基于遗传算法和模拟退火算法的布局问 题研究[J].计算机工程与应用,2003,39(36):70—72. 合,能够避免运算陷入局部最优解,提高算法收敛 速度。 [7】高经纬,张 煦.求解TSPIhq题的遗传算法实现[J].计算机 时代,2004(2):19-21. [8李大卫,王8]参考文献: [1】Balinski M,Quandt R.On an integer program for a delivery 莉,王梦光.遗传算法在有时间窗车辆路径 问题上的应用[J】.系统工程理论与实践,1999(8):6-69. problem[J].Operation Research,1 962,1 0(2):300—304. [2]Berger J,Barkaoui M.A parallel hybrid genetic algorithm for 收稿日期:2010—03—29 修订日期:2010-06—2l the vehicle routing problem with time windows[J].Computers andOperationsResearch,2004,31(12):2 037—2053. 责任编辑:付建飞 (上接第64页) 利用方案进行科学论证外,还应严格按规定的权限 管理信息系统建设规划列入铁路发展规划,设计 进行审批,严格按经批准的开发利用方案实施,用 和制定铁路用地管理信息系统建设发展规划,确 严格的制度来维护铁路的整体利益,以保证铁路用 定发展的总体目标和阶段目标,明确建设任务和 地效益的最大化。 责任分工,制定促进铁路用地管理信息化发展的 和保障措施,提高铁路用地管理信息的利用 效率。 3结束语 随着和谐铁路建设的不断深入和发展,铁路用 (5)促进铁路用地的开发利用。铁路用地具 地管理作为一项重要的基础性工作,在铁路改革发 有较强的区位优势,蕴含较大的经济效益,依法开 展中发挥着越来越大的作用。因此,必须加强铁路 发、合理利用铁路用地势在必行。铁路用地的开发 用地管理工作,努力为铁路运输生产服务,为我国 利用要以持续发展为基本出发点,通过优化资源配 铁路事业的发展创造必要条件。 置,盘活铁路用地资产。通过铁路用地的开发使铁 路用地布局趋于合理,用途结构不断优化,利用水 平明显提高,铁路安全生产条件和沿线生态环境明 收稿日期:2010-08-23 责任编辑:金颖 显改善,铁路用地对铁路可持续发展的保障能力明 显增强。由于铁路用地的特殊性、用途的规定性、 安全的关联性和规划的确定性,对于铁路用地的开 发利用必须严格开发利用程序,除对铁路用地开发 一 9期 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- xiaozhentang.com 版权所有 湘ICP备2023022495号-4

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务