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

袁絳書 馮振宇 朱天樂 陳銘思 姜雨辰

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

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

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

1 研究背景

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

2 問題分析

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

3 模型假設(shè)

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

4 模型的建立與求解

4.1 模型建立

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

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

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

在本模型中，精力作為主觀指標(biāo)，無法通過查找資料直接獲取。本文進(jìn)行如下計算以量化精力：假設(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)編號，狀態(tài)變量Sk表示游客抵達(dá)k節(jié)點(diǎn)時身上攜帶資源換算成單權(quán)后的剩余權(quán)值，決策變量xk表示是否游覽k號節(jié)點(diǎn)。

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

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

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

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

5 模型應(yīng)用

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

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

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

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

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

參考文獻(xiàn)

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

[2]王東.基于用戶興趣與關(guān)注度的旅游路線推薦研究[J].電腦知識與技術(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]牛悅誠.基于蟻群算法的智慧旅游路線規(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]周嘯，李少梅，李森，等.一種基于局部貪心搜索的興趣旅游路線規(guī)劃算法[J].河北師范大學(xué)學(xué)報（自然科學(xué)版），2019，43（03）：262-268.