1.一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,包括:S1,构建基于时间窗的车辆路径优化主任务F的目标函数与约束条件;
S2,动态构建基于阶梯式约束松弛策略的动态辅助任务S的目标函数与约束条件;其中,辅助任务S的目标函数与主任务F的目标函数一致;所述基于阶梯式约束松弛策略的动态辅助任务S为:通过在局部搜索过程中逐步减小约束松弛变量,允许插入客户后生成暂时的不合约路线,得到不合约方案解,以有效突破不可行区域的限制,搜索更多的非连续可行解区域;
S3,根据获取的由若干客户组成的客户集,生成初始方案解,并保存至存档,初始化辅助存档;
S4,开启主任务F,执行任务协同机制,动态开启辅助任务S;其中,所述动态开启为:当存档中方案解的多样性不足时,开启辅助任务S,执行多任务优化;否则,不开启辅助任务S,执行单任务优化;
S5,主任务F开启后,从存档中选择一个解进行目标驱动的局部搜索,并将满足主任务约束条件且占优的规划方案,即合约方案解,更新至存档;辅助任务S开启时,若辅助存档为空,则从存档中选择一个解进行目标驱动的局部搜索,否则从存档中选择一个解进行目标驱动的局部搜索,更新合约方案解至存档,将不合约方案解更新至存档;
S6,当判断到当前优化任务达到停止条件时,终止搜索,输出存档中的所有方案,即为多任务多目标车辆路径规划方案;否则,继续执行任务协同机制。
2.根据权利要求1所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,所述目标函数包括调度使用的车辆数目、总行驶距离、路径的最长行驶时间、所有车辆的等待时间总和以及所有客户点的延误时间总和,公式分别为:;
;
;
;
;
其中,R表示方案解的路径集合;M表示R的维度大小,即方案解的总数;
表示第i条行驶路径的距离,表达式为:
;
其中,表示客户点至客户点之间的行驶距离;表示客户变量;表示路径i的客户点数量;
表示第i条路径的行驶时间,表达式为:
;
其中,表示车辆在客户点至之间的行驶时间;
表示车辆到达客户点的时间早于该客户点的最早服务时间时,产生的等待时间,表达式为:;
;
其中,表示离开客户点的时间;
表示客户点需要的服务时间;
表示第i条路径上的所有客户点的等待时间总和,表达式为:;
其中,表示车辆到达客户点时产生的等待时间;
表示第i条路径上所有客户点的延迟时间总和,表达式为:;
;
其中,表示客户点的最迟服务时间;表示车辆到达客户点的延迟时间。
3.根据权利要求2所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,所述约束条件包括需求约束、行程时间限制约束与返回时间约束;其中,主任务F的约束条件为:F的需求约束,表示每条路线的乘客总需求不应超过车辆容量,表达式为:;
F的行程时间限制约束,表示延迟时间不应超过最大允许延迟时间,表达式为:;
F的返回时间约束,表示车辆应在关闭时间前返回车场,表达式为:;
其中, 表示客户点的乘客数量;表示车辆容量;
表示客户点的延迟时间;表示设置的最大允许延迟时间;
表示车辆返回车场时的时间;表示设置的车场关闭时间;
辅助任务S的约束条件为:
S的需求约束与F的需求约束一致;
S的行程时间限制约束,表示延迟时间不应超过最大允许延迟时间,表达式为:;
S的返回时间约束,表示车辆应在关闭时间前返回车场,表达式为:;
其中,表示约束松弛变量,用于将客户重新插入路线时,路线暂时违反约束条件与,定义如下:;
其中,表示目标驱动局部搜索的最大搜索深度;为当前搜索深度。
4.根据权利要求3所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,所述初始方案解中的所有路径均以车场为起点,并以车场为终点;所述S3具体为:随机选择客户集中的两个客户A和B,以客户A创建路径,构建初始方案解,并将创建的路径加入初始方案解;
在不违反F的约束条件的情况下,将客户B插入至客户A创建的路径的下一个位置中;若插入客户B后导致违反F的约束条件,则不进行插入操作,遍历初始方案解中的其他路径,迭代查询是否能在不违反F的约束条件的情况下插入该客户,若遍历完初始方案解中所有路径均未找到满足约束条件的插入位置,则客户B创建一条新路加入初始方案解,直至将客户集中的所有客户都插入至初始方案解中的路径,完成初始方案解的构建。
5.根据权利要求3所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,所述任务协同机制具体为:从存档中选择一个解,排除,从剩余的存档中选择两个解记为,;同时获取存档中的边界解;其中,所述边界解位于解空间的极端区域,即目标函数值达到最小或最大的解;
计算解和解中每个目标值之间的欧氏距离之和,并记为;
计算解和解中每个目标值之间的欧氏距离之和,并记为;
计算边界解和解中每个目标值之间的欧氏距离之和,并记为;
若 时,则当前存档的解聚集较为集中,陷入局部最优,需增强存档的多样性,开启辅助任务S;否则,当前存档的解分布均匀,无需开启辅助任务S,将计算资源集中至主任务的搜索上,进一步收敛存档。
6.根据权利要求5所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,所述单任务优化具体为:仅运行主任务F,在满足主任务F的约束条件的情况下,优化主任务F的目标函数,以目标驱动进行局部搜索,得到新方案,并更新至存档;
所述多任务优化为:同时对主任务F和辅助任务S进行优化;主任务F的优化过程与所述单任务优化相同;优化辅助任务S时,在满足辅助任务S的约束条件的情况下,优化辅助任务S的目标函数,以目标驱动进行局部搜索,并根据约束松弛变量逐步放松辅助任务S的约束条件,探索更广泛的解空间,得到新方案,并加入到集合中;将中满足F的约束条件的方案,更新至存档,否则为不合约方案解,更新至存档。
7.根据权利要求1所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,对主任务F和辅助任务S进行优化时,各自主动发起与另一个任务的知识传递,通过存档间接进行知识传递;其中,主任务F发起的知识传递具体为:主任务F进行搜索优化时,得到收敛性更好的新方案解,并保存至存档中;
此时,新方案解在辅助任务S被选中进行局部搜索;
辅助任务S对新方案解进行破坏重建,在原先方案解的周围突破障碍,搜索到新的可行区域中的解;
主任务F完成向辅助任务S的知识传递;
辅助任务S发起的知识传递具体为:
辅助任务S在搜索过程中获取到新可行区域的解,并更新至存档中;
该新可行区域的解在主任务F搜索时被选中;
主任务F选取该新可行区域的解进行搜索,从而获取到可行区域的更多的可行优质解;
辅助任务完成向主任务的知识传递。
8.根据权利要求1-7任意一项所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,对存档进行更新时,执行存档更新策略,具体为:设要更新至存档的方案解为;
将方案解更新至存档时,若当前存档为空,则将存入至存档;否则,遍历存档中的所有方案解,删除被占优的方案解,若比存档中的任意一个方案解更劣,则不加入;若比存档中的任意一个方案解更优,则将加入存档中,结束更新;
将方案解更新至存档时,若当前存档为空,则将加入至存档;遍历存档中的所有方案解,删除被占优且约束违反程度劣于的方案解;若比存档中任意一个方案解更劣,则不加入;若比存档中任意一个方案解更优且的约束违反程度更优,则将加入存档,结束更新。
9.根据权利要求3所述的一种基于辅助任务的多任务多目标车辆路径规划方法,其特征在于,在进行目标驱动的局部搜索操作时,根据当前要优化的目标应用不同的策略,具体为:当优化目标为调度使用的车辆数目时:选择对应存档方案中车辆数最小的一条路径,即最小车辆路径,将所述最小车辆路径的客户依次加入至其余路径的最佳位置后,评估方案是否符合现有约束条件且优于搜索前的方案,若符合,则优化目标成功;否则优化失败,恢复方案;
当优化目标为除了以外的目标至时:随机选择对应存档方案中的一条路径,采用大邻域算子对该条路径进行破坏和重建,并评估是否符合约束条件且优于搜索前的方案,若符合,则优化成功;否则优化失败,恢复方案;
在目标驱动的局部搜索中,根据搜索深度,找到比先前目标更优的解x,并判断是否到达最大搜索深度;若未到达,以解x继续在优化的目标上进行搜索;否则,返回位于最大搜索深度时的解;
其中,所述大邻域算子包括、与三种方式,具体为:
:使用轮盘选择策略随机选择对应存档方案中的一条路径i;从路径i中选择一个客户点,排除客户点,再选择一个客户点;将客户点到客户点间的客户顺序进行反转;
:使用轮盘选择策略随机选择对应存档方案中的两条路径;从这两条路径中随机移除p个客户,若这两条路径中的客户数为 k,则 1 < p < k;将移除的p个客户依次插入存档中方案解的最佳位置;
:随机在对应存档方案中选择两条路径,寻找这两条路径中的相邻客户,并检查是否能合并这两条路径,同时调整客户的顺序以优化路径。
10.一种基于辅助任务的多任务多目标车辆路径规划装置,其特征在于,包括:主任务构建单元,用于构建基于时间窗的车辆路径优化主任务F的目标函数与约束条件;
辅助任务构建单元,用于动态构建基于阶梯式约束松弛策略的动态辅助任务S的目标函数与约束条件;其中,辅助任务S的目标函数与主任务F的目标函数一致;所述基于阶梯式约束松弛策略的动态辅助任务S为:通过在局部搜索过程中逐步减小约束松弛变量,允许插入客户后生成暂时的不合约路线,得到不合约方案解,以有效突破不可行区域的限制,搜索更多的非连续可行解区域;
初始方案解生成单元,用于根据获取的由若干客户组成的客户集,生成初始方案解,并保存至存档,初始化辅助存档;
任务协同机制单元,用于开启主任务F,执行任务协同机制,动态开启辅助任务S;其中,所述动态开启为:当存档中方案解的多样性不足时,开启辅助任务S,执行多任务优化;否则,不开启辅助任务S,执行单任务优化;
局部搜索单元,用于主任务F开启后,从存档中选择一个解进行目标驱动的局部搜索,并将满足主任务约束条件且占优的规划方案,即合约方案解,更新至存档;辅助任务S开启时,若辅助存档为空,则从存档中选择一个解进行目标驱动的局部搜索,否则从存档中选择一个解进行目标驱动的局部搜索,更新合约方案解至存档,将不合约方案解更新至存档;
输出单元,用于当判断到当前优化任务达到停止条件时,终止搜索,输出存档中的所有方案,即为多任务多目标车辆路径规划方案;否则,继续执行任务协同机制。