文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 蚁群优化算法在物流配送车辆路径问题中的应用研究
侵权投诉

蚁群优化算法在物流配送车辆路径问题中的应用研究

车辆路径问题(VRP)是一类物流配送领域具有广泛应用的组合优化问题,属于NP难题。一种改进的蚁群优化算法可以用于求解VRP。实验结果表明,采用蚁群优化算法能有效求解VRP问题。

第 l卷 6期 l第

席先杰:蚁群优化算法在物流配送车辆路径问题中的应用研究

21年 1 01 2月

示)有 (,,, )客户需要配送货物, 12… n个每个客

f['( ) Z t] i i pk:

() p t]

.

厂

,

户需要配送的货物量是 ( i=12 3…, )客户,,, n,点 i的距离为d (,到 =12…, )设实际所需,, n,要的车辆数为,每辆配送车的配送货物容量是 Q, n为第 k 辆车所经过的客户点总数,用集合 R =

{[ ) ) J ( 1]] k7 ) t r he w

其中,为蚂蚁 k当前状态下尚未访问过的客 户位点的集合,该集合在系统进行过程中会不断地 和配送货物所用时间的相对比重。随着时间的推移,

{ 1 i n) r 0≤≤来表示第 k辆车所经过的客户动态调整;参数 a分别用来控制信息素轨迹强度, 点,其中,表示第 k r辆车经过的第 i个客户点,如果经过则 r为 1否则为 0 r表示配货中心, ,,。得到的数学模型如下: miz n 1= m () 1

信息素量将逐渐挥发。用参数 19 -表示信息素浓度/强度的降低程度,经过 h个时刻后,蚁群会完成一次配送移动过程,此时客户点 i,线路上的信息素浓度强度根据下式进行调整:

m z=∑ J=0∑ dr i: i=0∑=1 i n j k

() 2 () 3 () 4

r(+h=P . t+ A: t ) z() r 。 f :

() 8

st∑ X≤Q s,…, .. ,=1,舰 2 i=0

式 (),表示第 k只蚂蚁在本次配送过程 8中 Ar

∑r=1i,…,,=1, n 2 k= l

中对客户点 i,之间线路上信息素浓度强度的增量,其定义如下: f , Q/如果蚂蚁在本次配送中经过了

∑ k=0

=

,

=

1 2…,

5= 1 2,,,, k;,… m

() 5 () 6

A={ r t

路径 i,

() 9

o否则, = ,= 1,…, s= 1,…, i 2, k; 2, m

洒∑ k=0

式( ) Q表示信息素浓度强度是一定常数; 9中,

其中, ()目标函数最小化车辆数,式 1式 () 2 z是求得最短的总路径长度, 3为车辆容量式( )限制,保证每条路径上各客户点的货物需求总量和必须小于车辆容载能力, ()式 4为每个客户的运输任务仅由一辆车完成; ()式 5和式 ( )限制了每个客 6户点必须有一辆车完成且只能由一辆车来完成,且 只能被访问一次。 2 3配送车辆路径规划问题 .

L ::= t表示蚂蚁k在本次配送中完成送货单中 所有货物的客户位点花费的时间。文对信息素浓本

度强度进行调整时利用整体信息而不是局部信息, 因此,求解车辆路径规化问题时具有较好性能。 2 4算法描述 .基本蚁群算法在每次进化时,只能固定地选择其中一条路径,若在每一个点上都放置一只蚂蚁,必

配送车辆路径规划就是对含有个配送目的地

的货单,寻找一条最佳的货物配送路径,通过合理调 度配送车辆和货物单,使完成一次配所送花费的成本最小。本文利用基本蚁群算法并对其进行改进, 以求解货物配送过程中的最短路径。求解过程如下,设定蚁群中的蚂蚁数量为 m, t表示 t刻在 i r ()时, 线路上残留的信息素量,表示的实际意义为完成所客户点 i的货物配送后,选择客户点配送货物的

信息素的强度。系统初始状态时,各个客户点上的信息素量相等, 0 r ( )= r,,t是能见度因数,。 () 在

然使算法复杂度增加,搜索时间变长。对于车辆路径规化问题,针对问题本身的特点,由于每次配送操作时车辆都是从物流中心点开始配送,且完成配送任务后又回到配送中心点,因此,文对基本蚁群算法本进行改进。次配送进行开始时,每在起始节点即配送客户点上放置 m只蚂蚁。作业开始后,只蚂蚁随 m机地选择下一个配送客户点。此方法有效减小了算法复杂度,缩短了搜索时间。 算法具体步骤如下: () 1系统初始化, t=0配送次数 n r c=0每条边,即客户点 i到客户

点线路上的 ()= r,△ 0。且 r 0= (,, .)tb= (忌表为空 ), 0 1…,, u 禁 n a。 .

=

本文中定义为(, ) 7表示从客户点 i 1 ,1 到客户点 送货用时。蚂蚁 k k=12…,在运动过程中, (,, m) 根据送货线路上信息素的强度来决定转移方向, t 义为

() m只蚂蚁放置在物流中心初始位置处, 2将将

第 k只蚂蚁所在的客户点号从中删除,并加入到 t u中, a k开始循环搜索路径, b根据式() 7中概率 p选择 下一个要送货的客户点并记录该客户点编号,将刚选 (下转 3 5页 )

时刻蚂蚁k从客户点到客户点的转移概率p定: 择的客户点编号从中删除,并加入到 t u中。 a b 31

蚁群优化算法在物流配送车辆路径问题中的应用研究

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email