基于两阶段法的多车型卷烟配送路径优化研究

赵 峰，王 泽，李 轶 ZHAO Feng,WANG Ze,LI Yi

0 引言

目前的卷烟配送线路安排主要有两种模式，一种是通过卷烟配送系统安排线路，另一种是根据人工经验安排线路。据调查，大多数地级市商业性烟草企业在卷烟配送时采取的都是以人工经验为主、系统为辅的配送模式，由于人工安排的线路中其主观性较大，不能根据实际情况综合考虑问题，这对卷烟的配送提出了严峻的挑战，其配送网络布局和路线规划的合理与否直接影响到卷烟的配送效率和成本。因此，就如何合理的规划线路来提高卷烟的配送效率和降低配送成本成为烟草配送急需解决的关键问题。

Tu W等[1]利用基于双层Voronoi图的元启发式算法来解决大规模多车场车辆路径问题（MDVRP）。Wei Td等[2]在针对带时间窗的大规模车辆路径问题（VRPTW） 时，提出了基于时空Voronoi图的启发式方法，从时空Voronoi图导出空间—时间Voronoi距离，以在时空搜索上找到近邻，并提出了一种集成时间扭曲操作的Voronoi距离衰减策略，以加速局部搜索过程。潘国鹏[3]以安阳烟草公司为例，结合安阳烟草公司出现的实际问题，运用先分组后路线的两阶段方法对大规模卷烟配送线路进行优化，先用K-means聚类算法划分配送区域，后对各区域内运用最大最小蚁群算法优化线路。罗勇等[4]提出了基于序的选择算子、最小代价树的交叉算子和随机点长度控制的变异算子的改进遗传算法对物流配送路径进行优化，并通过实例仿真验证了其有效性。任晓智、宾彬超[5]提出了基于聚类分析的卷烟配送路径优化，并给出了具体步骤和求解过程。蒋国清等[6]针对物流配送路径优化问题提出了一种两阶段式的物流配送路径优化方法，即遗传—蚁群结合的路径搜索方法，先通过遗传算法找到问题的初始解，后通过蚁群算法寻找最优方案，通过实例验证其在求解时鲁棒性更强。王力锋等[7]针对传统遗传算法在物流配送路径优化中的不足，提出了一种基于蚁群算法的物流运输快速配送路径规划方法。蒲思睿[8]在解决车辆路径优化问题中引入了GIS，构建了动态的GIS-TSP模型。本文在总结前人的基础上运用两阶段法对卷烟配送路径进行优化，先利用K-means聚类算法对区域进行划分，再考虑工作量均衡的条件下引入遗传算法对区域调整，最后利用混合遗传算法对各配送区域进行线路优化。

1 基于K-means聚类算法对配送区域的划分

本文以Q市雨山、花山两区周三的送货线路为例运用两阶段法对其进行分析，在其既定的服务范围内进行线路优化。由于全市卷烟配送问题具有通性，该区域的优化思路可适当应用到全市。

Q市雨山、花山区周三服务的零售户共有1 088户，其分布如图1所示，其配送路线为11条，其客户分布如图2所示（图中不同颜色的点表示不同的线路上的零售户）。从图2可以看出当前划分的线路间交叉迂回现象较为突出，严重影响了卷烟的配送效率和成本，为提高配送效率，急需对原配送路线进行整合重新规划线路。

图1 客户分布图

图2 各配送路线上客户分布图

（1）K值的确定

由于在卷烟的实际配送中涉及到多种车型，其中涉及到车辆的指派与车型选择的问题，本文利用文献[9]中K值的确定方法确定区域的个数，建立数学模型，运用LINGO软件对模型进行求解，其中v1=5 000，v2=6 000，n1=15，n2=4，Q=42 526，其中最大装载量为5 000条烟的车和6 000条烟的车百公里耗油量分别为10L和11L，每升油价为6.57元/L，可得每公里单位成本c1=0.657元/km，c2=0.7227元/km，模型求解结果为取最大装载量为5 000的车4辆，最大装载量为6 000的车4辆，由此得出q=5 500，即K=8。

（2） 初始聚类结果

利用K-means聚类算法对零售户进行聚类，初始聚类结果如图3所示：

根据图3的聚类结果对聚类后各区域所含的客户数和总需求量进行统计汇总，如表1所示：

图3 初始聚类结果图

表1 聚类后各区域客户数及需求量统计表

2 考虑工作量均衡的区域划分调整

传统的K-means聚类在聚类时仅考虑到客户间的分布密度，并没有考虑到聚类后各区域内需求总量和总里程的限制，不能满足使划分好的区域间工作量均衡的要求，直接影响到卷烟的配送效率。针对上述缺点，本文在传统的K-means聚类的基础上引入遗传算法，先计算K个聚类中心对应聚类内的零售户数、卷烟配送总量Qj和各区域内最大配送里程Lj；将每个聚类内的零售户卷烟配送总量Qj及总配送里程Lj与对应车型的单车最大载货量Qmax及允许配送的最大里程Lmax进行比较：若Qj≤Qmax且Lj≤Lmax成立，则表示聚类后该区域符合约束条件，即将该客户点归入该聚类，否则，将距离该聚类中心最远的客户点弹出，将其纳入与之最近的聚类中并进行条件判断；再选择距该聚类次之的客户点进行条件判断，直至所有区域均调整完毕。

根据上述思路对区域做进一步优化调整，其聚类中心的选取收敛图及各区域的划分图如图4、图5所示。

图4 优化调整后聚类中心收敛图

图5 优化调整后区域划分图

从图4聚类中心的收敛图中可以看出约在45代左右算法达到收敛，即各区域内聚类中心达到稳定状态。图5为优化调整后的区域划分图，将优化后各聚类所含客户数和总需求进行汇总，如表2所示：

表2 各聚类客户数及需求表

从表2中可以看出各区域内的客户数量和总需求量都相对均衡，且车辆利用率较高，区域8有186户，是因为区域8处于市中心地段，客户相对集中，区域3中的客户数为67户，相对较少，是因为区域3离市区较远且客户位置分布较为分散。

3 卷烟配送线路优化模型的建立

（1） 问题描述

烟草物流作为特殊的物流行业，其卷烟的配送路径问题是一种大规模车辆路径问题，属于NP难问题。一般多车辆多服务点的大规模路径优化问题可以分两步进行：①对配送区域划分，②对子区域进行线路优化。故针对多车型的单车辆多服务点配送问题可以描述为：由配送中心针对划分好的区域对K种不同型号的车辆进行合理的调度，选择合适的车型对相应区域内的客户进行服务，各区域内的每个客户必须且仅能由一辆车进行访问，有且仅能访问一次，区域内的客户需求量和总里程不能超过单车的最大核载能力和行驶能力。其中配送中心和各区域内客户点位置、需求量已知，完成配送任务后车辆返回配送中心。

（2） 数学模型的构建

通过对Q烟草公司卷烟配送中心的实地调查和根据现实中的实际配送情况对问题进行适当的抽象和简化，以配送总成本最小为目标建立数学模型。

上述模型中式（1）为卷烟配送路径优化的目标函数，表示配送总成本最小，其中包括运输成本和车辆固定使用成本；式（2）和式 （3）表示每个客户点都由某种车型服务，且仅有一次；式（4）表示所有的配送车辆均从配送中心出发且最终回到该配送中心；式（5）表示一条线路上所有客户间的里程和不能超过配送车辆的最大行驶里程限制；式（6）表示特定车型所负责配送的客户卷烟总量不能超过该车的最大装载量限制；式（7）和式（8）为决策变量的取值范围。

（3） 模型变量说明

n表示客户点集合，n=｛1,2 ,…,n｝；m配送车辆车型集合，m=｛1,2 ,…,k｝；uk表示k型车的数量，k∈m；Lk表示k型车的最大行驶距离；fk表示k型车的固定费用，一般包括车杂费、折旧费、修理费等费用；ck表示k型车的单位行驶费用；qi表示每个客户的需求量，i=｛1,2 ,…,n｝；Qkmax表示k型车的最大装载量；dij表示客户i到客户j间的配送距离，其中，d0j表示配送中心到各客户的配送距离，i,j=1,2,…,n，xijkl和yikl为0、1决策变量，具体表示如下：

4 基于混合遗传算法的卷烟配送线路优化

4.1 混合遗传算法原理

本文提出的遗传—爬山混合算法是针对遗传算法在全局搜索能力较强，而局部搜索能力较弱的基础上嵌入局部搜索能力较强的爬山算法，该算法主要在遗传—变异算子执行后引入爬山算子，利用爬山操作在每代群体中选择最优的个体作为迭代种群进一步迭代寻优找出最优解。嵌入爬山操作的遗传算法能有效地降低其陷入局部最优的缺陷，提高算法的求解性能。

4.2 混合遗传算法的设计与改进

本文针对遗传算法容易出现早熟的缺陷，采用局部搜索能力较强的爬山算法与遗传算法相结合的混合遗传算法对一般遗传算法进行改进，并在算法的交叉和变异操作阶段设计了自适应交叉、变异概率，且结合爬山算法在遗传算法的变异操作基础上引入爬山算子来提高优质的个体被选中的概率，在一定程度上能有效降低遗传算法早熟的缺陷，提高算法的求解性能，具体设计如下：

（1） 染色体编码设计

车辆路径优化问题是一种组合优化问题，本文针对该问题对染色体采用自然数编码。在经过区域划分后，本文直接将配送中心和路径中被访问的客户依次编码成一条染色体，每条染色体对应一条路径，其编码方式如（0 7 6 1 9 4 8 2 5 3 0），其具体表述为：配送中心 （0） →客户 （7） →客户 （6） →客户 （1） →客户 （9） →客户 （4） →客户 （8） →客户 （2） →客户（5） →客户 （3） →配送中心 （0）。

（2） 适应度函数

在遗传算法中适应度的大小是评价个体优劣的重要标志，适应度越大，个体被选中的几率就越大，适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。本文需解决的问题是在卷烟配送时使配送总成本最小，即目标函数值最小，故将目标函数转化为适应度：

式（11）中，Zi表示种群中第i条染色体所对应的的目标函数值，即配送总成本；fi是第i条染色体所对应的适应度，fi越大，被选则的几率就越大。

（3） 选择操作

本文采用轮盘赌选择策略进行选择，为确保种群的多样性，在算法的交叉、变异操作阶段引入自适应的交叉、变异概率对交叉、变异操作做自适应调整。自适应交叉概率pc和pm变异概率函数引用文献[10]。

（4） 交叉操作

本文在混合遗传算法中的交叉操作所采用方法为部分匹配交叉法（PMX）[11]。PMX交叉法与传统的交叉方式有所不同，以染色体A：123456789，B：987654321为例，先在待交叉的两个父代上随机选取两个交叉位，如A：123|4567|89，B：987|6543|21，然后交换交叉区域，将交叉段放在父体的待交叉的首个基因前，如 A′：6543123456789，B′：4567987654321，再删去与该交叉段相同的基因，得到最终染色体，如A′′：654312789，B′′：456798321。

PMX交叉法的优点在于在交叉过程中即使有两个相同的个体存在也同样能通过交叉操作获得新的个体，在增加个体多样性的同时，也在一定程度上降低了早熟现象发生的概率。

（5） 变异操作

为进一步提高种群的多样性和个体的适应度，本文采用的变异方法为利用倒位变异算子对算法执行变异操作，以染色体A：123456789为例，随机选取变异位，如A'：123|45678|9，利用上述算子产生的染色体为A''：123876549。

（6） 爬山操作

本文采用基因换位算子来实现遗传—爬山混合操作，先从父代中随机选择两个基因，交换位置，判断交换后适应度是否增加，若适应度函数值增加，则用该个体替换原个体，重复爬山操作到预设的次数为止。

（7） 终止准则

本文以迭代次数作为终止准则，若算法搜索达到预设的迭代次数时终止迭代，输出最优解，否则迭代次数加1继续迭代，直到满足预设的迭代次数时算法迭代终止，输出结果。

4.3 模型求解

本文运用Matlab实现算法，经过大量的试验不断的对算法参数进行调整，得出的最佳参数组合为：种群大小：40；最大迭代次数：3 000；最大爬山次数：50；交叉概率：pc1：0.8，pc2：0.5；变异概率：pm1：0.2，pm2：0.002。优化结果如表3所示：

表3 路线优化结果表

从表3中线路优化的结果中可以看出优化后共生成8条路径方案，各配送区域内的总里程、总需求及客户数相对均衡，再一次验证了考虑工作量后对区域划分的合理性。鉴于篇幅关系文中不一一列出，此处选区域3的配送线路优化结果作为参考，运行后得出的路径优化图和迭代图如图6、图7所示：

图6 区域3车辆运行路线图

图7 算法迭代图

车辆运行路线如下（其中0表示配送中心）：

0→710→772→771→767→746→769→766→768→734→743→742→723→722→721→727→724→726→725→729→730→728→733→752→748→749→750→762→764→770→712→709→708→706→718→717→719→720→735→739→740→744→741→714→761→763→751→760→756→753→757→747→759→758→755→754→765→707→732→731→736→745→716→737→738→713→715→711→0

4.4 优化效果及对比分析

将优化前与优化后的配送进行对比，如表4所示。

表4 优化前与优化后配送对比表

从表4可以看出，优化后的路径方案比优化前减少3条，配送车辆减少3辆；空载率同比下降25.52%；优化后的配送里程较目前线路同比下降18.71%；优化后配送成本较目前线路成本同比下降25.42%，优化效果明显。

5 结论

本文以卷烟的配送为背景，针对当下烟草企业卷烟配送存在的问题，运用两阶段法对其配送线路进行优化。文章以Q烟草公司为例，先运用K-means聚类算法对配送区域进行划分；再在考虑工作量均衡的条件下加入遗传算法对区域进行调整；最后通过嵌入爬山算法的混合遗传算法对各配送区域进行线路优化，从配送里程、线路数、总成本、车辆数、空载率等指标上两阶段法的配送效果更优。