基于禁忌搜索算法的生鲜农产品冷链物流配送路径优化研究

唐 琼，李 翠，刘石洋

（衡阳师范学院 经济与管理学院， 湖南 衡阳 421001）

一、引言

生鲜农产品具有易腐的特殊性，在配送过程中对时间、环境等要求苛刻，加之现代社会的人们越来越关注产品的品质、对产品的新鲜程度要求越来越高，冷链物流配送越来越受到重视。合理安排冷链物流配送路径，不仅可以降低生鲜产品的配送时间、节约配送里程，而且可以降低配送过程中的货损及能耗损失，节约配送成本，增加客户对配送服务的好感度和满意度。

许多学者对该类问题做了一些研究，娄丹建立考虑固定成本、运输成本、货损成本、惩罚成本和能源成本等五个部分之和的配送总成本最小为目标函数的冷链物流车辆配送路径优化模型，设计了蜂群算法。康凯等构建考虑碳排放的生鲜农产品配送路径优化模型，设计了蚁群算法。张璇在传统生鲜农产品配送路径优化的基础上，结合软硬时间窗约束，考虑配送过程带取送的双向作业模式，建立非线性混合整数规划模型，设计了遗传算法。郑义彬等构建了考虑运输成本、货损成本及惩罚成本之和最小化的优化模型，设计了遗传算法。任腾等构建了运输成本、惩罚成本及碳成本之和最小化的优化模型，设计了蚁群算法。

本文旨在对当前生鲜农产品冷链配送存在的配送路径选择不当、配送时间窗得不到满足、产品腐损率较高等问题的研究，提出配送优化生鲜农产品的路径方案。

二、模型建立

(一)模型假设

某生鲜农产品冷链物流配送中心对多个客户进行生鲜农产品配送，且满足以下条件：(1)每个客户点需求已知，被车辆访问一次。(2)车辆从配送中心出发，完成运输工作后空车返回配送中心。(3)车辆经过任何客户点时的载运量不能大于其最大装载容量。(4)客户有规定的时间窗，若配送达到时间不在客户要求的配送时间窗内，则产生相应的惩罚成本。

(二)成本分析

本文考虑的冷链物流配送成本主要包括运输成本、惩罚成本、货损成本及碳排放成本，目标函数是最小化配送总成本。

参数描述：N：客户点的集合；N：点的集合，包括客户点(用 i 表示)和车场(用 0 表示)；变量 x(0-1 变量)：如果车辆经过点i 到点j，为1，否则为0。Q：车辆的最大装载容量；M：非常大的数；G：用来避免子环的辅助变量。

冷链物流配送的运输成本与运输距离相关，由式(1)计算：

其中：t：车辆从点 i 到点 j 需要的运输时间；v：车辆从点i 到点j 行驶的速度。

如果车辆未在客户i 规定的时间窗[ET,LT]范围内送达货物，将产生惩罚成本。计算公式如下：

其中：T为到达客户点i 的时间；P表示没按客户要求提前将货物送到平均单位时间的惩罚成本；P表示没按客户要求延迟将货物送到平均单位时间的惩罚成本。

考虑与车辆运输时间、车辆门开关次数有关的货损成本，计算公式如(3)：

其中：D：客户点 i 的需求；P：表示单位时间运输造成的货物损失；P：表示单次开门造成的货物损失。

考虑与车辆运输距离、车辆运输速度、车辆载重相关的碳排放成本，计算公式如(4)：

其中：ω：单位碳排放成本；d：车辆从 i 点到 j 点行驶的距离；q：从 i 点行驶至 j 点的车辆载重量；ɑ、β：碳排放成本系数，m∈{0，1，2，3}。

(三)数学模型构建

基于以上描述，构建了生鲜农产品冷链物流配送路径优化数学模型，如式(5)所示，目标函数是最小化车辆运输成本C、惩罚成本C、货损成本C和碳排放成本C之和。

目标函数(4)最小化配送总成本。等式(5-7)确保车辆最多只能访问客户点一次。约束(8)是避免子环条件，确保不出现不经过车场的回路。约束(9)确保车辆上的负荷不能大于车辆的最大装载容量。等式(10)表示车辆到达客户点的时间关系等式。约束(11)确保辅助变量为非负整数。约束(12)定义变量x为二元变量。

三、算法设计

本文使用禁忌搜索求解上述数学模型，具体的流程如Algorithm1。本文采用实数编码，使用交换、插入、2-opt 三种领域算子，每种算子使用独立的禁忌列表(TABU、TABU、TABU)，禁忌长度分别为 l1、l2 和 l3。在该TS 过程中，设s表示初始解，s 表示当前解，s表示当前可搜索到的最优解，TABU、TABU和 TABU表示三个禁忌列表，N(s)表示由当前解s 生成的邻域解的集合，TC(s)表示当前解s 的总惩罚成本，TC(s)表示到目前为止的最小总惩罚成本，ConsIter 表示当前最优解没有改进的连续迭代次数，MaxConsIter 表示当前最优解没有改进的最大连续迭代次数。

四、算例分析

本节采用Matlab2014a 对算法进行编码并求解。采用文[5]中算例验证提出的模型与算法的科学性和有效性。采取1-34 号的数据，包括点坐标、需求量及客户服务时间窗信息，其中配送中心为编号1，2-34 为客户点。本文问题参数中设置如下：Q=15；P=3；P=2；P=10；P=10；ω=1；ɑ=1.576；ɑ=17.6；ɑ=0.00117；ɑ=36.067；ɑ=10；β=1。

本文设计的禁忌搜索算法中的参数设置如下：l=l=l=20；ConsIter=500，MaxConsIter=100。

图1 最优配送路径

图2 总成本收敛情况

利用禁忌搜索算法进行计算，对应的最优配送路线如图1 所示，总成本为40403.71，算法求解时间为1.6s。图2 为总成本收敛迭代曲线，从图2 可以看出，迭代超过50 次后，曲线基于平稳，逐渐收敛域最优值。

通过算例分析，可以看出本文设计的禁忌搜索算法可以快速地规划最优路线，同时算法也可以快速收敛到最优解。

五、结语

本文对生鲜农产品冷链物流配送各部分成本进行分析，以运输成本、惩罚成本、货损成本及碳排放成本最小为目标建立了生鲜冷链物流配送路径优化模型，并设计了禁忌搜索算法对模型求解，通过算例分析验证了模型与算法的科学性，可以为冷链配送路径优化问题决策提供理论依据。