最優旅行目的地選擇及旅行路徑規劃

李雨彤

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

【關鍵詞】最優旅行路線;游客體驗;Dijkstra算法;非線性規劃

一、引言

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

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

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

二、問題的描述

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

三、改進層次分析法確定目的地優先級

可選的景點數不勝數，但是在同一次旅行中游客能夠前往的地點是有限的.因此在開始計算前，我們要根據游客的喜好將所有目的地進行排序.該順序將作為目的地被考慮的先后順序.游客對景點的喜好值將決定景點是否可以被納入考慮的范圍，并將被用來衡量游客對于最終的方案的滿意度.

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

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

（1）

圖1層次分析法用于景點排序的流程圖

在該評分系統下，分值高的景點表示傾向于被游客選擇.在各景點Sj已知后，按照從大到小的順序排序，即可得到景點被該（組）游客喜好的排名.當景點過多時，我們為了簡化算法，假設游客總旅程天數為D0，由于每天旅行的景點有限，景點過多會極大地影響游客旅行體驗，因此不妨假設景點不超過3個，則在篩選時僅保留排名約為3，旅程天數為D0及以前的景點，排名位于3，旅程天數為D0以后的景點不做考慮.

四、Dijkstra算法尋找兩點之間最優路徑

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

每一條線段上的數值amn為綜合考慮費用和時間的結果，賦值計算方法為

amn=fmn×tmn（2）

其中fmn表示每一小段路上的費用，tmn表示每一小段路上的時間.

圖2Dijkstra算法示例圖

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

五、旅行問題變量定義

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

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

xij=1，該游客從i點前往j點xij=0，該游客不從i點前往j點

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

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

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

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

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

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

（5）

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

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

（6）

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

Tmean，j=PmomentPaverage×Topen（7）

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

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

（8）

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

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

（9）

六、三類非線性規劃模型

1.金額限定型

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

目標函數：

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為游客要求的時間上限

目標函數：

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.雙重限定型

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

目標函數：

MAXE=Uefficiency×UsatisfactionFtotal×Dtotal（14）

限制條件：

Ftotal≤F0，Dtotal≤D0.（15）

七、模型驗證與求解

本文帶入了北京市景區的數據對模型進行驗證.

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

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

八、結語

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

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

【參考文獻】

[1]伍雄斌，關宏志，韓艷.多約束下基于游客體驗的旅游路線優化模型[J].科學技術與工程，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]龐亮.基于多目標優化的旅游路線的建模[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]楊靜.旅游路線的最優化設計研究[J].新經濟，2016（09）：18-19.

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

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

[8]郭慶春，孔令軍，崔文娟，史永博，張小永.基于BP神經網絡模型的國內旅游人數預測[J].價值工程，2011，30（27）：7.

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