基于改进遗传算法的卷烟物流配送线路优化模型构建

0 引 言

配送线路优化是卷烟物流配送工作中的重要环节。随着物流业务的不断发展，推进行业内物流降本增效、个性化配送服务的建立和应急物流保障服务体系的健全成为了烟草行业物流高质量发展过程中亟需解决的重要问题。

本文以R县配送业务作为研究对象，利用DMAIC管理模式开展物流配送线路优化的试点探索，通过有效调整送货线路、控制送货人员的劳动强度和作业时间来保障卷烟物流配送工作高效运行。

1 算法概述

1.1 传统的遗传算法

遗传算法是基于“适者生存”的一种高度并行、随机和自适应的优化算法。它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的逐代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解[1]。相对于一些常规的优化算法，它在求解较为复杂的组合优化问题时通常能够快速获得较好的优化结果。

1.2 改进的遗传算法

遗传算法中起核心作用的就是交叉运算[2]。传统遗传算法的交叉运算是指染色体在遗传过程中，依照一定规则互相交换特定位置的基因信息，从而产生继承父代的大部分信息而又不同于父代的子代染色体[3]。

本文考虑到优化后的配送线路必须涵盖辖区内的所有零售客户，且访销周期调整尽量少的情况，在交叉运算方面做出了一些改变。改进的遗传算法在交叉运算操作中，个体编码路段按照穷举法随机进行交叉重组产生新线路，从而避免了在变异算子作用下对访销周期进行重新调整。图1为改进后的遗传算法概述图。

图1 改进的遗传算法概述图

2 编码方式

2.1 配送线路

配送线路是指某台单独的送货车在一个周期中某天的送货路径。截至2021年3月1日，R县的配送线路共计14条，在每周工作5天的情况下，需要由3个班组来完成配送任务。

2.2 路段

每一条配送线路由不同路段组成，每个路段由连续排列的一部分客户组成。在遗传算法计算的过程中，每条路段被视为单个需要进行交叉重组的染色体。为便于拆分重组，以R县城区一线为例，可拆分为“镇政府”“南环东路（东段）”和“坝厂村”3个路段。如图2所示。

图2 R县城区一线路段分布图

2.3 编码规则

传统遗传算法主要采用二进制方式编码[4]，它使用的编码集是由二进制符号0和1所组成的二值符号集{0，1}。对于一些连续函数的优化问题，其存在连续函数离散化时的映射误差，不利于反映问题的特定知识。改进的遗传算法则参照符号编码方法制定了一套编码规则，通过设立中心点将所有路段按照距离中心点的远近进行取值，具体的编码规则如下。

2.3.1 按距离远近设置一级编码

如城区范围内的路段统一用“1”作为其一级编码，乡镇范围内的路段则按照与城区的距离分别以“2”“3”作为其一级编码。其中，离城区较近的区域，如R县一六镇和桂头近郊（即靠近城区的5公里范围内）的一级编码为“2”；离城区较远的区域，如大桥镇、大布镇，包括桂头圩镇的一级编码为“3”。

2.3.2 按线路位置设置二级编码

将城区和乡镇的具体线路进行分类，并将其区域排列序号作为二级编码。

2.3.3 按路段排序设置三级编码

将每一条线路按不同街道、乡村再划分为1～3个路段，并用“a”“b”“c”等字母作为三级编码。第三级编码仅作为序号使用，不作为距离的判断依据。

3 模型构建

3.1 线路优化原则

3.1.1 就近整合原则

就近整合原则是指在重组路线时，应当按照各路段的编码尽可能地选取临近路段合并为新线路，做到下一个配送路段是距当前配送路段最近且配送较方便的。这样做便于管理和操作，分析编码时只须计算前2位编码。

3.1.2 均衡运力原则

在配送过程中，综合考虑服务零售户数量、单车装载卷烟数量、单车工作时长3种因素，以实现要素均衡。各因素应满足以下条件。

3.1.2.1 服务零售户数量

每条重组之后的新线路，城区零售户数量范围须在90～130户，农网数量则在60～90户。

3.1.2.2 单车装载卷烟数量

依据零售户订单量的大小进行合理调配，城区线路卷烟配送量为4 000～6 000条，农网卷烟配送量为3 000～5 000条。

3.1.2.3 单车工作时长

按照线路长短和耗时、与零售户交接时间以及途经较差道路所导致的送货时间延长，综合计算每条线路的基本工作时长。每条线路的日均送货时长应尽量控制在6～8小时。路线长短、耗时可参照地图导航软件数据，初步预估每户的交接时间约为2.5分钟，途经较差道路所导致的送货时间延长则由送货员人工录入。

3.2 设定适应度函数

适应度函数是评价每个重组线路优劣的函数，是获得最优配送方案的基本依据。本文将各方案的最终得分设置为其中各线路评分的平均值，根据线路优化原则设计评价各线路的适应度函数为。

式中，S指某一线路中各路段接近程度的评分，其评分范围为0～40分。N指与各线路平均户数接近程度的评分，其评分范围为0～40分。T指某一线路中单车装载卷烟数量和工作时长的评分，当两者同时达标时，T=20分，反之T=0分。F为所有方案的最终得分。将方案得分依次排列，大概设置90分（含）以上的为A类方案，80分（含）以上的为B类方案，80分以下的为C类方案。

3.3 运算过程

通过借鉴计算机关于网络IP地址临近关系的计算方法可对各路段的位置信息进行临近程度分析。当人工智能系统收到关于减少线路数量、增加配送任务、增减零售网点等优化请求时，可自动选取临近路段，在不超过单车配送能力的情况下，开展线路优化重组。若需要精简线路时，人工智能程序将会逐条解除线路，解除后的配送经过点将依据户数、配送量与距离等方面的参数要求分别按局部最小代价调整到其他相邻路线。

生成所有新的线路组合方案后，系统将自动根据适应度函数进行横向对比评分。按照适应度函数的判定结果，程序会自动选取出所有A类、B类方案供物流管理人员选择出最优方案后还可用百度地图开放平台对线路细节进行人工微调。

4 基于DMAIC管理模式进行案例应用

本文选定R县物流对接点作为试点区域，并基于DMAIC管理模式对改进的遗传算法进行实践应用。如图3所示。截至2021年3月1日，R县零售客户共822户，配送线路共14条，其中城区有9条线路，乡镇有5条线路。

图3 运用DMAIC管理模式进行案例应用

4.1 D阶段：编码设置

将覆盖辖区内所有零售客户门店的14条线路合理地划分成32个路段，并为各个路段设置运算编码。

4.1.1 R县城区内的路段编码以1开头

以位于城区最东端的物流对接点作为起始位置，其所在的候公渡线路区域的编码为“1.1”，稍临近的鹰峰东、新兴线路区域的编码为“1.2”，城区最远端的鹰峰西、城西区域的编码为“1.5”。具体线路按不同路段进行三级编码，但第三级编码不作为运算编码使用。

4.1.2 乡镇线路则按其所在方向归类编码

其中东南方向包含一六镇、桂头镇共计155户零售客户；东北方向为大桥镇，共计79户零售客户；西南方向则包含了大布镇和洛阳镇2个区域，共计76户零售客户。 表1 为R县卷烟物流配送路段编码及零售客户分布情况。

表1 R县卷烟物流配送路段编码及零售客户分布情况

4.2 M阶段：测量差距

优化前，R县的送货里程为3 296公里，单车日均送货量为51.95户/车，当月累积人均卷烟的配送效率为1 111.85万支/人，低于全市平均水平的385.73万支/人，图4为2021年2月S市各县级直属单位人均卷烟配送效率情况。

图4 2021年2月S市各县级直属单位人均卷烟配送效率

4.3 A阶段：分析条件

根据前文的算法模型，通过分析配送线路的约束条件，对模型中的已知常量进行设置。

条件1：路段临近程度。重组路线时，应按照各路段的编码尽可能地选取临近路段合并为新线路，以便于管理和操作。分析编码时只须计算前2位编码。

条件2：单车配送能力。单车配送能力由服务零售户数量、单车装载卷烟数量和单车工作时长3个指标衡量。表2为单车配送能力指标赋值。

表2 单车配送能力指标赋值

4.4 I阶段：线路优化

4.4.1 实施过程

通过利用模型求解，R县卷烟配送线路由14条优化至9条，其中乡镇线路由4条优化至3条，城区线路由10条优化至6条；配送车辆由3台减少至2台。城区配送线路的具体优化过程如图5-7所示。

图5 2021年3月优化前城区线路分布图示

图6 2021年4月城区线路优化结果

图7 2021年7月城区线路优化结果

4.4.2 利用百度地图开放平台优化增量线路

百度地图开放平台是为开发者开发应用软件而推出的一套应用调用接口；它为用户提供在网站构建时具有交互性的界面、多种数据处理服务和多种服务接口[5]，简化了开发的复杂度，可以为卷烟配送线路优化工作提供最合适的网点地图定位服务。

由于城市化建设步伐加快，卷烟物流配送环境常因网点调整、销量变化、路桥新设、市政维护等原因发生变化，以致配送线路需要进行及时的调整和优化。针对此类情况，只需将变更的零售客户经纬度坐标录入百度地图开放平台，便可及时地对配送线路进行动态优化与调整。图8为R县城区二线配送路径局部图。

图8 R县城区二线配送路径局部图

4.5 C阶段：效果检测

2021年12 月，通过对R县物流对接点的各项物流指标进行验算分析，其送货里程、送货车次、配送费用、日均送货户数和人均配送效率5项指标都有明显的优化提升。如图9和表3所示。

图9 2021年2—9月人均卷烟配送效率趋势图

表3 R县物流配送线路优化测试效果对比统计表

5 结 论

本研究通过对遗传算法的改进，结合DMAIC管理模式对R县配送区域开展试点验证，为卷烟物流配送探索了一种线路优化的新模型，将智能化手段与卷烟物流配送业务进行创新性融合，进一步推动了绿色高效物流体系的建设与完善。未来人们还可利用“卷烟物流配送线路优化模型”解决其他卷烟物流配送问题，如在柔性化配送和跨区域配送方面开展应用，以进一步提升卷烟物流配送效率。