成都市內(nèi)旅游路線規(guī)劃研究
——基于SA、GA算法

0 引言

隨著我國經(jīng)濟的不斷增長，旅游行業(yè)從無到有、從弱到強，在增進中國同其他國家之間的友誼和交往中發(fā)揮了積極作用和協(xié)同功能，旅游業(yè)已成為發(fā)出中國聲音、講好中國故事、加強與世界聯(lián)系的重要平臺。在滿足基本溫飽的基礎(chǔ)之上，人民對精神文明的追求日益增長，旅游已經(jīng)成為一種新興的生活方式，是人們工作之余休閑娛樂的重要選擇之一。在出行時，由于景點較多時間較短，規(guī)劃出一條距離最短的最優(yōu)路線，無論是對消費者還是景區(qū)都是一件不可多得的好事，同時也是提高消費者旅途幸福感的重要體現(xiàn)。一條合理的旅游路線可以花費最少的時間成本，將各個旅游景點串聯(lián)起來形成哈密頓圈，從而獲得最大的觀賞體驗。

2021年，成都市實現(xiàn)旅游總收入3085億元，接待游客2.05億人次，入選“2021中國旅游業(yè)最發(fā)達城市TOP6”。本文的研究以成都市內(nèi)的12個熱門旅游景點為例，基于SA、GA算法，利用python編程找出最優(yōu)路徑，為旅游者提供路線規(guī)劃。

1 算法的基本思想及計算流程

本節(jié)以TSP問題為研究對象，分別介紹模擬退火算法和遺傳算法在解決TSP問題時的算法思想及算法流程。

1.1 模擬退火算法

1.1.1 算法思想

由初始解和控制參數(shù)初值開始，對當前解重復(fù)“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減控制參數(shù)值，算法終止時，當前解的值即為近似最優(yōu)解，這便是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。

①設(shè)組合優(yōu)化問題的一個解i及其目標函數(shù)（fi）分別與固體的一個微觀狀態(tài)i及其能量Ei等價。

②令隨算法進程遞減其值的溫度控制參數(shù)t擔當固體退火過程中的溫度T的角色；則對于控制參數(shù)t的每一取值，算法持續(xù)進行“產(chǎn)生新解一判斷一接受／舍棄”的達代過程，就對應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程，也就是執(zhí)行了一次Metropolis算法。

③重復(fù)執(zhí)行Metropolis算法，就可以在控制參數(shù)，趨于零時，最終求得組合優(yōu)化問題的整體最優(yōu)解。

1.1.2 計算流程

使用模擬退火算法解決TSP問題的流程圖如圖1所示。

圖1 模擬退火算法實現(xiàn)TSP流程

1.2 遺傳算法

1.2.1 算法思想

①遺傳算法將生物進化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對各個體進行篩選，從而使適值高的個體被保留下來，組成新的群體。

②新群體包含上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。這樣不斷迭代循環(huán)，群體中各個體適值不斷提高，直至滿足一定的極限條件。

③此時，群體中適值最高的個體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復(fù)雜空間進行全局優(yōu)化搜索。

④遺傳算法對于搜索空間不需要連續(xù)、可微、單峰等限制性的假設(shè)。

1.2.2 計算流程

①初始參數(shù)設(shè)置。在搜索空間U上定義一個適應(yīng)度函數(shù)（fx），給定種群規(guī)模N，交叉率Pc和變異率Pm，迭代次數(shù)T。②初始種群產(chǎn)生。隨機產(chǎn)生U中的N個個體S1，S2，…，SN，組成初始種群S={S1，S2，…，SN}，置迭代次數(shù)計數(shù)器t=1。③計算適應(yīng)度。計算S中每個個體的適應(yīng)度f（）。④迭代判斷。若終止條件滿足，則取S中適應(yīng)度最大的個體作為所求結(jié)果，算法結(jié)束。⑤選擇-復(fù)制。按選擇概率P（xi）所決定的選中機會，每次從S中隨機選定1個個體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個染色體組成群體S1。⑥交叉。按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，兩兩隨機配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2。⑦變異。按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3。⑧將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步③。

2 算法的實現(xiàn)

2022年1月20日，國務(wù)院印發(fā)《“十四五”旅游業(yè)發(fā)展規(guī)劃》，成都成為首增“旅游城市布局”專欄中34個旅游樞紐城市之一。成都市4A級及以上景區(qū)51家、國家級旅游度假區(qū)1家、省級旅游度假區(qū)14家，A級景區(qū)2021年全年接待游客1.5億人次，同比增長42.33%，門票收入15.87億元，同比增長93.81%。

本研究選取了金沙遺址、杜甫草堂、青羊?qū)m、武侯祠、錦里、寬窄巷子、人民公園、文殊院、春熙路、九眼橋、環(huán)球中心、成都市熊貓繁育基地等12個景點，并依次用V→V分別表示，其經(jīng)緯度如表1所示。假如一位熱愛自駕游的旅行者按上述景點進行旅游路線規(guī)劃，在模擬退火算法和遺傳算法中，采用各個景點的經(jīng)緯度，用Python編程實現(xiàn)，最終得到景點間最優(yōu)路線的閉合哈密頓圈。

2.1 SA算法的Python實現(xiàn)

以表1中的坐標數(shù)據(jù)為輸入，根據(jù)SA算法輸出結(jié)果圖2可知，經(jīng)過模擬退火算法進行數(shù)次迭代，得到最終的哈密頓圈，若以V為起點，得到遍歷12個景點的最優(yōu)路徑為：V→V→V→V→V→V→V→V→V→V→V→V→V

圖2 SA算法下成都市旅游最優(yōu)路徑

表1 成都市景區(qū)經(jīng)緯度 單位：度

即游覽路線為武侯祠、青羊?qū)m、金沙遺址、寬窄巷子、文殊院、成都市熊貓培育基地、春熙路、杜甫草堂、人民公園、環(huán)球中心、九眼橋、錦里、最后回到武侯祠時，游覽路徑最短。

2.2 GA算法的Python實現(xiàn)

同樣的，以表1中的坐標為數(shù)據(jù)輸入，根據(jù)GA算法輸出結(jié)果圖3可知，經(jīng)過遺傳算法進行數(shù)次復(fù)制、交叉、變異，得到最終的哈密頓圈，若以V為起點，得到遍歷12個景點的最優(yōu)路徑為：V→V→V→V→V→V→V→V→V→V→V→V→V

圖3 GA算法下成都市旅游最優(yōu)路徑

即游覽路線為環(huán)球中心、九眼橋、錦里、武侯祠、青羊?qū)m、金沙遺址、寬窄巷子、文殊院、成都市熊貓培育基地、春熙路、杜甫草堂、人民公園、最后回到環(huán)球中心時，游覽路徑最短。

圖4 進化過程

3 結(jié)論

本研究選取成都市內(nèi)旅游景點，以自駕游或打車的旅行者為研究對象，采集百度地圖上成都市內(nèi)12個景點的經(jīng)緯度，基于路程最優(yōu)化采取SA算法和GA算法構(gòu)建哈密頓圈，并采用python求解得出最優(yōu)游覽路線。觀察兩種算法得結(jié)果可以發(fā)現(xiàn)，模擬退火算法和遺傳算法采用Python進行尋優(yōu)時，得出的最小哈密頓圈路徑相同。模型的優(yōu)點在于：

①采用該模型，可以針對所需達到的點構(gòu)造出一個哈密頓圈，求出最優(yōu)路線，節(jié)約了大量的時間和資金成本。

②與傳統(tǒng)的采用Matlab進行遍歷循環(huán)不同，該模型基于python編程實現(xiàn)，語言更加簡單優(yōu)美并且免費，對旅游者來說節(jié)約成本并有更強的實用性。

除此以外，也存在一些不足之處：

①該模型采用的是景點的經(jīng)緯度數(shù)據(jù)，沒有考慮到實際行程中早晚行車高峰期帶來的影響。

②僅是從規(guī)劃串聯(lián)12個景區(qū)的最優(yōu)路徑出發(fā)，沒有考慮在景點內(nèi)的游玩時間，以及一次性游玩所有景點的可能性。

為完成一次美好的旅游體驗，對旅行者提出以下建議：

①旅游之前規(guī)劃好出行路線，盡可能地減少中轉(zhuǎn)次數(shù)，節(jié)省時間和精力。

②旅游途中安排好住宿問題，盡量安排在靠近中心區(qū)域，方便出行和景點游覽。

對于旅游公司提出以下建議：

①充分發(fā)掘旅游資源的潛力，打造有特色的旅游景區(qū)，充分利用互聯(lián)網(wǎng)媒體的廣泛覆蓋優(yōu)勢，挖掘潛在的旅游客戶。

②基于數(shù)據(jù)分析，制定出各個景點之間的最優(yōu)路線，達到節(jié)約資源提升旅行者的幸福感。

③在旅游旺季，增加景點擺渡車輛，減少候車時間，使旅行者更多的在景區(qū)里而不是在路上。

該方法不僅可適用于消費者規(guī)劃出全國各省的最佳旅游路線，而且可以運用到網(wǎng)紅店打卡最優(yōu)問題、貨物運輸問題和快遞行業(yè)送貨上門問題以及小區(qū)、學(xué)校、醫(yī)院等公共基礎(chǔ)建設(shè)的選址問題等。本文僅選取了成都市內(nèi)的景點，景點選擇較為單一，后續(xù)研究可以從市內(nèi)擴展到周邊，例如同時考慮到周邊的青城山、都江堰、峨眉山、樂山、九寨溝、黃龍景區(qū)、四姑娘山等景點，并用一定的方法賦予各個游覽景點價值系數(shù)，選取其中一些價值系數(shù)更高的景點進行旅游路線規(guī)劃，使旅行的價值最大化。