基于遺傳算法的旅游線路優化*

潘玉俠， 梁勤歐

(浙江師范大學地理與環境科學學院，浙江金華 321004)

0 引言

一個旅游區域內各景點分布在不同的位置，對某些景點進行游覽的先后順序有多種不同的串聯方式，組合成不同的旅游線路．為了使旅游者能花費較少的時間而盡可能多地游覽風景名勝，設計出最優的旅游線路成為必要．但是，旅游業發展到今天，無論在國內還是國外，旅游線路設計的成果都不是很多，高水平的研究成果更為稀少［1］．規劃出的旅游線路多是依據各景點的歷史文化背景和景區特色進行的分類規劃，綜合考慮到使旅行時間和距離最優化的研究很少．目前國內外有關這方面的文獻主要有:文獻［2］建立了最優旅游線路的模型;文獻［3］研究了從中心城市出發的最優旅游線路;文獻［4-5］選擇不同的角度，構造了5種旅行線路模式．本文擬引進遺傳算法，對旅游線路進行優化，實驗對象為浙江省內20個旅游景點的旅游線路優化，目的是研究遺傳算法進行旅游線路優化的可行性和高效性．

1 旅游線路優化問題描述

旅行線路設計的好壞直接影響到開發的功效，因此，旅游線路設計在區域旅游的開發中是一個非常重要的內容．一般的旅游設計著重于旅行景點的多樣化，使游客在旅行過程中對每個景點都能產生截然不同的感覺;也有的旅游線路將同類的旅游景點串聯起來，給游客展現出一類景點的完整畫面，如歷史古跡游、風景名勝游等．但這些線路的設計往往只考慮到某些景點的串聯可以帶給游客怎樣的感官享受．這種設計方法很少注重效益方面的問題，即旅游者在出游時希望通過最小的旅游時間和成本獲取最大的旅游經歷．時間上，一般一個景點的游覽時間大約都是一致的，予以重點考慮的是旅途時間，在空間上盡可能使整條線路有最便捷的走向來提高旅游效益．本文以景點之間的距離這個約束因素，對選定的20個旅游景點的旅行線路進行距離上的優化．

2 遺傳算法對旅行線路優化求解設計

遺傳算法最早由美國密執安大學的Holland教授提出，起源于20世紀60年代對自然和人工自適應系統的研究，是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法［6］．遺傳算法對旅行線路優化求解設計的具體運算過程如圖1所示．

2．1 染色體編碼

遺傳算法中有多種不同的編碼方法，主要有二進制編碼方法、符號編碼方法、浮點數編碼方法等．在遺傳算法的運行過程中，它不對所求解問題的實際決策變量直接進行操作，而是對表示可行解的個體編碼施加選擇、交叉、變異等操作，不斷搜索出適應度較高的個體，并在群體中逐漸增加其數量，最終尋出問題的最優解或近似最優解．

為了本文的研究簡便起見，筆者采用符號編碼方法．符號編碼方法是指個體染色體編碼串中的基因值取自一個無數值含義，而只有代碼含義的符號集．這個符號集可以是1個字母表，如{A，B，C，D，…};也可以是 1 個數字序號表，如{1，2，3，4，5，…}等;本文需要研究包含20個旅游景點的旅行路線優化問題;用符號編碼的方法，每個數字代表1個景點，隨機生成區間為［1，20］的20個整數的隨機排列，如下所示，這個排列就可以作為一個染色體．

圖1 遺傳算法對旅行線路優化求解設計的主要運算過程

?

從以上可以看出，符號編碼具有以下優點:1)符合有意義積木塊編碼原則;2)便于在遺傳算法中利用所求解問題的專門知識;3)便于遺傳算法與相關近似算法之間的混合使用．

2．2 適應度函數設計

本文所要研究的是在給定特定景點的情況下，選擇怎樣的編排方式，使旅途所花費的時間和成本最少，取得最優效益．因此，構造適應度函數時，為了簡單起見，本文只考慮各景點之間的實際距離．適應度函數構造如下:

式(1)中，Sij代表第i個景點和第j個景點之間的歐氏距離．

2．3 控制參數設計

遺傳算法進行旅游線路優化控制參數設計如表1所示．

表1 遺傳算法主要控制參數

2．4 存活選擇策略

采用輪盤賭的方式，選取適應值大的個體作為父體．

選擇過程是以旋轉賭輪100次為基礎，每次旋轉都為新的種群選擇一個個體．賭輪是按個體的適應度進行選擇的，適應值大的個體則選取，適應值小的個體則去除．具體算法設計是:先計算出每個個體累計概率值，然后從區間［0，1］中產生出一個隨機數r，若某個個體的累計概率值大于這個隨機數r，則選取這個個體．

2．5 遺傳算子設計

1)交叉算子設計:本文采用部分映射交叉(PMX)，確定交叉操作的父代，將100個樣本兩兩組合分為50組．首先從閉區間［0，1］中產生2個隨機數b1和b2，另r1等于b1×100和b2×100，確定2個位置，對2位置中間的數據進行交叉．交叉后，同一樣本中會有重復的景點，不重復的數字保留，重復的數字采用部分映射交叉法消除重復．

2)變異算子設計:本文采用倒位變異法，和交叉算子的設計相似．即隨機選擇2個點c1和c2，交換位置，并將2點間的數字從c2開始倒序放置．

3 實驗仿真

本文采用位于浙江省內的20個景點進行路線優化的試驗，景點名稱和景點序號代碼及景點經緯度坐標如表2所示，所選取的景點排除了受季節性影響比較大的個體，如舟山桃花島．因為景點級別相當，文中對景點權重值和游客在每個景點的逗留時間進行了簡化處理，即假設各景點的權重值及游客在每個景點的逗留時間均為1，在進行旅游線路優化時，只考慮景點之間的歐氏距離，即給出各景點的相對坐標值，采用歐氏距離的計算方法:

式(2)中:Sij代表第i點到第j點之間的距離;(xi，yi)，(xj，yj)為i點和j點的相對經緯度坐標值．實驗中忽略了地圖投影引起的差異，在小范圍內作實驗研究，只是想說明遺傳算法的效果，在以后進一步的研究中將以實驗球面距離來計算．

表2 各景點的相對經緯坐標值

本文基于遺傳算法理論建立的旅行線路優化算法運行結果如圖2所示，其中的1～20數字是各城市的代號，具體所代表的城市和表2相對應．運行的最優結果為 10．409 3，平均值為12．475 4．圖3 為搜索過程，驗證了該算法具有較好的收斂性;圖4為搜索路徑的最終結果圖，較好地展示了最優的行走路線．為了更好地將結果展示出來，本文采用ArcGIS軟件將結果在地圖上繪制出來，如圖5所示，以使結果更明確，同時根據路線圖也驗證了實驗所得的數據具有一定的真實性，最終驗證了遺傳算法理論運用于旅行線路優化設計中的可行性．

圖2 旅游線路優化算法運行結果

圖3 搜索最優旅游路線過程

圖4 最優旅游路徑運行結果

4 結論

隨著旅游業的蓬勃發展，設計出完善可行的旅游線路，既有利于我國旅游業的發展，也有利于游客及旅行社在旅游過程中節約成本．而現階段的旅游線路設計多是著重于旅游景點的搭配和特色旅游線路之上，很少有從優化旅行距離和時間入手的．鑒于此，本文首次提出了將遺傳算法理論運用于旅游線路優化之中，并建立了基于遺傳算法的旅行線路優化算法．經過實驗仿真，證明了遺傳算法理論運用于旅游線路優化之中的有效性．在采用遺傳算法理論進行旅游線路優化的過程中，所選取的影響因子過于單一，本文變量因子只有距離因素，有可能會使實驗結果與事實有一定程度的偏差，許多方面還有待完善．期望在以后的研究中能夠有更完善的成果，使采用該方法規劃的旅游線路能夠具有一定的靈活性，并和事實能夠緊密結合，讓這一理論在旅游線路規劃和設計方面的應用能夠擴展開來，真正應用到實際中來．

圖5 最優旅行路線圖

［1］呂威，倪玉華．基于等距加密和案例推理的旅游線路聚類算法［J］．計算機工程和應用，2010，46(11):223-225．

［2］Campbell C K．An approach to research in recreational geography［M］．British Columbia:Department of Geography，University of British Columbia，1967:32-37．

［3］滕聰，曹文．旅游景點篩選組合及旅游線路的優化算法與應用［J］．地球信息科學學報，2010(5):668-673．

［4］Stewart S I，Vogt C A．Multi-destination trip patterns［J］．Annals of Tourism Research，1997，24(2):458-461．

［5］Lundgren J O J．The development of tourist travel system:A metropolitan economic hegemony par excellence［M］．Jahrgang:Jahrbuch fur Fremdenverkegr，1972:62-65．

［6］周明，孫樹棟．遺傳算法原理及應用［M］．北京:國防工業出版社，1999:38-39．