基于遺傳算法的旅游線路規(guī)劃研究

郭豐林

摘 要：本文針對當(dāng)前重點(diǎn)關(guān)注的旅游路徑規(guī)劃問題，綜合利用圖論和智能算法的相關(guān)理論，通過建立TSP數(shù)學(xué)模型和使用遺傳算法對問題進(jìn)行求解，得到了遍歷30個景點(diǎn)的時(shí)間最短、總距離最短的旅游路徑。結(jié)果表明該方法具有較好的有效性和實(shí)用性。

關(guān)鍵詞：旅游路徑規(guī)劃，TSP，遺傳算法

當(dāng)前旅游業(yè)正朝著定制化、個性化方向發(fā)展，對旅游路徑的規(guī)劃也逐漸成為研究熱點(diǎn)。多數(shù)學(xué)者針對單一景區(qū)內(nèi)的游人行走線路或針對長距離、大跨度的跨省、出境游路徑規(guī)劃展開研究，而忽略了受眾更廣，更貼近日常出行真實(shí)狀況的中遠(yuǎn)途（不跨?。⒍虝r(shí)間內(nèi)（不超過1周）的自駕出行情況，本文正是針對該范圍內(nèi)的中小型區(qū)域旅游展開研究，將上海及周邊多個景區(qū)構(gòu)成的旅游目的地網(wǎng)絡(luò)作為研究對象，將路線規(guī)劃問題抽象成TSP問題并建立哈密頓回路的數(shù)學(xué)模型，通過傳統(tǒng)遺傳算法實(shí)現(xiàn)對該區(qū)域旅游路徑的規(guī)劃，幫助游客提升出行體驗(yàn)。

一、提出問題

假設(shè)一游客計(jì)劃從上海出發(fā)，自駕游覽上海市及周邊共30個景區(qū)并最終回到出發(fā)地，根據(jù)出行需求，游客要遍歷每個景區(qū)且各個景區(qū)只能到訪一次，如何規(guī)劃路線可以使游客在最短時(shí)間內(nèi)完成游覽目標(biāo)。

根據(jù)問題，提出以下假設(shè)：

（1）每兩個景區(qū)之間都有直接接通的公路，不存在兩個景點(diǎn)間必須通過其他景點(diǎn)才能到達(dá)的情況，且連接各景區(qū)的公路均為直線。

（2）游客在景區(qū)間的移動過程全程自駕，且平均車速為40km/h。

（3）不考慮游客中途停車、用餐、夜間休息或其他突發(fā)因素造成的時(shí)間增加，且游客到達(dá)景區(qū)馬上開始游覽，沒有時(shí)間間隔。

（4）游客在各個景區(qū)內(nèi)的游覽時(shí)間是固定的，不因到達(dá)的時(shí)刻不同而變化。

二、建立模型

TSP問題即旅行商問題，可描述為：已知n各城市坐標(biāo)，一個商人從起點(diǎn)城市出發(fā)，經(jīng)過且只經(jīng)過每個城市一次，最后回到起點(diǎn)城市的最短路程。TSP問題屬于NP完全問題的一種，目前沒有精確算法可以找到最優(yōu)解，只能找到有效地近似解。

TSP問題的數(shù)學(xué)描述為：在正權(quán)圖G（V，E）中，頂點(diǎn)集合V={1，2，…，n}，邊集合為E，d為城市i到城市j的距離矩陣，要找到最短路徑的回路，成為最佳哈密頓回路或最佳哈密頓圈。

三、算法實(shí)現(xiàn)

遺傳算法是模擬生物界“物競天擇，適者生存”的自然演化規(guī)律的一種隨機(jī)搜索方法，它將自然界繁殖、雜交、變異、競爭等概念引入算法當(dāng)中，通過一組可行解進(jìn)行交叉、變異、逆轉(zhuǎn)化等操作得到最優(yōu)解，是一種全局最優(yōu)算法。其基本思路為，首先對問題參數(shù)進(jìn)行編碼，形成一定數(shù)量的染色體，即初始種群，然后計(jì)算種群的適應(yīng)度，再利用迭代對初始種群進(jìn)行交叉、變異等操作得到更加優(yōu)秀（適應(yīng)度更高）的種群，最終保留符合目標(biāo)的最優(yōu)群體。

在本例中，利用遺傳算法求解上述模型的主要步驟及部分代碼如下：

（1）編碼

在遺傳算法中，大部分時(shí)候采用二進(jìn)制編碼方式，但在求解旅行商問題時(shí)最簡單最直接的編碼方式是基于結(jié)點(diǎn)順序進(jìn)行編碼，如針對一個9個景點(diǎn)的旅游路徑3-2-6-4-8-9-5-1-7可直接用（3 2 6 4 8 9 5 1 7）進(jìn)行編碼，直觀明了的情況下還可以滿足模型中的約束條件。

（2）初始化種群

隨機(jī)生成一個初始解，初始解的個數(shù)決定了初始化種群的數(shù)量，本文中設(shè)定初始解中個體的數(shù)量為NIND=30，同時(shí)設(shè)定最大迭代次數(shù)為GENMAX=500次。

（3）適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來評判個體優(yōu)劣性的唯一標(biāo)準(zhǔn)，是遺傳算法進(jìn)行個體選擇的依據(jù)，通常適應(yīng)度函數(shù)由目標(biāo)函數(shù)轉(zhuǎn)化而來，當(dāng)求解目標(biāo)函數(shù)最小值時(shí)，一般使適應(yīng)度值最大，因此采用目標(biāo)函數(shù)的倒數(shù)值作為適應(yīng)度值，本文模型中目標(biāo)函數(shù)為總距離最短，因此適應(yīng)度函數(shù)設(shè)置如下

?（4）選擇操作

選擇操作是使用輪盤賭的方式，從上一代種群中選擇較優(yōu)秀的個體作為父代繁衍子代，父代個體被選擇的概率與其適應(yīng)度值相關(guān)，適應(yīng)度值越高，被選擇的概率越大，個體i被選擇的概率pi為

?（5）交叉操作

將上一步選擇的兩個個體作為父代進(jìn)行交叉操作以產(chǎn)生新的子代，其方法是在[1，9]（以9個城市為例）之間隨機(jī)取兩個整數(shù)r1和r2，將r1和r2之間的部分交換，本文中設(shè)置交叉概率pc=0.8。

（6）變異操作

變異操作是指在新產(chǎn)生的子代個體上進(jìn)行的變異操作，主要為了維持子代個體的多樣性，其方法是在[1，9]之間隨機(jī)取兩個整數(shù)r1和r2，將個體這兩個位置上的編碼數(shù)字互換。

（7）終止條件判定

本文的終止條件為迭代次數(shù)=GENMAX（最大迭代次數(shù)），否則返回步驟3進(jìn)行循環(huán)。

四、結(jié)果分析

根據(jù)以上遺傳算法模型，利用MATLAB編程進(jìn)行模擬求解，得到結(jié)果在第462代的到最優(yōu)結(jié)果，最優(yōu)路徑為1-2-19-20-10-21-18-3-9-11-7-8-14-15-24-25-26-29-28-27-23-22-16-17-30-12-13-4-5-6-1，總距離為459.86km，計(jì)算后可得游客在旅途路上（不包括游覽時(shí)間）所用的最短時(shí)間為11.5h。對結(jié)果分析可知，該模型和算法大大縮短了總路程，根據(jù)問題描述和假設(shè)，得到了最短距離、最短時(shí)間游覽全部景點(diǎn)的路徑，該問題得到解決，可見遺傳算法對于解決TSP旅游路徑規(guī)劃問題效果顯著。

總結(jié)與展望

本文首先將旅游規(guī)劃問題轉(zhuǎn)換成TSP問題，然后建立混合整數(shù)規(guī)劃模型，最后利用遺傳算法設(shè)計(jì)程序并求解該問題，高效便捷的解決了旅游線路規(guī)劃問題。但本研究結(jié)果仍存在不足，如當(dāng)景點(diǎn)數(shù)量n過大時(shí)，遺傳算法求解效率會大幅降低，此時(shí)可以考慮將其他近似算法與遺傳算法相結(jié)合提高求解效率，這些內(nèi)容有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] 徐婷婷，王? 柱，徐海洋.旅游路線規(guī)劃數(shù)學(xué)模型的建立與應(yīng)用探討[J].廊坊師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2016，16（1）：23-26.

[2] 喻? 菡.遺傳算法求解TSP的研究[D].西南交通大學(xué)，2006.

[3] 鄭天翔.基于動態(tài)實(shí)時(shí)調(diào)度的主題公園游客時(shí)空分流導(dǎo)航管理研究[J].旅游科學(xué)，2012，26（4）：8-16.

[4] 鄭天翔，吳? 蓉，羅海媛.國內(nèi)景區(qū)旅游流調(diào)控研究綜述[J].地理與地理信息科學(xué)，2015，31（5）：90-96.