基于遗传算法的鲜奶冷链物流配送路径优化

张培 武忠

摘 要：随着物流领域的不断发展，越来越多的方法可用于解决VRP问题，其中，启发式人工智能算法更是得到了巨大的发展。笔者首先对背景公司的配送现状进行了简要分析，然后分别用节约法和遗传算法对实例进行优化求解并得出结果，其中遗传算法的求解过程是借助Matlab软件实现的。最后，将两种方法求得的结果进行综合比较，发现在同样的条件下，遗传算法能够更好地实现对配送路径的优化。

关键词：车辆路径优化;节约法;遗传算法

中图分类号：F252                      文献标识码：A               文章编号：1008-4428（2018）03-15  -03

一、引言

车辆路径优化问题（Vehicle Routing Problem），简称VRP问题，指的是已知配送中心的位置和客户需求点的位置、需求量，并且已知配送中心所拥有的一定数量的配送车辆的载货量和容量，在满足一定的约束条件前提下，以特定的优化指标（距离最短、时间最短等）为目标，合理安排车辆的配送方案。文章以一鸣真鲜奶吧为背景，对其在杭州市江干区的一鸣真鲜奶吧的配送路径进行优化。

一鸣真鲜奶吧隶属于浙江一鸣食品股份有限公司。浙江一鸣食品股份有限公司主要生产经营与乳制品有关的产品，其打造的泰顺高山牧场的奶源保证了产品的质量。目前，温州地区80%的奶源都由一鸣供应，为了提升奶源的质量，一鸣创建了全方位的牧业管理体系，集牧草种植、牧场管理、乳牛饲养、饲料加工等为一体，并且率先实行了“公司+农户”的生产方法，利用当地劳动力来维持牧场的日常生产，在节省劳动力的同时也带动了当地经济的发展。其采用招商加盟模式运营的一鸣真鲜奶吧由于新鲜的奶源、独特的产品而广受欢迎，店铺已经多达五百多家，利润颇丰。

二、配送存在的问题

（一）车辆路线选择的经验操作性较强

公司的物流长途上主要依赖与其他物流配送公司的合作，而短途配送则是雇有专门的司机，对司机的专业知识水平要求较低，司机每天配送一次，每个司机固定地负责一个区域，由于对时间没有硬性要求，因此他们并不会也无法对配送线路问题进行系统的研究和优化，因此经验操作的成分较高。司机通常会根据自己的经验选择配送路径，他们往往会因为顺路或者距离近而将两家或多家门店归为同一条线路。这种安排的方式常常会由于城市复杂的交通状况而对配送产生较大的不确定性，因此这种方式就配送而言不够科学，甚至经常会出现重叠运输的现象。

（二）对时间约束认识不足

专人负责专区，不存在业务竞争，也没有严格的奖惩制度，只要求上午送到，没有具体的时间约束，就导致司机对工作没有紧张感。另外，车辆由配送中心安排，司机只负责运输，对冷藏车辆的消耗认识不够深刻，缺乏主人翁意识，所以他们通常采用随遇而安的态度对待配送，对不必要的时间和成本消耗视而不见，对时间约束认识不足。

三、公司实际问题描述

该公司共有500多家鲜奶吧，为了便于研究，本文选取了该公司在杭州市余杭区的鲜奶吧进行研究，共9家一鸣真鲜奶吧。为了保证奶制品的质量，契合其经营理念，该公司所有的乳制品都是采用当天配送当天销售的方式，每天鲜奶从生产地温州装车配送，而该公司在杭州地区没有配送中心或中转站，所以鲜奶一般是直接运送到门店。据了解，由于门店需求有限以及牛奶体积较小，杭州市江干区的部分鲜奶吧和余杭区的鲜奶吧由同一辆车配送，司机通常是配送完江干区的再去余杭区进行配送，江干区最后配送的鲜奶吧是计量店，所以将其假定为配送中心，并且假定配送完余杭区的门店之后车辆最后回到配送中心。由于给江干区的门店配送完后是九点，所以给余杭区的门店配送是在九点之后，避开了拥堵高峰期，所以假设道路通畅。配送中心要选择最短路径完成其所有的送货任务。

为了方便求解，为余杭区的9家鲜奶吧进行编号排序（见表1），各个门店之间的距离见表2。

四、节约法求解

（一）根据表2作各点之间的最短距离表（见表3）：

（二）根据表3，利用节约法的基本原理计算出若合并巡回路线，各需求門店之间的可以节约的里程数，作节约里程表（见表4）：

（三）将表4中的节约的路程总数按由大到小的顺序排序，然后作出节约里程排序表（见表5），从而尽量满足总的节约里程数最多的目的。

（四）根据表5，整理得到实例最终的配送路线为：0-7-8-

6-5-4-3-2-9-1-0，该路线的总路程为：11.5+36.7+8.7+1.4+1.5+

1+27.8+13.8+28+7.7=138.1（km）。

五、遗传算法求解

（一）遗传算法结构

先把需要求解的实际问题具体表述成对目标函数的寻优问题，这样需要优化的目标函数就是种群对自然的适应能力，个体的生物种群对应于优化变量，然后从当前的种群出发，复制、交叉、变异和选择产生新一代种群，这个过程是重复的，直到达到进化时间的要求或者找到符合要求的种群，这就是遗传算法优化求解问题的基本思路。其操作过程如下：

1.初始化数值：进化代数的初始值设为t=0，同时确定最大迭代次数T的值，初始种群P（0）随机生成，其中有N个个体。

2.评价个体：由适应度函数的表达式求出每一代种群P（t）中所有个体的适应度。

3.选择操作：根据对种群中个体的适应度的评估，把选择算子作用到种群上。选择运算有两个目标，直接且优秀的个体遗传至子代，或者是遗传由交叉或配对产生的新个体。

4.交叉操作：把交叉算子作用到种群上，这是最核心的算子。

5.变异操作：把变异算子作用到种群上，这是在更改种群中个体串的某一些基因座上的基因值。

6.产生下一代：下一代种群P（t+1）将由种群P（t）经过选择、交叉、变异操作产生。

7.判断终止条件：当t=T时，即达到最大的迭代次数时，则会将进化中获得的有着最大适应值的个体作为最优解输出。

（二）遗传算法特点

遗传算法的具体特点可以概述为如下：

1.与传统算法不同，遗传算法与其最大的差别就是遗传算法是从问题的解集出发的，而非单一的解。从初始解集开始搜索择优，覆盖的范围较大，有利于全局范围内择优。

2.遗传算法在搜索空间中同时评价多个解，即同时对多个个体的适应度进行计算，有效降低了陷入局部范围最优解的风险。

3.遗传算法在运算操作时，基本上只使用通过适应度函数求得的数值来对个体进行评估，而不需要搜索空间的知识或是其他辅助信息。适应度函数自变量的范围，也就是它的定义域可以随便设置，并且不强求函数必须连续可微，此特性大大扩展了遗传算法适用的范围。

4.遗传算法利用概率变迁原则来确定其查找的方向，而非确定性规则。

5.遗传算法的自组织性、自适应性、自学习性使其根据运算过程中得到的信息进行查找时，保证适应度较大的个体有更大的生存下去的可能性，并拥有更能适应自然的基因结构。

6.遗传算法在进化过程中也可以通过自身动态的自适应能力，自动调节算法编码的精度与参数的控制。

（三）Matlab软件

Matlab软件主要是提供了面对交互式程序设计、可视化以及科学计算的高科技的计算环境。它提供了一个方便使用的视窗环境，其中融合了矩阵计算、数值分析和Matlab软件主要是提供了面对交互式程序设计、可视化以及科学计算的高科技的计算环境。它提供了一个方便使用的视窗环境，其中融合了矩阵计算、数值分析和非线性动态系统的建模和仿真等功能，为科研、工程设计等很多科学领域提供了完备的处理方案，并且可以说是跳出了以往的非交互式程序设计语言的编辑模式，是当前有着先进水平的国际科学计算软件的代表。

在数值计算方面，Matlab在数学方面的科技应用软件中始终处于领先地位，由于其强大的创建用户界面、绘制函数和数据、实现算法、矩阵运算、连接其他编程语言的程序等功能，在图像处理、金融建模设计、信号处理与通讯、信号检测、工程计算、控制设计与分析等领域中都有应用。

（四）仿真求解

通过具体问题的描述，结合实际构建的模型，为了保证求解结果的准确性，本文借助Matlab对该问题进行了仿真，求解最优路径，具体操作过程如下：

打开Matlab通过具体问题的描述，结合实际构建的模型，为了保证求解结果的准确性，本文借助Matlab对该问题进行了仿真，求解最优路径，具体操作过程如下：

1.打开Matlab。

2.新建M文件，编辑代码，设置参数：迭代次数为50，交叉概率为0.7，变异概率为0.02，更新百分比为0.7，设置配送车辆数为1，由于实例中所有需求点都是由同一辆车进行配送，不存在载重限制问题，所以为了方便计算，将车辆的最大载重能力设为10，需求量全部设为0。

3.代码共分为两部分，首先分别编辑选择、交叉、变异部分，最后编辑主程序，程序运行时运行主程序，其中自动调用选择、交叉、变异程序。

4.改变设置参数，比较仿真结果，部分结果见表6：

运行程序，发现经多次反复实验，当初始种群为200时，总里程数最少。

（五）结果分析

由于遗传算法的操作是基于概率而非确定的，所以其运算结果并不是唯一的，这也是其相比于其他方法最大的缺点。并且由上述仿真过程可知，参数的设置会导致仿真结果出现不同，所以使用遗传算法求解具有很大的不确定性，需要多次改变参数设置和反复运行程序才能得到最优解，找到最优路径。

由Matlab软件进行仿真之后的结果显示，使用遗传算法求解案例时，最终的最优配送路径为：0-8-7-5-6-9-3-4-2-1-0，总路程为108.1km。

节约法与遗传算法求解结果见表7。通过对结果的分析比较发现，遗传算法比节约法节省了30km路程，虽然遗传算法具有不稳定性，但是其运算结果总体来说还是由于节约法的，即用遗传算法求出的最优路径下的总路程明显比用节约法求出的要短，说明使用遗传算法可以更有效地解决VRP问题。通过分析对比，可将其运用到实际配送过程中去，将会实现车辆路径选择的科学性。

六、结论

文章调查分析了浙江一鸣食品股份有限公司对杭州市余杭区的鲜奶吧配送的实际情况，并以该区的一鸣真鲜奶吧为例，建立了配送路径最短的数学模型;在相同背景条件下，分别运用节约法和遗传算法对实例进行优化分析，人工智能算法一般需要借助计算机实现，因此在使用遗传算法时，求解是通过Matlab对其仿真而进行的，从而得到了不同方法下的最优解;对两种方法求得的最优结果进行对比分析，发现运用遗传算法求得的结果要优于节约法，今后可将此方法大量运用于同类问题中。

参考文献：

[1]Chen P， Huang H，Dong X Y. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem [J]. Expert Systems with Applications， 2010，37（2）： 1620-1627.

[2]杨丹婷.冷链物流配送路径优化研究[D].大连：大连海事大学，2014.

[3]赵光哲.大学排课问题中的遗传算法设計[J].延边大学学报，2006，32（1）：64-68.

[4]周欣.多学科虚拟样机工具软件集成技术研究与实现[D].南京：南京航空航天大学，2010.

[5]彭敏.基于改进遗传算法的农产品物流配送车辆路径优化研究[D].长沙：长沙理工大学，2009.

作者简介：

张培，女，江苏镇江人，东南大学经济管理学院研究生，研究方向：物流与供应链管理;

武忠，男，内蒙古人，东南大学经济管理学院副教授、博士，研究方向：电子商务。