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

强添纲，任亚平

(东北林业大学交通学院，哈尔滨150040)

森林防火巡逻是日常林区预防火灾发生的长效机制，一般有护林员或附近居民等组成巡逻队伍，对附近的林区进行日常巡视检查，防患于未然。大多数的林区巡逻路径是依据当地人的经验而选择的。经验固然重要，但有时可能会造成多走路，耗时多，成本高的问题，甚至有些地形复杂的林区还没有形成一套固定有效的防火巡逻路径，为解决该问题，本文提出将先进的智能算法技术应用到森林防火巡逻路径优化中。

本文所指的TSP算法是以遗传算法为核心的智能算法，除智能算法外，解决TSP问题的算法，还有贪心算法、动态规划、回溯法等算法［1-3］。贪心算法常得到局部最优解，因为它不是从整体最优考虑的;动态规划算法从多项式角度入手，计算过程与分治法类似，所以会出现对同一个子问题的多次重复计算，降低了求解效率，不太适合解决TSP问题;回溯法时间复杂度为O(n!)，在地点较多时，耗时太久，而遗传智能算法的时间复杂度为O(2^n)，在TSP问题中，运行速度较快，且可求得最优解，所以本文选用遗传算法基础上的TSP算法，并用于森林防火巡逻路径模型的优化中。

1 传统的TSP模型

TSP是典型的NP完全问题(Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题)，又是一个组合优化问题，该问题可以被证明具有NP计算复杂性。TSP问题可描述为:假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是使求得的路径路程为所有路径之中的最小值。该问题表示如下:

整数集合N={1，2，3，…，n}(N中的元素表示要旅行的n个城市的编号)，则一个排列D={D1，D2，…，Dn}，使

取公式(1)最小值，其中，d(Di，Di+1)表示城市Di到城市Di+1的距离(二维平面距离)。

1．1 建立森林防火巡逻路径优化模型

本模型中首先明确目标函数为巡逻路径的总行程∑dij(dij表示从i地到j地的距离)。一般林区都划分为若干个巡逻区域，而每个巡逻区域通常是由一支巡逻队伍完成该区域范围内的巡回检查，所以本文中的模型是以划分的若干区域中的一个区域为研究对象，即在本问题中只存在一个移动对象。最后，确定巡回路线，即由出发点依次经各个必经地点，且每个必经地在一次巡逻中只需要经过一次，最终再返回出发点。本文所讲的巡逻路径问题和TSP问题类似，也是为了求得多个易发火灾地点之间的最短路径［4-8］，但是本问题还考虑了两点之间行程距离的约束，这样更符合森林防火巡逻路线的实际要求［9-10］。

1．1．1 模型假设

(1)存在n个必经地点(包括出发点)。

(2)一个区域只有一支巡逻队伍，且不存在一支队伍中的队员分开进行巡逻。

(3)每个必经地在一次巡逻中只需巡逻一次，就不再返回该点。

(4)必经地两点间的最大距离不得大于1．5 km。

(5)每支巡逻队伍携带一定的防火物资(包括简单的灭火工具)。

(6)两点间距离采用三维空间距离，考虑高度差异。

1．1．2 建立数学模型

根据问题描述和做出的假设，定义以下模型参数:

S表示出发点。

D={m|m=1，2，…n-1}是除了出发点S外的所有必经地点的集合。

A=S∪D是包含出发点S在内的所有必经地点的集合。

∪表示巡逻队携带的防火物资。

d(Di，Dj)表示必经地点Di到Dj的距离(三维空间距离)。

则可建立如下数学模型:

Minimize:

Subject to:

其中，公式(2)为该模型的决策函数，表示在遵循TSP问题基本假设的前提下，并考虑了本路径模型的特殊要求(公式(3)～公式(7)的约束条件)，然后求得路径行程的最小值;公式(3)保证每一个必经的巡逻地点，巡逻队伍都只经过一次，不发生再次返回该点的情形;公式(4)表示巡逻队伍到达一个巡逻地点后就离开该点，前往下一点;公式(5)说明巡逻队从出发点前往其他必经巡逻地时，随身携带一定的防火物资;公式(6)规定了除出发点外，巡逻队需要完成巡视检查工作地点的数量为n-1;公式(7)是对两巡逻地点间距离的约束，该约束用来控制巡逻的覆盖密度;公式(8)表示整数约束，然后得到最优解或近似最优解(最终优化得出的路径选择方式和选择该路径下的总行程)。

1．2 TSP算法两次改进前后运行结果的分析与比较

文中试验数据来源于深圳市梧桐山地带的仙湖植物园保护区，借助于深圳市卫星电子地图和Google地图软件来获取和处理相关数据信息，共采集和筛选出12组数据信息(见表1)，采用MATLAB软件优化平台，针对该保护区的防火巡逻路径建立了相关数学模型，提出不同于传统TSP问题的决策约束条件，并于2014年8月18日(星期六)进行一次实地考察和测量。同时，本文截取了2014年11月22日(星期六)的遥感图像如图1和图2所示，该遥感图像的获取时间不同于实地考察时间，但这对于本模型的决策函数和决策约束都不会产生影响，因为这段时间内，该林区的交通网络体系和防火巡逻机制没有发生变化。图1(从图中大坑塘位置看，视角海拔高度为2．90 km)在一定程度上客观反映了该保护区的地形和地质状况，可以大致看出，该区域为低山地和丘陵混合地形，有较明显的海拔差异，图2主要标注了该地区一些重要地点的位置，其中有一些地点被选为本文测试的必经地点。

表1 地理坐标信息Tab．1 Geographical coordinates information

表1为本测试所有采集地点中选取的12个必经地点(包括出发点)，给出了12个必经地点的地理坐标及其海拔高度等原始数据信息。

表1对12组测试数据进行了序号标注，以下必经地点为方便处理，采用相应序号代表地点。另外，表1中的地理坐标在实际测试中，并没有直接输入MATLAB编程中，而是首先对地理坐标进行转化，利用相关的角度弧度转换器工具将地理坐标直接转化为方便在MATLAB直角坐标系图像中显示的弧度坐标值，这样可以实现图像的可视化(即经MATLAB编程运行后，得出的路径选择图像的x，y轴为实数形式)。

图1 梧桐山遥感图像Fig．1 The remote sensing image of Mount．Wutong

图2 梧桐山遥感图像Fig．2 The remote sensing image of Mount．Wutong

图3～图8为两次测试中的相关数据结果和图像。

1．2．1 第一次TSP算法改进测试

第一次测试，需要在传统的TSP模型上增加式公(3)～公式(8)等决策约束进行改进调整，但不将海拔作为影响因素考虑进巡逻路径模型中，即仍采用二维平面坐标体系(仅将地理坐标的经纬度编入程序)求得的距离，然后开始MATLAB编程运行和数据处理，结果显示出最优路径选择和最短距离如图3～图5所示:

图3表示初始种群中的一个随机方案［11-14］，即种群初始化时，随机选择出的一条完整巡逻路径。其中1号点为出发点，即从电视塔处出发向其它的11个必经地点依次进行防火巡逻。具体路径选择为:1→5→12→11→9→10→6→7→8→2→4→3→1，该路径下的总距离为:17．335 8 km。

图4则是经过200次的遗传迭代进化后，得出的最优解，即最终的优化路径选择。具体路径选择为:1→10→8→3→4→7→9→6→11→5→12→2→1，其总距离为:6．649 3 km。

图3 第一次试验的随机方案Fig．3 The random solution of the first experiment

图4 第一次试验200次进化迭代的结果Fig．4 The result of 200 iterations in the first experiment

图5 第一次试验200次进化迭代的收敛曲线图Fig．5 The convergence graph of 200 iterations in the first experiment

图5为该测试下的迭代进化趋势图像，可反映出优化过程的信息。由进化图可以看出，测试中最大迭代次数MAXGEN=200，优化前后路径长度得到很大改进，25代以后路径长度已经保持不变了，可以认为已经是最优解了，总距离由优化前17．335 8 km 变 为 6．649 3 km，减 为 原 来 的38．4%。另外，在该算法中还添加了记录程序运行的时间，由MATLAB命令窗口最后一行“Elapsed time is 15．879 234 seconds．”可以看出，整个路径优化所用时间为15．879 234 s。

1．2．2 第二次TSP算法改进测试

第二次测试，不仅在传统TSP的模型上添加公式(3)～公式(8)等决策约束，还要改进原来的坐标体系，采用三维空间坐标体系(将地理坐标的经纬度和海拔高度都编入程序)求得的距离，然后进行MATLAB编程运行和数据处理。为方便直观地表达三维空间的路径选择图像，第二次测试中的图像采用空间路径在二维平面(x，y)上的投影，结果显示出最优路径选择和最短距离如图6～图8所示。

图6 第二次试验的随机方案Fig．6 The random solution of the second experiment

图6表示该次测试初始种群中的一个随机方案，仍将1号点(电视塔位置)作为出发点，向其它的11个必经地点依次进行防火巡逻。具体路径选择为:1→9→10→12→7→5→3→8→4→2→6→11→1，该路径下的总距离为:15．803 3 km。

图7 第二次试验200次进化迭代的结果Fig．7 The result of 200 iterations in the second experiment

图7同样是经过200次的遗传迭代进化后，得出的最优解。具体路径选择为:1→10→8→7→11→6→9→4→3→5→12→2→1，其总距离为:8．231 1 km。

图8 第二次试验200次进化迭代的收敛曲线图Fig．8 The convergence graph of 200 iterations in the second experiment

图8为第二次测试下的迭代进化趋势图像，由进化图可以看出，优化前后路径长度也得到很大改进，几乎从20代以后路径长度就已经保持不变了，总距离由优化前15．803 3 km变为8．231 1 km，减为原来的52．1%。记录程序运行的时间，由MATLAB命令窗口最后一行“．Elapsed time is 15．161 473 seconds．”可以看出，整个路径优化所用时间为 15．161 473 s。

表2给出了两次不同测试中所得数据信息的对比结果，从表中的初始距离、优化距离和优化效率上都可以明显看出两次测试都取得了很好的优化效果，表明在传统旅行商问题(TSP)模型的基础上，结合森林防火巡逻路径的特殊决策约束，研究的路径优化问题具有可行性。

观察两次测试的运行时间，可看出两次时间差异不大，则说明第二次改进在时间上没有发生较大变化，运行时间不超过16 s，算法效率比较高。

从第一次和第二次测试得出的优化路径上可看出，两次不同程度模型和算法上的改进，产生的结果有所不同，即最终路径的选择方案不同。进一步比较两次的最短距离，三维空间中的距离8．231 1 km大于二维平面距离6．649 3 km，相差1．581 8 km，差异比较明显。通过图4和图7所示，更能直观地发现二者优化结果的差异，图4是一条封闭的多边形，而图7中则出现了路线交叉，说明在该区域海拔差异对路径距离的影响很大，不能将其忽略，采用二次改进后的算法更合理，也更符合实际。

表2 两次不同改进后的TSP算法结果对比Tab．2 The results comparison between the two improved TSP algorithms

2 结束语

本文在对经典TSP问题模型和遗传算法进行分析的基础上，引入三维空间坐标体系，针对森林防火巡逻路径优化提出一种新的模型和路径优化算法，依据添加的诸多决策约束，对算法进行两次不同程度的改进，然后实现其编程。从运行结果的合理性和运行时间的高效性，对两次测试进行了比较和分析。两次测试结果表明，两次的优化效果都十分显著，说明本文建立的数学模型具有实际可行性，但两次测试得出的路径优化结果存在较大差异，这充分表明将二维平面转化为三维空间引入本文研究的模型中，取得了很好的效果，使优化结果更加真实客观。另外，不同的区域，具有不同的地形特点，本文选取的为最高海拔在1000 m左右的低山地和丘陵混合区，海拔差异所造成的影响不能忽略，但影响有时不是很明显，比如本文中两次测试后的最短距离虽有不同，但相差并不是很大，所以本文研究的模型和算法在海拔较高和海拔差异较大的地区应用，会体现出更大的价值。

［1］于莹莹．改进的遗传算法求解旅行商问题［J］，控制与决策，2014，29(8):1483-1488．

［2］孙慧平，李 健，郭伟刚．遗传算法在束流切割路径优化中的应用［J］，农业机械学报，2008，39(9):158-160．

［3］ Whitley D，Hains D，Howe A．A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover［A］．In:Proc．of the 11th Int Conf on Parallel Problem Solving from Nature［C］，Berlin:Springer Heidelberg，2010:566-575．

［4］刘玉锋，李 虎，陈功照．天山西部林区护林防火信息系统构建［J］，地球信息科学，2007，9(6):94-99．

［5］ Yu W，Liu Z，Bao X．Optimal deterministic algorithms for some variants of online quota traveling salesman problem［J］．European Journal of Operational Research，2014，238:735-740．

［6］ Akay A E，Wing M G，Sivrikaya F，et al．A GIS-based decision support system for determining the shortest and safest route to forest fires:a case study in Mediterranean Region of Turkey［J］．Environ ment Monitoring Assessment，2012，184(3):1391-1407．

［7］王阿川．森林火灾防治决策专家系统的研究与实现［J］，中国安全科学学报，2005，15(2):99-103．

［8］赵 璠，舒立福，邓忠坚，等．林火扑救队伍跟踪及扩林员巡护管理系统研究［J］．林业机械与木工设备，2014，42(12):22-26．

［9］谢阳生，黄水生，李惺颖，等．基于遗传算法的森林防火航空巡护路径规划［J］，吉林大学学报(理学版)，2014，52(5):1001-1006．

［10］赵 璠，周汝良，王艳霞，等．连续化森林火险天气等级预报模型的研究与实现［J］．林业机械与木工设备，2015，43(2):37-40．

［11］向佐勇，刘正才，申平安．一种改进的基于进化阶段的自适应遗传算法［J］，武汉大学学报(工学版)，2008，41(1):133-136．

［12］粱旗军．一种基于遗传算法的TSP建模方法［J］，计算机工程，2011，37(5):68-70．

［13］田贵超，黎 明，韦雪洁．旅行商问题(TSP)的几种求解方法［J］，计算机仿真，2006，8(8):153-157．

［14］ Ahmed Z．H．Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator［J］．International Journal of Biometrics and Bioinformatics，2010，3(6):96-105．