一种网点智能分区方法与流程

1.本发明属于物流技术领域，具体地说，是涉及一种网点智能分区方法。


背景技术：

2.目前，物流公司存在如下运维及配送痛点：在一个城市范围内配送网点众多，需要将不同网点进行划分后对同一区域网点需求订单进行统一配送调度。但目前网点分区作业主要依赖人工经验，订单量变动后，无法对于分区方案及时进行调整，现存按照区县及线路划分的分区方案不够精细，很难成为最优分区结果。
3.本背景技术所公开的上述信息仅仅用于增加对本技术背景技术的理解，因此，其可能包括不构成本领域普通技术人员已知的现有技术。


技术实现要素：

4.本发明针对现有技术中分区方案不够精细问题，无法最大程度降低运输成本的技术问题。
5.为实现上述发明/设计目的，本发明采用下述技术方案予以实现：
6.一种网点智能分区方法，所述方法为：
7.s1、获取所有仓库和网点，将所有网点划分为独立社区，计算仓库到社区的成本；
8.s2、遍历所有社区，计算将两个社区合并为一个新的社区后所带来的成本变化；
9.s3、在成本不降低时，当前方案为最优分区方案，否则，取成本降低最大的两个社区合并为一个新的网点，进入s1。
10.与现有技术相比，本发明的优点和积极效果是：一种网点智能分区方法，获取所有仓库和网点，将所有网点划分为独立社区，计算仓库到社区的成本；遍历所有社区，计算将任意两个社区合并为一个新的社区后所带来的成本变化；在成本不降低时，当前方案为最优分区方案，否则，取成本降低最大的两个社区合并为一个新的网点，直至确定最优分区方案。本发明将两个社区合并后的成本与合并前的成本相比降低最大的两个社区合并，由于成本的降低是终极需求，因而，本发明能够实现最优分区。
11.结合附图阅读本发明的具体实施方式后，本发明的其他特点和优点将变得更加清楚。
附图说明
12.为了更清楚地说明本发明实施例中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
13.图1-3是本发明所提出的一种实施例的网点分布示意图；
14.图4是本发明所提出的一种实施例的网点智能分区方法的流程图。
15.图5是本发明所提出的一种实施例双层模拟退火算法的流程图。
16.图6是本发明所提出的一种实施例外层sa算法编码示意图。
17.图7是本发明所提出的一种实施例初始解生成算法流程图。
18.图8是本发明所提出的一种实施例外层sa算法自适应扰动算子操作示意图。
19.图9是本发明所提出的一种实施例扰动算子自适应方法流程图。
具体实施方式
20.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
21.在本发明的描述中，需要理解的是，术语“中心”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此，不能理解为对本发明的限制。
22.在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。在实施方式的描述中，具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
23.术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。
24.在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。
25.本发明聚焦于大件物流的城市区配物流场景，主要配送的货物类型是具有良好外包装性质的大家电产品，如冰箱、空调、洗衣机、彩电，此类产品的外包装往往采用标准的长方体箱型包装。区配是指从城市内多个中心配送仓库运送到指定的网点。在这一物流场景中，由于区配网点、订单数量、调度车辆数众多，所以在管理上需要对所有的网点进行分区划片，从而降低管理的复杂度，使得运营管理更加简洁、高效，与此同时，由于分区后每个区域内的网点数量大大降低，这也能降低配车排程规划问题的求解复杂度。然而，分区后由于将整个系统割裂成多个子系统，在每个子系统内规划的最优配送方案从理论上来讲一定不优于在整个系统内规划的最优配送方案。因此，需要设计能够使得整个系统的运输成本最低的分区方案。
26.本发明的核心是在节点分类问题中嵌套了配车排程问题，从而设计使得整个城市运输成本尽可能低的节点分类方案，并设计了针对性的算法进行求解。
27.具体来讲，本发明所解决的问题就是对一个区域内的众多网点进行分区，且保证在这一分区方案下能够尽可能的降低整个区域的车辆运输成本，从而帮助物流企业在降低管理复杂度的同时节约运营成本。
28.与此同时，本发明中所提出的配车排程算法还能够在分区之后解决每个区域内的车辆调度和路径规划问题。
29.一种网点智能分区方法：
30.s1、获取所有仓库和网点，将所有网点划分为独立社区，计算仓库到社区的成本；
31.s2、遍历所有社区，计算将两个社区合并为一个新的社区后所带来的成本变化；
32.s3、在成本不降低时，当前方案为最优分区方案，否则，取成本降低最大的两个社区合并为一个新的网点，进入s1。
33.本实施例的网点智能分区方法采用ffp算法，ffp算法是将fast unfolding算法与配车排程问题dlsa算法相结合产生的一种分区划分算法，兼备有监督和无监督的特性。
34.第一步，初始化。如图1所示，首先将每个网点视为一个片区，并在各个片区上调用配车排程问题dlsa算法，计算当前片区的预期运行成本。之后将各个片区的成本加总，即为该分区方案的总成本。
35.第二步，确定最优合并节点对。如图2所示，该算法将遍历所有相邻节点对，计算若把该相邻节点对合并为一个片区后，所带来的成本变化。若不存在降低成本的相邻节点对合并方案，则当前方案即为最优，算法结束。
36.第三步，合并节点对，更新网点图。如图3，在基于第二步的基础上，取使成本降低最大的相邻节点对，将其合并为一个片区。并将该相邻节点对合并为一个新的网点，取代原来的两个节点，该新网点与其他网点的距离为之前两个节点中与其他网点的最小的距离。跳转回第一步。
37.其中，合并社区后形成的新的网点与其他网点的距离为合并为新的网点的两个社区中与其他网点的最小的距离。
38.例如，合并的节点是1、3，合并后的节点为13,1与2的距离小，则13与2的距离采用1与2的距离，3与4的距离小，则13与4的距离采用3与4的距离。
39.如图4所示，本实施例网点智能分区方法的流程为：
40.开始。
41.输入网点图g1＝{v,e}，v是网点集合，e是所有网点之间的路径集合，应包含两端网点与路径距离信息。
42.将所有网点划分为独立社区s。
43.按社区应用配车排程问题dlsa算法计算成本，得到社区成本集c。
44.在所有社区合并尝试失败时(成本不降低)，输出社区s结束。
45.在所有社区合并尝试成功时(成本降低)，逐社区si尝试与相邻社区{sj}合并，并计算合并后成本{c
ij
}。
46.合并社区si和sj＝argminc
ij
，且使得c
ij
≤ci+cj。
47.更新s和c，继续判断所有社区合并尝试结果。
48.当然，社区合并尝试失败条件也可以是成本降低低于阈值，相应的，社区合并尝试成功条件也可以是成本降低高于阈值。
49.计算仓库到社区成本的方法为配车排程问题dlsa算法。
50.配车排程问题模型构建：
51.本实施例将配车和排程建模为一个双层线性混合整数规划问题。考虑一天内的所有运单需求集o＝∪
i∈i,j∈joij
，其中o
ij
,i∈i,j∈j表示由仓库i调货、送往网点j的运单集。使用给定两类车辆c＝c1∪c2完成该运单集的运输任务，其中c
type
是类型为type的所有车辆
构成的集合，在本问题中type＝1,2分别表示小车和大车。配送中心需要将运单分配到车(配车问题)，然后为每一辆车指定一个调货、送货的路径策略(调度排程)，追求运输成本的最小化。运输成本具体包括距离成本、车辆固定成本、多仓取货成本(每车每到达一个仓库产生一次固定成本，用于衡量司机取货便捷性)、多点送货成本(每车每到达一个网点产生一次固定成本)、以及配送延迟成本(没有按时到达网点产生的延迟成本)。
52.配车问题是一个多任务指派问题。用0-1变量x
o,k
＝1表示第k辆车承运订单o(∈o)，反之则记x
o,k
＝0。记为第k辆车的配车决策变量，即：
53.sk＝1
(0,∞)
(∑
o∈o
x
o,k
),k∈c。
54.取值为1和0分别表示第k辆车至少承运了一个订单和没有承运任何订单。假设运单o产生vo体积单位的运输需求，并且该运输需求不可拆分，必须由一辆车承运，则存在如下容积约束：
55.∑ox
o,kvo
≤volk,k∈c。
56.其中volk为第k辆车的实际容积。由于堆垛方式的限制，另外假设每单位体积的运输需求会产生β单位的空间浪费，则上式应改为：
57.∑ox
o,kvo
(1β)≤volk,k∈c；
58.或等价地：
59.∑ox
o,kvo
≤αvolk,k∈c。
60.其中α＝1/(1+β)为实际装载率，αvolk为第k辆车的可用容积。该问题的成本是两部分的，一部分是使用车辆k带来的固定成本fk(sk)＝fksk，另一部分是由运单任务产生的可变成本
61.进一步假设，
62.即任意来自同一仓库并送往同一网点的运单体积之和小于最大车型的可用容积。从实际问题来看，这一假定是与日常运输场景相符的。并且需要注意的是，显然当一批来自同一仓库并送往同一网点的运单体积之和不小于最大车型的可用容积时，将该批运单分解为若干与最大车型可用容积相当的整批运单和一批较小体积的运单可以求得满意解，其中整批运单由整车运输。因此，可将问题规约成o
ij
均为单点集的情形。
63.排程问题(给定配车方案时)可以建模为经典的tsp问题的变种。对于每一辆货车k，为其指定最优的多仓提货、多点送货方案。首先为其指定初始提货仓，假设全部车辆都从虚拟初始节点出发，则随后其历经的仓库为所有提货仓库。然后基于最小化运输成本(最短距离)目标，选择车辆串联所有网点的运送路径。与传统旅行商问题的区别之处为车辆需要先遍历承运订单中涉及的全部仓库，再对网点进行排程。
64.计算仓库到社区成本的方法为：
65.获取运单信息，提取模型参数；
66.对配车排程问题模型通过双层模拟退火算法进行模型求解，配车排程问题模型包括外层配车模型和内层路径规划模型，双层模拟退火算法包括外层sa算法和内层sa算法；外层sa算法用于求解最优派车方案，内层sa算法用于求解给定派车方案下的最优车辆路径，在外层sa算法中，调用内层sa算法求解当前派车方案的路径成本，用于评估当前派车方
案解的质量，以使得双层模拟退火算法找到运输成本最小的最优的派车方案以及相应的最优路径。
67.外层配车模型为：
68.目标函数：
69.约束条件1：变量逻辑约束
70.约束条件2：满足需求约束
71.约束条件3：车辆容积约束∑
i∈i,j∈j
x
ij,kvij
≤αvolk,k∈c；
72.约束条件4：车辆载重约束
73.约束条件5：0-1变量约束；
74.决策变量x
ij,k
,sk都是0-1变量；
75.内层路径规划模型为：对每个k∈c，
76.目标函数：目标函数：
77.约束条件1：节点决策和边决策变量的逻辑约束约束条件1：节点决策和边决策变量的逻辑约束
78.约束条件(组)2：满足取、送货需求约束
[0079][0080][0081]
约束条件3：出入度平衡约束
[0082][0083]
约束条件4：避免子圈约束
[0084][0085]
约束条件5：时间窗约束
[0086][0087][0088]
ρi≥t
i,p-m(1-z
i,p
)-tli,p∈c,i∈n；
[0089]
其中，ρi衡量了节点i的配送延迟时长；
[0090]
约束条件6：网点可达性约束
[0091]
约束条件7：整数(0-1)约束，x
ij,k
，y
pq,k
，z
p,k
，sk是0-1变量；
[0092]
其中，集合定义：
[0093]
c：车辆集合，c＝c1∪c2；
[0094]
i：：仓库集合；
[0095]
j：：网点集合，j＝j1∪j2，其中j1为所有车型可达网点，j2为仅小型车辆可达网点；
[0096]
参数定义：
[0097]
volk：：第k(∈c)辆车的实际容积；
[0098]
mask：：第k(∈c)辆车的最大载重；
[0099]
velok：：第k(∈c)k辆车的平均在途速度；
[0100]fk
：第k辆车的固定成本；
[0101]ck
：第k辆车的可变成本/单位距离；
[0102]
α：实际装载率；
[0103]vij
：仓库i(∈i)到网点j(∈j)的订单包的体积；
[0104]mij
：仓库i(∈i)到网点j(∈j)的订单包的质量；
[0105]
每车每到一个仓库提货产生的成本；
[0106]
p：每车每到一个网点送货产生的成本；
[0107]
pd：送货迟到产生的成本；
[0108]
ti：仓库i(∈i)平均提货用时；
[0109]
tj：网点j(∈j)平均装卸用时；
[0110]
ρi：网点i的配货延迟时长；
[0111]
tli：节点i(∈i)的时间窗要求；
[0112]
图模型g2(n,a):
[0113]
n:节点集合，n：＝{s}∪i∪j∪{e}，其中s为虚拟初始节点，e为虚拟终止节点；
[0114]
a:有向边集合，a：＝({s}
×
i)∪(i
×
i)∪(i
×
j)∪(j
×
j)∪(j
×
{e})；
[0115]dpq
：边权重，节点p到节点q的导航距离；
[0116]
m:不小于|n|的整数；
[0117]
决策变量：
[0118]
x
ij,k
:第k辆车是否承运由仓库i到网点j的订单包；
[0119]
sk:第k辆车是否承运至少一个订单；
[0120]ypq,k
:第k辆车是否走过由节点p(∈n)到节点q(∈n)的导航路径；
[0121]zp,k
:第k辆车是否经过节点p(∈n{s})；
[0122]
t
p,k
:第k辆车到达节点p的时间；
[0123]up,k
:对应第k辆车和节点p(∈n)的虚拟变量。
[0124]
问题合并：对外层配车模型和内层配车模型引入中间变量gk，形成线性混合整数规划模型：
[0125]
min
x,s,y,z,u
∑
kfk
sk+∑
kgk
；
[0126][0127][0128][0129]
∑
i∈i,j∈j
x
ij,kvij
≤αvolk,k∈c；
[0130][0131]
[0132][0133][0134][0135][0136][0137][0138]
ρi≥t
i,p-m(1-z
i,p
)-tli,p∈c,i∈n；
[0139]
x,y,z,s∈{0,1}。
[0140]
下面对配车排程问题dlsa算法进行说明：
[0141]
本实施例考虑的配送场景与常见的车辆路径优化问题不同，车辆调度中心首先需要进行派车工作，即确定“仓库-网点”运单集与车辆之间的对应关系，才能够为每辆车进行路径排程。由于该问题的特殊性，本实施例设计了一类同时考虑派车工作与排程工作的双层模拟退火算法(dlsa算法)，用于模型求解，并为智能分区算法提供决策支持，算法的整体框架设计如图5所示。
[0142]
dlsa算法的大致思路如下：外层sa算法用于求解最优派车方案，内层sa算法用于求解给定派车方案下的最优车辆路径；在外层sa算法中，需要调用内层sa算法求解当前解(派车方案)的路径成本，用于评估当前派单方案解的质量，以保证dlsa能找到接近全局最优的派车方案以及相应的最优路径。下面将主要介绍dlsa算法的关键技术细节：模拟退火算法接受新解准则、外层sa算法编码、外层sa算法生成初始解方法与外层sa算法自适应扰动算子；内层sa算法采用的算法编码、生成初始解方法(贪心算法)以及扰动算子(2-opt/3-opt/swap)已广泛应用于相关研究中，此处不再赘述。
[0143]
1、模拟退火算法与metropolis原则
[0144]
模拟退火算法在求解车辆调度与排程问题上的有效性已经得到了充分证明。该算法是是一类基于monte-carlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在求解空间中随机寻找目标函数的全局最优解，即在能概率性地跳出局部最优并最终趋于全局最优。
[0145]
相较于传统的爬山算法，模拟退火算法的优势在于可以一定程度上地避免陷入局部最优，这是基于metropolis原则迭代的结果，即以一定概率接受劣解，从而跳出局部最优。metropolis原则的具体操作机制可表达如下。
[0146]
当前外层sa算法中温度为t，初始解sol的目标函数值为obj，迭代产生新解sol_new的目标函数值为obj
′
，若obj
′
＜obj，则接受新解，令sol＝sol
′
；若obj
′
≥obj，则以概率p＝e-(obj
′‑
obj)/t
接受新解，随着温度t的下降，接受劣解的概率不断下降，算法逐渐收敛。
[0147]
2、外层sa算法编码
[0148]
外层sa算法用于求解派车问题，即确定车辆与“仓库-网点”运单集(运单集概念参
见第四章第3节)之间的对应关系，每个“仓库-网点”运单集由一辆车完成，每辆车可以完成多个“仓库-网点”订单的配送任务。结合上述问题特点，派车问题的解可以采用图6所示进行编码，以图中车辆1为例，就代表当前解派给车辆1仓库a到网点1、仓库b到网点1、仓库c到网点3共三个运单集的配送任务。
[0149]
3、外层sa算法生成初始解方法
[0150]
外层配车模型生成初始解的方法为：在单仓提货的前提下，选取距离最近且有订单任务的网点，再从当前网点出发，选取距离最近且有订单任务的网点，直到达到第一类型车辆运载的体积上限，将所选取的网点订单打包派给所述第一类型车辆，在单个运单集体积大于第一类型车辆运载体积时，安排第二类型车辆，第二类型车辆的运载体积大于第一类型车辆。
[0151]
本实施例是基于贪婪思想生成初始解的算法，其算法流程图如图7所示。初始解生成的核心思想是：在单仓提货的前提下，从一个仓库出发，选取距离最近且有订单任务的网点，再从当前网点出发，选取距离最近且有订单任务的网点，直到达到小车运载的体积上限，将所选取的网点订单打包派给一辆小车。对于单个运单集体积大于小车运载体积但小于大车运载体积的情况，如果网点允许大车通行，直接安排一辆大车进行装载，否则安排两辆小车进行装载；对于单个运单集体积大于大车运载体积的情况，通知人工预处理，安排整车发运后，剩余不足整车的运输任务加入算法进行初始解生成。因此，本方案生成的初始解存在仅允许单仓提货和大车的利用率/装载率不高的问题，但这些问题将会在模拟退火过程中不断被优化。
[0152]
4、外层sa算法自适应扰动算子
[0153]
本实施例设计了车辆订单合并(merge)、车辆订单拆分(spi lt)、车辆订单更换(swap)与车辆订单转移(drop-add)四类算子用于生成新解。
[0154]
具体的，如图8所示，外层sa算法自适应扰动算子包括：
[0155]
合并算子(merge)：随机选取两辆车，将当前迭代步中两辆车上被分配到的订单合并，将合并后的订单分配到两辆车中的随机一辆；如果合并后的订单中存在无法由大车配送的，则必配分到两辆车中的小车。(注意在定义合并算子时不需要考虑车辆装载量约束，因为后续会强制拆解无法装载的车辆)。
[0156]
拆分算子(spi lt)：随机选取一辆装载有货物的货车，将当前迭代步中其被分配到的订单进行拆分；具体，每件订单以用户给定概率alpha(默认0.5)下车，下车的订单将被随机分配到一辆空车。如果下车的订单中包含大车无法配送的，则必分配给一辆小车类型的空车。
[0157]
更换算子(swap)：随机选取两辆车，分别以等概率从两辆车当前被分配到的、并可以由对方车辆可以配送的订单，并交换该订单；如果随机选取到的车辆中存在一辆车，其当前被分配到的订单全部无法由对方车辆配送(由于当前订单所在网点交通不便只能允许小车通行)，则重新随机选取车辆直至完成一次更换。
[0158]
转移算子(drop-add)：随机选取一辆车，以等概率从当前迭代步被分配到的订单中选择一件下车，将下车的订单随机分配到一辆可以配送的车辆。
[0159]
考虑到生成的新解可能会出现车辆空载率过高、或者车辆超载等不符合实际的情况，本实施例设计了图9自适应机制，在每次迭代时都根据当前车辆装载率调整merge算子
与spilt算子的概率，使新解向适度车辆装载率移动；此外，通过swap算子与drop-add算子等随机操作，使新解向成本最优方向移动。
[0160]
如图9所示，扰动算子自适应方法为：
[0161]
输入当前解sol；
[0162]
计算当前解车辆平均装载率l；
[0163]
根据l调整选择四类算子概率p；
[0164]
依概率p选择算子生成新解sol_new；
[0165]
计算新解车辆平均装载率l_new；
[0166]
根据新解车辆平均装载率与预设值阈值范围的关系进行合并算子调整或者拆分算子调整或者不调整。
[0167]
新解车辆平均装载率在预设值阈值范围之间时不调整；新解车辆平均装载率超出预设值阈值范围上限时，进行拆分算子调整；新解车辆平均装载率低于预设值阈值范围下限时，进行拆分算子调整。
[0168]
每个第一周期根据最新历史数据和未来需求预测数据进行一次分区，每个第二周期根据下一第二周期的确定性需求数据进行一次配车排程，第一周期长于第二周期。
[0169]
例如，第一周期为一个季度，第二周期为一天。
[0170]
本实施例设计的数智化车辆运输模型具一体性/整体性，考虑了多仓存储的物流运输问题的全流程，包含一套完整的、相互依赖的智能分区方案和排程的智能优化方案，一方面，在本实施例给出的区划下，该排程方案可以近似实现最低的成本；另一方面，针对该排程方案，本实施例给出的智能分区方案可以输出近似于整体最优的区划。本实施例所设计算法的高度耦合、完整一体的特性，使全流程的物流方案在整体上是近似最优的，实现尽可能低的总成本。本实施例的模型具有高度耦合性和全局最优性。
[0171]
本实施例针对性的优化算法设计，不依赖于gurobi(软件名，古洛比)等商业求解器，可以由物流企业独立实现，并给出了结合高、低频率的求解方案，满足实际使用需求。本实施例所建立的优化模型是一个混合整数规划问题，即使使用商业求解器求解也是非常困难的(难以接受的求解时间、无法在满足需求的时间内给出满意解甚至无法给出可行解)。本实施例涉及的算法针对性的根据该规划问题的结构，将求解分为配车排程和分区划片两步，设计了前述的两套算法以及结合高、低求解频率的求解方案，每个季度根据最新历史数据和未来需求预测数据求解一次分区划片问题，每个工作日根据下一工作日的确定性需求数据求解一次配车排程问题，实现了在规定时间内输出满意解，满足现实需求。另一方面，本实施例还包含集成了全要素数据库和上述优化算法的信息系统，实现了输入需求、输出运输计划的数智化，可以在分单、派车、备货、取货、运输、卸货的全流程中给出具体的实施方案，解决了传统物流中依赖人工经验、管理难度高的痛点。
[0172]
本实施例具有普适性/拓展性。本实施例所提出的模型是一般化的，涵盖各种尺度的多对多的物流运输问题，包括从多个城市仓到多个网点的区域配送问题、从多个前置仓直接到客户端的点配问题等。而不同尺度的问题反映在模型上的区别主要在于优化问题的规模(即参数量)，由于本实施例设计的算法求解效率高，因此可以用来解决上述多对多的物流运输问题。
[0173]
本实施例数智化车辆运输算法是全面且具有现实性的，可行性和易用性。解决了
多仓、多网的物流场景中运输调度的多个痛点，实现尽可能少的司机多仓取货次数，节约取货时间，并提高司机的满意度；提高运输效率，降低配送与装卸货时间；考虑了客制化的配送需求，保证特定货物在规定时间窗内配送至规定地点；考虑了道路和网点的交通条件限制，输出可以实现的配车方案。
[0174]
以上实施例仅用以说明本发明的技术方案，而非对其进行限制；尽管参照前述实施例对本发明进行了详细的说明，对于本领域的普通技术人员来说，依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或替换，并不使相应技术方案的本质脱离本发明所要求保护的技术方案的精神和范围。

技术特征：
1.一种网点智能分区方法，其特征在于，所述方法为：s1、获取所有仓库和网点，将所有网点划分为独立社区，计算仓库到社区的成本；s2、遍历所有社区，计算将两个社区合并为一个新的社区后所带来的成本变化；s3、在成本不降低时，当前方案为最优分区方案，否则，取成本降低最大的两个社区合并为一个新的网点，进入s1。2.根据权利要求1所述的网点智能分区方法，其特征在于，所述新的网点与其他网点的距离为合并为所述新的网点的两个社区中与其他网点的最小的距离。3.根据权利要求1所述的网点智能分区方法，其特征在于，计算仓库到社区成本的方法为：获取运单信息，提取模型参数；对配车排程问题模型通过双层模拟退火算法进行模型求解，所述配车排程问题模型包括外层配车模型和内层路径规划模型，所述双层模拟退火算法包括外层sa算法和内层sa算法；外层sa算法用于求解最优派车方案，内层sa算法用于求解给定派车方案下的最优车辆路径，在所述外层sa算法中，调用所述内层sa算法求解当前派车方案的路径成本，用于评估当前派车方案解的质量，以使得所述双层模拟退火算法找到运输成本最小的最优的派车方案以及相应的最优路径。4.根据权利要求3所述的网点智能分区方法，其特征在于，所述外层配车模型为：目标函数：约束条件1：变量逻辑约束约束条件2：满足需求约束约束条件3：车辆容积约束∑
i∈i,j∈j
x
ij,kvij
≤αvol
k
,k∈c；约束条件4：车辆载重约束约束条件5：0-1变量约束；决策变量x
ij,k
,s
k
都是0-1变量；所述内层路径规划模型为：对每个k∈c，目标函数：目标函数：约束条件1：节点决策和边决策变量的逻辑约束约束条件1：节点决策和边决策变量的逻辑约束约束条件(组)2：满足取、送货需求约束约束条件(组)2：满足取、送货需求约束约束条件3：出入度平衡约束约束条件4：避免子圈约束
约束条件5：时间窗约束约束条件5：时间窗约束ρ
i
≥t
i,p-m(1-z
i,p
)-tl
i
,p∈c,i∈n；其中，ρ
i
衡量了节点i的配送延迟时长；约束条件6：网点可达性约束约束条件7：整数(0-1)约束，x
ij,k
，y
pq,k
，z
p,k
，s
k
是0-1变量；其中，c:车辆集合，c＝c1∪c2；i：仓库集合；j：网点集合，j＝j1∪j2，其中j1为所有车型可达网点，j2为仅小型车辆可达网点；vol
k
：第k(∈c)辆车的实际容积；mas
k
：第k(∈c)辆车的最大载重；velo
k
：第k(∈c)辆车的平均在途速度；f
k
:第k辆车的固定成本；c
k
:第k辆车的可变成本/单位距离；α:实际装载率；v
ij
:仓库i(∈i)到网点j(∈j)的订单包的体积；m
ij
:仓库i(∈i)到网点j(∈j)的订单包的质量；每车每到一个仓库提货产生的成本；p:每车每到一个网点送货产生的成本；pd：送货迟到产生的成本；t
i
:仓库i(∈i)平均提货用时；t
j
:网点j(∈j)平均装卸用时；ρ
i
：网点i的配货延迟时长；tl
i
:节点i(∈i)的时间窗要求；n:节点集合，n：＝{s}∪i∪j∪{e}，其中s为虚拟初始节点，e为虚拟终止节点；a:有向边集合，a：＝({s}
×
i)∪(i
×
i)∪(i
×
j)∪(j
×
j)∪(j
×
{e})；d
pq
：边权重，节点p到节点q的导航距离；m:不小于|n|的整数；x
ij,k
:第k辆车是否承运由仓库i到网点j的订单包；s
k
:第k辆车是否承运至少一个订单；y
pq,k
:第k辆车是否走过由节点p(∈n)到节点q(∈n)的导航路径；z
p,k
:第k辆车是否经过节点p(∈n{s})；t
p,k
:第k辆车到达节点p的时间；u
p,k
:对应第k辆车和节点p(∈n)的虚拟变量。
5.根据权利要求3所述的网点智能分区方法，其特征在于，对所述外层配车模型和内层配车模型引入中间变量g
k
，形成线性混合整数规划模型：min
x,s,y,z,u
∑
k
f
k
s
k
+∑
k
g
k
；；；∑
i∈i,j∈j
x
ij,kvij
≤αvol
k
,k∈c；,k∈c；,k∈c；,k∈c；,k∈c；,k∈c；,k∈c；,k∈c；ρ
i
≥t
i,p-m(1-z
i,p
)-tl
i
,p∈c,i∈n；x,y,z,s∈{0,1}。6.根据权利要求4或5所述的网点智能分区方法，其特征在于，当前外层sa算法中温度为t，初始解sol的目标函数值为obj，迭代产生新解sol_new的目标函数值为boj
′
，若boj
′
＜obj，则接受新解，令sol＝sol
′
；若obj
′
≥obj，则以概率p＝e-(obj
′‑
obj)/t
接受新解，随着温度t的下降，接受劣解的概率不断下降，算法逐渐收敛。7.根据权利要求6所述的网点智能分区方法，其特征在于，所述外层配车模型生成初始解的方法为：在单仓提货的前提下，选取距离最近且有订单任务的网点，再从当前网点出发，选取距离最近且有订单任务的网点，直到达到第一类型车辆运载的体积上限，将所选取的网点订单打包派给所述第一类型车辆，在单个运单集体积大于第一类型车辆运载体积时，安排第二类型车辆，所述第二类型车辆的运载体积大于所述第一类型车辆。8.根据权利要求3所述的网点智能分区方法，其特征在于，所述外层sa算法自适应扰动算子包括：合并算子(merge)：随机选取两辆车，将当前迭代步中两辆车上被分配到的订单合并，将合并后的订单分配到两辆车中的随机一辆；拆分算子(spilt)：随机选取一辆装载有货物的货车，将当前迭代步中其被分配到的订单进行拆分；更换算子(swap)：随机选取两辆车，分别以等概率从两辆车当前被分配到的、并可以由
对方车辆可以配送的订单中选取一个，并交换该订单；转移算子(drop-add)：随机选取一辆车，以等概率从当前迭代步被分配到的订单中选择一件下车，将下车的订单随机分配到一辆可以配送的车辆。9.根据权利要求8所述的网点智能分区方法，其特征在于，所述扰动算子自适应方法为：输入当前解sol；计算当前解车辆平均装载率l；根据l调整选择四类算子概率p；依概率p选择算子生成新解sol_new；计算新解车辆平均装载率l_new；根据新解车辆平均装载率与预设值阈值范围的关系进行合并算子调整或者拆分算子调整或者不调整。10.根据权利要求3所述的网点智能分区方法，其特征在于，每个第一周期根据最新历史数据和未来需求预测数据进行一次分区，每个第二周期根据下一第二周期的确定性需求数据进行一次配车排程，第二周期长于第一周期。

技术总结
本发明公开了一种网点智能分区方法，获取所有仓库和网点，将所有网点划分为独立社区，计算仓库到社区的成本；遍历所有社区，计算将任意两个社区合并为一个新的社区后所带来的成本变化；在成本不降低时，当前方案为最优分区方案，否则，取成本降低最大的两个社区合并为一个新的网点，直至确定最优分区方案。本发明将两个社区合并后的成本与合并前的成本相比降低最大的两个社区合并，由于成本的降低是终极需求，因而，本发明能够实现最优分区。本发明能够实现最优分区。本发明能够实现最优分区。


技术研发人员：王正刚 高跃 杨宇瑶 王月泉 李仑 杨子豪 史鑫博 殷博文 董雁天 江金阳 陈丽华
受保护的技术使用者：日日顺供应链科技股份有限公司
技术研发日：2023.03.31
技术公布日：2023/7/12