基于旅行費用約束的景點及路徑動態(tài)規(guī)劃研究

方蘇杰 張宇航 方成剛

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

0 引 言

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

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

1 問題描述與分析

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

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

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

2 數(shù)學建模及動態(tài)規(guī)劃求解

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

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

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

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

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

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

2.1 景點綜合評價指數(shù)建模

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

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

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

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

a1——游客評價，通過網(wǎng)評方式由游客對景區(qū)進行游覽體驗評價，其評價指數(shù)可采用5分制；

ci——景區(qū)門票費用；

ti——景區(qū)平均游覽時間；

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

(1)

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

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

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

(2)

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

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

(3)

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

(4)

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

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

(5)

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

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

(6)

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

2.4 基于二分法的循環(huán)優(yōu)化

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

圖1 景點規(guī)劃流程圖

2.5 算法時間復雜性分析

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

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

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

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

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

3 算例分析

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

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

表3 景點間距離矩陣

續(xù)表3

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

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

圖3 預算總費用1 000元規(guī)劃結果

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

圖4 城市選擇界面

圖5 參數(shù)輸入界面

圖6 規(guī)劃結果界面

4 結 語

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

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