烟草行业配送线路优化方法、系统、设备及介质与流程

1.本发明涉及烟草物流规划技术领域，具体地说是一种烟草行业配送线路优化方法、系统、设备及介质。


背景技术：

2.目前在烟草行业进行配送线路优化时，一般直接通过采集零售户的位置信息、仓库的位置，结合电子地图的道路等信息和送货车辆装载情况，使用各种车辆路径算法来对送货线路进行划分和调整。但通过这种方式进行的线路优化，一方面无法提前了解现有模式下配送线路所具备的优化空间，导致优化后无法达到预期的效果，有时甚至出现优化后反而增加送货成本及效率降低的情况；另一方面由于电子地图数据存在更新滞后的情况，往往优化后的结果与实际情况不符合，最终导致优化结果失败，从而浪费了大量的人力和财力。
3.故如何规划配送线路，减少配送里程，缩短配送时长，提高工作效率是目前亟待解决的技术问题。


技术实现要素：

4.本发明的技术任务是提供一种烟草行业配送线路优化方法、系统、设备及介质，来解决如何规划配送线路，减少配送里程，缩短配送时长，提高工作效率的问题。
5.本发明的技术任务是按以下方式实现的，一种烟草行业配送线路优化方法，该方法是以启发式机器学习为基础，结合烟草物流终端配送，达到优化访销周期、优化线路分布以及优化烟草配送顺序的目的；具体如下：
6.通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间尽量平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；
7.通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。其中，tsp指的是“旅行商问题”(traveling salesman problem)，是一种经典的组合优化问题，通常被描述为：一个旅行商想要在多个城市之间旅行，每个城市之间的距离是已知的，旅行商想要找到一条路线，使得他只经过每个城市一次，最终回到起点，并且总路程最短。
8.作为优选，通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域具体如下：
9.生成随机质心：对k-means算法进行改进，即改进初始聚类中心的选定方法；
10.定义目标约束：第一层约束聚类算法的线性规划模型具体为：设中转站配送区域
下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为li；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；
11.以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：
[0012][0013]
目标函数具体如下：
[0014][0015]
约束条件具体如下：
[0016][0017]
其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；
[0018]
公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；
[0019]
公式(3)表示各子区域配送量不超过各区规定配送量上下界；
[0020]
公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；
[0021]
公式(5)表示每个零售户决策变量；
[0022]
线性规划求解：对k-means算法进行改进，即在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到较近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总距离最小；
[0023]
最优解归属：第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解，以解决分区边缘交叉问题，从而使得分区边缘更加平滑，减少交叉现象；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；同时，该算法也可以根据实际应用场景的需求，调整选择最优分区解的原则，如选择分区边缘长度最小的解等；
[0024]
聚类结果：通过第一层约束聚类算法将样本零售户划分成k个配送区域。
[0025]
更优地，改进初始聚类中心的选定方法具体为：
[0026]
确定一个聚类中心距离阈值并初始化聚类中心；
[0027]
计算聚类中心两两之间的距离；
[0028]
判断聚类中心间最小距离是否大于聚类中心距离阈值：
[0029]
若是，则以当前生成的聚类中心作为初始区域中心；
[0030]
若否，则重新生成，直到得到满足要求的聚类中心。
[0031]
作为优选，通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，在返回站点具体如下：
[0032]
定义路网矩阵：第二层求解tsp是基于道路距离路网矩阵完成；
[0033]
定义目标约束；
[0034]
最小弧路径算法求解初始解：使用最小弧路径算法从路线“开始”节点开始，将该节点连接到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，类似于贪婪算法，自顶向下，逐步迭代，具有算法简单，耗时短的特点，进而确定配送线路的大致方向；
[0035]
引导式本地搜索启发式算法求最终解：使用引导式本地搜索启发式算法(gls)，采用元启发式算法求解车辆路线，元启发式算法是一种位于局部搜索算法之上以改变其行为的方法，引导式本地搜索启发式算法在搜索期间建立惩罚，引导式本地搜索启发式算法使用惩罚帮助局部搜索算法摆脱局部最小值和
‘
高原’，
‘
高原’指的是函数的局部最小值区域或平坦区域。在这些区域中，函数的梯度(或导数)接近于零，导致局部搜索算法可能会停留在这些区域，无法进一步探索更好的解决方案；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚存在于该解决方案中的所有那些具有最大效用的特征(通过增加特征的惩罚)，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表。
[0036]
更优地，定义路网矩阵具体如下：
[0037]
把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息，有效避免了道路拥堵、恶劣天气、周期性集市等不确定因素对运算结果的影响；路网矩阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更。
[0038]
更优地，定义约束目标具体如下：
[0039]
设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；
[0040]
以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：
[0041][0042]
目标函数具体如下：
[0043][0044]
约束条件具体如下：
[0045][0046]
其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；
[0047]
公式(2)表示任一点都会被途径，且只经过一次；
[0048]
公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；
[0049]
公式(4)表示防止线路中出现孤立子环；
[0050]
公式(5)表示决策变量取值。
[0051]
一种烟草行业配送线路优化系统，该系统包括配送区域划分单元和配送路顺获取单元；
[0052]
配送区域划分单元用于通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间尽量平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；
[0053]
配送路顺获取单元用于通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。
[0054]
作为优选，所述配送区域划分单元包括随机质心生成模块、目标约束定义模块一、线性规划求解模块、最优解归属模块以及聚类结果模块；
[0055]
随机质心生成用于确定一个聚类中心距离阈值并初始化聚类中心，并计算聚类中心两两之间的距离，进而判断聚类中心间最小距离是否大于聚类中心距离阈值：若是，则以当前生成的聚类中心作为初始区域中心；若否，则重新生成，直到得到满足要求的聚类中心；
[0056]
目标约束定义模块一用于利用第一层约束聚类算法的线性规划模型定义约束条件，具体为：设中转站配送区域下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为li；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；
[0057]
以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：
[0058][0059]
目标函数具体如下：
[0060][0061]
约束条件具体如下：
[0062][0063]
其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；
[0064]
公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；
[0065]
公式(3)表示各子区域配送量不超过各区规定配送量上下界；
[0066]
公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；
[0067]
公式(5)表示每个零售户决策变量；
[0068]
线性规划求解模块用于在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到较近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总距离最小；
[0069]
最优解归属模块用于根据第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解，以解决分区边缘交叉问题，从而使得分区边缘更加平滑，减少交叉现象；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；同时，该算法也可以根据实际应用场景的需求，调整选择最优分区解的原
则，如选择分区边缘长度最小的解等；
[0070]
聚类结果模块用于通过第一层约束聚类算法将样本零售户划分成k个配送区域；
[0071]
所述配送路顺获取单元包括路网矩阵定义模块、目标约束定义模块二、初始解求解模块以及最终解求解模块；
[0072]
路网矩阵定义模块用于把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息，有效避免了道路拥堵、恶劣天气、周期性集市等不确定因素对运算结果的影响；路网矩阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更；
[0073]
目标约束定义模块二用于设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；
[0074]
以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：
[0075][0076]
目标函数具体如下：
[0077][0078]
约束条件具体如下：
[0079][0080]
其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；
[0081]
公式(2)表示任一点都会被途径，且只经过一次；
[0082]
公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；
[0083]
公式(4)表示防止线路中出现孤立子环；
[0084]
公式(5)表示决策变量取值；
[0085]
初始解求解模块用于使用最小弧路径算法从路线“开始”节点开始，将该节点连接
到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，类似于贪婪算法，自顶向下，逐步迭代，具有算法简单，耗时短的特点，进而确定配送线路的大致方向；
[0086]
最终解求解模块用于采用元启发式算法求解车辆路线，元启发式算法是一种位于局部搜索算法之上以改变其行为的方法，引导式本地搜索启发式算法在搜索期间建立惩罚，引导式本地搜索启发式算法使用惩罚帮助局部搜索算法摆脱局部最小值和
‘
高原’；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚存在于该解决方案中的所有那些具有最大效用的特征(通过增加特征的惩罚)，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表；其中，最优路径有序列表包括k个配送线路以及每个配送线路配送的顺序，完成线路规划的内容。
[0087]
一种电子设备，包括：存储器和至少一个处理器；
[0088]
其中，所述存储器上存储有计算机程序；
[0089]
所述至少一个处理器执行所述存储器存储的计算机程序，使得所述至少一个处理器执行如上述的烟草行业配送线路优化方法。
[0090]
一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，所述计算机程序可被处理器执行以实现如上述的烟草行业配送线路优化方法。
[0091]
本发明的烟草行业配送线路优化方法、系统、设备及介质具有以下优点：
[0092]
(一)本发明针对一个烟草物流送货部，计算出多个配送线路，线路之间平滑无交叉，且零售户数量、配送量相对均衡，使得各个配送人员工作量平衡；
[0093]
(二)本发明使用启发式算法，计算出每个配送线路的具体配送顺序，驾驶员比之间送的更顺，配送时长更短，提升工作效率，同时优化路顺使得配送距离更短，节省燃油费用，减少碳排放；
[0094]
(三)本发明建立在烟草物流终端配送的业务场景下，利用网络地图路网数据，基于启发式机器学习科学合理的规划配送线路，减少配送里程，缩短配送时长，提高驾驶员和送货员的工作效率，节省燃油费用，减少碳排放；
[0095]
(四)本发明将基础数据、道路数据、参数约束输入，经过第一层约束聚类算法得到若干配送区域，通过第二层求解tsp得到最优配送路顺，最终输出最优路径有序列表，实现科学合理的配送线路规划，提高配送效率；
[0096]
(五)本发明使用带有约束的改进k-means聚类算法划分烟草物流终端配送区域，通过设置初始聚类中心选择阈值和约束条件，使得样本零售户到所属聚类中心的总距离最小，提高路径规划效率；
[0097]
(六)本发明使用两阶段启发式算法规划烟草物流终端配送路顺，第一阶段采用近似算法求取大的配送方向，第二阶段采用元启发式算法得到最终路顺，提高线路规划的准确性和效率。
附图说明
[0098]
下面结合附图对本发明进一步说明。
[0099]
附图1为烟草行业配送线路优化方法的示意图。
具体实施方式
[0100]
参照说明书附图和具体实施例对本发明的烟草行业配送线路优化方法、系统、设备及介质作以下详细地说明。
[0101]
实施例1：
[0102]
如附图1所示，本实施例提供了一种烟草行业配送线路优化方法，该方法是以启发式机器学习为基础，结合烟草物流终端配送，达到优化访销周期、优化线路分布以及优化烟草配送顺序的目的；具体如下：
[0103]
s1、通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间尽量平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；
[0104]
第一层约束聚类算法使用带有约束的改进k-means聚类算法。k-means算法基本思想是选取k个数据对象作为初始聚类中心，通过迭代把数据对象划分到不同的簇中，使簇内部对象之间的相似度很大，簇之间对象的相似度很小。
[0105]
s2、通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。
[0106]
本实施例步骤s1中的通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域具体如下：
[0107]
s101、生成随机质心：对k-means算法进行改进，即改进初始聚类中心的选定方法；
[0108]
s102、定义目标约束：第一层约束聚类算法的线性规划模型具体为：设中转站配送区域下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为li；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；
[0109]
以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：
[0110][0111]
目标函数具体如下：
[0112][0113]
约束条件具体如下：
[0114][0115]
其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；
[0116]
公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；
[0117]
公式(3)表示各子区域配送量不超过各区规定配送量上下界；
[0118]
公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；
[0119]
公式(5)表示每个零售户决策变量；
[0120]
s103、线性规划求解：对k-means算法进行改进，即在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到较近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总距离最小；通过这种基于线性规划的方法，可以有效地解决k-means算法中初始聚类中心选择的问题，同时也可以使得聚类结果更加准确和稳定；
[0121]
s104、最优解归属：第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解，以解决分区边缘交叉问题，从而使得分区边缘更加平滑，减少交叉现象；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；同时，该算法也可以根据实际应用场景的需求，调整选择最优分区解的原则，如选择分区边缘长度最小的解等；
[0122]
s105、聚类结果：通过第一层约束聚类算法将样本零售户划分成k个配送区域。
[0123]
本实施例步骤s101中的改进初始聚类中心的选定方法具体为：
[0124]
s10101、确定一个聚类中心距离阈值并初始化聚类中心；
[0125]
s10102、计算聚类中心两两之间的距离；
[0126]
s10103、判断聚类中心间最小距离是否大于聚类中心距离阈值：
[0127]
①
若是，则以当前生成的聚类中心作为初始区域中心；
[0128]
②
若否，则重新生成，直到得到满足要求的聚类中心。
[0129]
本实施例步骤s2中的通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，在返回站点具体如下：
[0130]
s201、定义路网矩阵：第二层求解tsp是基于道路距离路网矩阵完成；
[0131]
s202、定义目标约束；
[0132]
第二层求解tsp包含两个阶段，第一阶段采用近似算法求取初始可行解，第二阶段采用元启发式算法得到较优的局部最优解；两阶段本地搜索算法能够缩短寻优时间，在提高求解收敛速度的同时，并保持全局最优的优化方向，从而得到更加优良的结果；两阶段本地搜索算法，也非常符合烟草物流终端配送实际的配送思路，即先确定大的配送方向，再沿着大方向完成周围零售户的配送；
[0133]
s203、最小弧路径算法求解初始解：使用最小弧路径算法从路线“开始”节点开始，将该节点连接到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，类似于贪婪算法，自顶向下，逐步迭代，具有算法简单，耗时短的特点，进而确定配送线路的大致方向；
[0134]
s204、引导式本地搜索启发式算法求最终解：使用引导式本地搜索启发式算法(gls)，采用元启发式算法求解车辆路线，元启发式算法是一种位于局部搜索算法之上以改变其行为的方法，引导式本地搜索启发式算法在搜索期间建立惩罚，引导式本地搜索启发式算法使用惩罚帮助局部搜索算法摆脱局部最小值和
‘
高原’；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚存在于该解决方案中的所有那些具有最大效用的特征(通过增加特征的惩罚)，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表。
[0135]
本实施例步骤s201中的定义路网矩阵具体如下：
[0136]
把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息，有效避免了道路拥堵、恶劣天气、周期性集市等不确定因素对运算结果的影响；路网矩阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更。
[0137]
本实施例步骤s202中的定义约束目标具体如下：
[0138]
设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；
[0139]
以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：
[0140][0141]
目标函数具体如下：
[0142][0143]
约束条件具体如下：
[0144][0145]
其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；
[0146]
公式(2)表示任一点都会被途径，且只经过一次；
[0147]
公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；
[0148]
公式(4)表示防止线路中出现孤立子环；
[0149]
公式(5)表示决策变量取值。
[0150]
实施例2：
[0151]
对j省s市22000多户零售户进行配送线路优化，包括以下步骤。
[0152]
(1)对s市烟草物流配送中心、各中转站、22000多户零售户进行坐标点采集和校准；
[0153]
(2)使用高德服务对s市烟草物流站点和零售户进行路网矩阵计算；
[0154]
(3)根据s市弹性大线路的配送模式，使用第一层约束聚类方法，将s市送货部划分为5个片区，对应每周5个访销周期；
[0155]
(4)使用第二层启发式求解tsp算法，对每个片区串一条大线路；第一阶段规划出大致配送方向，第二阶段算出具体配送顺序；
[0156]
(5)将规划好的配送线路，导入到配送系统，在日常做配送运算业务的时候，按照满载装车划分配送单，供送货员送货使用。
[0157]
实施例3：
[0158]
本实施例中的一种烟草行业配送线路优化系统，该系统包括配送区域划分单元和配送路顺获取单元；
[0159]
配送区域划分单元用于通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间尽量平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；
[0160]
配送路顺获取单元用于通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点(物流站点包括物流中心、中转站、对接点)出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。
[0161]
本实施例中的配送区域划分单元包括随机质心生成模块、目标约束定义模块一、
线性规划求解模块、最优解归属模块以及聚类结果模块；
[0162]
随机质心生成用于确定一个聚类中心距离阈值并初始化聚类中心，并计算聚类中心两两之间的距离，进而判断聚类中心间最小距离是否大于聚类中心距离阈值：若是，则以当前生成的聚类中心作为初始区域中心；若否，则重新生成，直到得到满足要求的聚类中心；
[0163]
目标约束定义模块一用于利用第一层约束聚类算法的线性规划模型定义约束条件，具体为：设中转站配送区域下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为li；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；
[0164]
以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：
[0165][0166]
目标函数具体如下：
[0167][0168]
约束条件具体如下：
[0169][0170]
其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；
[0171]
公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；
[0172]
公式(3)表示各子区域配送量不超过各区规定配送量上下界；
[0173]
公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；
[0174]
公式(5)表示每个零售户决策变量；
[0175]
线性规划求解模块用于在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到较近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总距离最小；
[0176]
最优解归属模块用于根据第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对
每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解，以解决分区边缘交叉问题，从而使得分区边缘更加平滑，减少交叉现象；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；同时，该算法也可以根据实际应用场景的需求，调整选择最优分区解的原则，如选择分区边缘长度最小的解等；
[0177]
聚类结果模块用于通过第一层约束聚类算法将样本零售户划分成k个配送区域。
[0178]
本实施例中的配送路顺获取单元包括路网矩阵定义模块、目标约束定义模块二、初始解求解模块以及最终解求解模块；
[0179]
路网矩阵定义模块用于把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息，有效避免了道路拥堵、恶劣天气、周期性集市等不确定因素对运算结果的影响；路网矩阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更；
[0180]
目标约束定义模块二用于设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；
[0181]
以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：
[0182][0183]
目标函数具体如下：
[0184][0185]
约束条件具体如下：
[0186][0187]
其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；
[0188]
公式(2)表示任一点都会被途径，且只经过一次；
[0189]
公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；
[0190]
公式(4)表示防止线路中出现孤立子环；
[0191]
公式(5)表示决策变量取值；
[0192]
初始解求解模块用于使用最小弧路径算法从路线“开始”节点开始，将该节点连接到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，类似于贪婪算法，自顶向下，逐步迭代，具有算法简单，耗时短的特点，进而确定配送线路的大致方向；
[0193]
最终解求解模块用于采用元启发式算法求解车辆路线，元启发式算法是一种位于局部搜索算法之上以改变其行为的方法，引导式本地搜索启发式算法在搜索期间建立惩罚，引导式本地搜索启发式算法使用惩罚帮助局部搜索算法摆脱局部最小值和
‘
高原’；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚存在于该解决方案中的所有那些具有最大效用的特征(通过增加特征的惩罚)，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表；其中，最优路径有序列表包括k个配送线路以及每个配送线路配送的顺序，完成线路规划的内容。
[0194]
实施例4：
[0195]
本实施例还提供了一种电子设备，包括：存储器和处理器；
[0196]
其中，存储器存储计算机执行指令；
[0197]
处理器执行所述存储器存储的计算机执行指令，使得处理器执行本发明任一实施例中的烟草行业配送线路优化方法。
[0198]
处理器可以是中央处理单元(cpu)，还可以是其他通用处理器、数字信号处理器(dsp)、专用集成电路(asic)、现成可编程门阵列(fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通过处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。
[0199]
存储器可用于储存计算机程序和/或模块，处理器通过运行或执行存储在存储器内的计算机程序和/或模块，以及调用存储在存储器内的数据，实现电子设备的各种功能。存储器可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序等；存储数据区可存储根据终端的使用所创建的数据等。此外，存储器还可以包括高速随机存取存储器，还可以包括非易失性存储器，例如硬盘、内存、插接式硬盘，只能存储卡(smc)，安全数字(sd)卡，闪存卡、至少一个磁盘存储期间、闪存器件、或其他易失性固态存储器件。
[0200]
实施例5：
[0201]
本发明实施例还提供了一种计算机可读存储介质，其中存储有多条指令，指令由处理器加载，使处理器执行本发明任一实施例中的烟草行业配送线路优化方法。具体地，可以提供配有存储介质的系统或者装置，在该存储介质上存储着实现上述实施例中任一实施例的功能的软件程序代码，且使该系统或者装置的计算机(或cpu或mpu)读出并执行存储在存储介质中的程序代码。
[0202]
在这种情况下，从存储介质读取的程序代码本身可实现上述实施例中任何一项实施例的功能，因此程序代码和存储程序代码的存储介质构成了本发明的一部分。
[0203]
用于提供程序代码的存储介质实施例包括软盘、硬盘、磁光盘、光盘(如cd-rom、cd-r、cd-rw、dvd-rom、dvd-rym、dvd-rw、dvd+rw)、磁带、非易失性存储卡和rom。可选择地，可以由通信网络从服务器计算机上下载程序代码。
[0204]
此外，应该清楚的是，不仅可以通过执行计算机所读出的程序代码，而且可以通过基于程序代码的指令使计算机上操作的操作系统等来完成部分或者全部的实际操作，从而实现上述实施例中任意一项实施例的功能。
[0205]
此外，可以理解的是，将由存储介质读出的程序代码写到插入计算机内的扩展板中所设置的存储器中或者写到与计算机相连接的扩展单元中设置的存储器中，随后基于程序代码的指令使安装在扩展板或者扩展单元上的cpu等来执行部分和全部实际操作，从而实现上述实施例中任一实施例的功能。
[0206]
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

技术特征：
1.一种烟草行业配送线路优化方法，其特征在于，该方法是以启发式机器学习为基础，结合烟草物流终端配送，达到优化访销周期、优化线路分布以及优化烟草配送顺序的目的；具体如下：通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。2.根据权利要求1所述的烟草行业配送线路优化方法，其特征在于，通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域具体如下：生成随机质心：对k-means算法进行改进，即改进初始聚类中心的选定方法；定义目标约束：第一层约束聚类算法的线性规划模型具体为：设中转站配送区域下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为l
i
；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：目标函数具体如下：约束条件具体如下：其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；
公式(3)表示各子区域配送量不超过各区规定配送量上下界；公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；公式(5)表示每个零售户决策变量；线性规划求解：对k-means算法进行改进，即在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总距离最小；最优解归属：第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；聚类结果：通过第一层约束聚类算法将样本零售户划分成k个配送区域。3.根据权利要求2所述的烟草行业配送线路优化方法，其特征在于，改进初始聚类中心的选定方法具体为：确定一个聚类中心距离阈值并初始化聚类中心；计算聚类中心两两之间的距离；判断聚类中心间最小距离是否大于聚类中心距离阈值：若是，则以当前生成的聚类中心作为初始区域中心；若否，则重新生成，直到得到满足要求的聚类中心。4.根据权利要求1所述的烟草行业配送线路优化方法，其特征在于，通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点出发，把对应区域内所有零售户遍历一遍，在返回站点具体如下：定义路网矩阵：第二层求解tsp是基于道路距离路网矩阵完成；定义目标约束；最小弧路径算法求解初始解：使用最小弧路径算法从路线“开始”节点开始，将该节点连接到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，自顶向下，逐步迭代，进而确定配送线路的大致方向；引导式本地搜索启发式算法求最终解：采用元启发式算法求解车辆路线；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚具有最大效用的特征，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表。5.根据权利要求4所述的烟草行业配送线路优化方法，其特征在于，定义路网矩阵具体如下：把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息；路网矩
阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更。6.根据权利要求4所述的烟草行业配送线路优化方法，其特征在于，定义约束目标具体如下：设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：目标函数具体如下：约束条件具体如下：其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；公式(2)表示任一点都会被途径，且只经过一次；公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；公式(4)表示防止线路中出现孤立子环；公式(5)表示决策变量取值。7.一种烟草行业配送线路优化系统，其特征在于，该系统包括配送区域划分单元和配送路顺获取单元；配送区域划分单元用于通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域：以一个烟草物流送货部为基础，把送货部下的零售户划分为若干个区域，同时区域内零售户满足对应的约束条件，使得各子区域内部地理因素的同质性最大，区域之间的异质性最大且区域之间平滑不交叉；其中，约束条件是指销量均衡及数量均衡，通过设置约束条件的上下限实现；配送路顺获取单元用于通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站
点出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。8.根据权利要求7所述的烟草行业配送线路优化系统，其特征在于，所述配送区域划分单元包括随机质心生成模块、目标约束定义模块一、线性规划求解模块、最优解归属模块以及聚类结果模块；随机质心生成用于确定一个聚类中心距离阈值并初始化聚类中心，并计算聚类中心两两之间的距离，进而判断聚类中心间最小距离是否大于聚类中心距离阈值：若是，则以当前生成的聚类中心作为初始区域中心；若否，则重新生成，直到得到满足要求的聚类中心；目标约束定义模块一用于利用第一层约束聚类算法的线性规划模型定义约束条件，具体为：设中转站配送区域下总共有n个零售户，零售户以i表示，i∈{1,2,
…
,n}；需要对中转站配送区域划分m区，各区聚类中心以k表示，k∈{1,2,
…
,m}；零售户i的货物需求量为l
i
；零售户i到聚类中心k的距离为d
ik
；h
low
及h
up
分别表示每个子区域配送户数的下界跟上界；w
low
及w
up
分别表示每个子区域配送量的下界跟上界；以x
ik
为决策变量，表示零售户i是否归属于聚类中心k，公式如下：目标函数具体如下：约束条件具体如下：其中，公式(1)表示所要优化的目标函数，即总体距离成本最小；公式(2)表示各子区域配送户数不超过各区规定配送户数上下界；公式(3)表示各子区域配送量不超过各区规定配送量上下界；公式(4)表示每个零售户都被分配给任一个聚类中心，且只能属于一个聚类中心；公式(5)表示每个零售户决策变量；线性规划求解模块用于在对样本点到聚类簇的分配方法上，采用单纯形法求解线性规划模型，通过不断交换基变量和非基变量的方式逐步优化目标函数，直到达到最优解；最终将样本点分配到近的簇中，在满足各簇约束条件的同时，使得样本点到所属聚类中心的总
距离最小；最优解归属模块用于根据第一层约束聚类算法由内循环跟外循环组成，设定外循环次数为n，表示需要执行n次不同的内循环，即初始化n次不同的聚类中心，内循环是针对每一次生成的聚类中心，不断迭代，直到得到本次循环的最优结果；第一层约束聚类算法采用外循环的方式执行n次，得到n个分区结果；再根据凸包交叉户数最少得原则，选择最优分区解；凸包交叉户数是指分区边缘凸包间的交叉点数，交叉点越少，表示分区边缘的交叉现象越少，分区边缘相对更加平滑；聚类结果模块用于通过第一层约束聚类算法将样本零售户划分成k个配送区域；所述配送路顺获取单元包括路网矩阵定义模块、目标约束定义模块二、初始解求解模块以及最终解求解模块；路网矩阵定义模块用于把所有烟草物流站点和所有零售户都加入到一个点集合，基于位置坐标计算每个点到集合内所有其他点的道路距离，最终拼成一个n
×
n的道路距离路网矩阵；计算道路距离时，采用主流互联网地图的路网数据，及时更新数据，同时在计算时参考实时路况信息；路网矩阵定期更新，更新内容包括新零售户加入矩阵、注销零售户剔除矩阵及修路修桥导致距离变更；目标约束定义模块二用于设中转站配送区域下总共有n个零售户，零售户以i,j表示，i,j∈v；0表示中转站，所有点的集合记为v＝{0,1,2,
…
,n}，所有v-{0}的真子集集合记为点i到点j的距离为d
ij
；以x
ij
为决策变量，表示车辆是否从i行驶到j，公式如下：目标函数具体如下：约束条件具体如下：其中，公式(1)表示所要优化的目标函数，即车辆行驶路径最短；公式(2)表示任一点都会被途径，且只经过一次；
公式(3)表示网络中的流量平衡条件，也即给零售户j配送的车辆，从配送中心或其他零售户到j，配送完后，再从零售户j到配送中心或其他零售户；公式(4)表示防止线路中出现孤立子环；公式(5)表示决策变量取值；初始解求解模块用于使用最小弧路径算法从路线“开始”节点开始，将该节点连接到产生最便宜路线段的节点，再通过迭代添加到路线的最后一个节点实现路线扩展，自顶向下，逐步迭代，进而确定配送线路的大致方向；最终解求解模块用于采用元启发式算法求解车辆路线；当给定的局部搜索算法达到局部最优时，引导式本地搜索启发式算法使用设定方案修改目标函数；当局部搜索算法返回一个局部最小值时，引导式本地搜索启发式算法会惩罚具有最大效用的特征，通过惩罚局部最小值中存在的特征，允许引导局部搜索算法脱离局部最小值，得到最优配送路顺，最终输出最优路径有序列表。9.一种电子设备，其特征在于，包括：存储器和至少一个处理器；其中，所述存储器上存储有计算机程序；所述至少一个处理器执行所述存储器存储的计算机程序，使得所述至少一个处理器执行如权利要求1至6任一项所述的烟草行业配送线路优化方法。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有计算机程序，所述计算机程序可被处理器执行以实现如权利要求1至6中任一项所述的烟草行业配送线路优化方法。

技术总结
本发明公开了烟草行业配送线路优化方法、系统、设备及介质，属于烟草物流规划技术领域，本发明要解决的技术问题为如何规划配送线路，减少配送里程，缩短配送时长，提高工作效率，采用的技术方案为：该方法是以启发式机器学习为基础，结合烟草物流终端配送，达到优化访销周期、优化线路分布以及优化烟草配送顺序的目的；具体如下：通过第一层约束聚类算法获取零售户访销周期，并对零售户访销周期下配送线路进行划分，获取对应的配送区域；通过第二层求解tsp对每一个配送区域求解tsp，从烟草物流站点出发，把对应区域内所有零售户遍历一遍，再返回站点，进而获取配送方向及最终配送路顺。进而获取配送方向及最终配送路顺。进而获取配送方向及最终配送路顺。


技术研发人员：王鑫 王茂基 宗世旺 王乃永 肖瑞 庞信义
受保护的技术使用者：山东浪潮数字商业科技有限公司
技术研发日：2023.07.20
技术公布日：2023/10/11