王海军

(鄂尔多斯应用技术学院,内蒙古 鄂尔多斯 017000)

PSO-GA-ACO算法在冷链物流配送路径优化中的应用*

王海军

(鄂尔多斯应用技术学院,内蒙古 鄂尔多斯 017000)

伴随着现代物流的快速发展，冷链物流也得到快速发展。在冷链物流研究中配送路径优化问题对冷链物流的发展起到至关重要的作用，鉴于蚁群算法在路径优化问题中的成功应用，因此将蚁群算法应用到冷链物流配送路径优化问题中。考虑到蚁群算法运行中存在的问题，将遗传算法与粒子群算法引入到蚁群算法中，构成基于PSO-GA-ACO算法的冷链物流配送路径优化算法。实验结果表明，这种构想是可行的，可以有效提高算法运行效率，缩短配送距离，提高经济效益。

蚁群算法；遗传算法；粒子群算法；物流；路径优化

0 引言

随着经济的发展，现代物流观念不仅在工业、商业、制造业有了成功的应用，而且开始逐步深入应用到生鲜类农产品的发展中[1]。由于生鲜类农产品具有易腐败变质的特点，因此就产生了专门针对生鲜类农产品产运销的冷链物流[2]。配送路径优化问题是物流研究的一个核心，在冷链物流中也同样如此，生鲜易腐食品从生产者到最终消费者的过程中，有80%以上的时间花在配送运输上[3]。因此本文主要研究智能算法在冷链物流配送路径优化上的应用，目前常用的路径优化算法主要集中在遗传算法(GA)、粒子群算法(PSO)和蚁群算法(ACO)等一些算法上，本文主要研究ACO算法在冷链物流配送路径中的应用。已有研究成果[4]表明，ACO算法存在易过早陷入局部最优，从而造成算法停滞现象等一系列问题，因此本文将GA、PSO算法引入到ACO算法的优化中，研究PSO-GA-ACO算法在冷链物流配送路径优化中的应用。

1 路径配送模型的构建[5]

在本研究中，设所在城市有一个冷库储存生鲜产品，当所有客户均收到货物后货车回到冷库。设总的接受配送的客户数为M，客户i和j之间的距离为dij，因为每两个客户间的配送距离不相同，所以计算配送费用时单位配送距离费用相同。设单位配送费用为P，总的配送费用为S,符号变量xij表示客户i与客户j之间是否存在前后配送关系。则该配送模型可以建立目标函数为：

S=min(∑∑(xijdij))P,i,j∈{0,1,2,…,M}

(1)

其中xij需要满足如下几个条件：

(2)

(3)

(4)

∑∑xij≤M+1,i,j∈{0,1,2,…,M}

(5)

约束条件(3)表示配送车辆到达每个客户一次且只到达一次，约束条件(4)表示配送车辆到达用户p且必须离开用户p，约束条件(5)保证配送车辆起、止于配送中心。

2 PSO-GA-ACO冷链物流配送算法设计

2.1 蚁群算法基本原理

蚁群算法(Ant Colony Optimization, ACO)是一种用来在图中寻找优化路径的机率型算法。它是DORIGO M博士于1992年提出的，其灵感来源于蚂蚁在寻找食物过程中发现最佳路径的行为。ACO是通过模拟自然界中蚁群的觅食行为而发展起来的一种智能算法。在该算法中，蚂蚁在觅食过程中会在其走过的路径上释放生物信息素，感知到信息素的蚂蚁会沿着同样路径同时也会释放信息素从而强化路径上已经存在的信息素，如此反复进行[6]，到最后就会形成一条高浓度信息素的路径，所有蚂蚁都会选择这条路径去觅食，这样就形成了一条洞穴到食物的最佳路径[7]。

2.2 基本ACO执行步骤

j∈allowedk

(6)

(3)浓度计算：根据tabu表按式(7)[9]计算每只蚂蚁在每条路径上所遗留的信息浓度增量：

(7)

式中，Q表示信息素强度，Lk表示蚂蚁k在本次循环中所走路径的总长度。

(4)浓度更新：当所有蚂蚁完成一次对所有城市遍历的循环后，用式(8)[9]对信息浓度进行一次更新。

(8)其中，ρ表示信息素挥发系数，1-ρ则表示信息素残留因子。

(5)终止判断：判断循环次数nc是否小于最大循环次数NC，如果是，则停止循环，输出gcbest和gtbest，否则，将所有禁忌表清空，并且重复步骤(2)～步骤(5)，直到满足停止条件为止。

2.3 PSO-GA-ACO设计思想

GA与PSO算法在运算初期能够快速逼近最优解，有效优化系统参数，但中后期运行效率低，易早熟收敛，局部寻优能力差。而ACO算法运行初期由于信息素少，计算时间长、收敛速度慢、易陷入局部最优，但是后期局部寻优能力较强。因此在本算法中将GA、PSO算法融入到ACO算法求解中，使新算法能够尽可能避免过早陷入局部极小值，提高算法整体寻优能力。算法设计思路:(1)蚂蚁群粒子化;(2)按照信息素大小进行遍历;(3)对蚂蚁得到的路径进行遗传交叉、变异，从而产生新解;(4)利用PSO算法对得到的新路径根据粒子群优化算法中的局部极值和全局极值进行调整;(5)调整结束后，根据结果判定算法是否继续。

2.4 PSO-GA-ACO算法实现

为了提高ACO算法的运行效率，减少其过早陷入局部最优、易出现停滞等现象，本文将以下三步[10-12]融合到蚁群算法中，构建出基于PSO-GA-ACO算法的冷链物流最优配送路径算法。

(1)蚂蚁粒化：在path表中，产生2m条随机路径，并对这2m条路径的长度进行排序，取其中的m条长度最短的路径作为m只蚂蚁的初始个体最优路径pcbest，取其路径长度为个体极值plbest。将m只蚂蚁中的最小的plbest作为蚂蚁群体的全局极值glbest，其路径为全局最优路径gcbest。

(2)随机交叉：在当前蚂蚁完成一次对所有客户的遍历后对其走过路径进行顺序交叉，选取2个随机交叉点j1与j2，设j1

(3)变异更新：在交叉操作后，对路径path2进行逆转变异，在路径path2中交换第p次和第q次访问的城市，其余顺序不变，从而得到新路径path3；根据path3计算路径长度，若新路径长度小于交叉变异前的路径长度则接受新值，更新path表中相应蚂蚁的个体极值ptbest和位置极值pcbest，并更新全局极值gtbest和gcbest，否则拒绝。

将以上三个改进步骤与基本ACO执行步骤结合起来就构成了新的PSO-GA-ACO算法，具体执行步骤为：(1)参数设定;(2)蚂蚁粒化；(3)启动蚂蚁；(4)随机交叉;(5)变异更新;(6)浓度计算;(7)浓度更新;(8)终止判断。

当运行到步骤(8)时，判断是否达到最大运行次数，如果是则结束运算，否则重复步骤(3)～步骤(8)，直到满足停止条件为止。当算法最终运行结束后，所求出的解即为冷链物流最优配送路径。

3 仿真实验

3.1 参数设置

考虑到在实际配送中，一般一个冷库的配送点数不会特别多，因此，在文中采用30个城市的TSP问题数据作为研究对象进行比较研究。为了验证本文算法的有效性，将算法运行结果分别与GA、PSO与ACO算法运行结果进行比较，基本参数设置如下。

GA-PSO-ACO算法参数:α=1，β=5，ρ=0.95，Q=100，NcMax=200，m=30；ACO算法参数:α=1，β=5，ρ=0.95，Q=100，NcMax=200，m=30;GA算法：初始种群inn=100，交叉概率0.8，变异概率0.8，最大迭代次数gnmax=200；PSO算法： 粒子个数num=30, 最大迭代次数NcMax=200。

3.2 实验结果

采用MATLAB语言实现如表所示算法模型对30个城市的TSP问题分别运行10次，表1给出算法运行结果，从表中可以看出在算法运行200次的情况下， GA-PSO-ACO与ACO算法的运行稳定性要明显好于PSO算法与GA算法，其中GA-PSO-ACO算法的稳定性最好，它的平均配送距离比ACO、PSO及GA算法分别减少了4.811 8 km、45.995 3 km及32.468 6 km。按照现在城市道路货车每公里1.2元计算，则每配送一趟比其他算法给出的路径可以分别节省5.77元、55.19元及38.96元，这样长期配送节约的费用将是一个巨大的数字。图1～图4给出了4种算法某次运行结果，从结果中可以看出GA-PSO-ACO算法对配送拐点的处理好于其他算法, 因此在局部寻优方面效果明显好于其他三种。

表1 各种算法运行结果

图1 基于GA-PSO-ACO算法配送路径

图2 基于ACO算法的配送路径

图3 基于PSO算法配送路径

图4 基于GA算法配送路径

4 结论

冷鲜食品属于易变质的食品，对冷鲜食品的配送一般要求在最短的时间、最短路径、最低成本下完成配送。考虑到实际配送过程的复杂性，本文主要研究冷链物流的最短配送路径，鉴于ACO算法在冷链物流配送路径优化中的应用，考虑到采用ACO算法进行冷链物流配送，但是ACO算法在路径优化中存在易过早陷入局部最优、算法易出现停滞现象等一系列问题，因此将另外两种智能算法GA与PSO算法引入到ACO算法的优化中，给出了基于PSO、GA和ACO融合算法的冷链物流配送路径设计思想和算法运行步骤。实验结果表明，本文的构想是可行的，可以有效提高配送路径优化效率，提高经济效益。

[1] 王文铭,郑薇.果蔬配送中心物流作业建模与仿真研究[J]物流工程与管理,2010,32(4):115-117.

[2] 邓汝春.我国的冷链物流市场及其发展策略[J].商场现代化,2008,17(2): 8-14．[3] 缪小红,周新年,林森.第3方冷链物流配送路径优化研究[J].运筹与管理,2011,20(4):32-38.

[4] 吴天羿,许继恒,刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用,2013,33(4):1157-1160.

[5] 苏涛,王庆斌,孙聪，等.蚁群算法的军事物流配送路径优化[J].海军航空工程学院学报,2012,27(3):342-346.

[6] 林娜,刘二超.基于改进蚁群算法的无人机动态航路规划[J].计算机测量与控制,2016,24(3):149-153.

[7] 戴天虹,李昊.基于改进蚁群算法的无线传感器网络路由的优化[J].计算机测量与控制, 2016,24(2):321-324.

[8] 谈晓勇,林鹰.基于改进遗传蚁群算法的灾后救援路径规划[J].计算机工程与设计,2014,35(7):2626-2531.

[9] 刘道伟,关昕.蚁群算法在林火扑救路径选择中的应用[J].计算机工程,2011,37(14):214-217.

[10] 冯兴杰,岳鹏涛.基于动态优先级的机场滑行道调度优化算法[J].计算机工程与设计,2016,37(4):999-1003.

[11] 高尚, 张晓如.蚁群遗传混合算法[J].数学的实践与认识,2009,39(24):93-98.

[12] 徐江乐,肖志涛,赵京华.基于遗传算法的改进智能优化蚁群算法[J].微电子学与计算机,2011,28(8):47-50.

PSO-GA-ACO algorithm used in cold chain logistics distribution route optimization

Wang Haijun

(College of Ordos Applied Technology, Ordos 017000， China)

With the rapid development of modern logistics industry, cold chain logistics industry also has developed rapidly. In cold chain logistics research, distribution routing optimization problem plays a crucial role for the development of cold logistics chain. In view of the suceessful application of ant colony algorithm in the path optimization, it applies the ant colony algorithm to cold chain logistics distribution routing problem.Taking into account the problems of ant colony algorithm when running, it introduces genetic algorithm and particle swarm algorithm into the ant colony algorithm, forming PSO-GA-ACO algorithm based cold chain logistics distribution routing optimization algorithm. The experimental results show that this idea is feasible, and can effectively improve the algorithm efficiency, shorten delivery distances, and increase economic efficiency.

ant colony algorithm; genetic algorithm; particle swarm optimization; supply chain; path optimization

内蒙古自治区高等学校科学研究项目(NJZY16382)

TP301.6, TP15

A

10.19358/j.issn.1674- 7720.2016.24.026

王海军. PSO-GA-ACO算法在冷链物流配送路径优化中的应用[J].微型机与应用，2016,35(24)：91-93，100.

2016-07-25)

王海军(1982-)，通信作者，男，工学硕士，高级工程师,主要研究方向：人工智能算法应用。E-mail:wanghaijun11249@126.com。