车辆路径问题(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

6 蚁群优化算法在物流配送车辆路径问题中的应用研究席先杰 ( 台州职业技术学院, 浙江 台州 318000) =摘 要> 车辆路径问题( VR P) 是一类物流配送领 域具有广...
蚁群算法优化车辆路径问题的研究蚁群算法优化车辆路径问题的研究隐藏>> 第27卷...物流配送路线的优化问题,是评 定配送质量好坏的重要标准。因此,本文以目前研 ...
基于改进蚁群算法的物流配送路径优化问题研究_文化/宗教_人文社科_专业资料。...2.1 VRP在实际应用上的假设 (1)所有车辆路线均起始并终止于设施点; (2)...
基于改进蚁群算法的物流配送路径优化问题研究_生产/经营管理_经管营销_专业资料...2.1 VRP在实际应用上的假设 (1)所有车辆路线均起始并终止于设施点; (2)...
: 车辆路径问题 (VRP) 是物流研究领域中一个具有重要理论和现实意义的问题。... 正反馈自催化机制以及潜在的 并行性等特点 , 蚁群优化算法越来越多的被应用到...
利用蚁群算法对物流配送路径优化问题进行求 解, 是本文研究的核心问题。 1 ...次配 送的最大行驶距离 ;(4) 每个客户的需求必须满足且只能由一辆配送 车...
改进的蚁群算法在物流配送路径 问题求解中的应用杨... sw ap 物流配 送路 径问 题也 称车 辆路 径...助教, 硕士, 现从事物理实验教学及系 统优化研究。...
物流配送车辆路径优化方... 134页 免费 蚁群优化算法求解车辆路... 3页 3...(一)蚁群算法的应用研究 蚁群算法是一种鲁棒算法,把它在 TSP 问题中的经典...
蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能优化算法, 通过介绍... 以及蚁群算法在 TSP 问题中的应用, 在分析 TSP 与车辆路径问题 (VRP ) 的...
基于蚁群算法的城市物流配送路径优化问题的研究_理学_高等教育_教育专区。蚁群...由于该问题被公认为属于车辆路径问题(VehicleRouting Problem,VRP)的应用,因此本文...
热门文档