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

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

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

中圖分類號：F27???? 文獻標識碼：A????? doi：10.19311/j.cnki.1672-3198.2020.20.016

1 研究背景

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

2 問題分析

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

3 模型假設

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

4 模型的建立與求解

4.1 模型建立

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

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

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

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

最終得出如表1所示權值。

4.2 模型的求解

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

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

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

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

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

5 模型應用

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

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

第2天：鳴弦泉→花谷→吊橋庵→天都峰→猴子觀?！は挤濉淆?zhí)?/p>

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

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

參考文獻

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

[2]王東.基于用戶興趣與關注度的旅游路線推薦研究[J].電腦知識與技術，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].南京：南京郵電大學，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]吳育華，杜剛.管理科學基礎[M].天津：天津大學出版社，2009：94-97.

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