基于旅行商問題的森林防火巡邏路徑優(yōu)化

強(qiáng)添綱，任亞平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S表示出發(fā)點(diǎn)。

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

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

∪表示巡邏隊(duì)攜帶的防火物資。

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

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

Minimize:

Subject to:

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

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

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

表1 地理坐標(biāo)信息Tab．1 Geographical coordinates information

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

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

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

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

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

1．2．1 第一次TSP算法改進(jìn)測(cè)試

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

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

圖4則是經(jīng)過200次的遺傳迭代進(jìn)化后，得出的最優(yōu)解，即最終的優(yōu)化路徑選擇。具體路徑選擇為:1→10→8→3→4→7→9→6→11→5→12→2→1，其總距離為:6．649 3 km。

圖3 第一次試驗(yàn)的隨機(jī)方案Fig．3 The random solution of the first experiment

圖4 第一次試驗(yàn)200次進(jìn)化迭代的結(jié)果Fig．4 The result of 200 iterations in the first experiment

圖5 第一次試驗(yàn)200次進(jìn)化迭代的收斂曲線圖Fig．5 The convergence graph of 200 iterations in the first experiment

圖5為該測(cè)試下的迭代進(jìn)化趨勢(shì)圖像，可反映出優(yōu)化過程的信息。由進(jìn)化圖可以看出，測(cè)試中最大迭代次數(shù)MAXGEN=200，優(yōu)化前后路徑長度得到很大改進(jìn)，25代以后路徑長度已經(jīng)保持不變了，可以認(rèn)為已經(jīng)是最優(yōu)解了，總距離由優(yōu)化前17．335 8 km 變 為 6．649 3 km，減 為 原 來 的38．4%。另外，在該算法中還添加了記錄程序運(yùn)行的時(shí)間，由MATLAB命令窗口最后一行“Elapsed time is 15．879 234 seconds．”可以看出，整個(gè)路徑優(yōu)化所用時(shí)間為15．879 234 s。

1．2．2 第二次TSP算法改進(jìn)測(cè)試

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

圖6 第二次試驗(yàn)的隨機(jī)方案Fig．6 The random solution of the second experiment

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

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

圖7同樣是經(jīng)過200次的遺傳迭代進(jìn)化后，得出的最優(yōu)解。具體路徑選擇為:1→10→8→7→11→6→9→4→3→5→12→2→1，其總距離為:8．231 1 km。

圖8 第二次試驗(yàn)200次進(jìn)化迭代的收斂曲線圖Fig．8 The convergence graph of 200 iterations in the second experiment

圖8為第二次測(cè)試下的迭代進(jìn)化趨勢(shì)圖像，由進(jìn)化圖可以看出，優(yōu)化前后路徑長度也得到很大改進(jìn)，幾乎從20代以后路徑長度就已經(jīng)保持不變了，總距離由優(yōu)化前15．803 3 km變?yōu)?．231 1 km，減為原來的52．1%。記錄程序運(yùn)行的時(shí)間，由MATLAB命令窗口最后一行“．Elapsed time is 15．161 473 seconds．”可以看出，整個(gè)路徑優(yōu)化所用時(shí)間為 15．161 473 s。

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

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

從第一次和第二次測(cè)試得出的優(yōu)化路徑上可看出，兩次不同程度模型和算法上的改進(jìn)，產(chǎn)生的結(jié)果有所不同，即最終路徑的選擇方案不同。進(jìn)一步比較兩次的最短距離，三維空間中的距離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ū)域海拔差異對(duì)路徑距離的影響很大，不能將其忽略，采用二次改進(jìn)后的算法更合理，也更符合實(shí)際。

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

2 結(jié)束語

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

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

［2］孫慧平，李 健，郭偉剛．遺傳算法在束流切割路徑優(yōu)化中的應(yīng)用［J］，農(nóng)業(yè)機(jī)械學(xué)報(bào)，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ū)護(hù)林防火信息系統(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)的研究與實(shí)現(xiàn)［J］，中國安全科學(xué)學(xué)報(bào)，2005，15(2):99-103．

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

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

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

［11］向佐勇，劉正才，申平安．一種改進(jìn)的基于進(jìn)化階段的自適應(yīng)遺傳算法［J］，武漢大學(xué)學(xué)報(bào)(工學(xué)版)，2008，41(1):133-136．

［12］粱旗軍．一種基于遺傳算法的TSP建模方法［J］，計(jì)算機(jī)工程，2011，37(5):68-70．

［13］田貴超，黎 明，韋雪潔．旅行商問題(TSP)的幾種求解方法［J］，計(jì)算機(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．