1.一种基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,包括:获取待优化路径中道路的端点和交汇点的位置,以所述道路端点和交汇点作为节点建立无向路网图G=(V,E);
其中,V为节点集合,E为边集;
筛选出所述无向路网图中奇数度节点集合Vodd,构建由Vodd中所有节点间最短路径形成的完全图;
对Vodd中的奇数度节点进行聚类,得到多个子节点群;
合并子节点群,使合并后的各子节点群自身邻近节点集合覆盖率均在邻近节点集合覆盖率阈值以上;
对合并后的子节点群进行偶数化处理,使每个合并后的子节点群中节点的数量均为偶数;
求解偶数化后的各子节点群内的最短匹配边集,并将所述最短匹配边集中的对应边添加到所述无向路网图上,形成所有节点度均为偶数的欧拉图;
确定路径起点,在所述欧拉图中得到从该起点开始的欧拉回路作为优化路径。
2.根据权利要求1所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,所述子节点群自身邻近节点集合覆盖率通过如下公式进行计算:式中,Coverageij表示子节点群Ci对邻近节点集合CNj中节点的覆盖率;Ni为同时属于子节点群Ci和CNj的节点集合;|Ni|为节点集合Ni中的节点个数;|CNj|为邻近节点集合CNj中的节点个数。
3.根据权利要求2所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,所述邻近节点集合覆盖率阈值为:式中,thresholdcov为邻近节点集合覆盖率阈值,Num为聚类得到的子节点群的个数。
4.根据权利要求3所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,对合并后的子节点群进行偶数化处理的方法为:筛选出节点个数为奇数的子节点群,作为目标子节点群;
计算各目标子节点群的中心节点间的最短匹配边集;
筛选出最短匹配边集对应的两子节点群中靠近子节点群边缘,且到两个子节群中心距离差最小的节点,记为边界节点;
将所述边界节点的属类,使所述匹配群中心节点归属由最短匹配边集对应的两子节点群中的一个节点群修改为另一个节点群。
5.根据权利要求3或4所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,基于蚁群算法求解偶数化后的各子节点群内的最短匹配边集,多只蚂蚁同时进行下述操作:步骤1、随机选择一个未匹配节点,并计算当前节点选择其余未匹配节点的概率;
步骤2、依据概率从其余未匹配节点中随机选择一个节点,两者进行匹配;
若仍有节点未进行匹配则重复步骤1‑2,直到所有节点均已匹配完成;
步骤3、从多只蚂蚁所得的匹配结果中,选择具有最短添加路径长度的匹配结果,作为最佳匹配结果,并对最佳匹配结果对应蚂蚁的信息素进行更新;
重复进行步骤1‑3,直到达到最大迭代次数,保存的整体最佳匹配结果作为最终结果;
其中,在迭代过程中,若当次的最佳匹配结果优于之前迭代的最佳匹配结果,则保存当前的最佳匹配结果作为整体最佳匹配结果。
6.根据权利要求5所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,对信息素进行更新时,每次增加量为常量。
7.根据权利要求6所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,采用密度峰值聚类算法对Vodd中的奇数度节点进行聚类,包括下步骤:对节点按照决策值γ由大到小顺序进行排序,得到节点序列;
选择决策值γ超过决策值阈值γthreshold的节点作为聚类中心集合CP1;
在所述节点序列中由前向后选择具有最大决策值邻近差γdmax的节点,经具有最大决策值邻近差γdmax的节点和其之前的所有节点作为聚类中心集合CP2;
选择CP1和CP2中节点数量较多的集合作为选定的聚类中心集合,其余节点按照相对聚类中心点的距离进行聚类,形成多个子节点群Vc={C1,…,CNum};
其中,Num为聚类得到的子节点群的个数。
8.根据权利要求7所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,决策值γ通过如下公式进行计算:式中,γi表示节点i的决策值;ρmax,ρmin分别为所有节点局部密度的最大值和最小值,δmax,δmin分别所有节点相对距离的最大值和最小值;ρi表示节点i的局部密度和δi表示节点i的相对距离。
9.根据权利要求8所述的基于大规模稀疏中国邮递员问题的路径规划方法,其特征在于,最大决策值邻近差γdmax的计算公式为:γdmax=maxi≥1∩i=N‑1(γi+1‑γi‑1);
其中,N为奇数度节点的个数;γi+1和γi‑1分别表示节点i+1和节点i‑1的决策值。