融合边组装交叉蚁群系统的带服务约束多物流车协同方法

摘要: 本发明涉及物流调度优化领域,特别涉及融合边组装交叉蚁群系统的带服务约束多物流车协同方法。背景技术:1、在现代物流配送、无人车调度、多机器人协同作业等实际场景中,...
融合边组装交叉蚁群系统的带服务约束多物流车协同方法

本发明涉及物流调度优化领域,特别涉及融合边组装交叉蚁群系统的带服务约束多物流车协同方法。

背景技术:

1、在现代物流配送、无人车调度、多机器人协同作业等实际场景中,一个常见且重要的任务是:调度多辆运输车从仓库出发,为分布在各地的客户点提供配送服务,每辆车完成任务后返回其出发起点。这类问题统称为多物流车路径规划问题。其核心约束包括:每个客户点必须被某辆车服务且仅被服务一次;每辆车的路径形成一条闭合回路。优化目标通常有两大类:最小化所有车辆的总服务成本,以及最小化所有车辆中的最大服务成本。其中,最小化所有车辆中的最大服务成本目标更贴合实际需求,它能有效均衡各车辆的工作负荷,避免部分车辆过度忙碌而其他车辆闲置,同时有利于多车协同和任务同步化。

2、然而,真实物流场景中还存在一个至关重要的约束:服务权限。由于车辆类型差异(例如冷链车只能服务生鲜客户、危化品车有专门路线)、服务区域划分(不同车辆负责不同片区)、客户特殊要求(如某些园区只允许特定品牌的车辆进入)等原因,每个客户点往往只能由少数特定的物流车提供服务。也就是说,物流车与客户点之间存在一个“是否有权服务”的二元关系。这一约束的松紧程度随场景变化,忽视服务约束,将导致规划出的路径方案在实际中无法执行。

3、当前,针对带服务约束的多物流车路径规划问题,尤其是最小化所有车辆中的最大服务成本目标的研究仍十分有限。精确算法仅能处理极小规模实例,无法扩展到实际配送网络。许多现有方法将车辆起点预先固定,忽略了起点本身也可以从客户点中动态选择以优化负载均衡的潜力。

4、蚁群优化算法因其并行搜索、正反馈机制和鲁棒性,在路径规划类问题中表现优异。然而,将蚁群优化算法直接应用于带服务约束的多物流车路径规划问题面临多重挑战:传统蚁群优化算法的状态转移概率基于信息素和距离启发式,未考虑服务权限,导致蚂蚁可能选择无权客户点,生成不可行路径;蚁群优化算法本身属于构造式启发算法,其局部寻优能力有限。

5、综上所述,现有方法在处理带服务约束的最小化所有车辆中的最大服务成本目标下的多物流车路径规划问题时,在约束处理、动态起点选择、信息素导向等方面均存在明显不足。

技术实现思路

1、发明目的:针对以上问题,本发明目的是提供融合边组装交叉蚁群系统的带服务约束多物流车协同方法。

2、技术方案:本发明的融合边组装交叉蚁群系统的带服务约束多物流车协同方法,包括以下步骤:

3、s1,获取物流场景信息,将多物流车服务客户问题建模为带服务约束的最小化最大服务成本问题;

4、s2,采用贪心算法求得初始调度方案的最大服务成本,利用所述最大服务成本初始化信息素矩阵和起点权重矩阵,维护存档容量,并设置蚁群系统参数,在蚁群系统中,每只蚂蚁用于构建一个完整的候选调度方案;

5、s3,基于起点权重矩阵和各物流车的服务权限,为每辆物流车动态选择起点,从起点出发,根据信息素浓度和启发式信息,在服务权限约束下轮流为每辆物流车扩展路径,直至所有客户点均被服务,构建完整的多物流车服务方案;

6、s4,利用存档机制保存历史最优解,当存档非空时采用边组装交叉算子对存档个体与当代蚂蚁解进行交叉操作,生成子代解,所有子代解与所有原始蚂蚁解共同构成候选解池;

7、s5,对候选解池中的每个个体,基于适应值计算局部搜索执行概率,并按概率执行融合跨路径客户点重分配与2-opt的局部搜索,得到优化后的候选解池;

8、s6,计算优化后的候选解池中所有个体的适应值,更新全局最优服务方案;

9、s7,对全局最优服务方案中的每条边进行信息素全局更新,同时对全局最优服务方案中的每个起点进行起点权重全局更新;

10、s8,将候选解池中的最优服务方案插入存档,并维持存档容量;

11、s9,判断是否满足迭代终止条件,如果满足迭代终止条件,输出全局最优的多物流车服务方案,若不满足迭代终止条件,则转到步骤s3。

12、优选地,所述物流场景信息包括:

13、客户点个数、各客户点位置信息、物流车数量、服务权限约束矩阵,其中矩阵中第行第列的元素记为,表示第辆物流车有权服务客户点,否则为0;

14、所述将多物流车服务客户问题建模为带服务约束的最小化最大服务成本问题表示为:

15、;

16、其中,sol代表一个服务方案,为第k辆物流车的服务成本,其数学表达式为:

17、;

18、其中,为客户点与客户点之间的服务成本,为二元决策变量,表示车辆是否直接从客户点行驶至客户点,如果车辆直接从客户点行驶至客户点则取值为1,否则为0。

19、优选地,在步骤s2中,采用贪心算法求得初始调度方案的最大服务成本,利用所述最大服务成本初始化信息素矩阵和起点权重矩阵的步骤包括:

20、为每辆物流车分配互斥的起点,然后轮流为每辆车选择未服务且有权服务的最近客户点扩展,直至所有客户点被服务,得到初始调度方案;

21、计算各车辆路径的服务成本,即闭合回路中相邻客户点间的服务成本之和,将最大服务成本记为;

22、设置信息素初始值为:,起点权重初始值为:;

23、初始化信息素矩阵中所有元素为,若则起点权重矩阵中第行第列的元素赋值为,否则,起点选择时根据权重矩阵为每辆物流车分配互斥的起点。

24、优选地,步骤s3包括:

25、s301,对于每只蚂蚁所构建的完整方案,在构造过程中需为其包含的每辆物流车动态选择互斥的起点,选择完成后对该起点对应物流车权重执行局部更新,更新公式为:

26、,

27、其中,为当前路径起点,为当前物流车的序号,表示更新后客户点作为第辆物流车起点的权重值,表示更新前客户点作为第辆物流车起点的权重值,为信息素及权重局部更新系数;

28、s302,初始化所有客户点为未服务状态,各车起点已标记为已服务;

29、s303,当存在未服务客户点时,依次遍历每辆物流车,若当前车辆的路径末端为点,筛选出未服务且的客户点作为候选集candidate;

30、s304,若候选集非空,计算从当前点到每个候选点的转移值,公式为:

31、,

32、其中,候选点为候选集中的客户点,为启发式信息,代表点与点间的服务成本;

33、生成随机数,若随机数小于客户点选择概率,则选择转移值最大的候选点作为下一客户点;否则按轮盘赌方式选择,每个候选点被选中的概率为:,其中,为信息素权重,为启发式信息权重;

34、将下一客户点添加到当前车辆路径末端,标记为已服务;

35、s305,执行信息素局部更新,更新公式为:

36、,

37、其中,表示更新后边上的信息素浓度,表示更新前边上的信息素浓度;

38、s306,重复步骤s303至步骤s305,直至所有客户点均被服务,每辆车路径末端返回自身起点,进而形成完整调度方案。

39、优选地,在步骤301中,为每辆物流车动态选择互斥的起点的步骤包括:

40、首先根据构建的起点权重矩阵,按顺序为每辆物流车动态选择起点;每只蚂蚁,按顺序处理每辆车,获取所有尚未被选为起点且的客户点集合allowed;若allowed为空,则允许重复使用已被选为起点的客户点;根据当前起点权重矩阵计算每个候选客户点的权重;

41、然后生成随机数,若小于起点选择概率,则选择第列中权重最大的客户点作为起点;否则按照轮盘赌方式选择起点。

42、优选地,在步骤s4中,所述利用存档机制保存历史最优解,当存档非空时采用边组装交叉算子对存档个体与当代蚂蚁解进行交叉操作,生成子代解的步骤包括:

43、s401,维护一个容量为的存档,所述存档用于保存进化过程中发现的历史最优调度方案,初始时存档为空,交叉默认从第二代开始执行;

44、s402,对于每个当代蚂蚁解,从存档中随机选择一个父代解,首先分别提取父代解和父代解的边集、,然后合并两个边集从而构建并集得到图,在图中交替追踪来自和的边,生成若干个交替环,选取包含边数最多的交替环作为中心交替环,通过移除父代解中属于中心交替环的边并添加属于中心交替环的边,对得到的环路按边数降序排列,取第二大环路为临时环路,然后将中心交替环加入操作边集,将与临时环路有公共顶点的其他交替环加入操作边集;最后对原始父代解操作,通过移除中属于操作边集的边并添加属于操作边集的边,生成中间解;

45、s403,如果中间解子路径个数小于,则执行拆分操作;如果子路径个数大于,则执行合并操作,重复执行拆分或合并操作,直到得到一个子路径条数满足要求的子代解;

46、其中所述拆分操作用于将一条服务成本过大的子路径拆分为两条,其拆分增量成本计算如下:

47、;

48、其中,、为从原子路径中删除的两条不相邻边且来自同一条路径,、为添加的两条新边,、、、分别表示边、、、的服务成本,即该边所连接的两个客户点之间的服务成本;

49、所述合并操作用于将两个子路径合并为一个,其合并增量成本计算如下:

50、;

51、其中,、分别来自两个不同子路径,、为添加的两条连接边;

52、通过选择使拆分增量成本最小的切割方式,或者通过选择使合并增量成本最小的连接方式,实现以最小的成本增量完成拆分或合并。

53、优选地,步骤s5包括:

54、s501,计算候选解池中所有个体的适应值,找出最大值和最小值,对于每个个体的服务方案,分别计算局部搜索执行概率为:

55、;

56、其中,为极小正常数用于防止分母为0;

57、s502,对每个个体,首先随机生成一个随机数,若随机数小于局部搜索执行概率,则依次执行局部搜索操作,否则跳转至步骤s502;

58、s503,将执行局部搜索后得到的新解与未执行搜索的原解共同构成优化后的候选解池;

59、其中,所述局部搜索操作的过程包括:

60、首先对每辆物流车的路径分别执行2-opt优化,即遍历路径中所有客户点,一旦找到翻转两点之间的序列使服务成本减少的两个点,立即翻转并重新开始扫描,连续执行直至无法改进;

61、然后执行跨路径客户点重分配操作,分为以下两个步骤:

62、首先,遍历所有物流车对,找出路径与路径之间服务成本最小的一对客户点,将边界客户点从各自路径中删除,采用贪心插入方式将删除的客户点重新插入到所有可能的符合服务约束要求的位置中使整体最大服务成本最小的位置;

63、然后,找出当前调度方案中的总服务成本最大的子路径,遍历该路径上的每个客户点,对于每个客户点,利用地理上最近的个客户点所在路径且对该客户点具备服务权限的车辆路径作为候选目标,不包括该客户点本身所在原路径,模拟将该客户点从原路径删除并插入到候选目标路径的最优位置,计算迁移后全局最大服务成本的变化量;

64、经过对所有客户点和候选目标的评估,选择能使全局最大服务成本严格下降且下降量最大的一个迁移执行,并重复此过程直至无法改进。

65、优选地,步骤s7包括:

66、每代结束后,对全局最优解中的每条边执行信息素全局更新,更新公式为:

67、;

68、其中,和为同一辆物流车路径上相邻的客户点,包括从最后一个客户点返回起点的边,和分别为更新前后边上的信息素浓度,为全局最优解的适应值,即该方案中所有车辆服务成本的最大值;为信息素及权重全局挥发系数;

69、同时,对全局最优解中每辆物流车的起点客户点,执行起点权重全局更新,更新公式为:

70、;

71、其中,和分别为更新前后客户点作为第辆物流车起点的权重值。

72、有益效果:本发明与现有技术相比,其显著优点是:

73、1、针对实际物流场景中车辆服务权限差异性的需求,本发明引入服务约束矩阵对车辆-客户点服务权限关系进行精确刻画,可模拟多种实际物流场景,适用范围广;

74、2、本发明设计了动态起点选择、服务约束集成状态转移、信息素局部更新、信息素全局更新等机制,有效引导算法向负载均衡方向收敛,克服了传统蚁群优化算法的聚合缺陷;

75、3、本发明中通过嵌入最小增量成本的分割与重组操作,将聚合型交叉算子改造为适用于本问题的均衡型算子,在保留优良边结构的同时实现负载均衡;

76、4、本发明中融合跨路径客户点重分配与2-opt的局部搜索,协同增强了局部寻优能力,且概率执行策略节省了计算资源。