利索能及
我要发布
收藏
专利号: 2018102238506
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-07-29
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种并行均衡的多路线规划方法,基于各个旅行商,实现多目标位置节点的集合划分,以及各集合中目标位置节点的路径规划;其中,多目标位置节点的数量大于旅行商的数量,其特征在于,包括如下步骤:步骤A.初始化目标位置节点集合V={vn|n=1,…,N},N表示目标位置节点的数量;以及初始化各个旅行商分别一一对应的c1、…、cm、…、cM各访问集合,并针对各个访问集合cm,定义访问集合上限容量为 M表示旅行商的数量,然后进入步骤B;

步骤B.定义m=1,由目标位置节点集合V中随机选择一个目标位置节点,作为cm访问集合的集合中心,并在目标位置节点集合V中删除该目标位置节点,然后进入步骤C;

步骤C.判断m+1是否大于M,是则即针对所有访问集合,获得各个访问集合cm的集合中心,并进入步骤F;否则进入步骤D;

步骤D.分别针对目标位置节点集合V中的各个目标位置节点,获得目标位置节点分别到各个具有集合中心的访问集合的欧几里得距离dnm,并获得其中的最短欧几里得距离,作为该目标位置节点所对应的最短欧几里得距离,进而获得目标位置节点集合V中各目标位置节点所对应最短欧几里得距离之和Sum,然后进入步骤E;

步骤E.在0至Sum范围中任取一个整数值Ram,并按目标位置节点集合V中各目标位置节点的标号顺序,以及各个具有集合中心的访问集合的标号顺序,依次遍历目标位置节点集合V中各目标位置节点分别对应各具有集合中心的访问集合的欧几里得距离dnm,若Ram-dnm的值小于或等于0,则直接将该dnm所对应的目标位置节点,作为cm+1访问集合的集合中心,并停止遍历,以及在目标位置节点集合V中删除该目标位置节点,然后针对m的值进行加1更新,并返回步骤C;

步骤F.获得目标位置节点集合V中各个目标位置节点分别到各个访问集合cm的集合中心的欧几里得距离,并进入步骤G;

步骤G.以单次循环方式,依次针对各个访问集合,基于访问集合中已存在目标位置节点的数量,以及访问集合上限容量为b,将距离该访问集合cm的集合中心、最小欧几里得距离所对应的一个目标位置节点,加入至该访问集合cm当中,并在目标位置节点集合V中删除该目标位置节点;如此依次进行各个单次循环,直至目标位置节点集合V为空集;即完成目标位置节点集合V中所有目标位置节点,向各个访问集合的分配,然后进入步骤H;

步骤H.基于各个访问集合cm分别所包含的目标位置节点,分别获得各个访问集合cm中的新集合中心,然后判断是否存在原集合中心与新集合中心彼此不一致的访问集合,是则进入步骤I;否则进入步骤J;

步骤I.分别针对各个访问集合cm,首先采用新集合中心替换原集合中心,接着将访问集合中除集合中心以外的全部目标位置节点,加入至目标位置节点集合V当中,并删除该访问集合中除集合中心以外的全部目标位置节点,进而更新所有访问集合,然后返回步骤F;

步骤J.计算获得各个访问集合cm分别所对应的全局最优路线访问顺序,最后由各个旅行商分别针对其所对应的访问集合,按访问集合所对应的全局最优路线访问顺序,针对访问集合中各个目标位置节点依次进行访问。

2.根据权利要求1所述一种并行均衡的多路线规划方法,其特征在于:所述步骤D中,分别针对目标位置节点集合V中的各个目标位置节点,按如下公式:获得目标位置节点分别到各个具有集合中心的访问集合的欧几里得距离dnm,其中,表示第m个访问集合的集合中心,dnm表示目标位置节点集合V中第n个目标位置节点与第m个访问集合的集合中心之间的欧几里得距离。

3.根据权利要求1所述一种并行均衡的多路线规划方法,其特征在于,所述步骤G包括如下步骤:步骤G1.判断目标位置节点集合V是否为空集,是则即完成目标位置节点集合V中所有目标位置节点,向各个访问集合的分配,然后进入步骤H;否则进入步骤G2;

步骤G2.定义m=1,并进入步骤G3;

步骤G3.判断访问集合cm中已存在目标位置节点的数量,是否等于访问集合上限容量为b,是则进入步骤G4;否则将距离访问集合cm、最小欧几里得距离所对应的一个目标位置节点,加入至访问集合cm当中,并在目标位置节点集合V中删除该目标位置节点,然后进入步骤G4;

步骤G4.判断m是否等于M,是则返回步骤G1;否则针对m的值进行加1更新,并返回步骤G3。

4.根据权利要求1所述一种并行均衡的多路线规划方法,其特征在于,所述步骤H中,基于各个访问集合cm分别所包含的目标位置节点,按如下公式:分别获得各个访问集合cm中的新集合中心,其中, 表示属于第m个访问集合的第n个目标位置节点的横坐标, 表示属于第m个访问集合的第n个目标位置节点的纵坐标, 表示第m个访问集合的集合中心的横坐标, 表示第m个访问集合的集合中心的纵坐标, 表示第m个访问集合中目标位置节点的个数。

5.根据权利要求1所述一种并行均衡的多路线规划方法,其特征在于,所述步骤J中,分别针对各个访问集合cm,可并行执行如下步骤J1至步骤J7,分别获得各个访问集合cm分别所对应的全局最优路线访问顺序,最后由各个旅行商分别针对其所对应的访问集合,按访问集合所对应的全局最优路线访问顺序,针对访问集合中各个目标位置节点依次进行访问;

步骤J1.初始化参数,设置粒子为xi,i=1,2,…,I,访问集合cm中目标位置节点的个数为 粒子个体的感知范围 吸引系数β、最大迭代次数tmax参数,然后进入步骤J2;

步骤J2.采用切比雪夫混沌映射生成由I个粒子组成的初始种群,分别针对各粒子xi,获得粒子xi所对应一组解路径为 代表粒子xi所对应解路径中、途经的第l个城市,根据如下公式:

计算各粒子xi所对应解路径长度f(xi),再根据如下公式:

计算各粒子xi的绝对吸引度 然后进入步骤J3;

步骤J3.根据如下公式:

计算粒子xp和粒子xq之间的距离 其中,p=1,2,…,I,q=1,2,…,I,粒子xp所对应一组解路径为 粒子xq所对应一组解路径为再根据如下公式:

计算群体中各粒子之间的相对吸引度 然后进入步骤J4;其中,L0表示粒子绝对吸引度的初值,由绝对吸引度 的目标函数所决定,β表示预设吸引系数,且β∈[0,1],e表示自然对数的底数;

步骤J4.根据如下公式:

计算各粒子xp移向邻域集内粒子xq的选择概率 其中, 表示粒子xp在t时刻邻居的集合,t表示迭代次数,然后进入步骤J5;

步骤J5.通过轮盘赌的方式进行位置选择,计算更新粒子的位置,重新计算各粒子之间的相对吸引度 然后进入步骤J6;

步骤J6.计算各粒子所对应的解路径长度,并判断是否满足最大迭代次数tmax,是则获得全局最优值,以及访问集合cm所对应的全局最优路线访问顺序;否则进入步骤J7;

步骤J7.针对各粒子分别所对应的解路径,调用C2Opt算子进行局部调整优化,然后返回步骤J3。