公开(公告)号：CN118464030A

公开(公告)日：2024-08-09

申请号：CN202410509963.8

申请日：2024-04-26

Applicant: 吉林大学

Inventor： 何丽莉 ,  唐继州 ,  白洪涛 ,  曹英晖 ,  张洋

IPC: G01C21/26 ,  G06N5/01 ,  G01C21/34 ,  G01C21/20

Abstract: 本发明公开了一种基于关键边的多车路径规划方法，包括：初始解的构造，使用关键边的邻域构造和禁忌搜索，解优化方法。算法流程如下：使用改进的K‑POSTMEN算法求得初始解S1，即为当前解S；计算图G中的关键边集合KE，并计算初始解S1中每条回路RL包含的关键边集合Sk；通过禁忌搜索算法迭代搜索最优解：移动关键边构造邻域。本发明涉及多车路径规划技术领域，本发明的有益效果是，邻域构造规则决定了当前解的变化方式，也决定了算法的搜索范围和收敛快慢。CTA‑kroutes算法以关键边为基础，从当前解的最长路径RLa中移动关键边及其周边路径rc到当前解的最短路径RLb中，即在最长路径RLa中删除rc并在最短路径RLb中添加rc。

公开(公告)号：CN116718205A

公开(公告)日：2023-09-08

申请号：CN202310617932.X

申请日：2023-05-30

Applicant: 吉林大学

Inventor： 何丽莉 ,  唐继州 ,  白洪涛 ,  曹英晖 ,  张洋

IPC: G01C21/34 ,  G01C21/20 ,  G06Q10/047 ,  G06F18/23 ,  G06N3/006 ,  G06Q50/32

Abstract: 本发明公开了一种基于大规模稀疏中国邮递员问题的路径规划方法，包括：获取待优化路径中道路的端点和交汇点的位置，以道路端点和交汇点作为节点建立无向路网图；筛选出无向路网图中奇数度节点集合Vodd，构建由Vodd中所有节点间最短路径形成的完全图；对Vodd中的奇数度节点进行聚类，得到多个子节点群；合并子节点群，使合并后的各子节点群自身邻近节点集合覆盖率均在邻近节点集合覆盖率阈值以上；对合并后的子节点群进行偶数化处理；求解偶数化后的各子节点群内的最短匹配边集，并将最短匹配边集中的对应边添加到无向路网图上，形成所有节点度均为偶数的欧拉图；确定路径起点，在欧拉图中得到从该起点开始的欧拉回路作为优化路径。