旅游線路推薦與優(yōu)化的研究進(jìn)展

孟小丁，劉茄琳，駱鵬睿

(河西學(xué)院 物理與機(jī)電工程學(xué)院，甘肅 張掖 734000)

閑暇時(shí)節(jié)，旅游是人們討論的熱門話題. 去哪兒旅游需要人們作出決策. 線路安排和所需費(fèi)用則是旅行前需要準(zhǔn)游客做出籌劃的內(nèi)容. 但是，人們的思維一般傾向去沒有游歷過的城市和景點(diǎn). 然而，對(duì)于一個(gè)陌生的城市，游客在規(guī)劃旅游線路的過程中均面臨著很多問題，比如對(duì)于旅游地不熟悉以及不了解當(dāng)?shù)氐慕煌ǔ鲂械葐栴}. 在有限的時(shí)間或旅游預(yù)算內(nèi)，游客希望能夠有一條理想型的旅游線路. 針對(duì)實(shí)際生活中人們所面臨的困擾，結(jié)合“智慧旅游”的概念[1]，國內(nèi)外學(xué)者主要對(duì)旅游線路的探討集中在旅游線路個(gè)性化推薦和旅游線路的優(yōu)化設(shè)計(jì)兩個(gè)方面.

1 旅游線路個(gè)性化推薦

1.1 基于興趣點(diǎn)(POI)的研究

Kurashima(倉島健)[2]將帶有地理標(biāo)記的照片，并按時(shí)間序列整理形成用戶的旅游足跡，利用這些照片提出來一種旅游推薦方法，將馬爾可夫(Markov)和主題模型合并提出概率行為模型，獲得旅游者在該主題下對(duì)下一個(gè)旅游觀光點(diǎn)的參觀概率，求得一組滿足用戶興趣和時(shí)間約束的旅游線路，但沒有考慮用戶的游玩起點(diǎn)和終點(diǎn). Vansteenwegen(彼得·萬斯汀韋根)[3]概述了定向問題及其應(yīng)用領(lǐng)域，在滿足旅程約束條件(如時(shí)間預(yù)算、 起始點(diǎn)的位置)下，向旅行者推薦最佳的且同時(shí)能滿足用戶興趣和興趣點(diǎn)(POI)類型的旅游觀光線路. Gionis(阿里斯蒂德斯·吉奧尼斯)[4]綜合考慮了用戶的興趣點(diǎn)，時(shí)間和距離限制等信息，提出了基于遞歸的動(dòng)態(tài)規(guī)劃算法(Rel-DP，Cover-DP)，利用Foursquare數(shù)據(jù)集進(jìn)行試驗(yàn)，并將不同的算法進(jìn)行了對(duì)比. Brilhante(布里良特)[5]對(duì)旅行商問題進(jìn)行了改進(jìn)，最大限度地考慮了用戶的個(gè)人興趣和參觀時(shí)間預(yù)算，得到了基于興趣點(diǎn)(POI)流行度和用戶興趣集合的最佳旅游線路. 吳清霞等[6]提出了個(gè)性化旅游線路推薦(PTIR)算法，利用Flickr社交網(wǎng)絡(luò)的真實(shí)數(shù)據(jù)集進(jìn)行試驗(yàn)，對(duì)準(zhǔn)確率和召回率兩個(gè)指標(biāo)進(jìn)行對(duì)比分析，結(jié)果顯示所提出的算法相比傳統(tǒng)的算法有較大提升. 宋曉宇等[7]結(jié)合群體用戶的個(gè)人偏好，提出了一種群體受益最大且群體用戶局部分散的訪問路線，較好的解決了群體路線的公平性問題.

1.2 基于協(xié)同過濾(CF)算法的研究

朱敬華等[8]提出建立一個(gè)基于用戶的協(xié)同過濾樹和基于項(xiàng)目的協(xié)同過濾樹，并利用消息傳遞的思想進(jìn)行深度學(xué)習(xí). 徐雅斌等[9]根據(jù)用戶的簽到行為特點(diǎn)、 考慮用戶興趣點(diǎn)的語義特征，將改進(jìn)的混合協(xié)同過濾算法用于個(gè)性化位置推薦，對(duì)準(zhǔn)確率、 召回率、 平均絕對(duì)誤差(MAE)進(jìn)行對(duì)比分析，相比傳統(tǒng)的算法，推薦性能有較大提升. 劉亮亮[10]主要討論了基于社會(huì)網(wǎng)絡(luò)模型的協(xié)同過濾算法，將改進(jìn)的協(xié)同過濾算法應(yīng)用于旅游景點(diǎn)線路的推薦.

1.3 運(yùn)用旅游大數(shù)據(jù)的分析研究

李霞等[11]建立了應(yīng)用于個(gè)性化旅游線路推薦問題中的數(shù)學(xué)模型，將蟻群算法(AS)和遺傳算法(GA)應(yīng)用于個(gè)性化推薦中，爬取互聯(lián)網(wǎng)中的旅游數(shù)據(jù)，文中分別對(duì)蟻群算法和最大最小優(yōu)化蟻群算法(MMAS)、 遺傳算法和基于貪心解的混合遺傳算法(MGGA)進(jìn)行了參數(shù)(包括平均分值、 最優(yōu)分值、 平均耗時(shí))的對(duì)比分析. 孫文平等[12]通過構(gòu)建旅游圖譜信息，結(jié)合大量的旅行游記，生成了旅游線路數(shù)據(jù)庫，提出一種基于人物類型的頻繁線路序列模式挖掘算法，設(shè)計(jì)了一種多維度的個(gè)性化旅游線路. 尹書華等[13]將大數(shù)據(jù)信息進(jìn)行分詞，利用余弦相似度方法度量景點(diǎn)之間的相似度，從而為游客提供推薦服務(wù).

1.4 基于貝葉斯(Bayes)方法的研究

陳燕英等[14]利用用戶貢獻(xiàn)的社區(qū)照片提出貝葉斯學(xué)習(xí)模型，根據(jù)用戶特征(如性別、 年齡、 種族等)和用戶群體旅游方式(如家庭、 朋友、 戀人)為用戶推薦個(gè)性化的旅游觀光線路，但并未考慮用戶興趣或者興趣點(diǎn)類別. 徐盼等[15]把樸素貝葉斯(Bayes)方法應(yīng)用于個(gè)性化旅游線路推薦系統(tǒng)中，結(jié)果顯示，可提供與用戶需求相符合的旅游線路. 李廣麗等[16]采用分層抽樣統(tǒng)計(jì)(HSS)和貝葉斯個(gè)性化排序(BPR)相結(jié)合的方法對(duì)旅游景點(diǎn)進(jìn)行推薦，接著在“智能旅行”數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，與分層抽樣統(tǒng)計(jì)算法和貝葉斯個(gè)性化排序算法相比，作者提出的算法在推薦過程中的效果更好.

2 旅游線路優(yōu)化設(shè)計(jì)

2.1 求解的問題類型

Dumas(杜馬斯)等[17]提出了一種最小化旅行費(fèi)用的時(shí)間窗的旅行商問題(TSPTW)的旅游線路規(guī)劃. 該模型要求所有的旅游景點(diǎn)必須對(duì)其進(jìn)行訪問，因此對(duì)于時(shí)間有限制、 景點(diǎn)數(shù)量多的旅游線路不太適合. 張煜等[18]研究了時(shí)間不確定狀態(tài)下的時(shí)間窗的旅行商問題，對(duì)研究旅行線路優(yōu)化問題中涉及時(shí)間因素的研究是有可借鑒作用的. Vansteenwegen(范斯滕韋根)等[20]研究了帶時(shí)間窗的定向問題(TOPTW)，采用迭代局部搜索算法來對(duì)帶時(shí)間窗的定向問題進(jìn)行求解，該算法能夠在較短的時(shí)間內(nèi)計(jì)算出一條較優(yōu)的線路. Gavalas(加瓦拉斯)等[20]采用聚類和迭代搜索相結(jié)合的方法應(yīng)用于帶時(shí)間窗的定向問題.

2.2 求解的目標(biāo)函數(shù)

在旅游路線的設(shè)計(jì)過程中，以求解最短路程、 最短時(shí)間、 最低費(fèi)用、 動(dòng)態(tài)環(huán)境要素等信息為主要目標(biāo). 曹旭[21]從最短路旅游、 旅行商(TSP)問題、 規(guī)劃問題的旅游線路三個(gè)角度討論旅游線路的優(yōu)化問題，建立數(shù)學(xué)模型，借助Lingo和Matlab編程分別解決了提出的問題. 朱慶等[22]針對(duì)傳統(tǒng)旅游地圖靜態(tài)路網(wǎng)模型的缺陷，建立了多維動(dòng)態(tài)環(huán)境要素的導(dǎo)航網(wǎng)格模型，設(shè)計(jì)實(shí)現(xiàn)了動(dòng)態(tài)尋徑的A*算法. 侯樂等[23]建立了帶時(shí)間窗的的旅行商問題的數(shù)學(xué)模型，提出迭代局部搜索結(jié)合布谷鳥搜索(ILS-CS)的優(yōu)化算法混合算法，具體做法是首先用迭代局部搜索(ILS)算法求解旅游景點(diǎn)及初始化旅游線路，然后采用布谷鳥搜索(CS)算法優(yōu)化旅游線路的時(shí)間花費(fèi). 楊艷等[24]設(shè)計(jì)了基于游客擁擠感知的旅行線路，建立了多目標(biāo)規(guī)劃數(shù)學(xué)模型，借助粒子群優(yōu)化(PSO)算法對(duì)線路完成評(píng)價(jià).

2.3 求解方法的選擇

求解方法主要包括計(jì)算機(jī)仿真的方法和算法設(shè)計(jì)求解.

計(jì)算機(jī)仿真方面：任競(jìng)斐等[25]構(gòu)建了Logit模型，將游客在不同線路上進(jìn)行分配，建立了基于游客偏好、 擁擠度、 時(shí)間(等待時(shí)間和游覽時(shí)間)等指標(biāo)的效用函數(shù)，通過在多主體平臺(tái)上的仿真，可根據(jù)游客人數(shù)和游客等待時(shí)間的信息，采用不同的方案. 張笑白等[26]考慮了景區(qū)游客高峰期內(nèi)的旅游線路優(yōu)化，提出基于改進(jìn)Logit的高峰期內(nèi)人流量變換多線路調(diào)度的影響，將問題轉(zhuǎn)換為漢密爾頓(Hamilton)最優(yōu)回路規(guī)劃問題.

算法求解方面：包括迪杰斯特拉(Dijkstra)算法[21]9、 A*算法[22]、 粒子群優(yōu)化(PSO)算法[24]、 教與學(xué)優(yōu)化(TLBO)算法、 基于正態(tài)分布隨機(jī)數(shù)的遺傳算法(ND-GA)等. 具體體現(xiàn)在：王哲河等[27]以三亞旅游線路為研究對(duì)象，構(gòu)建了數(shù)學(xué)模型，同時(shí)結(jié)合了數(shù)據(jù)庫技術(shù)，使用狄氏最短路算法，可根據(jù)起始景點(diǎn)和優(yōu)化方案(如費(fèi)用最低)，計(jì)算得到旅游線路信息. 何紅等[28]設(shè)計(jì)了改進(jìn)的教與學(xué)優(yōu)化算法，并對(duì)漢中地區(qū)的旅行路線進(jìn)行優(yōu)化，實(shí)際結(jié)果表明該算法設(shè)計(jì)的旅游線路具有一定的可行性和高效性，特別為自駕游或者散客群體可提供參考. 李旭等[29]以合肥市為例，選取14個(gè)景點(diǎn)設(shè)計(jì)了合肥一日游的優(yōu)化旅游線路，運(yùn)用了蟻群算法求解. 吳澎等[30]針對(duì)全國201個(gè)5A級(jí)景區(qū)，運(yùn)用基于正態(tài)分布隨機(jī)數(shù)的遺傳算法(ND-GA)，對(duì)改進(jìn)旅行商(TSP)模型求解了包括201個(gè)5A景區(qū)的最優(yōu)旅游線路. 張子寒等[31]以南京主要景區(qū)為例，探討了多種模型的旅游線路規(guī)劃問題，給出了以旅行商模型和動(dòng)態(tài)規(guī)劃為基礎(chǔ)的解法，利用遺傳算法求解.

3 研究水平

結(jié)合研究現(xiàn)狀，目前國內(nèi)外的研究水平集中體現(xiàn)在以下五個(gè)方面.

其一，從學(xué)科特點(diǎn)來看，表現(xiàn)為定性研究，跨學(xué)科特征.

其二，從研究方法看，主要有運(yùn)籌學(xué)方法、 個(gè)性化推薦的方法等.

其三，從研究對(duì)象看，以游客的需求為主的研究較多，包括游客的喜好、 需求，起始點(diǎn)，預(yù)算的花費(fèi)及時(shí)間等信息.

其四，從研究范圍看，跨區(qū)域大尺度，小區(qū)域即特定城市的旅游景點(diǎn)的線路均有涉及.

其五，在數(shù)據(jù)選擇方面，主要通過爬取旅游網(wǎng)站數(shù)據(jù)，選用Flickr、 Daminaos等數(shù)據(jù)集獲取.

4 發(fā)展趨勢(shì)

旅游線路優(yōu)化設(shè)計(jì)相對(duì)比較成熟，主要體現(xiàn)在研究理論和研究方法上. 相對(duì)而言，智慧旅游背景下旅游線路推薦研究呈蓬勃發(fā)展之勢(shì). 結(jié)合已有的文獻(xiàn)資料，旅游線路的個(gè)性化推薦及旅游線路優(yōu)化預(yù)計(jì)在下述四個(gè)方面有進(jìn)一步的研究和探討.

一是獲取較新的旅游大數(shù)據(jù)并量化分析，從而較好地掌握訪客的出行規(guī)律.

二是靜態(tài)的環(huán)境信息會(huì)向動(dòng)態(tài)的多維環(huán)境信息過渡，以滿足智慧旅游個(gè)性化、 自適應(yīng)的需求.

三是結(jié)合大數(shù)據(jù)技術(shù)等構(gòu)建個(gè)性化推薦系統(tǒng)將更好地解決線路優(yōu)化問題，比如基于景點(diǎn)熱門程度的線路推薦，結(jié)合用戶需求的線路推薦與搜索，及基于敏感信息的查詢(如位置、 時(shí)間、 天氣等)的線路推薦等.

四是求解旅游線路的混合智能算法會(huì)做更進(jìn)一步的探討和開發(fā).