tsp 蚁群算法 数学建模
第11卷#第6期席先杰:蚁群优化算法在物流配送车辆路径问题中的应用研究2011年12月
B
示)有n(1,2,,,n)个客户需要配送货物,每个客户需要配送的货物量是Xi(i=1,2,3,,,n),客户点i到j的距离为dij(i,j=1,2,,,n),设实际所需要的车辆数为S,每辆配送车的配送货物容量是Q,nk为第k辆车所经过的客户点总数,用集合Rk=rki0[i[nk来表示第k辆车所经过的客户点,其中,rki表示第k辆车经过的第i个客户点,如果经过则rki为1,否则为0,rk0表示配货中心,得到的数学模型如下:
minz1=m
i=0j=0s=1
p=
kij
uIJ
k
Sij(t)Siu(t)
A
Gij(t)Giu(t)
,jIJk
(7)
0,otherwise
其中,Jk为蚂蚁k当前状态下尚未访问过的客户位点的集合,该集合在系统进行过程中会不断地动态调整;参数A,B分别用来控制信息素轨迹强度和配送货物所用时间的相对比重。随着时间的推移,信息素量将逐渐挥发。用参数1-Q表示信息素浓度强度的降低程度,经过h个时刻后,蚁群会完成一次配送移动过程,此时客户点i,j线路上的信息素浓度强度根据下式进行调整:
Sij(t+h)=Q#Sij(t)+
k
k=1
(1)
m
minz2= s.t.
ijs
EEE
kk
dijrijs(2)(3)(4)(5)(6)
E
m
$Sij
k
(8)
k=1
Er
i=0K
EXr
iik
k
is
[Q,s=1,2,,,m
式(8)中,$Sij表示第k只蚂蚁在本次配送过程中对客户点i,j之间线路上信息素浓度强度的增量,其定义如下:
QPLk,如果蚂蚁在本次配送中经过了k$Sij= 路径i,j(9)
0,否则
式(9)中,Q表示信息素浓度强度是一定常数;Lk=
=1,i=1,2,,,n
k=0K
ExEx
K
=rjs,j=1,2,,,k;s=1,2,,,m=ris,i=1,2,,,k;s=1,2,,,m
ijs
k=0
其中,式(1)目标函数z1最小化车辆数,式(2)z2是求得最短的总路径长度,式(3)为车辆容量限制,保证每条路径上各客户点的货物需求总量和必须小于车辆容载能力,式(4)为每个客户的运输任务仅由一辆车完成;式(5)和式(6)限制了每个客户点必须有一辆车完成且只能由一辆车来完成,且只能被访问一次。
2.3 配送车辆路径规划问题
配送车辆路径规划就是对含有n个配送目的地的货单,寻找一条最佳的货物配送路径,通过合理调度配送车辆和货物单,使完成一次配所送花费的成本最小。本文利用基本蚁群算法并对其进行改进,以求解货物配送过程中的最短路径。求解过程如下,设定蚁群中的蚂蚁数量为m,Sij(t)表示t时刻在i,j线路上残留的信息素量,所表示的实际意义为完成客户点i的货物配送后,选择客户点j配送货物的信息素的强度。系统初始状态时,各个客户点上的信息素量相等,Sij(0)=S0,Gij(t)是能见度因数,在本文中定义为(1PTij),Tij表示从客户点i到客户点j送货用时。蚂蚁k(k=1,2,,,m)在运动过程中,根据送货线路上信息素的强度来决定转移方向,t时刻蚂蚁k从客户点i到客户点j的转移概率p定义为
k
ij
E
tij表示蚂蚁k在本次配送中完成送货单中
k
所有货物的客户位点花费的时间。本文对信息素浓度强度进行调整时利用整体信息而不是局部信息,因此,求解车辆路径规化问题时具有较好性能。2.4 算法描述
基本蚁群算法在每次进化时,只能固定地选择其中一条路径,若在每一个点上都放置一只蚂蚁,必然使算法复杂度增加,搜索时间变长。对于车辆路径规化问题,针对问题本身的特点,由于每次配送操作时车辆都是从物流中心点开始配送,且完成配送任务后又回到配送中心点,因此,本文对基本蚁群算法进行改进。每次配送进行开始时,在起始节点即配送客户点上放置m只蚂蚁。作业开始后,m只蚂蚁随机地选择下一个配送客户点。此方法有效减小了算法复杂度,缩短了搜索时间。
算法具体步骤如下:
(1)系统初始化,t=0,配送次数nc=0,每条边即客户点i到客户点j线路上的Sij(0)=S0,且$Sij=0,Jk=(0,1,,,n),tabuk=ª(禁忌表为空)。(2)将m只蚂蚁放置在物流中心初始位置处,将第k只蚂蚁所在的客户点号从Jk中删除,并加入到
k
tabuk中,开始循环搜索路径,根据式(7)中概率pij选择下一个要送货的客户点j并记录该客户点编号,将刚选择的客户点编号j从Jk中删除,并加入到tabuk中。
(下转35页)
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 蚁群算法在物流配送路径优化中的研究 研究...
蚁群算法优化车辆路径问题的研究蚁群算法优化车辆路径问题的研究隐藏>> 第27卷...物流配送路线的优化问题,是评 定配送质量好坏的重要标准。因此,本文以目前研 ...
基于改进蚁群算法的物流配送路径优化问题研究_生产/经营管理_经管营销_专业资料...2.1 VRP在实际应用上的假设 (1)所有车辆路线均起始并终止于设施点; (2)...
基于改进蚁群算法的物流配送路径优化问题研究_文化/宗教_人文社科_专业资料。...2.1 VRP在实际应用上的假设 (1)所有车辆路线均起始并终止于设施点; (2)...
基于混合蚁群算法的物流配送路径优化研究_机械/仪表_工程科技_专业资料 暂无评价
: 车辆路径问题 (VRP) 是物流研究领域中一个具有重要理论和现实意义的问题。... 正反馈自催化机制以及潜在的 并行性等特点 , 蚁群优化算法越来越多的被应用到...
基于蚁群算法的物流车辆路径优化问题的研究_交通运输_工程科技_专业资料。介绍蚁群算法在TSP和VRP问题中的运用基于蚁群算法的物流车辆路径优化 问题的研究作者: 于芹...
利用蚁群算法对物流配送路径优化问题进行求 解, 是本文研究的核心问题。 1 ...次配 送的最大行驶距离 ;(4) 每个客户的需求必须满足且只能由一辆配送 车...
基于蚁群算法的城市物流配送路径优化问题的研究_理学_高等教育_教育专区。蚁群...由于该问题被公认为属于车辆路径问题(VehicleRouting Problem,VRP)的应用,因此本文...
热门文档