方蘇杰 張宇航 方成剛

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

0 引 言

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

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

1 問題描述與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

設(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ū)平均游覽時間；

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

(1)

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

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

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

(2)

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

上述數(shù)學(xué)模型是一個整數(shù)規(guī)劃問題，可采用遞歸算法進行求解。假設(shè)已經(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個景點的最短路徑以降低交通食宿費的比例。設(shè)景點的集合為V，為第i個景點到第j個景點之間的距離，則遍歷各旅游景點最短路徑的數(shù)學(xué)模型如下：

(5)

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

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

2.5 算法時間復(fù)雜性分析

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

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

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

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

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

3 算例分析

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

表2 南京主要景點的相關(guān)指標(biāo)列表

表3 景點間距離矩陣

續(xù)表3

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

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

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

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

圖4 城市選擇界面

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

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

4 結(jié) 語

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

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