灾情巡视最优路线的寻径算法  

Routing Algorithm of Disaster Inspection Optimal Paths

作　　者：刘长河 LIU Changhe(School of Science,Beijing University of Civil Engineering and Architecture,Beijing 100044)

机构地区：[1]北京建筑大学理学院

出　　处：《北京建筑大学学报》2019年第3期68-73,共6页Journal of Beijing University of Civil Engineering and Architecture

基　　金：国家社会科学基金项目(15AZD0081);住房和城乡建设部软科学研究项目(2016-R4-016)

摘　　要：灾情巡视属于旅行商问题,具有广泛的应用价值.假定有若干巡视组,分工协作对所辖区域内的各灾民聚集地进行巡视,需要对各巡视组的巡视任务、巡视路线进行合理的分配和设计.在现实生活中,各被巡视地点之间的交通网络都存在着连通性差的缺陷,它们几乎都不是全连通图,至包含度为1的节点.将遗传算法和Dijkstra算法结合起来,这一问题得到了很好解决.利用Matlab语言,编写出分组巡视所有灾区的最优巡视路线的寻径程序,并利用数值实验验证了此算法和程序的正确性.As the inspection tour of disaster is part of a traveling salesman problem(TSP),it plays an important role in disaster relief efforts.The routing algorithm is studied for seeking optimal paths to make inspection tours of disaster by certain number of various group of people and by the way of cooperation.In reality,the connectivity of the traffic network among the toured places is not good enough.Not only almost are they fully connected graphs,but also they frequently contain some nodes which degree is 1.The problem is overcome successfully through combination genetic algorithm and Dijkstra algorithm.Relevant procedures are written out in Matlab language.The correctness of our algorithms is validated by the result of numerical experiments.

关 键 词：灾情巡视 旅行商问题 遗传算法 DIJKSTRA算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP181[自动化与计算机技术—计算机科学与技术]