基于遺傳算法的旅游線路優(yōu)化*

潘玉俠， 梁勤歐

(浙江師范大學(xué)地理與環(huán)境科學(xué)學(xué)院，浙江金華 321004)

0 引言

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

1 旅游線路優(yōu)化問題描述

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

2 遺傳算法對旅行線路優(yōu)化求解設(shè)計

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

2．1 染色體編碼

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

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

圖1 遺傳算法對旅行線路優(yōu)化求解設(shè)計的主要運算過程

?

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

2．2 適應(yīng)度函數(shù)設(shè)計

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

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

2．3 控制參數(shù)設(shè)計

遺傳算法進行旅游線路優(yōu)化控制參數(shù)設(shè)計如表1所示．

表1 遺傳算法主要控制參數(shù)

2．4 存活選擇策略

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

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

2．5 遺傳算子設(shè)計

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

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

3 實驗仿真

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

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

表2 各景點的相對經(jīng)緯坐標值

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

圖2 旅游線路優(yōu)化算法運行結(jié)果

圖3 搜索最優(yōu)旅游路線過程

圖4 最優(yōu)旅游路徑運行結(jié)果

4 結(jié)論

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

圖5 最優(yōu)旅行路線圖

［1］呂威，倪玉華．基于等距加密和案例推理的旅游線路聚類算法［J］．計算機工程和應(yīng)用，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］滕聰，曹文．旅游景點篩選組合及旅游線路的優(yōu)化算法與應(yīng)用［J］．地球信息科學(xué)學(xué)報，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］周明，孫樹棟．遺傳算法原理及應(yīng)用［M］．北京:國防工業(yè)出版社，1999:38-39．