西南交通大学学报
西南交通大學學報
서남교통대학학보
JOURNAL OF SOUTHWEST JIAOTONG UNIVERSITY
2014年
1期
153-159
,共7页
航线%联程路径搜索%KMCSP问题%Yen*算法%A*算法%启发式策略
航線%聯程路徑搜索%KMCSP問題%Yen*算法%A*算法%啟髮式策略
항선%련정로경수색%KMCSP문제%Yen*산법%A*산법%계발식책략
flight path%connecting path search%KMCSP problem%Yen * algorithm%A * algorithm%heuristic strategy
为了解决在国际航线网络中查找联程路径时间花费较长的问题,针对国际航线网络联程路径搜索的特点,借助于A*算法的启发式策略,在对Yen算法改进的基础上,提出一种新的解决多约束条件下K条最短路径(K-multiple constrained shortest paths,KMCSP)问题的算法,即约束Yen*算法.在中转次数约束和特定中转点约束条件下,对国际航线网络进行了测试实验,结果表明:与约束Yen算法相比,约束Yen*算法的搜索效率提高了2.98倍,平均运行时间减少了78.3％,算法的搜索规模缩小了86％,且波动范围小.约束Yen*算法适用于多约束条件下快速求解国际航线网络联程路径搜索问题.
為瞭解決在國際航線網絡中查找聯程路徑時間花費較長的問題,針對國際航線網絡聯程路徑搜索的特點,藉助于A*算法的啟髮式策略,在對Yen算法改進的基礎上,提齣一種新的解決多約束條件下K條最短路徑(K-multiple constrained shortest paths,KMCSP)問題的算法,即約束Yen*算法.在中轉次數約束和特定中轉點約束條件下,對國際航線網絡進行瞭測試實驗,結果錶明:與約束Yen算法相比,約束Yen*算法的搜索效率提高瞭2.98倍,平均運行時間減少瞭78.3％,算法的搜索規模縮小瞭86％,且波動範圍小.約束Yen*算法適用于多約束條件下快速求解國際航線網絡聯程路徑搜索問題.
위료해결재국제항선망락중사조련정로경시간화비교장적문제,침대국제항선망락련정로경수색적특점,차조우A*산법적계발식책략,재대Yen산법개진적기출상,제출일충신적해결다약속조건하K조최단로경(K-multiple constrained shortest paths,KMCSP)문제적산법,즉약속Yen*산법.재중전차수약속화특정중전점약속조건하,대국제항선망락진행료측시실험,결과표명:여약속Yen산법상비,약속Yen*산법적수색효솔제고료2.98배,평균운행시간감소료78.3％,산법적수색규모축소료86％,차파동범위소.약속Yen*산법괄용우다약속조건하쾌속구해국제항선망락련정로경수색문제.
