基于改进遗传算法的农产品配送路径优化研究

周建国

[摘要]以第三方物流企业为视角，在保证配送质量最高的情况下，将配送成本最低作为优化目标，构建多目标农产品配送路径优化模型。针对此类NP问题，结合改进的遗传算法，在Matlab2015环境下设计仿真实验。结果表明，改进的遗传算法在解决此类问题时，可行解能够快速收敛到帕累托最优，同时证明了模型和算法的科学性。

[关键词]遗传算法；农产品物流；多目标优化；VRP

[DOI]1013939/jcnkizgsc201801136

1引言

当前，我国农产品流通过程中物流成本过高。一方面，在运输过程中，由于农产品自身的特点使得产品损失率较大，导致货损成本过高；另一方面，由于农产品呈现地域性特点，面对多网点的产地和销售点，传统的凭经验选择配送路线显得太不科学，造成了产品在途时间过长、迂回运输等现象。基于以上背景，文章以第三方物流企业为视角，在保证配送质量最高的情况下，将配送成本最低作为优化目标，构建多目标农产品配送路径优化模型。

文章研究的时间窗约束下的路径优化问题（VRP）属于多目标优化问题，对于这类问题很难用全局搜索法精确求解，目前解决这类问题大多数依靠启发式算法。例如，遗传算法、蚁群算法、粒子群算法、模拟退火算法等。[1]Feng Xu Li通过分析农产品流通的现状，提出一种軟时间窗约束下多类型车辆配送路径优化模型，创新性地考虑了在不同类型的车辆有不同的边际和成本费用，通过遗传算法解决；[2]王飞军等人在分析农产品配送车辆调度问题的基础上，引入蚁群算法解决该问题。实验证明，蚁群算法能够快速收敛到帕累托最优解，研究对于实现车辆合理调度、缩短运输路程、降低运输费用有较大意义。[3]张逊逊等人为了实现农产品配送系统的节能减排，将碳排放量考虑到VRP问题中去，构建碳排放量最低和最短路径决策模型，提出了基于相似性选择的演化算法，最后通过案例仿真验证了所提出算法的科学性。[4]

2多目标VRP优化问题数学模型构建

21货损成本

因为农产品自身的特性，如易变质性、地域性等特点，加上我国冷链不完善、温度的波动以及流通环节中不专业操作等因素，从生产到销售这段时间内产生的货损成本。

22物流满意度

一般而言，将现实中货物在途时间分为两部分，第一部分是客户期望收到货物的时间，这段时间内客户的物流满意度为100%；第二部分是客户在可以接受的时间范围内接收货物，假设在这段时间内，客户的物流满意度与时间呈线性关系。

3VRP问题下改进的遗传算法

GA主要依靠选择、交叉、变异等遗传算子实现种群的优胜劣汰，对于二进制编码的染色体而言，当种群不具多样性，算法易陷入早熟、收敛；对于十进制编码的染色体，面对组合优化问题时，不能在任意基因位交叉染色体，交叉会使得新产生的染色体不是优化问题的解。PGA的遗传操作仅在两条染色体上进行“交叉”为主，在一条染色体上进行变异操作为辅，即通过单个个体繁殖后代，所以称为单亲遗传算法。PGA的选择算子功能和GA无异；不同的是，PGA利用基因重组算子实现了GA的交叉和变异功能。

31基因换位操作[5]

GA主要通过交叉算子实现整个种群的迭代，但使用序数编码时候个别问题不能进行交叉操作，必须使用PMX、OX和CX等特殊的交叉算子。这些特殊的交叉算子操作复杂，并且执行效率不高。所以此处借助另一种遗传算子实现种群的更迭—基因换位算子。PGA的基因换位算子是按一定概率p随机交换染色体中基因位的过程。基因换位可以分为单点换位和多点换位，单点换位一次只交换一对基因位；多点换位是对于预先给定的正整数u，取随机数i（1≤i≤u），一次交换i对基因位。当u取3，i取2，PGA的多点换位操作如下：

R=2 5 8 7 4 1 3 6 9

R′=2 7 8 5 4 9 3 6 1

32编码及解码方案

本文采用十进制编码，0表示配送中心，1，2，3…表示目的地。首先，随机产生一组排列。假设有9个目的地，随机产生326481957的排列，具体编码思路如下：

（1）从左向右依次累计目的地的需求量，一旦累计需求量超过货车的载重量就停止计数，设经过n次累计之后累积量超过货车的载重，记录此时的断点1为n-1，累积量清零。

（2）从排列的第n位开始继续重复第一步，假设再次超过货车载重量时，此时的累计次数为m，记录断点2为n+m-1， 累积量清零。

（3）重复上述步骤直至排列的最后一位，生成断点矩阵。

（4）依据断点矩阵，在排列对应基因位和首末位加上0，编码完成。

33适应度函数[6]

适应度函数（ft）用于评价解集中的个体对于目标函数的优劣性，通常根据实际问题需要设定。在适应度函数的设计方面，常采用将目标函数映射成适应度函数的方法。本文选取（ft）=1/（Zmin+V·q）。V表示惩罚系数。

34算法流程

Step 1：确定编码方案，将待优化问题的潜在解表示成染色体。

Step 2：确定控制参数以及适应度函数。

Step 3：随机产生初始种群。

Step 4：计算种群中个体的适应度值和遗传概率。

Step 5：依据优胜劣汰规则，保留适应值较大的个体，淘汰适应值低的个体。

Step 6：依据选择概率复制最能适应环境的染色体，代替适应值较低的个体，保持种群规模基数不变。

Step 7：依据交叉概率和变异概率对种群重复Step 6。

Step 8：若满足终止条件，输出结果。若不满足重复步骤Step 5～Step 7。

4案例仿真及结果分析endprint

41案例描述

现某第三方物流企业计划从配送中心，坐标（00），向16个目的地配送农产品，配送采用单一型号的货车运输，汽车装载量为55吨，平均车速60km/h，车辆损失的机会成本为每小时15元，延迟费用80元。每天最早出发时间为6：00。单位路程运费率15，产品单位价值80，损失系数005。各网点的具体信息见上表。在Matlab2015程序下进行数值仿真，采用以下参数，选择概率pc=015，改进遗传算法的最大基因换位次数为6，初始种群个数20。

42结果分析

根据上述改进的遗传算法编写C语言程序，在Matlab2015环境下对该数学模型进行300次迭代寻优。在第110代左右时候寻得帕累托最优解。最终配送系统总成本2414575，目的地平均物流满意度为804%。仿真求得6條使配送总成本最低的路径（车辆从配送中心出发，完成对各个目的地的配送之后返回配送中心的过程），分别为，路径一：0-15-14-4-0；路径二：0-2-1-0；路径三：0-16-6-8-0：路径四：0-10-7-3-0；路径五：0-9-13-11-5-0；路径六：0-12-0。适应度函数变化趋势见下图，具体配送方案及时间见表2。

可行解的适应值随迭代次数的进化过程

从种群的进化趋势来看，适应度函数值从30代左右开始逐渐变大，种群中个体对于环境的适应性能力越来越强，每经过一段时间种群的更迭，解集越接近帕累托最优。从适应度的变化可知，曲线多处垂直上升，整体收敛速度较快。在经过110次迭代之后，曲线变化趋于平缓，最终找到帕累托最优解，证明了改进的遗传算法良好的寻优性能。

5结论

本文通过探讨农产品流通环节中的广义物流成本，结合实际情况，采用单一的对农产品配送路径优化从而控制流通成本，将农产品在途时间作为评价第三方物流满意度的标准，建立数学模型。针对多目标优化问题，考虑到模型求解的复杂性，利用改进之后的遗传算法在Matlab环境下对目标函数进行迭代寻优。通过案例证明模型的科学性，同时从适应度函数的变化趋势图证明了算法的可行性。该研究能够满足一定阶段下农产品运输中的路径决策问题，对于降低流通成本具有较大意义。另外，本文的配送系统只考虑单一型号的车辆，有且只有一个配送中心问题，对于多种农产品混合运输问题没有涉及，这都是今后需要研究的方向。

参考文献：

[1]罗勇，陈治亚基于改进遗传算法的物流配送路径优化[J].系统工程，2012（8）：118-122

[2]Feng Xu Li，Yue Fang Yang，Fei Wei，Feng WeiStudy on Multi-Vehicle Refrigerated Distribution of Agricultural Products with Soft Time Windows[J].Applied Mechanics and Materials，2013，2733（438）.

[3]王飞军，吕建新，杨建伟基于蚁群算法的农产品配送车辆调度问题研究[J].中国农机化学报，2014（1）.

[4]张逊逊，许宏科，于加晴融合PM25排放量和运输路程的区域农产品配送路径决策[J].长安大学学报：自然科学版，2017，37（2）：99-106

[5]李茂军，童调生，罗隆福单亲遗传算法及其应用研究[J].湖南大学学报，1998（6）.

[6]雷英杰，张善文，李续武MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2008endprint