基于集群旅行商问题的协同配送路径优化方法

技术领域

本发明属于路径规划领域，具体涉及一种基于集群旅行商问题的协同配送路径优化方法。

背景技术

随着移动互联网的发展，电商平台不断涌现，网络购物用户规模持续扩大，也为人们的日常生活带去了便利。同时，与网购密不可分的快递业务也在迅猛增长。快递业务已经逐渐渗透人们的日常生活，为各企业带来了巨大的商机。最后一公里配送是指在网络购物后，快递公司将货物从本地分拣中心交付到客户手中，是整个快递流程的最后一环。同时，最后一公里配送是城市智慧物流建设的重点，也是路径优化领域中很重要的研究场景。

路径优化问题经常被转换为求解旅行商问题(Traveling Salesman Problem，TSP)或其变体问题。其中，集群旅行商问题(Cluster Traveling Salesman Problem，CTSP)经常被用来求解区域化的最后一公里配送优化问题。Baniasadi P等人的研究中，其考虑了求解广义的CTSP问题：主要思想是将广义CTSP问题转化为普通的TSP模型，在此基础上采用启发式算法进行求解；此外，文中还介绍了所提方案在最后一公里配送中的应用，采用送货卡车运载无人机的形式来完成包裹运送任务，即当送货卡车从一个客户转移到为另一客户提供服务时，无人机会从卡车上取走包裹并为更多的近距离客户提供服务，同时每架无人机在相应的交付后返回卡车。在这种配送模式下，可以有效降低卡车的行驶时间，并能达到优化无人机空载率的目的。然而，由于无人机配送包裹的局限性，这种模式所服务的客户数量十分有限。此外，该模式忽略了现实生活中自提点的资源，导致整个配送过程与实际场景偏离。Phuong H N等人的研究，重点在于求解带优先级的CTSP：文中将各个客户按照紧急程度设立优先级，并根据优先级对客户节点分类。然而，严格的优先级制度不但会造成的总配送成本增加，还会限制解空间，从而影响最优解的求取。针对这一问题，Phuong H N等人为优先级排序设立了d松弛机制，规定当两客户节点优先级差值大于d时，才会按照严格的顺序被服务。实验结果证明，最终获得的路径与TSP问题求解方案相近。

但是现存的研究中，依旧存在以下问题：(1)忽视已有的自提点资源，导致所建立的模型与实际配送场景存在偏差；(2)只针对一条配送路线，无法提供有效的大区域协同配送方案。这些问题导致已有方案很难运用到实际配送场景中，实用性较差。

发明内容

本发明的目的在于提供一种贴合实际配送场景，而且可靠性高，实用性好的基于集群旅行商问题的协同配送路径优化方法。

本发明提供的这种基于集群旅行商问题的协同配送路径优化方法，包括如下步骤：

S1.获取待分析区域的区域参数；

S2.根据步骤S1获取的区域参数，构建具有覆盖的多集群旅行商问题模型；

S3.根据区域内的总配送请求，进行分区平衡优化；

S4.随机构建初始路径；

S5.采用扰动机制对步骤S4的初始路径进行优化；

S6.对后续路径进行再优化；

S7.重复步骤S5和S6直至达到设定的条件，得到最终的协同配送路径优化结果。

步骤S2所述的构建具有覆盖的多集群旅行商问题模型，具体为以配送员个数，客户遍历次数，自提点遍历次数，路径连续性，子行程约束，自提点容量限制以及自提点服务范围为限制条件，以最小化配送成本为目标，构建目标函数：

约束条件：

u

式中V为节点集合，且V＝V

步骤S3所述的进行分区平衡优化，具体为采用如下步骤进行优化：

A.在h个集群中，记各集群中的节点数量分别为N

B.采用如下算式计算每个配送员最多可以服务的节点数量

式中N

C.选择h个集群中节点最多的m个集群的中心点为类的初始质心，并记录各个类内的初始数量为L

D.计算其余中心点j到各初始质心i的欧几里得距离；

E.根据步骤D得到的欧几里得距离，选取距离最短的中心点，并进行如下操作和判断：

若将集群j整体加入到对应的类后当前类的节点个数不大于

若将集群j整体加入到对应的类后当前类的节点个数大于

F.重复步骤E直至所有的节点均被分配完毕；

G.计算每个快递员需要服务的节点个数之间的方差并进行判断：若方差小于设定的阈值，则终止分配过程；否则，计算各个类的中心点并设为质心；

H.重复步骤D～步骤G，直至各快递员被分配的客户个数方差小于设定的阈值。

步骤S4所述的随机构建初始路径，具体为在每个原始集群内随机构建内部路径，然后将各集群根据距离最短原则连接起来，由此建立初始路径。

步骤S5所述的采用扰动机制对步骤S4的初始路径进行优化，具体为采用如下步骤进行优化：

当前路径经过迭代优化后，进行如下判断：

若已经有k次路径成本没有降低且当前扰动机制为机制a，则将当前扰动机制修改为机制b，并进行后续的迭代优化；

若已经有k次路径成本没有降低且当前扰动机制为机制b，则将当前扰动机制修改为机制a，并进行后续的迭代优化；

若路径成本没有降低的次数没有达到设定的k次，则保持当前的扰动机制不变，并进行后续的迭代优化；

所述的机制a为：判断当前类中集群的个数：

当集群的个数大于等于设定值时，随机选择初始路径中类间的四条边，以最小成本原则重新连接，获得比之前更短的路径；

当集群的个数小于设定值时，随机选择两个集群，根据最小成本原则，重新为这两个集群选择插入位置；

所述的机制b为：判断当前类中集群的个数：

当集群的个数大于等于设定值时，随机选择初始路径中类间的三条边，以最小成本原则重新连接，获得比之前更短的路径；

当集群的个数小于设定值时，保持机制a；

采用上述的技术方案进行初始路径的优化，直至达到规定的迭代次数。

步骤S6所述的对后续路径进行再优化，具体为采用邻域随机搜索机制对后续路径进行再优化。

所述的采用邻域随机搜索机制对后续路径进行再优化，具体为采用如下步骤进行再优化：

随机选择如下4个邻域机制中的一种，对已有路径进行邻域搜索；同时，若选择的邻域机制未优化当前路径，则在剩余的未选择过的邻域机制中再随机选择一个，进行邻域搜索；若选择的邻域机制优化了当前路径，则继续采用当前的邻域机制进行搜索；

停止优化的条件为：所有的邻域搜索机制均已选择完毕；

所述的4个邻域机制为：

1)1-shift机制：随机选择节点i和j，并进行判断：

若节点i是客户节点：

若节点i和节点j均为客户节点，则直接将节点i移动到节点j前；

若节点i为客户节点且节点j为自提点，则判断节点i是否满足放进节点j的要求：

若节点i满足放进节点j的要求，则将节点i放入节点j中；

否则，直接将节点i放在节点j前；

若节点i为自提点，则记C

2)DropCheap机制：随机选择一个集群，取出其路径中消耗最大的节点，然后将选定的节点直接插入到最小消耗的位置；

3)2-Swap机制：

若节点i为客户节点：则进行如下判断：

若节点i和节点j均为客户节点，则直接将节点i与节点j交换；

若节点j为自提点，则记C

若节点i为自提点，则进行如下判断：

若节点j为客户节点，则直接将节点i与节点j交换；

若节点j为自提点，则记C

4)2-opt机制：

若节点i和节点j在同一集群内，则直接将两点之间的序列翻转；

若节点i和节点j不在同一集群内，则找到各簇之间的分界点m

本发明提供的这种基于集群旅行商问题的协同配送路径优化方法，构造目标函数和约束条件建立基础的数学模型，根据所输入的网络实例对各配送员的工作量进行均衡分配，之后获得每个配送员的初始路径方案，之后再对初始路径迭代地进行扰动操作和邻域搜索操作，从而获得最优的巡游路径；因此本发明方法能够有效平衡各配送员的工作量，并为他们提供最优的路径规划，能够有效的降低总配送成本，而且可靠性高，实用性好。

附图说明

图1为本发明方法的方法流程示意图。

图2为本发明方法的应用场景示意图。

具体实施方式

如图1所示为本发明方法的方法流程示意图，图2则为本发明方法的应用场景示意图。

本发明提供的这种基于集群旅行商问题的协同配送路径优化方法，包括如下步骤：

S1.获取待分析区域的区域参数；

S2.根据步骤S1获取的区域参数，构建具有覆盖的多集群旅行商问题模型；具体为以配送员个数，客户遍历次数，自提点遍历次数，路径连续性，子行程约束，自提点容量限制以及自提点服务范围为限制条件，以最小化配送成本为目标，构建目标函数：

约束条件：

u

式中V为节点集合，且V＝V

S3.根据区域内的总配送请求，进行分区平衡优化；具体为采用如下步骤进行优化：

A.在h个集群中，记各集群中的节点数量分别为N

B.采用如下算式计算每个配送员最多可以服务的节点数量

式中N

C.选择h个集群中节点最多的m个集群的中心点为类的初始质心，并记录各个类内的初始数量为L

D.计算其余中心点j到各初始质心i的欧几里得距离；

E.根据步骤D得到的欧几里得距离，选取距离最短的中心点，并进行如下操作和判断：

若将集群j整体加入到对应的类后当前类的节点个数不大于

若将集群j整体加入到对应的类后当前类的节点个数大于

F.重复步骤E直至所有的节点均被分配完毕；

G.计算每个快递员需要服务的节点个数之间的方差并进行判断：若方差小于设定的阈值，则终止分配过程；否则，计算各个类的中心点并设为质心；

H.重复步骤D～步骤G，直至各快递员被分配的客户个数方差小于设定的阈值。

S4.随机构建初始路径；具体为在每个原始集群内随机构建内部路径，然后将各集群根据距离最短原则连接起来，由此建立初始路径；

S5.采用扰动机制对步骤S4的初始路径进行优化；具体为采用如下步骤进行优化：

当前路径经过迭代优化后，进行如下判断：

若已经有k次路径成本没有降低且当前扰动机制为机制a，则将当前扰动机制修改为机制b，并进行后续的迭代优化；

若已经有k次路径成本没有降低且当前扰动机制为机制b，则将当前扰动机制修改为机制a，并进行后续的迭代优化；

若路径成本没有降低的次数没有达到设定的k次，则保持当前的扰动机制不变，并进行后续的迭代优化；

所述的机制a为：判断当前类中集群的个数：

当集群的个数大于等于设定值(比如8个)时，随机选择初始路径中类间的四条边，以最小成本原则重新连接，获得比之前更短的路径；

当集群的个数小于设定值(比如8个)时，随机选择两个集群，根据最小成本原则，重新为这两个集群选择插入位置；

所述的机制b为：判断当前类中集群的个数：

当集群的个数大于等于设定值(比如3个)时，随机选择初始路径中类间的三条边，以最小成本原则重新连接，获得比之前更短的路径；

当集群的个数小于设定值(比如3个)时，保持机制a；

采用上述的技术方案进行初始路径的优化，直至达到规定的迭代次数。

S6.对后续路径进行再优化；具体为采用邻域随机搜索机制对后续路径进行再优化；

具体实施时，采用如下步骤进行再优化：

随机选择如下4个邻域机制中的一种，对已有路径进行邻域搜索；同时，若选择的邻域机制未优化当前路径，则在剩余的未选择过的邻域机制中再随机选择一个，进行邻域搜索；若选择的邻域机制优化了当前路径，则继续采用当前的邻域机制进行搜索；

停止优化的条件为：

所有的邻域搜索机制均已选择完毕；

所述的4个邻域机制为：

1)1-shift机制：随机选择节点i和j，并进行判断：

若节点i是客户节点：

若节点i和节点j均为客户节点，则直接将节点i移动到节点j前；

若节点i为客户节点且节点j为自提点，则判断节点i是否满足放进节点j的要求：

若节点i满足放进节点j的要求，则将节点i放入节点j中；

否则，直接将节点i放在节点j前；

若节点i为自提点，则记C

2)DropCheap机制：随机选择一个集群，取出其路径中消耗最大的节点，然后将选定的节点直接插入到最小消耗的位置；

3)2-Swap机制：

若节点i为客户节点：则进行如下判断：

若节点i和节点j均为客户节点，则直接将节点i与节点j交换；

若节点j为自提点，则记C

若节点i为自提点，则进行如下判断：

若节点j为客户节点，则直接将节点i与节点j交换；

若节点j为自提点，则记C

4)2-opt机制：

若节点i和节点j在同一集群内，则直接将两点之间的序列翻转；

若节点i和节点j不在同一集群内，则找到各簇之间的分界点m

S7.重复步骤S5和S6直至达到设定的条件，得到最终的协同配送路径优化结果。