基于粒子群算法的农产品冷链物流配送路径优化研究

杨 玮， 李国栋, 张 倩

(陕西科技大学 机电工程学院， 陕西 西安 710021)

0 引言

冷链物流是指在冷藏环境下保证食品质量，减少食品损耗，以冷冻工艺学为基础、以制冷技术为手段，进行冷藏类食品的物流过程.物流过程包括采摘、分级预冷、包装加工、配送、批发零售.冷链物流是低温食品和超低温水产品供应链中的一个重要组成部分，将预冷技术、物流信息技术融合，把冷链物流配送、仓储理货、分装与加工和车辆调度等物流各功能环节，按照客户物流系统需求，实现客户冷链物流服务资源信息量的最大化[1，2].

目前，国内外关于生鲜农产品物流的研究较少，主要集中于以下三方面内容：一方面是从宏观的角度对国内冷链物流现状进行分析并提出发展策略；第二方面是对冷链物流配套设施设备提出更高水平的要求；第三方面是对生鲜农产品的安全监控及质量评估.

在国内，黄利伟分析了我国农产品冷链物流的现状和存在的主要问题，提出制约我国农产品冷链物流发展的主要因素，总结出适合我国农产品冷链物流发展的对策[3].王岚介绍了食品冷链的概念，研究了中国食品冷链发展的问题，并深入分析了问题的原因[4].苏秀谨从物流规划的主要组成部分，即物流服务水平、运输系统、仓储与仓库选址、库存与供应，分别具体论述在规划冷链物流时的方法和独特之处[5].胡军珠分析了北京某蔬菜加工企业的冷链运输流程现状和问题，借鉴北京奥运蔬菜冷链运输流程，采用六西格玛方法的DMAIC模型优化其冷链运输流程，并提出相应对策[6].在国外，Rohit Joshi提出了一个基于Delphi-AHP-TOPSIS的冷链性能评价的基准框架，该框架可以协助经理了解目前冷链的优点和缺点，从当前公司的运作条件和策略方面改善冷链的缺点，该框架也便于决策者更好理解冷链性能决策因素的复杂关系[7].R. Montanari通过比较欧拉法和拉格朗日法, 提出了一个确定最优冷链管理系统的模型，该模型可以找出最适当的管理解决方案，以达到物流成本最小化的目标[8].

从上述资料看出，很多专家学者从不同的角度对目前生鲜农产品物流存在的问题进行了研究，但这些理论研究中，大部分只是从宏观方面提出冷链物流优化策略，且一些规划方法即理论研究成果的可操作性不强，涉及计算的规划方法较少，结果也往往不尽如人意.

本文选用了算法简单、易实现，执行速度快的粒子群算法解决农产品冷链物流配送路线优化问题，在迭代过程中对部分粒子重新初始化，以保证粒子的多样性，避免结果陷入局部最优.通过实例验证了该算法在解决线路优化问题时具有时间短、算法收敛快、迭代次数少的优越性.

1 我国农产品冷链物流存在的问题

与发达国家相比，我国农产品冷链物流整体水平偏低，农产量流通过程中损耗较高，物流成本居高不下，尤其是在发展相对滞后的西部地区，农产品物流基础设施相对落后，流通效率低下，仓储、交通运输条件落后，缺乏先进的信息网络平台，致使农产品在流通过程损耗严重[9].我国冷链物流技术落后，导致鲜活农产品在运输过程中出现腐变、串味等问题，无法保证鲜活农产品在运输中的“安全”和“绿色”问题.同时，我国缺乏冷链物流的专业人才，制约了我国冷链物流快速发展[10].

陕西是个农业大省，农产品占有重要地位，冷链物流的重要性就显示出来.陕西省农产品冷链物流配送也受到人们的关注.陕西省农产品大多是才用普通卡车运输，由于农产品的冷藏运输效率低，在流通过程中损耗高，整个物流费用占到易腐保鲜食品成本的70 % .所以如何高效率合理的配送成为我们研究的重点.高效率合理的配送是冷链物流系统顺利运行的保证，合理安排配送线路，对配送速度、成本、效益有着重大影响.正确合理地安排车辆的配送线路，可以节约运输时间，增加车辆利用率，从而降低运输成本，提高企业经济效益与客户服务水平，使企业达到科学化的物流管理, 提高企业的竞争力.

2 冷链物流配送路径优化模型

物流配送路径优化问题可以描述为：配送中心有多辆汽车，每辆汽车从配送中心出发，给多个需求点送货，已知需求点的位置和需求量，每辆汽车的载重量，以汽车行驶总路径最短为优化目标，优化汽车的路线.

设配送中心有载重量为Qk(k=1,2,…,k)的K辆汽车向L个需求点送货，已知需求点的需求量qi(i=1,2,…,L)和运距dij，限制一辆车一次配送的距离不超过Dk，d0j(i,j=1,2,…,L)表示配送中心到需求点的距离，再设nk为第k辆汽车配送的客户数(nk=0表示未使用第k辆汽车)，用集合Rk表示第k条路径，令rk0表示配送中心，rki表示需求点rki在路径k中的顺序为i，则可建立如下物流配送路径优化问题的数学模型：

(1)

s.t.

(2)

(3)

0≤nk≤L

(4)

(5)

Rk={rki|rki∈{1,2,…,L},i=1,2,…,nk}

(6)

Rk1∩Rk2=φ∀k1≠k2

(7)

(8)

上述模型中：

(1)式为该模型的目标函数，以配送线路最短为优化目标；(2)式为每辆车的能力约束；(3)式为限制车辆配送的最大行驶距离；(4)式为限制每条路径上的需求点数；(5)式表明每个需求点都被服务；(6)式表示路径的需求点的组成；(7)式限制每个需求点仅被服务一次；(8)式表示当nk≥1时，取sign(nk)=1，当nk<1时，取sign(nk)=0.

3 粒子群优化算法

本文采用粒子群优化算法(Particle Swarm Optimizer，PSO)进行寻优.粒子群优化算法最早是由Kennedy和Eberhart于1995年提出的[7,8]，其核心思想是对生物社会性行为的模拟，这种算法的优点是实现容易、精度高、收敛快，并且在解决实际问题中具有优越性.

3.1 粒子群算法原理

粒子群算法是一种基于群体智能的随机寻优算法，它模拟鸟群的觅食行为，将问题的搜索空间类比于鸟类的飞行空间，将每只鸟抽象为一个无质量无体积的粒子，用以表征问题的一个候选解，优化所需用寻找的最优解则等同于要寻找的食物.PSO算法为每个粒子制定了类似鸟类运动的行为规则，使得整个粒子群的运动与鸟类觅食的特性类似，进而用来求解复杂的优化问题.该算法把每个优化问题的解都看成是搜索空间中的一只鸟.所有的粒子都有一个由被优化的函数决定的适应值(fitness value)以及决定他们飞行方向和距离的速度，粒子们追随当前的最优粒子在解空间中搜索.PSO算法寻优搜索的过程，每只鸟(粒子，Particle)在自己最优位置的基础上通过追踪有限个处于当前最优位置的邻居，一步步地向食物目标位置靠近.

在粒子群算法中，由n个粒子组成的种群X=(X1,X2,…,Xn)在D维空间中以一定的速度Vi=(Vi1,Vi2,…,ViD)T飞行，粒子飞过的每个位置Xi=(xi1,xi2,…,xiD)T都对于一个解，粒子飞行的过程就是搜索的过程.每个粒子在飞行时，根据自己飞过的历史最优点Pi=(Pi1,Pi2,…,PiD)T和群体邻域内所有粒子飞过的历史最优点Pg=(Pg1,Pg2,…,PgD)T更新自己的位置和速度.常用的速度和位置更新公式如下：

(9)

(10)

其中，c1，c2为加速因子，c1调节粒子飞向自身最好位置方向的步长,c2调节粒子向全局最好位置飞行的步长;r1，r2为[0，1]之间的随机数.w为惯性系数，一般取(0,1)之间的随机数；每一维的速度都被限制在最大速度vmax(vmax>0)内，当vk=-vmax,vk>vmax时，vk=vmax;当vk<-vmax时，vk=-vmax.

3.2 算法流程

粒子群优化算法流程如下：

Step1:随机初始化粒子位置和速度；

Step2:计算每个粒子的适应度值；

Step3:根据公式(11)、(12)更新当前个体最优和群体最优；

(11)

(12)

Step4:根据公式(9)、(10)更新各粒子位置和速度；

Step5:如达到终止条件，算法结束；否则，转向Step2.

粒子群优化算法的流程图如图1所示.

图1 粒子群优化算法流程图

4 实例分析

4.1 问题描述

本文以陕西某果业有限公司为例对冷链物流配送路径进行优化研究.该公司主要是给超市和农产品批发市场供应苹果.该公司有4辆车进行配送，每辆车限载量皆为q=4.0 t，用这4辆车来完成西安市内17家超市的配送任务.配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量见表1.

4.2 冷链物流配送路径优化问题的粒子群优化算法

(1)编码初始化.本文使用整数编码， 17个苹果需求点，用4辆车来进行配送，用从1到17的整数排列来表示粒子的状态X(x1，x2，…,xi)，随机生成初始种群；之后解码为1～20的20个随机数，因为有4辆车来配送，插入3个数将17个需求点分成4组，由4辆车分别给这4组需求点进行送货.编程的重点是要在每个粒子中插入三个数表示配送中心.

(2)适应度及约束条件计算.用PSO算法优化客户排序时，按照客户的排列顺序分配车辆，在每条线路的内部，用最邻近法优化线路.根据式(1)计算粒子的目标函数Z，粒子的适应度为目标函数Fitness=Z；计算约束条件每辆车的限载量为4吨.

(3)初始化局部最优和全局最优.当前各粒子的位置适应度是初始化局部最优pbest，所有局部最优中适应度值最优的适应度值是全局最优值gbest，对应的粒子为最优解.

(4)位置、速度按照公式(9)、(10)更新.

(5)循环终止.当循环到最大迭代次数时循环结束(或找到全局最优值停止循环)输出最优路径和适应度值.否则，继续更新位置和速度继续迭代.

表1 配送中心与需求点之间的

4.3 实例结果分析

根据上述实例的特点，作者利用计算机设计了粒子群算法的参数，通过matlab的运行随机求解10次，得到计算结果见表2.

表2 冷链物流配送路径优化问题的粒子群算法计算结果

从表2中的数据可以看出，第6次得到了该问题的最优解186.9 km，其对应的配送路径方案为：路径1：0-15-14-5-9-0；路径2：0-13-12-11-16-0；路径3：0-2-17-4-1-0；路径4：0-3-8-7-10-6-0.由此可见，对于冷链物流配送路径优化问题，运用粒子群优化算法可以方便有效的求得最优解.

5 结论

在农产品配送系统中，合理的选择物流配送路径是提高服务质量、降低配送成本、提高经济效益的重要手段.本文在建立了冷链物流配送路径优化模型的基础上，通过对配送路径优化问题的分析，构建了求解冷链物流配送路径问题的粒子群优化算法，通过实例进行试验计算，结果表明运用粒子群优化算法可以求得最优解.

[1] 吴稼乐，陈 坚，朱富强.低温物流基本构架和关键技术的探讨[J].制冷,2004，23(2)：29-33.

[2] 王 杨，顾英男.我国农产品冷链物流的研究[J].物流工程与管理,2010,32(9):4-6.

[3] 黄利伟.我国农产品冷链物流发展的问题与对策研究[D].北京：中国农业科学院，2007.

[4] Wanglan.A research on related questions of Chinese food cold chain development[J].International Conference on Management of Commerce and Government,2008,(8):18-21.

[5] 苏秀谨.食品冷链的物流规划研究[D].北京：国际经济贸易学院，2005.

[6] 胡军珠.北京Y公司蔬菜冷链运输流程优化研究[D].北京：北京交通大学，2009.

[7] Rohit Joshi.A Delphi-AHP-TOPSIS based benchmarking framework for performance improvement of a cold chain[J].Expert Systems with Applications,2011，(38):10 170-10 182.

[8] R.Montanari.Cold chain tracking:a managerial perspective[J].Trends in Food Science & Technology,2008,(19):425-431.

[9] 张春颖.我国西部特色农产品冷链物流的发展现状与策略研究[J].物流科技，2010,34(10):50-54.

[10] 吴 敏.我国农产品冷链物流体系建设的出路探讨[J].商品储运与养护，2008,30(7):13-16.