基于蟻群算法的5A景點(diǎn)旅游路線規(guī)劃問題研究

萬慧云 蔣艷

摘 要： 根據(jù)我國(guó)普通居民旅游情況，建立并求解乘坐公共交通工具、花費(fèi)較少時(shí)間進(jìn)行舒適度較高、花費(fèi)較低的綜合效益最大化旅游體驗(yàn)?zāi)Ｐ停蕴嵘覈?guó)居民生活質(zhì)量。收集我國(guó)5A景點(diǎn)的經(jīng)緯度坐標(biāo)、門票費(fèi)用、最佳旅游時(shí)間、路況及食宿費(fèi)用等相關(guān)數(shù)據(jù)，基于蟻群算法與Matlab2018a軟件進(jìn)行編程求解，得出全國(guó)5A景區(qū)旅游路線規(guī)劃方案。最后根據(jù)研究結(jié)果得出結(jié)論，綜合時(shí)間、費(fèi)用、路程和舒適度4個(gè)目標(biāo)效益最大化的模型與已有單方面或只有2～3個(gè)目標(biāo)函數(shù)的模型相比，其在進(jìn)行旅游路線規(guī)劃時(shí)，不僅考慮因素更加全面，而且更加貼合我國(guó)大部分居民的實(shí)際需求。

關(guān)鍵詞：旅游路線規(guī)劃;蟻群算法;最短路徑

DOI：10. 11907/rjdk. 182281

中圖分類號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0141-04

0 引言

隨著社會(huì)的發(fā)展和人們生活水平的不斷提高，旅游經(jīng)濟(jì)收入已成為很多城市的主要收入來源之一。由于私家車數(shù)量不斷增多，導(dǎo)致旅途交通擁擠、景區(qū)車輛停放等問題越來越突出。因此，如何選擇合適的交通工具、最佳游覽時(shí)間實(shí)現(xiàn)舒適度較高，而花費(fèi)較低的旅游體驗(yàn)，對(duì)于城市居民生活質(zhì)量提升具有重要意義[1]。

1 研究現(xiàn)狀

旅游路線規(guī)劃問題是基于經(jīng)典TSP問題演化而來的。TSP問題是一個(gè)典型的組合優(yōu)化問題，目前國(guó)內(nèi)外對(duì)于TSP問題研究較多，已提出基于經(jīng)典算法改進(jìn)的Dijkstra算法、動(dòng)態(tài)規(guī)劃算法、分支定界法等[2]，以及基于啟發(fā)式優(yōu)化算法改進(jìn)的蟻群算法、遺傳算法、模擬退火算法、禁忌搜索算法、Hopfieltl神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等[3]。但截至目前，尚沒有一個(gè)解決TSP問題的完美方案。20世紀(jì)90年代，我國(guó)學(xué)者開始將TSP模型應(yīng)用于實(shí)際的旅游路線規(guī)劃問題中，研究結(jié)果表明，旅游者類型具有多樣化特征，但其目標(biāo)主要?dú)w結(jié)為兩種，即自我耗費(fèi)成本最小化與獲得收益最大化[4]。吳凱[5]將定量與定性方法相結(jié)合設(shè)計(jì)旅游路線，但未進(jìn)行實(shí)證分析，僅停留在理論層面;吳小根[6]分析研究江蘇省省內(nèi)旅游路線中城市節(jié)點(diǎn)、景區(qū)節(jié)點(diǎn)、臨時(shí)節(jié)點(diǎn)三大節(jié)點(diǎn)類型的節(jié)點(diǎn)配置特征;史春云[7]研究基于線路節(jié)點(diǎn)特性的旅游模式，探究長(zhǎng)三角城市旅游經(jīng)濟(jì)收益的空間差異[8];黃燕平[9]研究影響消費(fèi)者旅游路線選擇的相關(guān)因素，并以湖南永州旅游路線為例進(jìn)行實(shí)證分析;劉宇青[10]研究高鐵開通對(duì)消費(fèi)者旅游路線選擇的顯著影響;黃騰[11]首先采用遺傳算法對(duì)河南省13個(gè)5A景點(diǎn)進(jìn)行無約束條件下的旅游路線規(guī)劃，然后運(yùn)用蟻群算法進(jìn)行有費(fèi)用約束條件下的旅游路線規(guī)劃。在以上研究基礎(chǔ)上，本文基于蟻群算法，并以時(shí)間最短、費(fèi)用最少、路線最短、舒適度最高為目標(biāo)，研究以全國(guó)任意城市為起點(diǎn)，乘坐公共交通工具游覽全國(guó)249個(gè)5A景區(qū)的旅游路線規(guī)劃設(shè)計(jì)，并以上海市作為出發(fā)城市進(jìn)行實(shí)證分析，得出具體旅游時(shí)間、費(fèi)用以及詳細(xì)行程安排。

2 蟻群算法

2.1 算法原理

蟻群算法（Ant Colony Algorithm）是由意大利學(xué)者Colorni等[12]于20世紀(jì)90年代初期通過模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法[13]。該算法采用分布式并行計(jì)算機(jī)制，具有較強(qiáng)的魯棒性，但是具有搜索時(shí)間長(zhǎng)、容易陷入局部最優(yōu)解的缺點(diǎn)[14]。

2.2 蟻群算法流程

（1）參數(shù)初始化。在計(jì)算之前對(duì)相關(guān)系數(shù)進(jìn)行初始化，如蟻群數(shù)量m、信息素重要程度因子[α]、啟發(fā)函數(shù)重要程度因子[β]、信息素?fù)]發(fā)因子[ρ]、信息素釋放總量Q、最大迭代次數(shù)maxiter等。設(shè)迭代次數(shù)初值iter為1，然后將m個(gè)螞蟻放置于n個(gè)頂點(diǎn)上[17]。

3 模型建立

3.1 模型假設(shè)

假設(shè)旅游者出發(fā)點(diǎn)是隨機(jī)的，是綜合距離最近、交通方便、票價(jià)最低3個(gè)因素得出的一個(gè)出發(fā)點(diǎn)，本文假設(shè)旅游者從自己所在地到達(dá)其城市站點(diǎn)的相關(guān)影響因素不在路線規(guī)劃考慮之內(nèi)，模型選取的出發(fā)點(diǎn)為旅游者所在城市公共交通工具的站點(diǎn)。旅游者只能選擇火車、飛機(jī)、長(zhǎng)途汽車3種出行方式，因此將每個(gè)城市站點(diǎn)分為火車站、飛機(jī)場(chǎng)與長(zhǎng)途客運(yùn)站3類，其中火車站包含出行方式有高鐵、動(dòng)車、普快。

（1）假設(shè)旅游總時(shí)間為T，Tij表示以城市i為起點(diǎn)、城市j為終點(diǎn)乘坐公共交通工具的消耗時(shí)間，Tjda表示從j城市車站到景點(diǎn)a之間乘坐交通工具的消耗時(shí)間，Tdab表示從j城市景點(diǎn)a到景點(diǎn)b之間乘坐公共交通工具的消耗時(shí)間，Tijh1表示以城市i為起點(diǎn)、城市j為終點(diǎn)乘坐公共交通工具的換乘時(shí)間，Tijh2表示在同一城市之內(nèi)不同地點(diǎn)之間的換乘時(shí)間，Tjda表示在城市j第k個(gè)景點(diǎn)的游玩時(shí)間。

（2）假設(shè)旅游總路程為R，Rij表示以城市i為起點(diǎn)、城市j為終點(diǎn)乘坐公共交通工具經(jīng)過的路程，Rjda表示從j城市車站到景點(diǎn)a之間乘坐交通工具的路程，Tdab表示從j城市景點(diǎn)a到景點(diǎn)b之間乘坐公共交通工具的路程。

（3）假設(shè)旅游總費(fèi)用為F，F(xiàn)ij表示以城市i為起點(diǎn)、城市j為終點(diǎn)乘坐公共交通工具的票價(jià)，F(xiàn)jda表示從j城市車站到景點(diǎn)a之間乘坐交通工具的票價(jià)，F(xiàn)dab表示從j城市景點(diǎn)a到景點(diǎn)b之間乘坐公共交通工具的票價(jià)，F(xiàn)jdk表示j城市第k個(gè)景點(diǎn)門票價(jià)格，F(xiàn)jdks表示在j城市第k個(gè)景點(diǎn)的食宿費(fèi)用。

（4）假設(shè)旅游者總體舒適感為S，Sjdkt表示在j城市第k個(gè)景點(diǎn)旅游時(shí)間方面的舒適度，如是否為景點(diǎn)最佳旅游時(shí)間點(diǎn);Sjdkv表示在j城市第k個(gè)景點(diǎn)旅游交通方面的舒適度，如旅游景點(diǎn)游客數(shù)量等。

（5）假設(shè)時(shí)間約束為：景區(qū)開放時(shí)間按照國(guó)家規(guī)定為8：00-18：00，共計(jì)10小時(shí)，因此在景區(qū)游玩時(shí)間0≤Tjda≤10;考慮到旅游舒適度影響因素，每天乘坐公共交通工具時(shí)間不能超過8小時(shí)，即0≤Tij+Tjda+Tdab≤8。

（6）假設(shè)選擇步驟約束為：旅游者通常首先選擇一個(gè)想要旅行的城市，再到該城市的5A景點(diǎn)游玩，只有在該城市5A景點(diǎn)全部游覽完之后再選擇下一城市，即目標(biāo)選取是有層次的。因此，本文模型可簡(jiǎn)化為先對(duì)全國(guó)249個(gè)5A景點(diǎn)涉及的城市作一個(gè)旅游路線規(guī)劃，再針對(duì)每個(gè)城市的5A景點(diǎn)作旅游路線規(guī)劃。

3.2 目標(biāo)函數(shù)

旅行總時(shí)間最小化目標(biāo)為：

最終針對(duì)不同人群進(jìn)行路徑規(guī)劃，主要分為3種：①對(duì)時(shí)間重視程度大于對(duì)金錢的重視程度;②對(duì)金錢重視程度大于對(duì)時(shí)間的重視程度;③對(duì)時(shí)間與金錢重視程度相同。對(duì)于相應(yīng)權(quán)重設(shè)置可以根據(jù)個(gè)人實(shí)際情況加以考慮。

3.3 約束條件

在不同城市之間乘坐公共交通工具的時(shí)間為Tij=到達(dá)目的地時(shí)間-出發(fā)時(shí)間[21]。

（2）每天乘車時(shí)間不超過8小時(shí)[22]。

（3）先選擇城市再確定景點(diǎn)，或者確定景點(diǎn)之后，在對(duì)應(yīng)城市之內(nèi)游玩所有5A景點(diǎn)，才能轉(zhuǎn)移到下一城市。

4 實(shí)證研究

4.1 數(shù)據(jù)處理

根據(jù)中國(guó)旅游局官網(wǎng)收集全國(guó)249個(gè)5A景區(qū)數(shù)據(jù)，每個(gè)景點(diǎn)所在城市站點(diǎn)總數(shù)為165個(gè)（共獲得景區(qū)所在市縣237個(gè)，但部分?jǐn)?shù)據(jù)無法獲得，因此歸并到最近市縣區(qū)）。按照官網(wǎng)順序從1開始編號(hào)，每組數(shù)據(jù)包含每個(gè)節(jié)點(diǎn)的經(jīng)緯度坐標(biāo)、節(jié)點(diǎn)名稱、景區(qū)最少游玩時(shí)間、景點(diǎn)門票費(fèi)用、景點(diǎn)地區(qū)最低食宿費(fèi)用等，然后到12306官網(wǎng)收集景點(diǎn)所在城市之間高鐵、動(dòng)車、普快的相關(guān)數(shù)據(jù)（發(fā)車時(shí)間、行車時(shí)間、票價(jià)等），共得到5 445組數(shù)據(jù)[23]。

4.2 模型求解

通過Matlab 2018a編程，第一步設(shè)計(jì)全國(guó)249個(gè)5A景點(diǎn)涉及165個(gè)城市之間的最優(yōu)路線，第二步是獨(dú)立設(shè)置每個(gè)城市5A景點(diǎn)的最佳旅游路線。隨機(jī)選擇出發(fā)城市，將模型與相應(yīng)數(shù)據(jù)結(jié)合，165個(gè)城市之間最佳路線如圖1所示。最后得出結(jié)果：旅游最少時(shí)間為615.5天，最低費(fèi)用為159 653元，最短路程為725.84km，此時(shí)舒適度相對(duì)最高。部分城市5A景區(qū)最佳路線規(guī)劃如圖2、圖3所示。

4.3 算例結(jié)果分析

以上海作為出發(fā)城市為例，即旅游者乘坐公共交通工具從上海出發(fā)游玩國(guó)內(nèi)249個(gè)5A景區(qū)。通過分析比較，綜合時(shí)間、費(fèi)用、路程、舒適度4個(gè)因素，得到旅游者綜合效益最優(yōu)的方案為：旅游總時(shí)間為587.5天，總費(fèi)用為153 653元，總路程為722.435km。

5 結(jié)語

綜合時(shí)間、費(fèi)用、路程和舒適度4個(gè)目標(biāo)效益最大化的模型與已有單方面或只有2～3個(gè)目標(biāo)函數(shù)的模型相比，一方面對(duì)各影響因素考慮更加全面，另一方面更加貼合我國(guó)大部分居民實(shí)際需求，在一定程度上也為我國(guó)相關(guān)部門制定旅游景點(diǎn)路線規(guī)劃提供了參考意見。本方法主要存在的不足是在模型假設(shè)中還有一些實(shí)際影響因素未考慮進(jìn)去，另外本文僅采用蟻群算法進(jìn)行求解，由于蟻群算法本身存在缺陷，容易導(dǎo)致結(jié)果可能不是最優(yōu)解，而是相對(duì)最優(yōu)解。如果能結(jié)合其它算法進(jìn)行混合算法編程求解，可能會(huì)達(dá)到更好的效果。

參考文獻(xiàn)：

[1] 楊云鵬，袁光輝，金陽，等. 全國(guó)5A級(jí)景區(qū)旅游路線規(guī)劃問題研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016（15）：74-80.

[2] 徐清泉，趙夏，尚慶生. 冷鏈配送中的優(yōu)化算法分析及應(yīng)用[J]. 數(shù)字技術(shù)與應(yīng)用，2016（8）：143-145.

[3] 于瑩瑩，陳燕，李桃迎. 改進(jìn)的遺傳算法求解旅行商問題[J]. 控制與決策，2014（8）： 1483-1488.

[4] 楊萍. 區(qū)域旅游者行為模式及影響研究[J]. 經(jīng)濟(jì)問題探索，2003（6）：114-117.

[5] 吳凱. 旅游線路設(shè)計(jì)與優(yōu)化中的運(yùn)籌學(xué)問題[J]. 旅游科學(xué)，2004（1）：41-44，62.

[6] 吳小根，李海鴿，馮英杰. 江蘇省國(guó)內(nèi)旅游線路節(jié)點(diǎn)配置研究[J]. 地域研究與開發(fā)，2011（5）：118-122.

[7] 史春云. 旅行模式對(duì)目的地旅游經(jīng)濟(jì)影響的空間差異[J]. 旅游學(xué)刊，2013（6）：102-110.

[8] 鄧志剛. 旅游目的地研究文章述評(píng)分析——以旅游學(xué)刊2013- 2014年為樣本[J]. 旅游縱覽，2015（8）：66-70.

[9] 黃燕平，程啟清，王建生.? 基于蟻群算法的孔群加工路徑優(yōu)化研究[J]. 機(jī)械研究與應(yīng)用，2016（5）：37-40.

[10] 劉宇青，楊惠，類延輝，等. 蟻群算法解決CTSP問題的參數(shù)設(shè)置研究[J].? 計(jì)算機(jī)與數(shù)字工程，2011（3）：34-39.

[11] 黃騰. 基于遺傳蟻群算法的5A景點(diǎn)旅游路線規(guī)劃問題研究[D]. 武漢：華中師范大學(xué)，2017.

[12] 張雨，李芳，周濤. 云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2014（6）： 51-55.

[13] 郭文昌，張惠珍. 應(yīng)用混合算法求解冷鏈配送中心選址問題[J]. 改革與開放，2017（8）： 82-84.

[14] 佟靜翠. 基于混合算法的生產(chǎn)調(diào)度系統(tǒng)在鋼構(gòu)企業(yè)的研究與應(yīng)用[D]. 天津：河北工業(yè)大學(xué)，2015.

[15] 秦傳東. 基于遺傳算法選擇參數(shù)的蟻群算法求解TSP問題研究[J]. 信息與電腦：理論版，2014（11）：180-185.

[16] 畢碩本，董學(xué)士，馬燕. 遺傳算法和蟻群算法優(yōu)化TSP的設(shè)計(jì)與分析[J]. 武漢理工大學(xué)學(xué)報(bào)，2010，32（16）：89-92.

[17] 封燕，高建瓴，粱志福. 城市物流中心選址問題研究[J]. 貴州大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，27（5）：76-80.

[18] WU B，SHI Z Z. A solvable continuous time dynamic principal-agent model[J]. Chinese Journal of Computers-Chinese，2001（12）： 1328-1333.

[19] 楊再甫，黃友銳，曲立國(guó)，等.? TSP的改進(jìn)蟻群算法求解及其仿真研究[J]. 合肥工業(yè)大學(xué)：自然科學(xué)版，2014（8）：928-932.

[20] 張家善.? 基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化研究[D]. 阜新：遼寧工程技術(shù)大學(xué)，2014.

[21] DORIGO M. An ant colony algorithm based partition algorithm for TSP[J].? Machine Learning， 2010（5）：582-597.

[22] 張?zhí)旌?，彭紹雄，羅亞民，等. 基于蟻群算法的艦載機(jī)避障路線分析[J]. 兵工自動(dòng)化，2017，36（10）：71-74.

[23] 米永強(qiáng). 蟻群算法及其在求解旅行商問題中的應(yīng)用[J]. 電腦知識(shí)與技術(shù)：學(xué)術(shù)交流，2014（3）：1505-1507.

[24] 王松濤. 基于優(yōu)化的遺傳算子改進(jìn)蟻群算法AGV路徑規(guī)劃[J]. 自動(dòng)化應(yīng)用，2017（3）：47-49.

（責(zé)任編輯：黃 健）