基于貪心算法的黃山景區(qū)旅游路線優(yōu)化設(shè)計(jì)

袁絳書(shū) 馮振宇 朱天樂(lè) 陳銘思 姜雨辰

摘 要：黃山景區(qū)景點(diǎn)眾多且許多知名景點(diǎn)分布過(guò)于分散、彼此間相距較遠(yuǎn)，使得很多游客沒(méi)有辦法在有限的時(shí)間內(nèi)游覽完期望的景點(diǎn)。因此根據(jù)游客個(gè)性化選擇為其推薦一條滿意度最高的路線尤為重要。本文考慮游客的景點(diǎn)偏好、金錢(qián)預(yù)算和精力等約束條件，建立了基于游客滿意度最大化的旅游路線優(yōu)化模型，引入兩點(diǎn)之間的高程、直線距離和路程量化游客的精力，根據(jù)年齡和性別賦予不同的初始精力，并賦予金錢(qián)和精力在不同線路的影響權(quán)重。利用貪心算法求解，在最優(yōu)條件下，根據(jù)不同的初始數(shù)據(jù)，可以得到基于游客個(gè)性化選擇為基礎(chǔ)，游客滿意度最大的最優(yōu)路線，從而可解決游客在有限的時(shí)間內(nèi)游覽黃山景區(qū)期望景點(diǎn)的需求。

關(guān)鍵詞：黃山;路線優(yōu)化;0-1規(guī)劃;貪心算法

中圖分類(lèi)號(hào)：F27???? 文獻(xiàn)標(biāo)識(shí)碼：A????? doi：10.19311/j.cnki.1672-3198.2020.20.016

1 研究背景

黃山景區(qū)占地面積共計(jì)1200平方千米，一日之內(nèi)難以全部游覽，因此，如何根據(jù)不同游客的個(gè)性化需求推薦旅游線路，成了大家關(guān)注的問(wèn)題?，F(xiàn)有文獻(xiàn)大都僅考慮用戶(hù)某一方面的約束，張久騰、吳小竹等人基于時(shí)間約束對(duì)多日游行程進(jìn)行規(guī)劃和優(yōu)化，王東基于用戶(hù)的對(duì)景點(diǎn)的興趣進(jìn)行旅游路線規(guī)劃，往往都沒(méi)有考慮到游客的時(shí)間預(yù)算、資金預(yù)算、自身身體狀況等約束條件，基于單一約束的推薦結(jié)果難以滿足用戶(hù)需求。本文基于黃山旅游景點(diǎn)開(kāi)放的線路，研究多約束多目標(biāo)的旅游線路推薦方法。對(duì)于多目標(biāo)規(guī)劃旅行線路，Weimin Zheng和Zhixue Liao提出用啟發(fā)式算法求得最優(yōu)解，牛悅誠(chéng)提出用蟻群算法求最有路徑解，而本文提出一種多屬性景點(diǎn)的評(píng)價(jià)機(jī)制，引入金錢(qián)、精力、游客偏好等因素，引用一種在多約束條件下的貪心算法，使用貪心算法選出前N條總體評(píng)價(jià)較高的路徑，然后，通過(guò)綜合評(píng)估路徑的有效性及多樣性，最終選出相對(duì)較優(yōu)的路徑作為推薦結(jié)果。

2 問(wèn)題分析

根據(jù)人群不同賦予不同的精力初始值，景點(diǎn)開(kāi)放接待游客的時(shí)間為每天早上9∶00到下午18∶00，金錢(qián)的權(quán)值只考慮部分路線中的索道、纜車(chē)費(fèi)用，在時(shí)間方面，本文通過(guò)查詢(xún)相連景點(diǎn)之間的游客步行時(shí)間和游覽時(shí)間之和進(jìn)行賦值，精力方面，采取相關(guān)算法將精力的定性分析轉(zhuǎn)化為定量分析，并給予不同類(lèi)型游客人群以不同的初始值。最后求解出三者權(quán)值之和再進(jìn)行歸一化，利用動(dòng)態(tài)規(guī)劃方法進(jìn)行求解。

3 模型假設(shè)

根據(jù)上述背景，我們對(duì)相關(guān)過(guò)程做出簡(jiǎn)化并做出以下假設(shè)：（1）游客所具備的時(shí)間、預(yù)算及精力都是有限的且可以量化的;游客偏好可通過(guò)游客對(duì)各景點(diǎn)賦分，以進(jìn)行量化。（2）景區(qū)的交通情況影響游客精力消耗及通行時(shí)間。為簡(jiǎn)化模型，游客在景點(diǎn)逗留時(shí)間根據(jù)資料賦予一個(gè)固定值。（3）游客游覽時(shí)間局限于景區(qū)開(kāi)放時(shí)間，假設(shè)景區(qū)開(kāi)始營(yíng)業(yè)時(shí)游客即開(kāi)始在景區(qū)游覽。（4）游覽天數(shù)及預(yù)算金額任一值消耗殆盡，停止游覽。（5）游客精力值根據(jù)年齡體能區(qū)別賦予，精力值可于第二天全額恢復(fù)，當(dāng)日精力或可游覽時(shí)間耗盡時(shí)，停止當(dāng)日游覽。（6）游客不會(huì)重復(fù)游覽。

4 模型的建立與求解

4.1 模型建立

基于以上假設(shè)，將各景點(diǎn)設(shè)為節(jié)點(diǎn)，景點(diǎn)間交通路線設(shè)為邊，通過(guò)游客偏好對(duì)景點(diǎn)價(jià)值進(jìn)行賦值，并將該值作為節(jié)點(diǎn)的權(quán)值;根據(jù)路線長(zhǎng)度，路線精力耗費(fèi)值及路線所需金錢(qián)對(duì)各邊進(jìn)行賦值。根據(jù)假設(shè)，運(yùn)用貪心算法進(jìn)行模擬計(jì)算，在每個(gè)游覽日中生成當(dāng)日游覽路線，最終解出在約束條件下使得游客滿意度最高的游覽路線集。

其中，n為景點(diǎn)序號(hào)，Tij為交通時(shí)間，t為游覽時(shí)間，Eij為交通精力，e為游覽精力，M為預(yù)算金額，m為景區(qū)消費(fèi)，V代表景點(diǎn)價(jià)值，S代表游客滿意值，h為景點(diǎn)海拔，Δhij為景點(diǎn)高差，sij代表景點(diǎn)距離，xij為景點(diǎn)路程，W是新定義指標(biāo)，用于統(tǒng)一T、E、m三個(gè)變量，yE為交通精力決策變量，ye為游覽精力決策變量，yT為交通時(shí)間決策變量，yt為游覽時(shí)間決策變量，ym為預(yù)算金額決策變量，yV為景點(diǎn)價(jià)值決策變量。

考慮到簡(jiǎn)化模型的原則，對(duì)賦予到邊上的各指標(biāo)進(jìn)行歸一處理，定義新的指標(biāo)W，對(duì)于路線指標(biāo)歸一有：W=0.3T+0.3E+0.4m

在本模型中，精力作為主觀指標(biāo)，無(wú)法通過(guò)查找資料直接獲取。本文進(jìn)行如下計(jì)算以量化精力：假設(shè)A點(diǎn)與C點(diǎn)為景區(qū)兩景點(diǎn)，A點(diǎn)海拔為hA，C點(diǎn)海拔為hC，兩點(diǎn)高差Δhac=|hA-hC|，AC兩點(diǎn)直線距離為sac，AC兩點(diǎn)交通距離為xac，游客從A景點(diǎn)到C景點(diǎn)的交通精力消耗值為：

最終得出如表1所示權(quán)值。

4.2 模型的求解

用階段變量k表示節(jié)點(diǎn)編號(hào)，狀態(tài)變量Sk表示游客抵達(dá)k節(jié)點(diǎn)時(shí)身上攜帶資源換算成單權(quán)后的剩余權(quán)值，決策變量xk表示是否游覽k號(hào)節(jié)點(diǎn)。

具體操作如下：游客從一個(gè)起點(diǎn)開(kāi)始，對(duì)圖進(jìn)行遍歷操作，直到游客攜帶的資源不能支持游客抵達(dá)終點(diǎn)為止。

選用貪婪算法，就要明確每一次決策時(shí)選擇k號(hào)節(jié)點(diǎn)的方法。此處提出單位權(quán)滿意度的概念，即目的節(jié)點(diǎn)的滿意度值與從當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)邊的權(quán)值的比，每次決策時(shí)，選擇單位權(quán)滿意度最大的邊的后繼節(jié)點(diǎn)。

本模型與背包問(wèn)題存在微小的差異，所以不能直接套用貪婪算法。此處筆者對(duì)貪婪算法進(jìn)行了一些改良，增加了算法的終止條件，即每次抵達(dá)一個(gè)新的節(jié)點(diǎn)時(shí)，檢查當(dāng)前節(jié)點(diǎn)到終點(diǎn)的最短路所花費(fèi)的權(quán)值，如果這個(gè)權(quán)值大于當(dāng)前游客攜帶資源的權(quán)值時(shí)，將狀態(tài)退回到上一節(jié)點(diǎn)。如果在上一節(jié)點(diǎn)發(fā)現(xiàn)無(wú)論下一步選擇哪個(gè)節(jié)點(diǎn)都不能滿足上述條件，則這個(gè)上一節(jié)點(diǎn)就是遍歷操作的停止點(diǎn)。

最終在遍歷停止的時(shí)候，記錄遍歷節(jié)點(diǎn)的順序，這就是模型的局部最優(yōu)解。

5 模型應(yīng)用

根據(jù)某旅行社的大數(shù)據(jù)統(tǒng)計(jì)，筆者對(duì)上文所述16個(gè)代表景點(diǎn)進(jìn)行滿意度賦值，并對(duì)時(shí)間、預(yù)算和精力分別賦以540min、300、100，預(yù)設(shè)游客游覽天數(shù)為3天，每天游覽8小時(shí)，各景點(diǎn)游覽半小時(shí)，從早上9時(shí)起到達(dá)游覽出發(fā)點(diǎn)。經(jīng)模型計(jì)算得出如下游覽路線集和計(jì)劃時(shí)間集：

第1天：云谷寺→迎客松→光明頂→丹霞峰→西海大峽谷→云門(mén)峰→老龍?zhí)?/p>

第2天：鳴弦泉→花谷→吊橋庵→天都峰→猴子觀海→丹霞峰→老龍?zhí)?/p>

第3天：九龍瀑→香爐峰→慈光閣→老龍?zhí)?/p>

本文基于黃山景點(diǎn)分布分散且彼此之間相距較遠(yuǎn)的現(xiàn)象，提出了基于游客滿意度最大化的旅游路線優(yōu)化模型。通過(guò)挖掘景點(diǎn)的信息為游客在黃山提供推薦旅游路線，并在金錢(qián)和精力，以及考慮游客年齡性別的各種限制下，為游客提供滿足其需求的推薦路線。

參考文獻(xiàn)

[1]張久滕，吳小竹，陳崇成，等.基于時(shí)間框架的多日游行程規(guī)劃及其優(yōu)化方法[J].福州大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，46（06）：787-793.

[2]王東.基于用戶(hù)興趣與關(guān)注度的旅游路線推薦研究[J].電腦知識(shí)與技術(shù)，2018，14（01）：18-19，22.

[3]Weimin Zheng， Zhixue Liao. Using a heuristic approach to design personalized tour routes for heterogeneous tourist groups[J]. Tourism Management，2019，（72）.

[4]牛悅誠(chéng).基于蟻群算法的智慧旅游路線規(guī)劃研究[D].南京：南京郵電大學(xué)，2017.

[5]Becky P. Y. Loo， Linna Li. Carbon dioxide emissions from passenger transport in China since 1949： Implications for developing sustainable transport[J]. Energy Policy，2012，（50）.

[6]吳育華，杜剛.管理科學(xué)基礎(chǔ)[M].天津：天津大學(xué)出版社，2009：94-97.

[7]周?chē)[，李少梅，李森，等.一種基于局部貪心搜索的興趣旅游路線規(guī)劃算法[J].河北師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，43（03）：262-268.