基于蚁群算法考虑路线安排的单配送中心选址

林　雄

摘要:对一类要求考虑路线安排的单配送中心选址问题建立基于蚁群算法的选址模型,模型目标以配送中心建设费用与运输费用之和最小;同时构造模型的蚁群算法求解结构;最后初步应用证明了该模型解决此类问题的有效性,为单配送选址提供又一种方法。

关键词:蚁群算法;配送中心;路线安排;选址

中图分类号:F224文献标识码:A

Abstract: Builds based-on ant colony algorithm's location model for a class of single distribution center location problem with consideration of the routing. Mimizing the cost of construction of distribution center and the transportation costs are the objectives of model. Construct the model's ant colony algorithm solving structure. Finally, using an example shows the effectiveness of the model, providing another method for single distribution center location.

Key words: ant colony algorithm; distribution center; routing; location

单配送中心选址模型目前主要采用连续模型,如重心法。这类方法在解决配送中心选址问题的局限性一方面在于模型要求区域内任意点都可以建设配送中心,但在实际环境中往往做不到,经常出现用这种方法求出的配送中心的位置在实际中不能建设,如求得的建设地点位于湖泊中、江河中等;另一方面,目前的单配送中心模型选址时,没有考虑配送路线的安排[1-2]。基于蚁群算法考虑路线安排的单配送中心选址模型克服了以上局限,能够解决这样一类配送中心选址问题:要求在选址区域内选择一个需求点来建设一个配送中心,同时需要考虑配送路线安排,目标是使得配送总费用最低。

1选址模型研究

1.1问题描述与分析

现实中有这样一类配送中心选址问题:已知某区域及区域内需求点地址集合,该区域内各需求点的需求特点是一次需求量少,且需求稳定,具有周期性,各需求点的一次需求总量也相对较小,对各需求点的一次需求实行一次巡回配送完成,现在要在各需求点中选出一个来扩建成配送中心为这个区域的需求服务,使得配送中心建设费用与运输费用最小。因为采用一次巡回配送,巡回路线的不同对运输费用影响很大,考虑到各需求点需求稳定且具有周期性,一旦获得最优的配送巡回路线,可以重复使用,而每个备选点都有其最优的运输费用与建设费用组合,基于这样的考虑,问题的目标就是寻找基于最优配送路线的一次运输费用与一次分摊建设费用之和最小的备选点位置。

1.2模型假设

(1)区域内仅建设一个配送中心;

(2)配送中心建立在某个需求点处;

(3)只考虑一级运输,即只考虑从配送中心到需求地的运输;

(4)配送中心的容量可以满足所有需求地的需求;

(5)各需求地的需求量为已知;

(6)运输费用与运输距离及运输量成正比;

(7)系统总费用只考虑配送中心的建设费用和运输费用。

1.3模型的建立

根据以上问题描述与模型假设,可以得出配送中心选址的一般模型表达:

minz=cdx+cdx+cdx+…+cdx+fm(1)

Subject to(2)

目标函数(1)表示配送中心选建在需求地i时的最小总费用,包括配送中心建设费用与配送费用;同时表示当配送中心建在需求地i时,最优配送为从i出发,配送路线依次经历需求地1,2,3,…,n,最后回到配送中心i处,模型中路线i→1→2→3→…→n→i是一个未定的路线,表示从i出发所有巡回配送路线中的任意一种;c,c,…,

c分别表示车辆经历分段路径i,1,1,2,…,n,i的运输费率,(单位为元·km-1·kg-1);d,d,…,d表示分段路径i,1,1,2,…,n,i的距离;x,x,…,x分别表示车辆经历分段路径i,1,1,2,…,n,i时的载重量;f表示配送中心建设在i点的建设费用,m表示配送中心服务年限内,所执行的配送次数,m=tp,t表示配送中心设计服务年限,p为每年执行配送的次数,fm表示建设费用分摊到每次配送的费用;Dj=1,2,…,n为各需求地的需求量。

2模型求解的蚁群算法

模型求解涉及巡回路线寻优,不仅要考虑各需求点间的距离,还要考虑各需求点的需求量不同,采用一般搜索方法难以解决,这里利用蚁群算法在路径寻优方面的优势设计求解模型的蚁群算法。

2.1基本的蚁群算法模型

定义如下参数:

m——蚁群中蚂蚁数量,d——路径i,j的距离,η——路径i,j的能见度,τt——t时刻路径i,j上的信息量,△τ——蚂蚁k在本次循环中留在路径i,j上的信息量,Pt——蚂蚁k在t时刻由位置i转移到位置j的概率,α——轨迹的相对重要性α≥0,β——能见度的相对重要性β≥0,ρ——信息素的持久性0≤ρ<1,1

-ρ——信息素的衰减度。初始时刻,设所有路径上的信息素都相等,τ0=0c是一个常数。蚂蚁kk=1,2,…,n在运动过程中,根据各条路径上的信息素的大小以一定的概率Pt决定转移方向,Pt表示为[3]:

Pt=(3)

其中,allowed=0,1,…,n表示t时刻蚂蚁k下一步允许选择的点。在蚂蚁算法中,假设人工蚁群系统有记忆功能,用tabukk=1,2,…,m记录蚂蚁k已经走过的节点。当一个周期结束,进入t+1时刻,对各路径上的信息素进行调整,即[3]:

τt+1=ρτt+Δτt,t+1 (4)

Δτt,t+1=Δτt,t+1 (5)

其中,△τt,t+1表示第k只蚂蚁在时刻t,t+1留在路径i,j上的信息素量,其值视蚂蚁表现的优劣程度而定。路径越短,信息素释放的就越多;△τt,t+1表示本次循环中路径i,j的信息素量的增量;1-ρ为信息素轨迹的衰减系数,通常设置系数ρ<1来避免路径上轨迹量的无限累加。根据具体算法的不同,△τ、△τ及Pt的表达形式可以不同,要根据具体问题而定。M.Dorigo曾给出三种不同模型[4]分别是蚁周系统(antcycle system)、蚁量系统(ant-quantity system),蚁密系统(ant-density system)[5]。

2.2基于蚁群算法的模型求解

2.2.1模型的求解步骤

模型求解思路:

当配送中心选建在任意点i,如果待配送的需求点有n个,那么可能的配送路线将有n!种,需要先从这n!种找出最小运输费用的一种配送方案,当n取值很大时,同时考虑距离和各需求点的需求量时常规算法将无法胜任,因而,引入蚁群算法进行路径寻优(这里的最优指经历路线的运输费用最小),得到配送中心建设在i点时的最优配送路线,根据此路线计算配送中心建设在需求地i且考虑配送路线安排的最小费用,重复计算,得到配送中心独立建设在各个需求点的最小费用,对这一系列费用进行排序,最小者即为选址方案。

求解步骤为:

步骤1:以任意一个需求地i为配送中心建设地,计算配送中心建设在该地点考虑配送路线安排的最小费用。即假设配送中心建设在i点,构造蚁群搜索规则搜索以i为起点的配送费用最小的配送路线,依据这一最优配送路线,依据公式(1)计算得到配送中心建设在该点的最小费用;

步骤2:重复步骤1,直到获得配送中心独立建设在每个需求地的最小费用及相应配送路线安排;

步骤3:对求得的一系列费用进行排序,其中费用最小的方案即为选址解决方案,如得到的结果为:配送中心建设在需求点j,配送路线安排为j→x→x→x→x→…→x→j,其中,x,x,x,…,x为区域内的需求点。

2.2.2模型求解蚁群算法的设计与实现

(1)初始化

设定时间计数器t,循环次数计数器N,蚂蚁数m,初始化关键参数α、β、ρ、τt的设置:信息素轨迹强度初始值采用最大最小蚂蚁系统(MMAS)的设置,即为经历两需求地间的每段路径i,j设置一个最大信息素轨迹强度的初始值τ=τ。△τ的设置:信息素轨迹增量的初始值设为0,随后计算的增量为一常数。η的设置:这里路径最优不一定指配送路线最短,路线最短不一定配送成本最低,因为配送费用还与各需求点的需求量有关,因而两点间的能见度在这里设为η=ξDd,0<ξ<1。禁忌表初始化为空集,把m只蚂蚁全都置于起始点i,同时将蚂蚁的初始位置这里即起始点i置于当前禁忌表中。

(2)蚂蚁开始搜索路径,建立路径解决方案

位于需求点i的蚂蚁选择下一需求点j的状态转移规则如下:

j=(6)

其中,q是在0,1区间均匀分布的随机数,q是一个参数0≤q≤1,由表达式(6)产生的状态转移规则,被称为伪随机比例规则[6]。参数q的大小决定了利用先验知识与探索新路径之间的相对重要性:每当一只位于需求点i的蚂蚁选择下一个将要到达的需求点j时,它选取一个随机数0≤q≤1。如果q≤q,则根据先验知识(根据式(6))第一式选择最好的边,否则按(3)概率地选择一条边,将刚刚选择的需求点j加到tabu中。根据这种规则每只蚂蚁建立各自的路径解决方案,完成一次循环。

(3)利用最大最小蚂蚁系统信息轨迹更新规则,对信息素轨迹进行全局更新

当m只蚂蚁都建立完一次路径解决方案,根据公式(1)找出寻到本次最优路径的蚂蚁,最优的蚂蚁就是搜索到的配送路线使得配送总费用最小的那只蚂蚁,只对这只蚂蚁经历的路径进行信息素更新,更新规则如下:

τt+1= (7)

其中,△τ是事先给定的一个合理常数,ρ是信息素挥发系数,0<ρ<1。为避免搜索过早停滞,对信息素轨迹的最大值和最小值分别施加了τ和τ限制,从而使对所有信息素轨迹τ≤τt≤τ;在每次循环后,确保轨迹量遵从这一限制。若有τt>τ,则设置τt=τ;若有τt<τ,则设置τt=τ。

(4)清空禁忌表,重复(1)、(2)、(3),直至达到设置的循环次数N,得到从需求点i出发的最后的最优配送路线。

(5)根据得到的最优路线安排,依据式(1)计算配送中心建在需求点i的总成本z。

(6)对每个需求点重复(1)～(5),得到把配送中心建在各需求点的总费用,z,z,…,z。

(7)对z,z,…,z进行排序,值最小对应的方案即为考虑路线安排的配送中心选址方案。

3初步应用

某企业为一个区域提供机械零件的配送服务,为控制费用并能有效地提供配送服务,决定在其中一个需求点建设一个配送中心,使得建设费用与配送费用最小。区域内共有10个需求点,各需求点的机械零件一次需求量较少,需求量及需求周期稳定,每个月定期执行4次配送,配送计划采用一次巡回配送。各需求点间的距离见表1;各需求点的定期一次需求量见表2;在各需求点建设配送中心的费用见表3。

根据式(1)建立配送中心选址模型,配送中心的设计服务年限为5年,利用上述提供的蚁群算法求解,编程计算,初始参数设置为:α=0.6;β=0.8;ρ=0.7。取运输费率为0.005元·km-1·kg-1。运算得到的最优选址方案为,配送中心P建立在需求点j处,配送路线为:Pj→h→g→b→f→e→c→i→a→d→Pj。执行一次配送的运输费用为367.2元,执行一次配送的建设费用的分摊为735.4元,执行一次配送总费用为1 102.6元。

4结论与讨论

现实商业中,广泛存在这样的一类配送中心选址问题,这类问题的特点可以总结为服务区域内的各需求点的一次需求量较少且较稳定,需求表现为明显的周期性特点,为提高配送车辆的利用率,降低车辆空载率从而降低配送费用,一般采用巡回配送,在这样的区域内确定一个配送中心的选址。对于这类问题,可以用式(1)建立的模型进行描述,利用蚁群算法容易得到满意解,初步应用证明了模型与算法的有效性,可以为这类问题提供一种解决方法。模型还存在一些局限性,模型的建立,没有考虑未来需求的变化,把未来的需求简化为是不变的,还有模型没有考虑需求点的紧急需求。

参考文献:

[1] 蒋利军,蒋明,赵正佳. 配送中心选址问题研究文献综述[J]. 物流科技,2008,31(4):31-33.

[2] 马丽娟. 物流中心选址模型比较[J]. 商场现代化,2008(5):138-139.

[3] Marco D. Ant colonies for the traveling salesman problem[J]. Biosystems, 1997(43):73-81.

[4] M Dorigo, V Maniezzo, A Colorni. Positive Feedback as a Search Strategy[J]. Technical Report, 2002(3):91-96.

[5] Yuvraj Gajpal, Prakash Abad. An ant colony system(ACS)for vehicle routing problem with simultaneous delivery and pickup[J]. Computers & Operations Research, 2009,36(12):15-23.

[6] 李士勇. 蚁群算法及其应用[M]. 哈尔滨:哈尔滨工业大学出版社,2004:22-40.