一种交通网络不相交路径搜寻方法

摘要

本发明公开一种交通网络不相交路径搜寻方法，该方法首先在二维坐标上建立交通网络模型，确定几何区域相交关系，然后在两条不相交路径的基础上使用启发式算法逼近最优解，最终找到两条几何区域不相交路径。本发明方法能够解决流通网络区域故障防御问题，建立一种启发式方法，对近似解修正迭代逼近最优解，提高搜寻两条几何区域不相交路径的效率。

主权项

一种交通网络不相交路径搜寻方法，其特征在于该方法包括以下步骤：步骤1)用户输入实数D，所述D为交通网络故障区域圆的直径；步骤2)用户输入交通网络无向图G(V,E)和两条从起始S到终点T的互不相交路径P1(V1,E1)、P2(V2,E2)，将P1(V1,E1)与P2(V2,E2)几何区域相交的点对加入集合，记为集合K；所述V是无向图G的所有点组成的集合，E是无向图G所有边组成的集合，所述V1为路径P1(V1,E1)上所有点组成的集合，E1为路径P1(V1,E1)上所有边组成的集合，V2为路径P2(V2,E2)上所有点组成的集合，E2为路径P2(V2,E2)上所有边组成的集合；所述两条路径互不相交是指：不存在点v，v∈V1且v∈V2；所述几何区域相交是指：存在点对(u,v)，其中u∈V1，u∈V2且u与v的欧几里德距离小于D；所述欧几里德距离是指，(x1,y1)和(x2,y2)的欧几里德距离为R，其中步骤3)初始化集合Q为空集，所述Q表示不可用点的集合；步骤4)将V划分成两个集合S1、S2，u到P1(V1,E1)的距离记为dis1，u到P2的距离记为dis2，若dis1<dis2，u∈S1，其中u∈V，若dis1≥dis2，u∈S2；所述点u到路径P的距离是指，u与路径P中所有点的欧几里德距离的最小值；步骤5)当K为空集，P1(V1,E1)与P2(V2,E2)即为两条几何区域不相交路径，结束求解过程；否则，寻找点k，使得k属于P1(V1,E1)和P2(V2,E2)并集去除Q组成的集合，即k∈(P1(V1,E1)∪P2(V2,E2))/Q，同时满足k＝x或k＝y，若这样的k点不存在，则不存在两条几何区域不相交路径，搜寻过程结束；所述K是步骤2)得到的集合；步骤6)寻找一条a到b的最短路Px(Vx,Ex)，其中Vx为路径Px上所有点组成的集合，Ex为路径Px所有边组成的集合，且其中a是k在Pj上的第一个前驱点，b是k在Pj上的第一个后继点，且v∈Vx，其中且不存在(x,y)∈K满足k＝x或k＝y；若Px存在，Q＝Q∪{k}；若Px不存在，返回步骤5)；所述v的第一个前驱点为p是指，v的第一个后继点为f是指其中Ej为Pj的边集，所述j∈{1,2}且k∈Pj；步骤7)将Vj更新为Vj_S→a∪Vx∪Vj_b→T，Ej更新为Ej_S→a∪Ex∪Ej_b→T，所述Vj_S→a是指S到a最短路上所有点组成的点集，Vj_b→T是指b到T最短路上所有点组成的点集；所述Ej_S→a是指S到a最短路上所有边组成的边集，Ej_b→T是指b到T最短路上所有点组成的点集；所述Vx为Px的点集，Ex为Px的边集；步骤8)将K设置为空集，执行步骤2)得到K；将S1、S2分别设置为空集，执行步骤4)得到S1、S2；返回步骤5)。