欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2023103192430
申请人: 暨南大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于大规模邻域搜索算法的路径规划方法,其特征在于,包括:

获取多个待配送目标所对应的配送请求信息,其中,所述配送请求信息中携带所述待配送目标所对应的配送位置信息;

将所述配送位置信息输入预设地图中,得到与位于对应的配送区域内的多个所述待配送目标所对应的配送运输参数,其中,所述配送运输参数用于表征任意两个所述配送位置信息之间对应的行驶参数;

基于已构建的路径规划模型和所述配送运输参数,规划生成与多个所述待配送目标对应的配送路径数据,其中,所述路径规划模型是基于自适应大规模邻域搜索算法ALNS和预设的毁灭重构操作所构建的;

在所述配送路径数据中,确定目标配送路径,并基于所述目标配送路径对多个所述待配送目标进行配送。

2.根据权利要求1所述的方法,其特征在于,将所述配送位置信息输入预设地图中,得到与位于对应的配送区域内的多个所述待配送目标所对应的配送运输参数,包括:从所述配送位置信息中获取配送地址信息,并将所述配送地址信息输入所述预设地图中,得到与所述配送地址信息对应的第一经纬度;

在所述第一经纬度中,检测处于对应的所述配送区域内的第二经纬度;

利用所述预设地图,对每个所述配送区域所对应的所述第二经纬度进行处理,生成与每个所述配送区域对应的所述配送运输参数,其中,所述配送运输参数包括以下参数:所述第二经纬度、任意两个所述第二经纬度之间的行驶距离、任意两个所述第二经纬度之间的行驶时间。

3.权利要求2所述的方法,其特征在于,在所述第一经纬度中,检测处于对应的所述配送区域内的第二经纬度,包括:确定所述配送区域的区域边缘所对应的关键经纬度,并基于所述关键经纬度,在所述预设地图中生成配送区域多边形,其中,所述配送区域是基于历史配送所划分的;

判断所述第一经纬度在所述预设地图中的坐标数据是否处于所述配送区域多边形中;

将处于所述配送区域多边形中的所述第一经纬度作为所述第二经纬度。

4.根据权利要求2所述的方法,其特征在于,基于已构建的路径规划模型和所述配送运输参数,规划生成与多个所述待配送目标对应的配送路径数据,包括:基于预设的构造算法,对所述配送运输参数所对应的多种所述参数进行处理,生成初始路径数据,其中,所述初始路径数据包括多个所述待配送目标所对应的所述第二经纬度和所述待配送目标所对应的目标信息;

利用轮盘赌算法,从预设的所述毁灭重构子算法所对应的多种毁灭destroy操作和多种重构repair操作中,选取目标destroy操作和目标repair操作,其中,所述destroy操作表征对所述初始路径数据中的所述第二经纬度或初始路径进行移除,所述repair操作表征向所述初始路径数据中插入所述第二经纬度;

在对所述初始路径数据进行所述destroy操作所得到的重构路径数据,进行所述repair操作,生成候选路径数据;

从所述候选路径数据中,确定出所述配送路径数据。

5.根据权利要求4所述的方法,其特征在于,所述destroy操作包括以下其中一种移除操作:随机移除所述第二经纬度、移除聚类值小于预设聚类值阈值的所述第二经纬度、移除对应的输送量小于预设输送量阈值的初始路径所对应的所有所述第二经纬度、在对应的输送量大于预设输送量阈值的初始路径所对应的所有所述第二经纬度中,移除聚类值小于预设聚类值阈值的所述第二经纬度、随机移除由多个所述第二经纬度组成的初始路径、移除对应的输送量的差值大于预设输送量阈值的相邻两条初始路径、移除对应的所述配送运输参数不满足预设参数值的初始路径,和/或,所述repair操作包括以下其中一种插入操作:

基于最近距离插入法,将移除的所述第二经纬度插入邻近的所述重构路径数据;

基于最近距离聚类插入法,将多个移除的所述第二经纬度聚类成经纬度团簇,并将所述经纬度团簇插入邻近的所述重构路径数据;

基于合并拆分法,将多个移除的所述第二经纬度和邻近的所述重构路径数据进行合并,并按输送量将合并得到的路径数据进行拆分;

基于工作量均衡插入法,将移除的所述第二经纬度插入指定路径数据中,其中,所述指定路径数据为相对移除的所述第二经纬度距离最近且对应的输送量小于预设输送量阈值的所述重构路径数据。

6.权利要求4所述的方法,其特征在于,在对所述初始路径数据进行所述destroy操作后,所述方法还包括:对完成所述destroy操作的初始路径数据进行destroy后操作,其中,所述destroy后操作包括以下其中一种移除操作:移除至少一个选定的所述第二经纬度、移除以至少一个选定的所述第二经纬度为中心的经纬度中心团簇和/或邻近经纬度团簇、移除与至少一个选定的所述第二经纬度的距离在预设距离半径范围内的所述第二经纬度、移除选定的所述初始路径上的多个所述第二经纬度、移除至少一条选定的所述初始路径、移除一条选定的所述初始路径及与该选定的所述初始路径邻近的多条初始路径。

7.根据权利要求4所述的方法,其特征在于,利用轮盘赌算法,从预设的所述毁灭重构子算法所对应的多种destroy操作和多种repair操作中,选取目标destroy操作和目标repair操作,包括:按如下公式分别计算所述destroy操作和所述repair操作所对应的概率;

pi为第i种所述destroy操作或所述repair操作所对应的概率,wi为第i种所述destroy操作或所述repair操作的对应的设定权重,k为所述destroy操作或所述repair操作所对应的总数量;

选取所述概率最大的所述destroy操作和所述概率最大的所述repair操作,得到所述目标destroy操作和所述目标repair操作。

8.根据权利要求4所述的方法,其特征在于,从所述候选路径数据中,确定出所述配送路径数据,包括:获取所述候选路径数据所对应的相邻两个所述第二经纬度之间的行驶时间,得到第一行驶时间;

判断所述第一行驶时间是否小于预设阈值;

在判断到所述第一行驶时间小于预设阈值的情况下,将小于预设阈值的所述第一行驶时间所对应的所述候选路径数据作为所述配送路径数据。

9.据所述权利要求2所述的方法,其特征在于,在所述配送路径数据中,确定目标配送路径,包括:确定多个所述待配送目标对应的配送起点所对应的起点经纬度,确定所述配送路径数据中所有所述第二经纬度与对应的所述起点经纬度的欧式距离,并基于所述欧式距离,利用最近邻排序算法,对所有所述第二经纬度进行排序,生成重排路径数据;

根据对应的路径数据中相邻两个所述第二经纬度之间的行驶时间,确定对应的路径数据所对应的第一总配送时间,并从所述重排路径数据和所述配送路径数据中,选取所述第一总配送时间最短的路径数据作为当前路径数据;

利用预设的邻域搜索法,对所述当前路径数据进行邻域搜索,得到多个邻域路径数据,并以所述邻域路径数据中相邻两个所述第二经纬度之间的行驶时间,确定所述邻域路径数据所对应的第二总配送时间,其中,所述邻域搜索法包括以下其中一种搜索方法:交换所述当前路径数据中的两个所述第二经纬度、交换所述当前路径数据中的两个由预设数目的所述第二经纬度连线组成的路径片段、将一个所述路径片段插入另一个所述路径片段之前、交换两个由多个所述第二经纬度聚类成的经纬度团簇,将一个所述经纬度团簇插入到另一个所述经纬度团簇前;

基于所述第二总配送时间和所述当前路径数据所对应的所述第一总配送时间,从所述当前路径数据和多个所述邻域路径数据中,选取配送时间最短的路径数据作为所述目标配送路径所对应的路径数据。

10.一种存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现权利要求1至9中任一项所述的基于大规模邻域搜索算法的路径规划方法。