基于蟻群算法的蘇州古城徒步旅游線路規(guī)劃

張志雄 費(fèi)理源 廖宇

摘要：本文在對(duì)蘇州市古城區(qū)內(nèi)主要景點(diǎn)基礎(chǔ)信息進(jìn)行采集的基礎(chǔ)上，綜合考慮游覽耗時(shí)和線路耗時(shí)等因素，基于優(yōu)化后的蟻群算法對(duì)蘇州古城徒步旅游線路進(jìn)行規(guī)劃。基于蟻群算法的蘇州古城徒步旅游線路規(guī)劃能夠得到最優(yōu)旅游線路，整體運(yùn)算運(yùn)行效率高、速度較快，能滿足日后進(jìn)一步開發(fā)規(guī)劃的需求。

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

作為始建于2500多年前的蘇州古城，蘇州有著深厚的文化底蘊(yùn)，文物古跡眾多，在古城區(qū)中就聚集了大量的歷史古跡。如何規(guī)劃游覽這些分散在蘇州大街小巷中的古跡、有效地安排旅游線路、提升游客的旅游質(zhì)量和旅游效率，在智慧旅游的設(shè)計(jì)中十分必要。特別是在散客時(shí)代，主流的旅游線路可能無法滿足游客的需求。目前，對(duì)蘇州古城旅游線路規(guī)劃的研究成果還較為缺乏，還未能提供線路規(guī)劃等個(gè)性化的服務(wù)。在數(shù)據(jù)豐富和網(wǎng)絡(luò)快速發(fā)展的今天，站在游客的角度，不斷優(yōu)化旅游資源，對(duì)提升旅游質(zhì)量和城市魅力有著重要的意義。

因此，關(guān)于蘇州古城徒步旅游線路規(guī)劃的研究有利于優(yōu)化文旅資源配置，有利于實(shí)現(xiàn)文旅資源共享共用;增加旅游公共服務(wù)的供給，是面向散客時(shí)代，打造旅游與城市充分融合的有效途徑;突出“以蘇州園林為名片、蘇州古城為核心”，促進(jìn)文旅融合，滿足深度體驗(yàn)的需要;提升市民和游客對(duì)全域旅游的感受度。

一、基本思路

考慮到蟻群算法是有較強(qiáng)的并行性、魯棒性，比較容易與其它方法融合，更重要的是蟻群算法很好地結(jié)合了貪婪式搜索、正反饋機(jī)制以及分布式計(jì)算，能夠很好地避免早熟收斂等問題出現(xiàn)，同時(shí)具備高效的搜索及優(yōu)解能力，因此本研究選擇將蟻群算法應(yīng)用于旅游路線規(guī)劃中。在徒步的旅游方式下，對(duì)蘇州市古城區(qū)內(nèi)43個(gè)主要景點(diǎn)基礎(chǔ)信息進(jìn)行采集，綜合考慮游覽耗時(shí)和線路耗時(shí)等因素，基于蟻群算法試圖規(guī)劃蘇州古城徒步旅游線路。

二、數(shù)據(jù)分析與整理

通過調(diào)研整理出蘇州市古城區(qū)內(nèi)43個(gè)主要景點(diǎn)的清單，這些景點(diǎn)涵蓋了古城內(nèi)的主要蘇州園林、博物館、寺廟、古城門、歷史文化名街等類型。接著對(duì)43個(gè)景點(diǎn)基礎(chǔ)信息進(jìn)行采集，包括了特征標(biāo)記、季節(jié)性特征標(biāo)記、游覽平均用時(shí)、門票價(jià)格、地址等（詳見附表1）。在此基礎(chǔ)之上再把43個(gè)景點(diǎn)兩兩配對(duì)，測算了來回徒步用時(shí)，共生成1806個(gè)結(jié)果作為基本數(shù)據(jù)。

三、模型的優(yōu)化與求解

（一）模型優(yōu)化

1.優(yōu)化方向

利用蟻群算法規(guī)劃蘇州古城徒步旅游線路，對(duì)蟻群算法的優(yōu)化方向主要考慮兩點(diǎn)：景點(diǎn)和推薦主題的吻合度、交通在總用時(shí)的占比。此外，考慮到旅行用時(shí)較長，未來可能需要兼容餐飲等方面的需要，所以在算法中增加了在特定時(shí)間段對(duì)特定景點(diǎn)的優(yōu)化增強(qiáng)。即算法在第i個(gè)景點(diǎn)選擇通過路徑（i，j）去往下一個(gè)景點(diǎn)j時(shí)，首先是計(jì)算：Evaluate=weight_preferably*Scenery（j）.preferably+weight_traffic*Path（i，j）.time。其中，路徑時(shí)間需先經(jīng)過歸一化處理。推薦度權(quán)重為0.5，交通時(shí)間占比權(quán)重為0.3，而在挑選景點(diǎn)j時(shí)，同時(shí)會(huì)用時(shí)間段匹配度對(duì)j的信息素進(jìn)行修正，即：Info（j）*=judgeTime（j）/thresholdTimeJudeg^2。時(shí)間吻合度門限為0.3，則按蟻群算法，最終景點(diǎn)j被選中的概率為：Info（j）*Evaluate^2/∑（j）

2.約束

在路徑選擇中存在兩個(gè)硬約束，即總用時(shí)和總費(fèi)用。考慮到這兩者都是有一定彈性的，所以我們對(duì)兩者采取了不同的約束策略：總用時(shí)在指定用時(shí)上下各20%之內(nèi)，即如果指定200分鐘的總用時(shí)，則算法的實(shí)際總用時(shí)約束為[160，240]分鐘。總費(fèi)用則約束為只要不超出20%即可，即如果指定100元的總費(fèi)用，則算法的實(shí)際總費(fèi)用約束為[0，120]元。

3.評(píng)分

路徑判優(yōu)的評(píng)分是所有推薦度的平均數(shù)、交通用時(shí)占比、總用時(shí)和指定總時(shí)長之比這三者的加權(quán)平均。其中推薦度的權(quán)重為0.5，交通用時(shí)占比的權(quán)重為0.3，總時(shí)長的權(quán)重為0.1。由于按蟻群算法的習(xí)慣，評(píng)分越小代表結(jié)果越好，所有需要對(duì)這三者的得分加以處理以遵循此習(xí)慣。

4.爬山算法

由于蟻群算法的特性，算法可能會(huì)存在極小值陷阱。所以在三趟計(jì)算出的最優(yōu)結(jié)果沒有變化時(shí)，需執(zhí)行一次爬山算法以嘗試突破可能的極小值陷阱。本算法所采取的爬山算法處理為：將當(dāng)前最優(yōu)結(jié)果的第二個(gè)景點(diǎn)和倒數(shù)第二個(gè)景點(diǎn)互換。然后以此路徑重新開始計(jì)算。計(jì)算結(jié)果表明，爬山算法有較大概率會(huì)導(dǎo)致更優(yōu)路徑的出現(xiàn)。所以，這一現(xiàn)象說明，本算法由于約束條件較多、優(yōu)化參數(shù)較多、評(píng)分參數(shù)較多，這些約束條件與參數(shù)的存在顯著增加了極小值陷阱的出現(xiàn)。

（二）求解

1.初始化參數(shù)

在計(jì)算之初，需要對(duì)相關(guān)的參數(shù)進(jìn)行初始化，如蟻群模型（螞蟻數(shù)量）m、信息系揮發(fā)因子、信息素釋放總量Q、最大迭代次數(shù)iter_max等。經(jīng)過權(quán)衡，我們最終確立了如下的參數(shù)：

螞蟻數(shù)：50只，趟次：30次，初始信息素濃度：0.9

初始螞蟻為全部景點(diǎn)中隨機(jī)爬取出的一條經(jīng)過所有景點(diǎn)的全路徑，然后對(duì)此路徑上的邊進(jìn)行初始的信息素釋放。

2.構(gòu)建解空間

算法要求在每次求取時(shí)需指定一個(gè)固定的起始點(diǎn)，即游客根據(jù)自己的下車或住宿點(diǎn)，選擇一個(gè)最近的景點(diǎn)作為起始點(diǎn)開始計(jì)算。考慮到彈性，算法可以指定終止點(diǎn)或不指定，即游客可以指定游覽結(jié)束于某景點(diǎn)，也可以不指定。從起始點(diǎn)開始，算法在每步按前述的優(yōu)化方向一節(jié)中的說明，計(jì)算可達(dá)景點(diǎn)的到達(dá)概率。需要注意的是，如果在啟動(dòng)算法時(shí)指定了特定時(shí)間段，則在計(jì)算出的總時(shí)間達(dá)到該時(shí)間段時(shí)，需要判斷待選擇景點(diǎn)是否也有相應(yīng)的時(shí)間段設(shè)置并計(jì)算這兩個(gè)時(shí)間段間的吻合度，然后根據(jù)這個(gè)吻合度來調(diào)整此景點(diǎn)的到達(dá)概率。然后根據(jù)達(dá)到概率隨機(jī)選擇下一個(gè)景點(diǎn)。選擇了下一個(gè)景點(diǎn)后，算法即計(jì)算添加到到達(dá)該景點(diǎn)的路徑后，是否還符合前述的約束，如果符合則繼續(xù)計(jì)算;否則終止本螞蟻的本次運(yùn)行，輸出計(jì)算結(jié)果。如果指定了終止點(diǎn)，則算法在計(jì)算約束條件時(shí)，需將最后到達(dá)終止點(diǎn)的路徑也納入約束計(jì)算中即可。

3.更新信息素

算法信息素的更新采取標(biāo)準(zhǔn)蟻群算法的信息素更新算法。按標(biāo)準(zhǔn)蟻群算法的實(shí)現(xiàn)，每支螞蟻在選擇了下一個(gè)景點(diǎn)后，做一次局部更新;在本趟所有螞蟻計(jì)算完畢后，做一次蒸發(fā);對(duì)本趟的最優(yōu)路徑做一次全局更新。局部更新參數(shù)的選擇按標(biāo)準(zhǔn)蟻群算法建議參數(shù)選擇即可。

4.判斷是否終止

如果未指定終止點(diǎn)，則按前述的約束一節(jié)計(jì)算本路徑是否需要終止。如果指定了終止點(diǎn)，則需要將當(dāng)前景點(diǎn)到終止點(diǎn)的路徑增加到整個(gè)路徑中之后再按前述的約束一節(jié)計(jì)算本路徑是否需要終止。

四、算例實(shí)踐

以“滄浪亭”為起點(diǎn)且不指定終點(diǎn)為例，利用程序運(yùn)算分別規(guī)劃出三小時(shí)左右的徒步旅游方案：滄浪亭到環(huán)秀山莊到中醫(yī)藥博物館、滄浪亭到蘇州佛教博物館到定慧寺、滄浪亭到七里山塘景區(qū)到閶門、滄浪亭到蘇州佛教博物館到環(huán)秀山莊、滄浪亭到蘇州警察博物館到藝圃、滄浪亭到拙政園、滄浪亭到蘇州佛教博物館到蘇州碑刻博物館、滄浪亭到蘇州佛教博物館到網(wǎng)師園等8個(gè)線路方案。其他起點(diǎn)參照此操作。通過以上測算結(jié)果生成的方案，不難看出利用蟻群算法可以極大地豐富路線規(guī)劃方案，為游客提供眾多的選擇可能。如果將主要的中外知名景點(diǎn)作為起點(diǎn)，將能規(guī)劃出數(shù)量非常可觀的路線方案。另外，在技術(shù)手段的支持下，通過進(jìn)一步對(duì)歷史文化底蘊(yùn)的發(fā)掘，我們進(jìn)一步完善開發(fā)出了“韻存千秋·大美昆曲”、“匠心獨(dú)妙·蘇作天工”“康乾南巡·駐蹕姑蘇”“狀元故里·文脈尋根”、“光輝之路·紅色遺跡”等多個(gè)文旅融合的特色旅游主題線路。相關(guān)特色線路被蘇州市旅游部門采用，參與體驗(yàn)的游客反饋滿意度較高。

五、結(jié)論與展望

基于蟻群算法的蘇州古城徒步旅游線路規(guī)劃能夠得到最優(yōu)旅游線路，整體運(yùn)算運(yùn)行效率高、速度較快，能滿足日后進(jìn)一步開發(fā)規(guī)劃的需求。后續(xù)可以進(jìn)一步考慮引入多種因素改進(jìn)算法以增加模型求解為游客提供更加貼心的線路規(guī)劃方案。比如，可以進(jìn)一步擴(kuò)充景點(diǎn)數(shù)量、增設(shè)景點(diǎn)標(biāo)簽以滿足不同需求的路線規(guī)劃;可以進(jìn)一步拓展綜合考慮各種交通方式拓展應(yīng)用場景，比如增加特色騎行、特色自駕游路線規(guī)劃方案;結(jié)合景點(diǎn)或線路的文化底蘊(yùn)挖掘，探尋特色文旅融合線路。

參考文獻(xiàn)：

[1]周茂杰、張翠.基于改進(jìn)蟻群算法的旅游線路優(yōu)化[J]. 現(xiàn)代計(jì)算機(jī)，2018.05下：24-27.

[2]郝海霞.用蟻群算法優(yōu)化四川旅游路線[J].北京印刷學(xué)院學(xué)報(bào)，2017（07）：181-182.

基金項(xiàng)目：2019年度蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院科研項(xiàng)目“基于蟻群算法的蘇州古城徒步旅游線路規(guī)劃”，項(xiàng)目編號(hào)為YJ-QN1908。2020年江蘇省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目“基于蟻群算法的蘇州市古城區(qū)特色旅游線路規(guī)劃” ，項(xiàng)目編號(hào)為202012685015Y。

作者簡介：

張志雄（1997-），男，廣東清遠(yuǎn)人，蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院學(xué)生，研究方向?yàn)榇髷?shù)據(jù)技術(shù)與應(yīng)用;

費(fèi)理源（1989-），男，江蘇吳江人，蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院教師，主要研究方向：高職教育管理、大數(shù)據(jù)技術(shù)與應(yīng)用;

廖宇（1982-），男，四川犍為人，蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院講師，主要研究方向：高職教育管理，大數(shù)據(jù)技術(shù)與應(yīng)用。