最優(yōu)旅行目的地選擇及旅行路徑規(guī)劃

李雨彤

【摘要】本論文利用數(shù)學(xué)建模的方法，根據(jù)游客的喜好推薦最優(yōu)旅行路線.首先，通過調(diào)查游客對于旅行景區(qū)不同因素的重視程度和各景點(diǎn)在不同方面的既有評分，用改進(jìn)層次分析法得到各景區(qū)排名，對景區(qū)進(jìn)行初步篩選.其次，運(yùn)用Dijkstra算法得到所有可選景點(diǎn)之間的最短路程，并使旅程時間和費(fèi)用多少與旅程長短成正比.最后，根據(jù)游客需求分別設(shè)定目標(biāo)函數(shù)和限制條件得到基于非線性規(guī)劃問題的最優(yōu)旅行路線模型.本文將北京部分景區(qū)的數(shù)據(jù)代入模型進(jìn)行驗證，得到了不同游客需求下的旅行最優(yōu)路線.

【關(guān)鍵詞】最優(yōu)旅行路線;游客體驗;Dijkstra算法;非線性規(guī)劃

一、引言

隨著全球化的到來，人們對于旅行的需求不斷增大，旅游半徑從居住地周圍的城市，逐漸擴(kuò)大到省、國家乃至世界范圍內(nèi)的景區(qū).然而，旅游服務(wù)并沒有成熟的旅程規(guī)劃系統(tǒng)為人們提供便捷的旅行規(guī)劃條件.因此，本論文希望通過建立數(shù)學(xué)模型，根據(jù)游客的個性化需求從景點(diǎn)庫中篩選出適合游客的目的地，并規(guī)劃最優(yōu)路線.

截止到目前，有許多學(xué)者對旅行路線的相關(guān)問題進(jìn)行研究.有的學(xué)者曾將游客旅行效用表示為與出行時間和出行費(fèi)用有關(guān)的函數(shù)，原因是發(fā)現(xiàn)擁擠度對游客旅行體驗有主要影響[1-2];有的學(xué)者采用逐步分層、蟻群算法、Floyd算法、“面包屑”擬合等研究方法進(jìn)行旅行規(guī)劃[3-5].

本文將主要根據(jù)游客的喜好，用改進(jìn)后的層次分析法對景點(diǎn)進(jìn)行排序、用Dijkstra算法計算每兩個景點(diǎn)之間的最優(yōu)旅行路線，并計算在旅行整體效果最好的情況下應(yīng)該以何種順序前往哪些景點(diǎn).本文將游客的需求分為三類：一是因假期時間有限對旅游總時間有限制要求的“時間限制型”;二是因財務(wù)狀況有限對旅游總花費(fèi)有限制要求的“金額限制型”;三是對兩者都有要求的“雙重限制型”.論文中針對以上三種情況分別設(shè)定了目標(biāo)函數(shù)和限制條件，定義了若干目標(biāo)函數(shù)，每種目標(biāo)函數(shù)與旅行效率和游客滿意度成正比、與游客不充足擁有量成反比.只需代入具體的景點(diǎn)，根據(jù)以往數(shù)據(jù)和游客的個人偏好即可計算出游客的具體旅行路線.

二、問題的描述

一個由若干人組成的旅行團(tuán)在某一確定的區(qū)域內(nèi)旅行，共有n個旅游目的地可供選擇（i=1，2，…，n）.此模型的最終結(jié)果將用有序數(shù)對（a，b）表示從a景點(diǎn)前往b景點(diǎn).從這些數(shù)對中我們也可以分析出人們是否前往某一景點(diǎn)以及訪問景點(diǎn)的順序.

三、改進(jìn)層次分析法確定目的地優(yōu)先級

可選的景點(diǎn)數(shù)不勝數(shù)，但是在同一次旅行中游客能夠前往的地點(diǎn)是有限的.因此在開始計算前，我們要根據(jù)游客的喜好將所有目的地進(jìn)行排序.該順序?qū)⒆鳛槟康牡乇豢紤]的先后順序.游客對景點(diǎn)的喜好值將決定景點(diǎn)是否可以被納入考慮的范圍，并將被用來衡量游客對于最終的方案的滿意度.

我們按照圖1所示方式將目標(biāo)、游客喜好和景點(diǎn)分別填入層次分析法的目標(biāo)層O、準(zhǔn)則層C和方案層P.某一指定方案Pj的最終評分為

Sj=∑mi=1Cij×Aj，j=1，2，…，n

（1）

圖1層次分析法用于景點(diǎn)排序的流程圖

在該評分系統(tǒng)下，分值高的景點(diǎn)表示傾向于被游客選擇.在各景點(diǎn)Sj已知后，按照從大到小的順序排序，即可得到景點(diǎn)被該（組）游客喜好的排名.當(dāng)景點(diǎn)過多時，我們?yōu)榱撕喕惴ǎ僭O(shè)游客總旅程天數(shù)為D0，由于每天旅行的景點(diǎn)有限，景點(diǎn)過多會極大地影響游客旅行體驗，因此不妨假設(shè)景點(diǎn)不超過3個，則在篩選時僅保留排名約為3，旅程天數(shù)為D0及以前的景點(diǎn)，排名位于3，旅程天數(shù)為D0以后的景點(diǎn)不做考慮.

四、Dijkstra算法尋找兩點(diǎn)之間最優(yōu)路徑

Dijkstra算法一般用于計算多點(diǎn)之間無向線段的最短路程.以某一節(jié)點(diǎn)作為起始點(diǎn)，Dijkstra算法可以得出該點(diǎn)和任意一點(diǎn)間的最短距離[6].

每一條線段上的數(shù)值amn為綜合考慮費(fèi)用和時間的結(jié)果，賦值計算方法為

amn=fmn×tmn（2）

其中fmn表示每一小段路上的費(fèi)用，tmn表示每一小段路上的時間.

圖2Dijkstra算法示例圖

在確定每條線段上的數(shù)值后，我們計算最短路徑.如圖2，假設(shè)需計算從故宮出發(fā)前往頤和園的最短距離，已知每條路線的距離（在現(xiàn)實中可以是公交線路、地鐵線路或者打車線路）.分別計算到每一節(jié)節(jié)點(diǎn)的值，如果兩點(diǎn)之間沒有路線則作為+∞計算，每次固定此時圖中的最小值，逐步往前推進(jìn)，直到確定了最終的值.產(chǎn)生最小值的路徑即為所求的最短路徑，終點(diǎn)處的數(shù)值為所求距離.按照這種方法，我們可以計算出從故宮到達(dá)頤和園的最優(yōu)路線是（故宮→C→D→頤和園），距離為12[7].該路程上的時間和費(fèi)用將作為后文中的中轉(zhuǎn)費(fèi)用Fij和中轉(zhuǎn)時間Tij.

五、旅行問題變量定義

在開始建立模型和得到具體數(shù)據(jù)前，先定義以下變量.

定義1：決策變量.xij為決策變量，取決于游客是否從一指定地點(diǎn)前往另一指定地點(diǎn)參觀.

xij=1，該游客從i點(diǎn)前往j點(diǎn)xij=0，該游客不從i點(diǎn)前往j點(diǎn)

i=1，2，3…，n.j=1，2，3…，n.i≠j.（3）

通常情況下，某次旅行時同一個景點(diǎn)最多只去一次，也就是說，如果該游客前往j點(diǎn)，則在所有的變量xnj中，只有一個會等于1.

定義2：停留時間.下式表示該旅行團(tuán)體在j處停留的時間.其中α0為游客對該類景點(diǎn)感興趣的程度，數(shù)值越大，游客對該景點(diǎn)該興趣程度越大.Tmean，j為該地游客的平均停留時間.W0為天氣變量，取決于該季度平均的天氣適宜指數(shù)，數(shù)字大表示氣候宜人，適合觀賞景點(diǎn);反之則表示氣候惡劣，不適合觀賞景點(diǎn).wj為該景區(qū)受天氣影響的程度，如果天氣對于該地點(diǎn)的游覽影響較小（如室內(nèi)展覽館）則該值接近于0.

Tj=α0×Tmean，j×（W0wj（4）

定義3：總旅行天數(shù).Ttotal為游覽所有景點(diǎn)所需時間，由所有景點(diǎn)之間，即路程上的時間Tij和景區(qū)內(nèi)游覽的時間Ti求和得到;tactive為該組游客每天在外游覽的時間.

Dtotal=Ttotaltactive=∑ni=1∑nj=1[Xij×（Tij+Tj）]tactive

（5）

定義4：總旅行費(fèi)用.旅行費(fèi)用分為基礎(chǔ)費(fèi)用和目的地游覽費(fèi)用.其中基礎(chǔ)費(fèi)用即每晚的酒店費(fèi)用Fhotel乘以住宿天數(shù)和每天的食品花銷求和得到.目的地游覽費(fèi)用由所有景點(diǎn)之間，即路程上的費(fèi)用Fij和景區(qū)內(nèi)游覽所需費(fèi)用Fi求和得到

Ftotal=∑ni=1∑nj=1Xij×Fij+Fj+Fhotel×（Dtotal-1）+Ffood×Dtotal

（6）

定義5：景區(qū)平均停留時間.Topen為該景區(qū)的平均開園時間.由于大部分景區(qū)擁有某固定時刻景區(qū)內(nèi)平均人數(shù)Pmoment的數(shù)據(jù)和每日平均客流量Paverage的數(shù)據(jù)，因此用以上三個數(shù)據(jù)一起計算出Tmean，j.

Tmean，j=PmomentPaverage×Topen（7）

定義6：旅行效率.定義為景點(diǎn)游覽的時間占總時間的比例.通過對于景點(diǎn)順序的合理規(guī)劃，可以有效減少在路上的無效時間，提高此旅行效率值Uefficiency.

Uefficiency=TvisitTtotal=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij×（Tij+Tj）]

（8）

定義7：游客滿意程度.運(yùn)用層次分析法求得的排名.因為認(rèn)為游客的滿意度與景點(diǎn)數(shù)無關(guān)，只與游客對前往景點(diǎn)的感興趣程度有關(guān)，所以將各個所選景點(diǎn)排名相加并除以景點(diǎn)個數(shù)，得到游客對于不同旅行方案的滿意度.

Usatisfaction=1（∑ni=1Si）/（∑ni=1xij

（9）

六、三類非線性規(guī)劃模型

1.金額限定型

定義F0為游客要求的金額上限

目標(biāo)函數(shù)：

MAXE=Uefficiency×UsatisfactionFtotal

=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij（Tij+Tj）]×1∑ni=1Sj/∑ni=1xj∑ni=1∑nj=1Xij（Fij+Fj）

（10）

約束條件：

Ftotal≤F0

（11）

2.時間限定型

定義T0為游客要求的時間上限

目標(biāo)函數(shù)：

MAXE=Uefficiency×UsatisfactionDtotal

=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1Xij（Tij+Tj）]×1（∑ni=1Sj）/（∑ni=1xj∑ni=1∑nj=1[Xij×（Tij+Tj）]tactive

（12）

限制條件：

Dtotal≤D0

（13）

3.雙重限定型

這種限制條件為前兩種的結(jié)合，即游客既受到時間上的限制，必須在一定時間內(nèi)完成旅行，又受到費(fèi)用上的限制.

目標(biāo)函數(shù)：

MAXE=Uefficiency×UsatisfactionFtotal×Dtotal（14）

限制條件：

Ftotal≤F0，Dtotal≤D0.（15）

七、模型驗證與求解

本文帶入了北京市景區(qū)的數(shù)據(jù)對模型進(jìn)行驗證.

首先，從北京城區(qū)內(nèi)隨機(jī)選擇較受歡迎的30個目的地[9].游客喜好評分僅作為示例，其中景色、人文、休閑和刺激四項參考了旅評網(wǎng)http：//www.ilvping.com/view/Index/home.html.對于景點(diǎn)的評分，擁擠和交通參考了蘋果地圖的路線規(guī)劃（可供選擇的公共方式越多該項評分越高）.

不妨設(shè)游客的預(yù)計游玩時間為3天，根據(jù)第三部分固定保留n=3×3=9個項目.得到的前十名景點(diǎn)分別是（23）頤和園、（22）長城、（24）十三陵、（25）香山、（11）798藝術(shù)中心、（13）圓明園、（28）魯迅博物館、（8）北京三聯(lián)韜奮書店和（9）五道營胡同.

八、結(jié)語

本文通過層次分析法、Dijkstra算法和三類非線性規(guī)劃建立了選擇旅行景點(diǎn)的模型，能夠針對游客的不同需求從任意的景點(diǎn)庫中篩選出景點(diǎn)并確定前往順序.

該論文的研究結(jié)果可以用于實際生活中的旅行規(guī)劃，同時使游客、景點(diǎn)、當(dāng)?shù)卣@利.對于游客，此規(guī)劃可以有效減少旅行者在設(shè)計旅行方案時的煩瑣過程，同時擁有更好的旅游體驗.對于當(dāng)?shù)氐木包c(diǎn)，只要在運(yùn)轉(zhuǎn)此模型時擁有足夠大的景點(diǎn)庫，便可以選出許多不為人熟知，卻符合游客興趣的景點(diǎn)，更好地促進(jìn)旅游業(yè)平衡發(fā)展.同時，當(dāng)?shù)卣?，將“旅行效率”納入主要考慮因素之一，可以減少游客路上時間，減緩路面負(fù)擔(dān)，讓城市交通運(yùn)轉(zhuǎn)更加順利.該方式并不受旅行目的地大小范圍的影響，選擇的目的地可以大到幾個國家之間旅行的范圍，也可以小到一個城市內(nèi)不同景點(diǎn)、餐廳、商場之間的選擇，應(yīng)用范圍較廣.

【參考文獻(xiàn)】

[1]伍雄斌，關(guān)宏志，韓艷.多約束下基于游客體驗的旅游路線優(yōu)化模型[J].科學(xué)技術(shù)與工程，2018，18（13）：8-13.

[2]Lim，Kwan Hui.Recommending and Planning Trip Itineraries for Individual Travellers and Groups of Tourists[J].International Conference on Automated Planning & Scheduling，2016，1-6.

[3]龐亮.基于多目標(biāo)優(yōu)化的旅游路線的建模[J].特區(qū)經(jīng)濟(jì)，2016（11）：126-129.

[4]Gionis A，Lappas T，Pelechrinis K，et al.Customized tour recommendations in urban areas[C].Proceedings of the 7th ACM International Conference on Web Search and Data.ACM，2014：313-322.

[5]楊靜.旅游路線的最優(yōu)化設(shè)計研究[J].新經(jīng)濟(jì)，2016（09）：18-19.

[6]李妍妍.Dijkstra最短路徑分析算法的優(yōu)化實現(xiàn)[J].測繪與空間地理信息，2014（05）：172-173，190.

[7]肖鵬.矩陣迭代和Dijkstra兩種算法在交通運(yùn)輸路徑選擇中的對比[J].電子技術(shù)與軟件工程，2017（10）：17-20.

[8]郭慶春，孔令軍，崔文娟，史永博，張小永.基于BP神經(jīng)網(wǎng)絡(luò)模型的國內(nèi)旅游人數(shù)預(yù)測[J].價值工程，2011，30（27）：7.

[9]何苗苗，范佳奧，陸晴，吳羿昕.孤獨(dú)星球——北京[M].北京：中國地圖出版社，2017.