基于旅行費用約束的景點及路徑動態規劃研究

方蘇杰 張宇航 方成剛

1(南京師范大學附屬中學 江蘇 南京 210003)2(南京工業大學 江蘇 南京 211800)

0 引 言

隨著生活水平的提高，人們對旅游消費的熱情一直處于持續增長的過程。游覽景點的規劃是否合理對于旅行過程的感受至關重要，合理的游覽路徑不僅使旅行者感到時間安排合理、費用合算、旅游感觀價值高，還能使旅行社降低成本、提高效益、提升好評指數。游覽景點規劃問題從不同角度對旅行過程進行優化，如從最短時間、最小費用、最短距離等不同方面對旅游景點進行尋優[1-3]。文獻[4]以廬山為例，以一日游為時間約束，利用Dijkstra算法實現盡可能多景點的最短路徑規劃；文獻[5]以旅游成本和游客舒適度為目標函數，利用遺傳算法對全國201個5A級景區的旅游路徑進行優化。

傳統的游覽景點規劃通常以成本最小作為優化目標，但對于旅行社或旅行者常常需要針對一定的旅行預算費用進行規劃，并希望在預算費用范圍內盡可能游覽更多綜合性價比高的景點。

1 問題描述與分析

旅行費用通常包括交通費、住宿膳食費、門票費等幾個部分，不同的游覽景點規劃將導致上述幾個費用比例發生變化。對于旅行社或旅行者而言，如何優化選擇旅游景點以便在合理的預算費用范圍內游覽更多評價指數高的景點是一個經常遇見的問題。

該問題難點在于旅行總費用隨景點規劃的不確定而發生動態變化，需要通過優化算法在預算費用范圍內選擇合適的游覽景點以降低交通食宿費所占比例，增強旅行體驗。上述問題求解可歸結為兩個方面：① 在預算費用約束條件下挑選盡可能多的高綜合評價指數景點，即0-1背包問題。② 遍歷規劃景點最短路徑以降低交通食宿費比例，即旅行商問題。

本文利用二分法及動態規劃算法，并結合上述兩個經典問題對基于旅行預算費用約束的游覽景點進行規劃，以獲取最大旅行價值體驗。此方法不僅適用于游覽景點規劃，亦可用于管路鋪設、道路修建等路徑規劃問題。

2 數學建模及動態規劃求解

為簡化起見，對上述旅游景點規劃問題做以下幾點假設：

(1) 旅行總費用T總為：

T總=T景點+T交通+T食宿

式中：T景點為旅行景點產生的費用，本例僅考慮門票費用總和；T交通為遍歷各個規劃旅游景點的交通費用總和；T食宿為旅行食宿費用總和，本例景點旅行時間每增加8個小時，則旅行天數增加一天。

(2) 采用自駕出行，交通費及交通時間與距離成線性關系。

(3) 交通與游覽時間之和每大于10小時，需要增加一次住宿膳食費。

2.1 景點綜合評價指數建模

景點主要參考指標及綜合評價指數如表1所示。

表1 景點主要參考指標及綜合評價指數

設影響每個景點綜合評價指數的主要因素包括以下幾個方面：

n1——質量等級，按《旅游景區質量等級的劃分與評定》(GB/T 17775-2003)對景區的綜合評分，分為A、AA、AAA、AAAA、AAAAA五個等級；

a1——游客評價，通過網評方式由游客對景區進行游覽體驗評價，其評價指數可采用5分制；

ci——景區門票費用；

ti——景區平均游覽時間；

對上述參考指標進行歸一化處理，并通過相關指標對景區進行綜合評價，其評價函數pi為:

(1)

式中：ω1為質量等級權重，質量等級指標由政府機構進行評估，可信度高，其權重取值可相對較大；ω2為游客評價權重；ω3為游覽時間/游覽費用權重。對于費用為零的景點，取ti/ci=1。

2.2 基于預算費用約束的游覽景點規劃[6-7]

如表1中共有n個景點，第i個景點的游覽費用為ci，綜合評價指數為pi，則在滿足游覽預算費用C的條件下選擇合適的景點，并使其綜合評價指數之和最大，其數學模型如下：

(2)

式中：xi=1，表示該景點被選中；xi=0，表示該景點未被選中。

上述數學模型是一個整數規劃問題，可采用遞歸算法進行求解。假設已經完成景點1，2，…，i-1的規劃，剩余游覽費用為j，則對i，i+1，…，n個景點進行規劃的最優解m(i，j)為：

(3)

建立m(i，j)的遞歸計算式為：

(4)

2.3 遍歷景點最短路徑規劃[8-9]

通過上述算法在n個景點中選擇了m個景點，進一步規劃遍歷m個景點的最短路徑以降低交通食宿費的比例。設景點的集合為V，為第i個景點到第j個景點之間的距離，則遍歷各旅游景點最短路徑的數學模型如下：

(5)

由于遍歷最短路徑與出發點無關，故可從任一景點i開始進行路徑尋優。令d(i,V′)為從景點i出發經過V′(尋優初始時，V′=V-{i})中各個景點一次且僅一次，最后回到出發點i的最短路徑長度。則求解d(i,V′)的動態規劃函數為：

d(i,V′)=min{cik+d(k,V′-{k})} (k∈V′)

(6)

d(k,{})=cki(k≠i)

2.4 基于二分法的循環優化

理想的景點規劃結果應提高游覽費用在總費用中的比例，盡可能游覽更多綜合評價指數高的景點。但在景點規劃的開始階段并不確定旅游費用中各個組成部分的比例，因此在利用式(2)進行景點規劃時，需要初定游覽費用比例，根據此設定費用進行景點規劃。本文采用二分法先初定游覽費用在總費用中的比例，再利用0-1背包算法挑選出合適的景點；進一步利用式(5)的旅行商算法遍歷前述規劃景點最短路徑，計算出相應的交通食宿費；最后驗算規劃費用與預算費用的差值絕對值是否小于允差，如不符合則使用二分法調整游覽費用比例繼續進行優化，直至符合條件為止。上述算法流程圖如圖1所示。

圖1 景點規劃流程圖

2.5 算法時間復雜性分析

上述算法包括三個部分，其時間復雜度如下：

1) 基于二分法的費用區間搜索，時間復雜度為O(log(n))；

2) 基于動態規劃法的0-1背包求解，時間復雜度為O(n×C)；

3) 基于動態規劃法的旅行商(TSP)求解，時間復雜度為O(n2×2n)。

按照上述算法循環規則計算整個程序的時間復雜度為O(max(log(n)×(n×C)，log(n)×(n2×2n))。由算法復雜度與時間效率關系可知該算法的效率較高，適用于旅游景點規劃一類計算量相對較小的場合，且可以獲得全局最優解。

3 算例分析

南京是中國十大風景名勝之一，其年度旅游總收入亦在國內排名前列，南京擁有鐘山風景區、夫子廟、總統府、秦淮河、玄武湖等優質旅游資源[10-11]。本文以南京的主要旅游景點為例(見表2)，景點的距離矩陣見表3，通過上述算法在規定預算費用范圍內進行景點優化選擇。

表2 南京主要景點的相關指標列表

表3 景點間距離矩陣

續表3

假設旅行食宿費為400元/天，交通費為3元/公里。利用MATLAB進行編程分別對旅行預算總費用為1 000元和500元兩種情況進行規劃，其計算結果見表4及圖2、圖3。

表4 按不同預算費用的規劃結果比較

圖3 預算總費用1 000元規劃結果

將上述算法利用java開發成基于安卓系統運行的APP，其界面如圖4、圖5所示，用戶僅需要輸入城市和旅行費用預算等相關參數，即可得到規劃結果，如圖6所示。

圖4 城市選擇界面

圖5 參數輸入界面

圖6 規劃結果界面

4 結 語

本文提出了以總旅行預算費用為約束條件獲取最大旅行體驗的旅游景點規劃問題，建立了景點綜合評價指數模型。通過0-1背包算法求得費用約束條件下綜合評價指數最高的景點集合，再利用旅行商算法遍歷景點獲取最短游覽路徑以降低交通費用，最后通過二分法循環優化上述過程得到景點規劃最優解。

本文以南京主要景點為例給出其景點評價指數和景點距離矩陣，通過上述優化算法分別對預算總費用為1 000元和500元兩種情況進行規劃，其規劃景點及游覽路徑合理，滿足預算費用要求。