基于人工蜂群算法的鲜活农产品冷链物流配送路径优化

蔡浩原　潘郁

摘要：鲜活农产品易变质的特性决定了其配送过程的困难性，针对这一难题，拟构建鲜活农产品的变质函数和配送时间的惩罚函数，并依此建立带有时间窗的鲜活农产品冷链物流路径优化模型。通过人工蜂群算法（ABC）对模型进行求解，以自然数编码的方式生成食物源，并讨论食物源的更新公式和适应度函数，研究具体的求解步骤和判断标准。利用数值算例验证了所建模型的合理性，结果表明，人工蜂群算法对此类问题具有有效性和可行性。

关键词：鲜活农产品；冷链物流；路径优化；人工蜂群算法

中图分类号： F252文献标志码： A

文章编号：1002-1302（2017）15-0318-04

随着科技的发展和收入的增加，人们对生活质量提出了更高的要求。鲜活农产品与人们的生活息息相关，人们对它的需求也随着生活水平的提高呈现多样化和个性化的发展趋势。鲜活农产品主要包括新鲜的蔬菜、水果、水产品、禽类和肉类等5类产品。虽然我国是一个农业大国，但是物流配送体系的发展却跟不上需求，且已经成为农产品市场发展的阻碍。目前，我国农产品物流体系不成熟、物流配送设施不完善以及物流人才缺乏等一系列的缺陷都是亟须加强和改善的地方，否则人们的需求便不能够得到满足。对于鲜活农产品这一类特殊的产品，因它们具有易腐变质的特性，需要冷链物流进行配送来保证其新鲜度。冷链物流指新鲜冷冻类食品从生产到被消费前每个流通环节都必须在一定低温环境下进行保存，从而保证食品新鲜度或降低食品变质和损耗程度。鲜活农产品的严格时间限制、高储藏成本和高服务质量等要求，给冷链物流商提出了很高的配送要求。因此，如何科学地规划配送路线、合理制定配送方案，以保证鲜活农产品的配送效率、食品的新鲜程度和低损耗率，提高服务质量水平，对于冷链物流商非常重要，也是鲜活农产品发展道路上亟须解决的难题。

车辆路径问题（vehicle routing problem，简称VRP）是指物流配送中心向一定数量的对于货物需求不同的需求点供货，在满足需求点配送要求的基础上，进行合理的路线规划，最终达到运输路程最短、运输成本最低等目的。由于对该问题的研究具有很强的现实意义，因此一直是国内外学者研究的热点。VRP的概念最早由Dantzig等提出[1]；考虑到现实中对于车辆路径问题总是有一定配送时间要求，所以Solomon等首先将时间约束条件加入到车辆路径问题的研究中[2]。启发式算法对于解决车辆路径问题具有很强的优越性，随着多种算法的产生，对启发式算法的研究也逐步丰富起来。Brito等将时间窗和模糊约束加入到近距离开放式的车辆路径问题中，并通过混合蚁群算法进行了求解[3]；de Armas等考虑了现实中动态丰富的多目标的车辆路径问题，使用了1种变领域搜索策略的启发式算法解决该问题[4]；Küüko[KG-*5]g[DD（-1*2][HT6]ˇ[DD）]lu等利用了基于禁忌搜索和模拟退火算法的混合算法，解决带有回程和时间窗的车辆路径问题[5]；陈志新等使用混合粒子群算法来解决物流配送路径优化问题[6]；邬开俊等改进了差分进化算法，结合贪心算法来解决具有非确定性多项式（non-deterministic polynomial，简称NP）难的VRP[7]；随着科技环境的变化，对于车辆路径研究的背景也在随之转变，向敏等研究了在电子商务环境下鲜活农产品物流配送路径的优化问题[8]。

虽然国内外学者对于车辆路径问题的研究很多，但是将车辆路径和冷链物流结合进行研究的却不多，将鲜活农产品作为配送物品的研究就更少。本研究考虑了鲜活农产品运输过程的损耗，加入时间窗的约束，并依此建立合理的鲜活农产品冷链物流配送模型，目的是使鲜活农产品冷链物流的配送成本最小化，力求使所建立的模型符合实际情形，从而为实际鲜活农产品的配送路線选择提供有力的参考。

1鲜活农产品冷链物流配送路径优化数学模型

1.1问题描述

鲜活农产品物流配送模型是由1个鲜活农产品配送中心向多个其覆盖范围内的配送点使用低温配送车进行货物配送的模型。假定配送中心的货量充足，每个需求点的需求量、位置以及时间窗约束都是已知的；配送中心配送车辆数量固定，型号相同，并且每个配送车辆的容量确定。为对建立的模型进行简化，需要考虑以下几个约束条件：配送车所载货物的质量或体积不得超过核定容量或载质量；货物在时间窗之外的时间送达，会受到对应时间惩罚函数的惩罚；配送车辆以固定的速度进行货物配送；每个需求点的货物需求只能由1辆车单次完成；路径优化的目标是使得配送成本最小化。

1.2鲜活农产品变质函数

对于鲜活易腐食品变质的函数，学者们很早便做了研究，结果表明，其函数形式过于复杂，不适合在实际应用中使用。因此，一般采用形式相对简单的指数函数作为鲜活食品的变质函数。变质往往与食品所在环境的温度以及所经历的时间长短有关，变质函数所要表现的就是两者与食品质量之间的关系。考虑到鲜活农产品是通过冷链物流运输的，其温度相对稳定，因此构建如下变质函数：

[JZ（]Q（t）=Qo·K·e-βt。[JZ）][JY]（1）

式中：Qo为鲜活农产品的初始质量；t为鲜活农产品运输所需要的时间；K为鲜活农产品随温度而变质的速度常数，本研究假定进行冷链物流配送是恒温环境，定为常数项1；β为鲜活农产品对于时间的敏感系数，若农产品对时间较为敏感，β的取值相对较小，反之β的取值较大。

1.3时间惩罚函数

为了更加贴合实际，在建立鲜活农产品冷链物流配送模型时，将时间窗加入到模型中进行考虑。时间窗分为软时间窗和硬时间窗，本模型中采用硬时间窗，即在需求点期望时间内送达，那么时间惩罚函数为0；超过期望时间区间，通过惩罚函数来增加成本。时间惩罚函数如下：

[JZ（]Gj=[JB（{][HL（2]M（ETdj-tj）（0

式中：Gj表示在需求点j的时间惩罚费用；M表示时间惩罚的系数；[ETdj，LTdj]表示需求点j的期望送达时间区间；tj表示到达需求点j的实际时间。tj的公式如下：

[JZ]tj=∑[DD（]ni=0[DD）]∑[DD（]mk=1[DD）]xijk（ti+tij+si）。

式中：k表示配送中心车辆的号码；xijk表示车辆号为k的配送车是否能够从需求点i到需求点j；tij表示从需求点i到需求点j的时间；si表示在需求点i卸货的时间。

1.4模型建立

在鲜活农产品变质函数和时间惩罚函数的基础上，建立鲜活农产品冷链物流配送模型，设G=（V，E）表示无向连通图，其中V={vi|i=1，…，N}表示图的顶点集，v0表示起点，每个顶点vi表示1个需求点，E={（vi，vj）vi，vj∈V，且vi≠vj}为边集，每条边（vi，vj）代表2个顶点间有直通道路。对模型中涉及到的变量及含义作如下说明：

m为配送中心所拥有型号相同的配送车辆的数量；n为在城市中需求点的数量，配送中心的编号为0，需求点的编号为1，2，3，…，n；Z为整个配送过程的总成本；dij为需求点i和需求点j之间的距离，i，j=0，1，2，…，n；C0为单位路程运输成本；Gi为在需求点i的时间惩罚费用；gi为需求点i的需求数量；Q为单位车辆的载货量；Qi为车辆k在时间tik上满足需求点i需要从配送中心装载的货量；p为单位数量鲜活农产品的损失价值；yik为车辆k是否到达需求点i。Qi=gi/（K·e-βtik）。

模型将鲜活农产品冷链物流配送的成本作为目标函数，成本主要由3个部分组成，分别是配送的运输成本、时间惩罚费用以及鲜活农产品的损失价值，具体如下：

式（4）表示需求点i是否可以到达需求点j；式（5）表示车辆k是否配送到需求点i；式（6）表示每辆车的配送量不能超过其最大装载量；式（7）表示每个需求点都有1辆车进行配送；式（8）和式（9）表示到达以及离开某个需求点的车辆有且只有1辆。

2人工蜂群算法（ABC）

2.1基本原理

人工蜂群算法是Karaboga在2005年提出的一種新型智能优化算法。在人工蜂群算法中，通过引领蜂、跟随蜂、侦查蜂3种角色的蜜蜂配合以及角色的转换来获得最优的食物源。而食物源的位置对应着优化问题的可能解，蜂群在食物源的收益度代表所优化问题的适应度。

算法开始，会随机产生有N个解的初始种群，并且每个解Xi（i=1，2，…，N）都是1个D维的向量。随后，引领蜂记住最优解，在食物源的邻域进行搜索，初始化后，3种蜜蜂循环搜索，搜索公式如下：

分别为第j维分量的最大值、最小值。

2.2求解路径优化的人工蜂群算法

2.2.1构造食物源编码

经典的人工蜂群算法，对于食物源的编码采用的是实数编码方式，这在鲜活农产品配送路径优化问题中显然是不可行的，配送中心进行配送的需求点是分散的，因此需要对编码方式重新考虑。本研究对需求点采用自然数的编码方式，则1条可行的食物源可以表示成（0，r11，r12，…，r1n；0，r21，r22，…，r2u；0，…；0，rm1，rm2，…，rmv）。此食物源表示第1辆车从配送中心出发，到达需求点r11，r12，…，r1n后返回配送中心；第2辆车从配送中心出发，到达需求点r21，r22，…，r2u后返回配送中心；……；第m辆车从配送中心出发，到达需求点rm1，rm2，…，rmv后返回配送中心。如有3辆车和9个需求点，食物源x=023601789045，表示第1辆车从配送中心出发到达需求点2、3、6后返回配送中心，第2辆车从配送中心出发到达需求点1、7、8、9后返回配送中心，第3辆车从配送中心出发到达需求点4、5后返回配送中心。

2.2.2生成候选食物源

由于在人工蜂群中采用了新的食物源编码方式，因此对候选食物源位置的更新也不能采用式（10）的方式。本研究通过交换邻域点的方法，随机地将食物源中的2个邻域点交换位置来得到候选食物源。以9个需求点和3辆车进行说明，图1表示交换前和交换后的食物源，可见通过交换第3位和第6位的点，可以得到候选食物源。交换前后食物源的变动不大，因此可以保持变换前食物源的众多优良特性；与此同时，随机的位置交换增加了食物源选择的多样性，避免陷入局部最优而得不到全局最优解。

好地对冷链物流配送路径进行优化，为现实中的决策提供有力的支持。

4结论

鲜活农产品的易腐特性，使得通过冷链物流进行运输时的路径选择变得尤为重要[9-10] 。科学的路线规划，不仅能够保证农产品的新鲜度，也能够在满足需求点时间要求的基础上降低运输成本。本研究对鲜活农产品冷链物流配送问题等众多条件进行了抽象定义，建立数学模型，并根据鲜活农产品易腐的特点，将变质函数加入模型；同时引入了时间窗，让所研究的模型更加贴合实际且更加具有研究意义；将人工蜂群算法具体到鲜活农产品冷链物流配送模型上来，对建立的模型进行求解，并通过仿真试验证明了人工蜂群算法对鲜活农产品冷链物流路径优化模型具有有效性和可行性，表明人工蜂群算法对于解决此类问题具有很强的现实意义。

参考文献：

[1]Dantzig G B，Ramser J H. The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[2]Solomon M，Desrosiers J. Time window constrained routing and scheduling problems[J]. Transportation Science，1988，22（1）：1-13.

[3]Brito J，Martínez F J，Moreno J A，et al. An ACO hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints[J]. Applied Soft Computing，2015，32：154-163.

[4]de Armas J，Melián-Batista B. Variable neighborhood search for a dynamic rich vehicle routing problem with time windows[J]. Computers and Industrial Engineering，2015，85：120-131.

[5]Küüko[KG-*5]g[DD（-1*2][HT6]ˇ[DD）]lu I，ztürk N. An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows[J]. Computers and Industrial Engineering，2015，86：60-68.

[6]陈志新，陈方玉，胡贵彦，等. 基于混合粒子群算法的配送车辆复杂路径优化[J]. 物流技术，2014，33（7）：176-178.

[7]邬开俊，王铁君. 基于改进差分进化的车辆路径优化算法[J]. 计算机工程与应用，2013，49（13）：17-20.

[8]向敏，袁嘉彬，于洁. 电子商务环境下鲜活农产品物流配送路径优化研究[J]. 科技管理研究，2015（18）：166-171.

[9]朱金凤，苌道方，林丹萍. 基于成本约束的冷链物流配送网络规划[J]. 江苏农业科学，2015，43（11）：572-575.

[10]李康，郑建国，伍大清. 生鲜农产品冷链物流配送干扰管理研究的思考[J]. 江苏农业科学，2015，43（11）：588-591.endprint