基于混合遗传算法的农产品物流配送路径优化

罗庆+周军

摘要：农业生产及农业生产资料供应和农产品的合理配送，除了应选择合适的运输方式外，还要确定合理的配送路线和货物的运输量，对于不同的运输条件、组织方法，车辆可以按照不同的配送路线完成农产品及其相关生产资料的配送任务。在构建了农产品及其生产资料的物流配送路径优化数学模型的基础上，提出了基于局部竞争机制的选择小生境技术和自适应调节交叉变异参数方法提高全局收敛性能，然后将带有记忆功能的模拟退火算法与上述改进遗传算法相结合，以提高局部搜索能力，从而构造出一种新的混合遗传算法。经过计算证明，这种混合算法可以在很大程度上解决上述问题，并得到最优解或者近似最优解。

关键词：农业生产；混合遗传算法；小生境技术；模拟退火算法；路径优化；农产品物流配送路线；最短路径；实例验证

中图分类号： TP301.6；F252.14文献标志码： A文章编号：1002-1302（2017）12-0174-04

农产品物流要求高，一是由于农产品与工业品不同，它是有生命的动物性与植物性产品，所以，农产品的物流特别要求“绿色物流”，在物流过程中做到不污染、不变质；二是由于农产品价格较低，一定要做到低成本运行；三是农产品流通涉及到保证与提高农民的收入。因此，农业现代生产和消费是靠物流运输业的发展来实现的，高效、廉价的农业物流配送系统能促使市场竞争加剧，带来生产经营中更多的规模经济效益及产品价格的下降。而农产品运输成本在物流总成本中所占比例非常大，是成本消耗最大的物流活动，约占物流总成本的1/3～2/3。在通常情况下，单位农产品的物流运输成本与运输距离成正比，故农产品配送路线的选择会直接影响运输成本的大小，在农产品配送的过程中尽量避免同一货物在同一路线上的往返，即对流现象的发生，同时也要防止运输迂回的出现。

由于在組织车辆完成农产品配送任务时，通常会存在多种可以选择的配送路线方案，而车辆按不同的运输路线完成同样的运输任务时，其利用效果是不一样的。因此，在满足农产品配送任务要求的前提下，要选择最经济的配送线路。所谓最经济的配送路线，就是在保证配送安全、满足配送服务要求的前提下，运输时间、运输费用最省的路线。由于在一般情况下车辆的行驶时间和运输费用均与配送路程成正比，因此在忽略车辆行驶速度、不同道路条件下车辆运行费用差别的前提下，可以认为配送路径最短的路线是最经济的物流配送线路。

在物流领域中，物流配送的路径优化实际上是一个多项式复杂程度的非确定性（NP）问题，传统的算法在解决这类问题时特别是在配送节点较多的情况下，求解的结果在满意程度上存在一定的不足。而遗传算法作为仿生智能方法，是一种较为有效的全局搜索算法，且具有运算简单、收敛速度快等优点，可以获得物流配送路径的近似最优解或满意解[1-2]，但是由于遗传算法的局部搜索能力不强，最终获取的解的质量并不是很高。为此本研究尝试结合多种算法来弥补遗传算法在这方面的不足，最后给出了实例验证和性能分析，用以证明混合遗传算法的可行性。

1物流配送路径优化数学模型的建立

物流配送路径是指各送货车辆向各个用户送货时所要经过的线路，配送路径合理与否对运输速度、车辆的合理利用和运输费用都有直接的影响。因此，采用科学合理的方法来确定配送路径，是物流管理中非常重要的工作。配送路径的优化目标可以是多种选择的，如果成本与路程相关性较强，而与其他因素的相关性较弱时，可以选择以路程最短为目标。本研究假设只有1个农产品配送中心，多辆汽车向多个农产品配送点送货，每个配送点的坐标和配送量一定，每辆配送车的载质量也是一定的，要求合理安排配送车辆的运行路线，使总运输线路距离最短，根据长期实际工作经验为实现满意的运行路线作出以下设计：

（1）将相互接近的农产品配送点的货物装载在1辆配送车上，且配送路径上的配送点需要量之和不能大于配送车辆的载质量；（2）配送路线从离农产品配送中心最远的停留点开始，一旦确认了最远的停留点之后，配送车辆应一并载上与这个关键停留点相邻的其他配送点的货物，因此要求配送路径不能超过配送车辆的最大行驶距离；（3）每个农产品配送点原则上只能由1辆配送车辆配送，且满足配送点的需求。

假设农产品配送中心有m辆汽车，每辆汽车的载质量为qi（i=1，2，…，m），最大行驶距离为Dm，向N个配送点配送，每个配送点需要货物量为Qi（i=1，2，…，N），且Qi

根据以上假设得如下模型[3-5]：

minZ=∑Ni=0∑Nj=0∑Ml=0cijdijl；（1）

受约束于：

h=<∑Qi/aq>；（2）

∑Ni=0Qiyil≤qil=1，2，…，h；（3）

∑hl=0yil=1，i=1，2，…，N

h，i=0；（4）

∑Ni=0dijl=yjl，j=1，2，…，N，l=1，2，…，h；（5）

∑Nj=1dijl=yjl，i=1，2，…，N，l=1，2，…，h。（6）

式（2）中：h为所需车辆数，辆；<>为上型取整；a为系数，0

由于物流配送的车辆不止1辆，但是在做配送计划时，可以按照区域分解为1辆汽车的配送路径，再将每辆汽车的最优配送路径按区域汇总，即可获得整个物流中心配送的方案。因此，为方便配送路径的优化，本研究主要针对单辆汽车的配送路径进行优化。

2遗传算法概述

遗传算法由美国Michigan大学Holland教授提出，按照“优胜劣汰，适者生存”的原则对目标函数进行优化，其本质是一种高效、并行的全局搜索的方法。

2.1染色体编码

对于路径优化的遗传算法一般采用的是自然数编码[6-7]，实际操作时可以随机生成1组<1的小数，例如采用随机生成函数产生10个小于1的1组染色体：

[0.156 5，0.977 6，0.953 2，0.486 4，0.805 3，0.142 2，0423 3，0.912 2，0.792 5，0.957 8]，再对染色体里的各个基因从小到大或者从大到小进行排列，获取其在数组中的位置数值体，例如上个染色体的信息就变为[6，1，7，4，9，5，8，3，10，2]，笔者可以将数组中的基因个体看作配送点，正好对应10个配送点，可以非常清晰地得到1组解，即1个染色体[8]。

假设用3辆车对10个配送点进行配送，则可以将上述染色体加上4个0作为本研究的路径配送方案，0代表的是物流配送中心。例如染色体为[0，6，1，7，0，4，9，5，0，8，3，10，2，0]表示的配送路径方案：路径1，0—6—1—7—0；路径2，0—4—9—5—0；路径3，0—8—3—10—2—0。共3条配送路径。

2.2适应度函数

在本研究中路径优化目标是配送路径成本最小值，因此将运输成本作为本研究的目标，结合考虑式（3）的约束条件作为运输成本的一部分，即[9]：

Z=∑Ni=0∑Nj=0∑Ml=0cijdijl+H∑hlmax（∑Ni=0Qiyil-qt，0）。（7）

当配送点的需求量大于配送车辆的最大载质量时，H作为惩罚系数，应趋于无穷大，使式（7）成本Z趨于无穷大，表示无解。为了方便计算，本研究设H=2 000 000，再将种群中的个体按照从小到大的顺序排列，最后进入选择操作。

2.3交叉算子

将“2.2”节中的种群按照最佳保留和一定概率进行保留相结合产生新的种群，种群中个体被选中的概率：

ps=b（1-b）u-11-（1-q）T。（8）

式中：b为系数范围≥0～≤0.15；u为第s个个体的排序序号；T为种群大小。

本研究对种群中的个体交叉采用随机交叉方式。例如假设有10个配送点，有2个染色体，其中A为0123045607890，B为0987065403210。先将物流配送中心0去掉，A′=123456789，B′=987654321；再随机产生交叉位置，将父代中间部分放在对方的前面，如果有重复的基因，则删除本身重复的数字，从而产生2个新的染色体[10-11]。例如选择第3位、第7位为交叉点A″=123|4567|89，B″=987|6543|21，修正后，A=6543|123456789，B=4567|987654321；去掉后面相同的数字得到，A=654312789，B=456798321；最终在原有位置重新加载4个0，即最后得到A=06543031207890，B=0456079803210。由此看出，此办法在父代相同的情况下，仍可以产生新的子代。

2.4变异算子

为了保持种群的多样性，避免过早陷入早熟，可以按照一定概率（一般为0～0.001）进行变异操作，实际上是随意交换个体中的2个位置，得到新的染色体C1，具体如下：

C=123|4567|89C1=127452389。

2.5进化结束

判断迭代次数达到预设的代数时，进化结束；否则，将迭代次数加1继续迭代。

2.6算法步骤

步骤1：输入配送点的位置数据，设置种群规模和迭代次数G；

步骤2：生成配送点之间的距离二维矩阵dm×n；

步骤3：随机生成n个染色体，分别为C1{s1′s2′s3′s4′s5′…sn′} 、C2{s1″s2″s3″s4″s5″…sn″}、C3{s1s2s3s4s5…sn}。计算各个染色体的适应度值，再将染色体按照适应度值降序排列[8-9]，此时迭代次数为0；

步骤4：根据交叉概率进行交叉操作；

步骤5：根据变异概率进行随机变异操作；

步骤6：将新一代种群按照适应度值进行升序排序，再选取n个最优个体组成下一代种群；

步骤7：判断迭代次数是否达到G，否则迭代次数加1，转到步骤4；

步骤8：计算结束，得到最优解。

3改进的遗传算法

针对早熟收敛现象，采用基于局部竞争选择的小生境技术，通过自适应调节交叉变异参数，将具有共同特性的基因个体进行交叉，避免了交叉随机性。小生境技术就是将每代个体划分为若干类，从每个类中选出若干适应度较大的个体作为1个类的优秀代表，从而组成1个群[12]，其中选择二进制编码策略如下：

若变量xi∈[uv]，则：

xi=ai+（bi-ai）·∑Lj≠1（gij·2i）/（2L+1-1）。

式中：L为变量xi对应串的长度；gij为第i个变量xi的第j个基因，与n个变量x1→xn相对应的基因串giL构成了1个长串gnL…gnlgn-1L…gn-1l…glL…gll，染色体长度为n·L，按照个体适应度生成m个小生境，在进化过程中，采用评价种群早熟的新指标α，根据以下公式实现自适应调整[13]：

Pc=11+exp（-k1·α）；（9）

Pm=11+exp（-k2·α）+1.0。（10）

式中：k1、k2>0，由于α始终≥0，故Pc的取值范围为0.5～10，Pm的取值范围为0～0.5。

可以看出，在进化过程中交叉变异参数会动态地进行调整，当种群个体有离散趋势时，α变大，则Pc增大，Pm减小；反之，种群个体增强时，α变小，则Pc减小，Pm增大。endprint

4模拟退火操作

为了利于遗传模拟退火混合算法的实现，本研究提出将带有记忆功能的模拟退火算法置于遗传算法中，作为1个独立的算子，对遗传算法经过选择、交叉、变异等步骤产生的新染色体进行模拟退火操作，并记住算法中的最优解，同时，将遗传算法的迭代次数作为模拟退火算法的退火时间。交叉、变异得到新的种群后，在新的种群中每个染色体i的邻域中随机挑选1个染色体模拟退火的概率：

Aij（te）=min1，exp-fj（te）-fi（te）te。（11）

根据模拟退火的概率接受或者拒绝j，其中fj（te）、fi（te）分别为个体i、j的目标函数值。对得到的种群计算目标函数值，找出最小函数值minfi（te）和它对应的最优解f*。

5仿真验证与性能分析

本研究假设有30个农产品配送点需要配送，配送点坐标如图1、表1所示。配送中心坐标为（0，0）。对普通遗传算法、改进遗传算法都取迭代次数为300次，种群大小为100个，按其普通遗传算法交叉概率与变异概率（表2）进行试验。

5.1改进遗传算法比较

根据表2所示参数，种群大小为100个，迭代次数为300

利用普通遗传算法所得最优路径为0—22—21—23—20—28—29—30—28—26—18—13—11—10—12—8—14—

15—16—17—24—25—19—9—1—3—7—6—0，总路程为222 km。

利用改进后的遗传算法所得最优路径为0—2—8—14—19—25—27—20—13—7—4—5—6—16—17—15—18—24—26—28—29—30—23—21—22—11—12—10—9—3—1—0，总路程为190 km。

通过图4、图5可以看出算法迭代的过程，普通的遗传算法一直迭代到250次左右，而改进的遗传算法迭代到80次左右，说明采用基于局部竞争机制的选择小生境技术和自适应调节交叉变异参数方法相结合的遗传算法进化过程比一般遗传算法的进化速度要快170次，而最终的路径优化也比一般遗传算法的要减少32 km配送距离。

5.2模拟退火的混合遗传算法比较

在基于局部竞争机制的选择小生境技术和自适应调节交叉变异参数方法相结合的遗传算法上，加入模拟退火算法进行仿真，初始温度为10 ℃，衰减系数为0.8，得到配送路径如图6所示。

在加入模拟退火后的改进遗传算法基础上得到的最优路径为0—9—10—11—22—21—23—20—27—29—30—28—

26—24—25—19—12—8—7—13—14—15—18—17—16—

6—5—2—4—3—1—0。总路程为184 km，减少配送距离 6 km。从图7可以看出，其迭代次数为35次，比改进的遗传算法减少45次，比普通遗传算法减少215次，大大提高了收敛速度。

6结论

本研究提出了在基于局部竞争机制的选择小生境技术和自适应调节交叉变异参数方法相结合的改进遗传算法上，加入模拟退火算法用于优化农产品物流配送路径，并从组合优化的角度对农产品物流路径优化问题提出解决方案，减少了搜索时间，提高了解空间质量，使混合算法的功效得到了极大提高。

参考文献：

[1]梅家斌. 遗传算法在神经网络权值优化中的应用[J]. 武汉科技学院学报，2001，14（3）：23-25.

[2]Ghoseiri K，Nadjari B. An ant colony optimaztion algorithm for the bi-objective shortest path problem[J]. Applied Soft Computing，2010，10（4）： 1237-1246.

[3]阎庆，鲍远律. 新型遗传模拟退火算法求解物流配送路径问题[J]. 计算机应用，2004，24（增刊1）：261-263.

[4]Pijls W，Post H. A new bidirectional search algorithm with shortened postprocessing[J]. European Journal of Operational Research，2009，198（2）： 363-369.

[5]姜大立，杨西龙，杜文，等.车辆路径问题的遗传算法研究[J]. 系统工程理论与实践，1999，19（6）：40-45.

[6]Amir G S，Ali N M，Saeed P，et al. Application of genetic algorithmfor solving multi-objective optimization problems in robust control of distillation column[J]. International Journal of Advancements in Computing Technology，2011，3（1）： 32-43.

[7]张波，叶家玮，胡郁葱. 模拟退火算法在路径优化问题中的应用[J]. 中国公路学报，2004，17（1）：79-81.

[8]Funke B，Grünert T，Irnich S. Local search for vehicle routing and scheduling problems： review and conceptual integration[J]. Journal of Heuristics，2005，11（4）： 267-306.

[9]刘岩. 带同时取货和送货的车辆路径优化问题研究[D]. 北京：北京交通大学，2009：15-17.

[10]Montemanni R，Gambardella L M，Rizzoli A E，et al. Ant colony system for a dynamic vehicle routing problem[J]. Journal of Combinatorial Optimization，2005（4）： 327-343.

[11]唐坤.车辆路径问题中的遗传算法设计[J]. 东华大学学报（自然科学版），2002，28（1）：66-70.

[12]林焰，郝聚民，纪卓尚，等. 隔离小生境遺传算法研究[J]. 系统工程学报，2000，15（1）：86-91.

[13]孙建永，申建中，徐宗本. 一类自适应遗传算法[J]. 西安交通大学学报，2000，34（10）：84-88.朱振伟，张开飞，李赫，等. 玉米秸秆力学特性的研究[J]. 江苏农业科学，2017，45（12）：178-181.endprint