供应链管理课程报告
供应链管理课程报告
基于蚁群智能的物流配送系统VRP 优化算法
学 院: 经济管理学院 指导教师: 翁克瑞
2015年04月22日
摘要:
相对弱小、个体功能并不强大的蚂蚁,通过信息素进行信息传递, 展现出复杂的集体智能行为自适应的路径寻优和高度的分布式协作。将这种蚁群智能与应用领城的启发式知识相结合构成的蚁群算法具有诸多优良性质,可以很好地用于解决物流配送系统中的VRP 优化问题。本文设计并实现了一种基于蚁群智能的物流配送系统VRP 优化智能算法:AnEtxplorer 。通过引人基于选择窗口和可调整候选解动态链表的概率转移策略,扩展基于领域启发信息的蚂蚁能见度概念,以及构造一种反映解分布特征的自适应信息素更新策略,较好地解决了传统VRP 算法中普遍存在的加速收效与局部停滞之间的矛盾。实验模拟结果表明,AnEtPxloerr 算法具有快速、高效的全局搜索性能和良好的可扩展性能,能够较好地适应物流配送系统的需求。
关键词:供应链;物流配送系统;VRP ;优化;蚁群智能
目录
一、前言..................................................4 二、需求分析与建模........................................4 三、基本蚁群算法简介与特点................................5 四、算法程序..............................................6 1、基于选择窗口和可调整候选解动态链表的概率转移策略.....6 2、基于问题领域启发信息的蚂蚁能见度.....................8 3、自适应信息众更新策略.................................8 五、算法实现..............................................9 六、结论..................................................10 七、参考文献.............................................10
基于蚁群智能的物流配送系统VRP 优化算法
一、前言
一个成功的企业需要具备很多必要条件,但往往有以下四方面是不可忽略的,分别是:
客户关系管理、采购与供应管理、生产与运作管理和物流管理。
其中,物流配送是物流企业日常生产中一个非常重要的环节, 其效率高低直接影响物流企业的运作效益。在配送管理中,经常需要决策的一个问题就是如何寻找一组最优的车辆路径,将货物配送到每个客户手中,也即所谓的车辆路径问题(Vhecile Rountig Prblem, 简称 VRP) ①。
VRP 本质上是一个NP-hard 问题,是组合优化领域的前沿与热点问题之一物流配送系统中的车辆路径选择较之经典的VRP 模型更为复杂,因为它所涉及多方面的约束条件与用户要求,包括货物需求量、发送量、交发货时间、车辆容量限制、行使里程限制、时间限制等。对于这类间题, 当问题的规模较大时, 将很难得到全局最优解或满意解. 而且随着问题规模的增大,算法的计算时间将以指数速度增加。
目前常用的、行之有效的方法一般都是通过一组启发式算法或生物进化算法来求解。基于蚁群智能思想的蚂蚁算法的出现,尤其是在被成功应用于解决TSP 问题之后,为求解物流配送VRP 优化问题提供了新的方法和工具。国内外学者已在该研究领域和提出了很多改进方案和算法,不同程度地推进了问题的解决。由于本质上的随机搜索特性,这些改进型VRP 蚂蚁算法普遍存在加速收敛与停滞现象之间的矛盾, 因此研究如何减少计算时间, 同时有效避免算法停滞的方法和策略始终是该领域的一个热点问题。鉴于此,本文试图从增强蚂蚁间分布式协作能力和提高其对信息素的利用效率的角度人手, 设计并实现一种新颖的物流配送系统VRP 优化蚂蚁算法,称之为AntExploerr 。
二、需求分析与建模
VRP问题可定义为:运输车辆从一个或多个设施到多个地理上分散的客户点,优化设计 一套货物流动的运输路线,同时要满足一系列的约束条件。前提条件是设施位置、客户点位 里和道路情况已知,由此确定一套车辆运输路线, 以满足目标函数。具体到物流配送系统, 该问题可以描述如下:
(1)客户独立均匀分布于配送区域,都有非负需求,且需求量不大于车的载重量; (2)配送中心拥有多辆同种载重量的车,且派出服务的每辆车的始、终点都在配送中 心,每辆车所服务的客户序列的总需求不能大于车的载重量; (3)每个客户只能被访问一次,每辆车只能服务一条路线; (4)目标是使系统运作费用最小,或路线数最少等; 在实际的配送系统中,还需要考虑一些面向应用的特殊要求,如配送中心往往拥有多种 载重量的车辆,客户需要在其指定的时间窗内接受服务。我们所考虑的费用包括每派出一 辆车的固定费用,车辆的行走费用和其它相关费用。目标是设计一组车辆路线,使物流配 送企业的总运作费用最小。为构造数学模型方便,将物流配送中心编号为0,任务编号为l , 2,...m ,任务及物流配送中心均以点i(i=0,1,2,„,m) 来表示。定义变量为:
x
ij
、
y
ij
为
车辆k 从点i 行驶到点j
x
ij
否则
点i 的任务有车辆k 完成
y
ij
=
否则
于是,可以对上述物流配送系统VRP 优化问题作如下形式化描述:
min (z )=
∑∑∑c x
i
j
k
ij
ijk
∑g y
i
i
ki
≤q , ∀ k ;
∑y
k
ki
=1 , i=1,2,...,m;∀ k; =
∑x
i
ijk
y
kj
, j=0,1,...m;∀ k ; , i=0,1,...m ;∀ k ;
∑x
j
ijk
=
y
kj
x = 模型中,为车辆容量;
模型中,为车辆容量;
(x ) ∈ S ;
ijk
x
ijk
=0或1, i,j=0,1,... ,m ;∀ k;
=0或1, i=0,1,... ,m ;∀ k;
y
ki
c c
ij
表示从点i 到点j 的运输成本,它的含义可以是距离、费用、时间等;q 为任务i 的运输量;S 为支路消去约束,即消去构成不完整线路的解。 表示从点i 到点j 的运输成本,它的含义可以是距离、费用、时间等;q 为任务i 的运输量;S 为支路消去约束,即消去构成不完整线路的解。
g
i
ij
g
i
三、基本蚊群算法简介与特点
实验观察表明,蚂蚁在运动过程中会留下一种分泌物(也称信息素) ,其后面的蚂蚁可根 据前边走过的蚂蚁所留下的分泌物选择其要走的路径。一条路径上的分泌物越多,妈蚁选 择这条路径的概率就越大。因此,蚂蚁群体的集体行为实际上构成一种学习信息的正反馈 现象,蚂蚁之间通过这种信息交流寻求通向食物的最短路径。蚁群算法正是模拟了这样的 优化机制,即通过个体之间的信息交流与相互协作最终找到最优解。
蚂蚁算法是由意大利学者M.Dorigo 等人首先提出的,他们充分利用蚁群搜索食物的过
程与旅行商问题(TSP)之间的相似性,用于解决VRP 问题,取得了很好的结果。之后,蚂蚁算法的理论与应用研究遍地开花,如应用于TSP 的AS 、ACS 、MMAS ,应用于二次分配问题(QAP)和任务调度问题(JSP)的ANTS 、HAS, 应用于网络路由问题的AniNet ,以及应用于本文所讨论的VRP 问题的AS 。
蚁群中的蚂蚁以信息素为媒介的间接的异步的联系方式是蚁群算法最大的特点,找出 高质量的解是群体中的所有个体之间全局性的相互协作的结果。我们认为,上述已有的研 究成果中普遍存在的一对矛盾是如何快速全局收敛并避免早敛和停滞现象出现,究其根源, 在于a) 蚂蚁之间分布式协作能力不足,b) 信息素的更新和利用效率偏低。前者体现在转移 策略的设计上,一般是基于可行点集allwoed 。来计算蚂蚁的转移概率进而限制蚂蚁的下一 步选择空间,未考虑或很少考虑利用问题领域的启发式知识来加强蚁群的协作行为;后者则 体现在信息素更新策略的设计上,要么对所有的蚂蚁所经过的路径增加信息量,要么只增加 最优适应度的路径上的信息量,其余信息量被削减,再要么就是基于等级变化的算法,让适 应度相对较好的蚂蚁固定在若干条路径上,根据其解的优劣程度决定信息量的增加幅度,这 些做法共同的缺陷就是忽视了算法搜索过程中解的分布特征。
四、算法程序
基于上述分析,在AntExpolerr 算法设计中,我们从增强蚂蚁间分布式协作能力和提高其对信息素的利用效率的角度人手,引人一种基于选择窗口和可调整候选解动态链表的概率 转移策略,依据问题领域的启发知识扩展蚂蚁能见度的概念,并在此基础上提出一种新颖的 能反映解的分布特征的自适应信息素更新策略,旨在使得AniExpoferr 算法在物流配送系统 路径寻优过程中具有自适应调整的能力,以克服蚁群算法计算时间长、易出现停滞的缺陷。
1、基于选择窗口和可调整候选解动态链表的概率转移策略
在设计AniExpoferr 概率转移策略中,我们依据文献②引人选择窗口的概念。选择窗口 是指蚂蚁k 在结点i 进行转移时允许选择的下一结点的数目,用群算法中,显然有
win (i )表示。在基本蚁
k
k
win (i )=CNT(allowed )时,其中,CNT (allowed )表示
k
k
k
k
集合中结点的数量。当win (i )=CNT(allowed )时, 算法实际上是在整allowed
k
个解空间中搜索。这种方法最大的缺点是搜索时间长。并且随着问题维数的增大,其解空间急剧放大,使得在有限时间内很难找到满意的结果。实际上,在应用蚁群算法求解VRP 问题过程中,发现所得到的解绝大部分是劣质解,而且干扰对优质解的寻找。如果能剔除这些劣质解,不但可以缩小解空间的搜索范围,而且可以减少劣质解的干扰,迅速发现优质解。因此如果对
allowed
k
集合中的结点进行一定的约束,缩小蚂蚁的选择窗口,限定蚂蚁每
次移动范围,或者说限定蚂蚁在每个结点所能“看到”的下一个结点的数目,则可以有效地剔除劣质解、缩小搜索范围,从而提高算法的运行速度和解的质量。
尽管本文吸收利用了文献②中有关选择窗口的概念,但是与它的处理方式不同的是, 我们在该选择窗口中还引人了一个自适应调整大小的动态链表,这里称之为CL(Candidates list) 。在蚁群算法运行t 次后,为了进一步缩小搜索范围同时又不陷人局部最优区域,我们把信息素含量最小的一定数量的劣质解加人CL 中。对于一个蚂蚁,它的选择窗口,除此之win (i )中的解均是可见的(visible),但是CL 内的解只是候选解(Candidates )
k
外的才是优先选择的解空间。改进后的概率转移策略如下式所示:
p ij
j ∈win k (i )
=
k ∈
[τij ][ηij ][μij ][kij ]
∂
βγ
θ
λ
allowed k
∂
∑
τik ηik μik k ik ∂
βγ
p ≤
r
;
⎧
p ij (t )依j ∈max ⎨τij k
win (i ), j ∉CL ⎩
k
[][ηij ][μij ][k ij ]
β
γ
∂
λ
选择j p ≥
r ;
1
p ij
=
j ∈win k (i )∉CL
k ∈
[τij ][ηij ][μij ][kij ]
β
γ
λ
λ
allowed k
∑
τik ηik μik k ik α
β
γ
ij
r
i 0
其中,
r
ij
表示边(i,j)上的信息素浓度,
η
ij
表示边(i,j)上的能见度,
μ=d +d -d
0i
ij
是考虑了任务点与配送中心间的距离而引入的变量,称为节约值,这吸收了节约法的思想,即在转移过程中, 两点样重要。
v 、v
i
j
间的距离
d
ij
固然重要,而两点相对于配送中心的位置也同
μ
ij
反映了将两点直接连接比将两点分别与配送中心连接所能获得的路径长度的节
约量,很显然,
μ
ij
越大,收益越大,而选择结点
v
j
|的概率也就越大。
k
ij
=(Q +q ) /Q
i
j
是考虑车辆容量约束而引人的变量。在满足容量约束的容量利用率就越高,因此选择点
k
ij
≤1的情况下,显然k ij 越大,车辆
v
j
的概率就应该越大。α表示信息素浓度在蚂蚁选择过
程中的相对重要性,β}、λ}、γ类似。p 是个随机数,服从(0,1)区间上的均匀分布。
r 、
11
r
的取值随算法的进化过程动态调整。在初始阶段,蚂蚁选择的范围比较大,因此
r 、r
的取值也应该比较大。在中间阶段,让蚂蚁更多地采用CL 链表约束受限的选择窗口的方式进行选择,若算法收敛速度比较慢,则减少若算法收敛速度比较快,则适当地放大的的大小
k
r 的取值,让算法更多地进行确定性选择,而
1
r 的值。若算法陷入局部解,则放大各结点窗口
1
win (i ),并加大r 0}的取值,让蚂蚁更多地进行随机选择。
2、基于问题领域启发信息的蚂蚁能见度
蚂蚁选中某一个节点的可能性是从蚂蚁目前所在节点到目标节点路径上残留信息量与
问题领域本身所提供的启发信息的函数,传统VRP 优化问题蚂蚁算法对于后者的处理通常 是简单地取结点间距的倒数,即
η
ij
=I /d ij ,其最直接的好处就是方便快捷,容易操作,
便于理解,但它存在明显的缺陷。对于配送问题而言,其实质上是一个多目标动态规划问题,涉及到很多因素,而且各种影响因素还是动态变化的,因而单以距离(或时间) 为蚂蚁寻优的启发知识,不能获得配送过程整体最优。基于这种考虑,我们将“蚂蚁能见度”的概念加以扩展,深人挖掘物流配送系统VRP 问题领域的启发式知识,提出了一种新的基于问题领域启发信息的蚂蚁能见度概念,并给出合适的计算方法。这里,蚂蚁能见度被定义为蚂蚁在寻优过程中对下一步可选节点或路径的综合偏好度。 在实际处理中, 我们采用下面的计算公式: 其中,
η
ij
=
c ηv
(c +c ) L (1+θ
ij
L
v
ij
ij
)(1-;
ij
c 、c 分别为单位时间内的人工成本和运输工具机会成本,L 力路段(i,j)Euclid
L
v
直线距离,
θ
ij
为该路段实际距离与直线距离修正系数,
v
ij
为通过该路段的平均速度,
c η
为能见度常系数,
ξ∈[0, 1]为该路段道路拥挤状况修正系数(当该路段受交通管制时则取
ij
最大值1) 。可以看出,上式综合考虑了配送系统的人工和车辆机会成本、各路段实际物理距离、路段通行速度、道路拥塞或临时交通管制状况,综合地友映了配送过程所涉及的各主要影响因素的启发性领域知识。
3、自适应信息众更新策略
前面所述的传统的固定信息量增减比例的信息素更新方式忽视了解的分布特征,而且 在问题规模较大时,由于信息素挥发因子的存在,使得那些未被搜索过的少到接近于零,从而降低了算法在这些路径上的搜索概率进而降低了发现新的优质解的能力,反之,当某条路径中信息量较大时,这些路径中的信息量持续增大,搜索过的路径再次被选择的机会就会变得较大。这两种情况都会造成算法早敛或停滞,影响到算法的全局搜索能力和收敛速度。我们下面从如何提高信息家利用效率人手,考虑算法在搜索过程中解的分布特征,提出一种动态改变τ值的自适应信息素更新策略:
(1-ρ) τ(t ) +
(1-ρ)
1-ψ(m )
τij (t ) +∑∆τij (t ) , r
k =1
s
k
τ
min
;
τij (t +1) =(1-
s
ρ)
1+ψ(m )
τij (t ) +∑∆τij (t ) , τ>
k =1
s
k
τ
min
;
∑∆τ
k =1
k ij
(t ) , 否则
其中,
τ
ij
(t ) 和τij (t +1) 分别表示原有信息素浓度和更新后的信息素浓度,p 为信息素挥发
因子,s 为经过路径(i,j)的蚂蚁数目,ψ(m ) 是一个与收敛次数m 成正比的函数,收敛次 数m 越多, ψ(m ) 的取值越大,例如: ψ(m ) =
m , c
其中c 为常数,这样,根据解的分布情况自适应地进行信息量的更新,从而动态地调整各路 径上的信息量强度,使蚂蚁既不过分集中也不过分分散,从而避免了早熟和局部收效,提高 全局搜索能力。
五、算法实现
AniExpolorer 算法的基本流程伪代码: Procedure Antprober() 1./* Initialixation */
initialize :various parametern, input_data nc←0,
ψ
*
←MAX ,
nc ψ
//max
*
:nc ,
nc
max
:初始和最大迭代次数
2./* Main Loop} */
repeat
activate bulid_
;构造初始回路集tabu Tabu ()
k
k
activateget _FeasibleSolution(v);// 获取可行解,v 为车辆数约束
//利用AntExplorer 算法转移策略和自适应信息素更新策略进行路径寻优 activate optimization()
while optimization() is active
wait an improved solution ψ from optimization() ψ←ψ
If (# active_vehicles( Kill otimization() end while
until a stopping criterion (e.g.,nc > =
*
ψ
*
)
nc
max
) is met
在上述算法流程中,我采用了两个主目标函数,按照优先级顺序,依次分别为:(a )最 小所需车辆数量(the minimization of the number of vehivles) ;(b )最小配送时间(the minimization of the travel time).
六、结论
本文设计并实现了一种新型的基于蚁群智能的物流配送系统车辆线路优化算法—AnTexplorer 。其目的是为了更好地解决现有算法中普遍存在的计算时间长、局部收敛或停滞等缺陷。为此我们引入了以下几种改进措施:(a )基于选择窗口和可调整候选解动态链表的概率转移策略;(b )基于问题领域启发信息的蚂蚁能见度计算方法;以及(c )能反映解的分布特征的自适应信息素更新策略。为了评估AnTexplorer 算法的性能,我们还建立仿真实验环境,对算法各方面的性能指标进行详尽的数值模拟。结果表明,AnTexplorerr 算法具有快速、高效的全局搜索性能和良好的可扩展性能,较好地解决了加速收敛与局部停滞之间的矛盾。
参考文献:
①郭耀煌,李军著。车辆优化调度. 成都:成都科技大学出版社,1994. ②刘志硕,申金升. 基于解均匀度的车辆路径问题的自然应蚁群算法. 系统仿真学报,2005 ③马良, 姚俭,范炳全. 蚂蚁算法在交通配流中的应用. 科技通报,2003. ④李爱梅,尤庆华,基于蚁群智能的物流配送系统VRP 优化算法,2001.
附上机实习截图: