基于旅行商问题的森林防火巡逻路径优化  

Forest Fire Patrol Path Optimization Based on the Traveling Salesman Problem

作　　者：强添纲[1] 任亚平[1] 

机构地区：[1]东北林业大学交通学院,哈尔滨150040

出　　处：《森林工程》2015年第6期80-84,88,共6页Forest Engineering

基　　金：国家自然科学基金项目(51405075);中央高校基本科研基金项目(2572014BB08);中国博士后科学基金项目(2013M541329);黑龙江省博士后级别资助项目(LBH-TZ0501)

摘　　要：在对传统TSP(traveling salesman problem,旅行商问题)模型进行研究的基础上,通过传统TSP模型和森林防火巡逻路径模型的比较,提出一种新的森林防火巡逻路径模型,并根据该模型对TSP算法进行第一次改进。然后,又在第一改进的前提下,首次将三维空间概念引入TSP算法,实现TSP算法的二次改进。随后对两次不同程度的改进分别进行了测试和分析。结果表明,两次改进优化效果都十分明显,第一次测试的路径优化效率达到61.6%,第二次测试的优化效率也达到47.9%。On the basis of the traditional TSP（ traveling salesman problem） model,by comparing the traditional TSP model and forest fire patrol path model,a new model for forest fire patrol path was proposed,and according to the model the TSP algorithm was improved for the first time. Then,the concept of three- dimensional space was introduced into TSP algorithm and accomplished secondary improvement on the TSP algorithm. The two different levels of improvements were tested and analyzed. The results showed that the optimization effects of the two improvements were obvious. The first test of path optimization efficiency reached 61. 6%,while the second test optimization efficiency was as high as 47. 9%.

关 键 词：森林防火 巡逻路径 模型 TSP算法 路径优化 

分 类 号：S765[农业科学—森林保护学]