強添綱，任亞平

(東北林業(yè)大學(xué)交通學(xué)院，哈爾濱150040)

森林防火巡邏是日常林區(qū)預(yù)防火災(zāi)發(fā)生的長效機制，一般有護林員或附近居民等組成巡邏隊伍，對附近的林區(qū)進行日常巡視檢查，防患于未然。大多數(shù)的林區(qū)巡邏路徑是依據(jù)當?shù)厝说慕?jīng)驗而選擇的。經(jīng)驗固然重要，但有時可能會造成多走路，耗時多，成本高的問題，甚至有些地形復(fù)雜的林區(qū)還沒有形成一套固定有效的防火巡邏路徑，為解決該問題，本文提出將先進的智能算法技術(shù)應(yīng)用到森林防火巡邏路徑優(yōu)化中。

本文所指的TSP算法是以遺傳算法為核心的智能算法，除智能算法外，解決TSP問題的算法，還有貪心算法、動態(tài)規(guī)劃、回溯法等算法［1-3］。貪心算法常得到局部最優(yōu)解，因為它不是從整體最優(yōu)考慮的;動態(tài)規(guī)劃算法從多項式角度入手，計算過程與分治法類似，所以會出現(xiàn)對同一個子問題的多次重復(fù)計算，降低了求解效率，不太適合解決TSP問題;回溯法時間復(fù)雜度為O(n!)，在地點較多時，耗時太久，而遺傳智能算法的時間復(fù)雜度為O(2^n)，在TSP問題中，運行速度較快，且可求得最優(yōu)解，所以本文選用遺傳算法基礎(chǔ)上的TSP算法，并用于森林防火巡邏路徑模型的優(yōu)化中。

1 傳統(tǒng)的TSP模型

TSP是典型的NP完全問題(Non-deterministic Polynomial的問題，即多項式復(fù)雜程度的非確定性問題)，又是一個組合優(yōu)化問題，該問題可以被證明具有NP計算復(fù)雜性。TSP問題可描述為:假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是使求得的路徑路程為所有路徑之中的最小值。該問題表示如下:

整數(shù)集合N={1，2，3，…，n}(N中的元素表示要旅行的n個城市的編號)，則一個排列D={D1，D2，…，Dn}，使

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

1．1 建立森林防火巡邏路徑優(yōu)化模型

本模型中首先明確目標函數(shù)為巡邏路徑的總行程∑dij(dij表示從i地到j(luò)地的距離)。一般林區(qū)都劃分為若干個巡邏區(qū)域，而每個巡邏區(qū)域通常是由一支巡邏隊伍完成該區(qū)域范圍內(nèi)的巡回檢查，所以本文中的模型是以劃分的若干區(qū)域中的一個區(qū)域為研究對象，即在本問題中只存在一個移動對象。最后，確定巡回路線，即由出發(fā)點依次經(jīng)各個必經(jīng)地點，且每個必經(jīng)地在一次巡邏中只需要經(jīng)過一次，最終再返回出發(fā)點。本文所講的巡邏路徑問題和TSP問題類似，也是為了求得多個易發(fā)火災(zāi)地點之間的最短路徑［4-8］，但是本問題還考慮了兩點之間行程距離的約束，這樣更符合森林防火巡邏路線的實際要求［9-10］。

1．1．1 模型假設(shè)

(1)存在n個必經(jīng)地點(包括出發(fā)點)。

(2)一個區(qū)域只有一支巡邏隊伍，且不存在一支隊伍中的隊員分開進行巡邏。

(3)每個必經(jīng)地在一次巡邏中只需巡邏一次，就不再返回該點。

(4)必經(jīng)地兩點間的最大距離不得大于1．5 km。

(5)每支巡邏隊伍攜帶一定的防火物資(包括簡單的滅火工具)。

(6)兩點間距離采用三維空間距離，考慮高度差異。

1．1．2 建立數(shù)學(xué)模型

根據(jù)問題描述和做出的假設(shè)，定義以下模型參數(shù):

S表示出發(fā)點。

D={m|m=1，2，…n-1}是除了出發(fā)點S外的所有必經(jīng)地點的集合。

A=S∪D是包含出發(fā)點S在內(nèi)的所有必經(jīng)地點的集合。

∪表示巡邏隊攜帶的防火物資。

d(Di，Dj)表示必經(jīng)地點Di到Dj的距離(三維空間距離)。

則可建立如下數(shù)學(xué)模型:

Minimize:

Subject to:

其中，公式(2)為該模型的決策函數(shù)，表示在遵循TSP問題基本假設(shè)的前提下，并考慮了本路徑模型的特殊要求(公式(3)～公式(7)的約束條件)，然后求得路徑行程的最小值;公式(3)保證每一個必經(jīng)的巡邏地點，巡邏隊伍都只經(jīng)過一次，不發(fā)生再次返回該點的情形;公式(4)表示巡邏隊伍到達一個巡邏地點后就離開該點，前往下一點;公式(5)說明巡邏隊從出發(fā)點前往其他必經(jīng)巡邏地時，隨身攜帶一定的防火物資;公式(6)規(guī)定了除出發(fā)點外，巡邏隊需要完成巡視檢查工作地點的數(shù)量為n-1;公式(7)是對兩巡邏地點間距離的約束，該約束用來控制巡邏的覆蓋密度;公式(8)表示整數(shù)約束，然后得到最優(yōu)解或近似最優(yōu)解(最終優(yōu)化得出的路徑選擇方式和選擇該路徑下的總行程)。

1．2 TSP算法兩次改進前后運行結(jié)果的分析與比較

文中試驗數(shù)據(jù)來源于深圳市梧桐山地帶的仙湖植物園保護區(qū)，借助于深圳市衛(wèi)星電子地圖和Google地圖軟件來獲取和處理相關(guān)數(shù)據(jù)信息，共采集和篩選出12組數(shù)據(jù)信息(見表1)，采用MATLAB軟件優(yōu)化平臺，針對該保護區(qū)的防火巡邏路徑建立了相關(guān)數(shù)學(xué)模型，提出不同于傳統(tǒng)TSP問題的決策約束條件，并于2014年8月18日(星期六)進行一次實地考察和測量。同時，本文截取了2014年11月22日(星期六)的遙感圖像如圖1和圖2所示，該遙感圖像的獲取時間不同于實地考察時間，但這對于本模型的決策函數(shù)和決策約束都不會產(chǎn)生影響，因為這段時間內(nèi)，該林區(qū)的交通網(wǎng)絡(luò)體系和防火巡邏機制沒有發(fā)生變化。圖1(從圖中大坑塘位置看，視角海拔高度為2．90 km)在一定程度上客觀反映了該保護區(qū)的地形和地質(zhì)狀況，可以大致看出，該區(qū)域為低山地和丘陵混合地形，有較明顯的海拔差異，圖2主要標注了該地區(qū)一些重要地點的位置，其中有一些地點被選為本文測試的必經(jīng)地點。

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

表1為本測試所有采集地點中選取的12個必經(jīng)地點(包括出發(fā)點)，給出了12個必經(jīng)地點的地理坐標及其海拔高度等原始數(shù)據(jù)信息。

表1對12組測試數(shù)據(jù)進行了序號標注，以下必經(jīng)地點為方便處理，采用相應(yīng)序號代表地點。另外，表1中的地理坐標在實際測試中，并沒有直接輸入MATLAB編程中，而是首先對地理坐標進行轉(zhuǎn)化，利用相關(guān)的角度弧度轉(zhuǎn)換器工具將地理坐標直接轉(zhuǎn)化為方便在MATLAB直角坐標系圖像中顯示的弧度坐標值，這樣可以實現(xiàn)圖像的可視化(即經(jīng)MATLAB編程運行后，得出的路徑選擇圖像的x，y軸為實數(shù)形式)。

圖1 梧桐山遙感圖像Fig．1 The remote sensing image of Mount．Wutong

圖2 梧桐山遙感圖像Fig．2 The remote sensing image of Mount．Wutong

圖3～圖8為兩次測試中的相關(guān)數(shù)據(jù)結(jié)果和圖像。

1．2．1 第一次TSP算法改進測試

第一次測試，需要在傳統(tǒng)的TSP模型上增加式公(3)～公式(8)等決策約束進行改進調(diào)整，但不將海拔作為影響因素考慮進巡邏路徑模型中，即仍采用二維平面坐標體系(僅將地理坐標的經(jīng)緯度編入程序)求得的距離，然后開始MATLAB編程運行和數(shù)據(jù)處理，結(jié)果顯示出最優(yōu)路徑選擇和最短距離如圖3～圖5所示:

圖3表示初始種群中的一個隨機方案［11-14］，即種群初始化時，隨機選擇出的一條完整巡邏路徑。其中1號點為出發(fā)點，即從電視塔處出發(fā)向其它的11個必經(jīng)地點依次進行防火巡邏。具體路徑選擇為:1→5→12→11→9→10→6→7→8→2→4→3→1，該路徑下的總距離為:17．335 8 km。

圖4則是經(jīng)過200次的遺傳迭代進化后，得出的最優(yōu)解，即最終的優(yōu)化路徑選擇。具體路徑選擇為: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次進化迭代的結(jié)果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為該測試下的迭代進化趨勢圖像，可反映出優(yōu)化過程的信息。由進化圖可以看出，測試中最大迭代次數(shù)MAXGEN=200，優(yōu)化前后路徑長度得到很大改進，25代以后路徑長度已經(jīng)保持不變了，可以認為已經(jīng)是最優(yōu)解了，總距離由優(yōu)化前17．335 8 km 變 為 6．649 3 km，減 為 原 來 的38．4%。另外，在該算法中還添加了記錄程序運行的時間，由MATLAB命令窗口最后一行“Elapsed time is 15．879 234 seconds．”可以看出，整個路徑優(yōu)化所用時間為15．879 234 s。

1．2．2 第二次TSP算法改進測試

第二次測試，不僅在傳統(tǒng)TSP的模型上添加公式(3)～公式(8)等決策約束，還要改進原來的坐標體系，采用三維空間坐標體系(將地理坐標的經(jīng)緯度和海拔高度都編入程序)求得的距離，然后進行MATLAB編程運行和數(shù)據(jù)處理。為方便直觀地表達三維空間的路徑選擇圖像，第二次測試中的圖像采用空間路徑在二維平面(x，y)上的投影，結(jié)果顯示出最優(yōu)路徑選擇和最短距離如圖6～圖8所示。

圖6 第二次試驗的隨機方案Fig．6 The random solution of the second experiment

圖6表示該次測試初始種群中的一個隨機方案，仍將1號點(電視塔位置)作為出發(fā)點，向其它的11個必經(jīng)地點依次進行防火巡邏。具體路徑選擇為:1→9→10→12→7→5→3→8→4→2→6→11→1，該路徑下的總距離為:15．803 3 km。

圖7 第二次試驗200次進化迭代的結(jié)果Fig．7 The result of 200 iterations in the second experiment

圖7同樣是經(jīng)過200次的遺傳迭代進化后，得出的最優(yōu)解。具體路徑選擇為: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為第二次測試下的迭代進化趨勢圖像，由進化圖可以看出，優(yōu)化前后路徑長度也得到很大改進，幾乎從20代以后路徑長度就已經(jīng)保持不變了，總距離由優(yōu)化前15．803 3 km變?yōu)?．231 1 km，減為原來的52．1%。記錄程序運行的時間，由MATLAB命令窗口最后一行“．Elapsed time is 15．161 473 seconds．”可以看出，整個路徑優(yōu)化所用時間為 15．161 473 s。

表2給出了兩次不同測試中所得數(shù)據(jù)信息的對比結(jié)果，從表中的初始距離、優(yōu)化距離和優(yōu)化效率上都可以明顯看出兩次測試都取得了很好的優(yōu)化效果，表明在傳統(tǒng)旅行商問題(TSP)模型的基礎(chǔ)上，結(jié)合森林防火巡邏路徑的特殊決策約束，研究的路徑優(yōu)化問題具有可行性。

觀察兩次測試的運行時間，可看出兩次時間差異不大，則說明第二次改進在時間上沒有發(fā)生較大變化，運行時間不超過16 s，算法效率比較高。

從第一次和第二次測試得出的優(yōu)化路徑上可看出，兩次不同程度模型和算法上的改進，產(chǎn)生的結(jié)果有所不同，即最終路徑的選擇方案不同。進一步比較兩次的最短距離，三維空間中的距離8．231 1 km大于二維平面距離6．649 3 km，相差1．581 8 km，差異比較明顯。通過圖4和圖7所示，更能直觀地發(fā)現(xiàn)二者優(yōu)化結(jié)果的差異，圖4是一條封閉的多邊形，而圖7中則出現(xiàn)了路線交叉，說明在該區(qū)域海拔差異對路徑距離的影響很大，不能將其忽略，采用二次改進后的算法更合理，也更符合實際。

表2 兩次不同改進后的TSP算法結(jié)果對比Tab．2 The results comparison between the two improved TSP algorithms

2 結(jié)束語

本文在對經(jīng)典TSP問題模型和遺傳算法進行分析的基礎(chǔ)上，引入三維空間坐標體系，針對森林防火巡邏路徑優(yōu)化提出一種新的模型和路徑優(yōu)化算法，依據(jù)添加的諸多決策約束，對算法進行兩次不同程度的改進，然后實現(xiàn)其編程。從運行結(jié)果的合理性和運行時間的高效性，對兩次測試進行了比較和分析。兩次測試結(jié)果表明，兩次的優(yōu)化效果都十分顯著，說明本文建立的數(shù)學(xué)模型具有實際可行性，但兩次測試得出的路徑優(yōu)化結(jié)果存在較大差異，這充分表明將二維平面轉(zhuǎn)化為三維空間引入本文研究的模型中，取得了很好的效果，使優(yōu)化結(jié)果更加真實客觀。另外，不同的區(qū)域，具有不同的地形特點，本文選取的為最高海拔在1000 m左右的低山地和丘陵混合區(qū)，海拔差異所造成的影響不能忽略，但影響有時不是很明顯，比如本文中兩次測試后的最短距離雖有不同，但相差并不是很大，所以本文研究的模型和算法在海拔較高和海拔差異較大的地區(qū)應(yīng)用，會體現(xiàn)出更大的價值。

［1］于瑩瑩．改進的遺傳算法求解旅行商問題［J］，控制與決策，2014，29(8):1483-1488．

［2］孫慧平，李 健，郭偉剛．遺傳算法在束流切割路徑優(yōu)化中的應(yīng)用［J］，農(nóng)業(yè)機械學(xué)報，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］劉玉鋒，李 虎，陳功照．天山西部林區(qū)護林防火信息系統(tǒng)構(gòu)建［J］，地球信息科學(xué)，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］王阿川．森林火災(zāi)防治決策專家系統(tǒng)的研究與實現(xiàn)［J］，中國安全科學(xué)學(xué)報，2005，15(2):99-103．

［8］趙 璠，舒立福，鄧忠堅，等．林火撲救隊伍跟蹤及擴林員巡護管理系統(tǒng)研究［J］．林業(yè)機械與木工設(shè)備，2014，42(12):22-26．

［9］謝陽生，黃水生，李惺穎，等．基于遺傳算法的森林防火航空巡護路徑規(guī)劃［J］，吉林大學(xué)學(xué)報(理學(xué)版)，2014，52(5):1001-1006．

［10］趙 璠，周汝良，王艷霞，等．連續(xù)化森林火險天氣等級預(yù)報模型的研究與實現(xiàn)［J］．林業(yè)機械與木工設(shè)備，2015，43(2):37-40．

［11］向佐勇，劉正才，申平安．一種改進的基于進化階段的自適應(yīng)遺傳算法［J］，武漢大學(xué)學(xué)報(工學(xué)版)，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．