趙人行 郭旭萌 霍俊生 趙景林

(1、北京郵電大學 經(jīng)濟管理學院,北京100876 2、成方金融信息技術(shù)服務(wù)有限公司,北京100120 3、方正國際大數(shù)據(jù)(北京)有限公司,北京100080 4、黑龍江省科學技術(shù)協(xié)會,黑龍江 哈爾濱150001)

1 概述

運籌學與工程系統(tǒng)分析中的行程選擇與設(shè)計問題,是數(shù)學領(lǐng)域內(nèi)行程路線最優(yōu)化的典型問題。我國旅游線路設(shè)計研究經(jīng)過十幾年的發(fā)展己經(jīng)初具研究成果,研究角度涉及地理學、經(jīng)濟學、運籌學等領(lǐng)域,但研究深度還不夠,實證研究多,理論研究少；一般描述多,深入分析少。目前結(jié)合旅游景區(qū)相關(guān)條件和交通工具的研究多為按照國界、旅游天數(shù)、旅游線路距離遠近、旅游活動內(nèi)容和性質(zhì)、乘坐交通工具、行為和意愿特性,綜合性旅游路線規(guī)劃還很少,研究對于數(shù)據(jù)的利用和挖掘還不夠充分。我們必須盡可能利用相關(guān)數(shù)據(jù)開展研究,同時對相關(guān)的新課題進行探索性研究。本文是根據(jù)國家旅游局公布的5A 級景區(qū)及相關(guān)信息和省會城市間道路信息,及《全國高速公路一覽表》中現(xiàn)階段交通道路情況,提出一個典型熱點問題：最佳出行方式的選擇,研究旅游路線的具體策略和方案。隨著各種旅游服務(wù)業(yè)的發(fā)展,出行方式還可以考慮乘坐高鐵或飛機到達與景區(qū)相鄰的省會城市,而后采用租車的方式自駕到景區(qū)游覽。依據(jù)數(shù)學模型,設(shè)計一個十年游遍所有201 個5A 景區(qū)、費用最優(yōu)、旅游體驗最好的旅游線路,給出每一次旅游的具體線路(含每次具體出行方式；每一天的出發(fā)地、費用、路途時間、游覽景區(qū)、每個景區(qū)的游覽時間。租車費用300 元/天,油費和高速過路費另計,租車和還車需在同一城市)。此種出行方式可以節(jié)省一些路途時間用于景區(qū)游覽或休閑娛樂,但這種出行方式也會給旅游者帶來一些不便,有時費用也會增加。旅游愛好者根據(jù)個人旅游偏好確定在每一個景區(qū)最長逗留時間不超過統(tǒng)計數(shù)據(jù)給出的最少時間的2 倍。若干城市之間的高鐵票價和相關(guān)信息(約定：選擇高鐵出行要求當天乘坐高鐵的時間不超過6 個小時,乘坐高鐵或飛機的當天至多安排半天的景區(qū)游覽)；若干省會城市之間的機票全價價格信息(含機場建設(shè)費)。設(shè)旅游愛好者一家3 人同行,綜合考慮前述全程自駕、先乘坐高鐵或飛機到達省會城市后再租車自駕到景區(qū)等出行方式(住宿費簡化為省會城市和旅游景區(qū)200 元/人·天,地級市150 元/人·天,縣城100元/人·天；高速公路的油耗加過路費平均為1.00 元/公里,普通公路上油耗平均為0.60 元/公里。各景區(qū)所在地的信息,若景區(qū)位于某城市市區(qū)或近郊,則這類景區(qū)的市內(nèi)交通費用已計入住宿費中,不再另計)。

2 模型假設(shè)與問題分析

2.1 模型假設(shè)和符號說明

2.1.1 模型假設(shè)。2.1.1.1 旅游的過程中選用的任何交通方式不受惡劣天氣、交通擁堵、突發(fā)事件等干擾因素的影響。2.1.1.2旅游方案中設(shè)計的所有高速公路都可以雙向行駛。2.1.1.3 城市到景區(qū)、景區(qū)到景區(qū)的公路均為普通公路。2.1.1.4 G75 蘭海高速瓊州海峽段以高速公路形式連通。2.1.1.5 租車自駕旅行過程中人和車全程需在同一城市內(nèi)。2.1.1.6 旅游者一家三口出游,三人住宿費以三個單人費用標準計算。2.1.1.7 旅游者一家三口出游,乘坐高鐵飛機費用均為全價成人票,不存在學生票和臨時優(yōu)惠情況。2.1.1.8 旅游者出游,旅途中所有住宿費計算均以整天為單位。2.1.1.9 國家4A 級景區(qū)游覽時間為0.5 天。

2.1.2 符號說明,見表1。

表1 符號說明

2.2 問題分析及數(shù)據(jù)采集

2.2.1 問題分析。以高鐵、飛機、租車與自駕4 種交通方式相結(jié)合的全國5A 級景區(qū)綜合旅游線路規(guī)劃。2.2.1.1 交通方式增加了高鐵和飛機之后,可以有效地解決省會之間遠距離、長時間駕駛的問題。根據(jù)自主收集了更為全面的全國高鐵和航班信息。使用Floyd 算法求解上述任意兩個省會城市之間的最短高鐵和航班路線。經(jīng)過對最短路徑矩陣和路由矩陣的分析可得,任意兩個省會城市之間均有直達航班或轉(zhuǎn)機航班,但是部分西部省份省會城市未通高鐵。2.2.1.2 題目指出了省會之間更為便捷的交通方式和異地租車旅游的思路,大大縮短了省會之間的交通代價和對自駕游的限制,也加大了省會城市之間和普通城市之間交通便捷程度的差異。本文利用這一差異,使用分治算法將整個國內(nèi)5A 級景區(qū)旅游線路規(guī)劃問題分解為多個省會及附近5A 級景區(qū)線路規(guī)劃的子問題。[1]由題設(shè)和分治算法可知,總問題與子問題性質(zhì)相同,解結(jié)構(gòu)相似,子問題之間相互獨立。求出所有子問題的解,就可以得到總問題的解。2.2.1.3 建立數(shù)學模型設(shè)計一個十年游遍所有201 個5A 景區(qū)、費用最優(yōu)、旅游體驗最好的旅游線路。這一要求中包含一個定量條件,即十年內(nèi)遍歷201 個5A 級景區(qū)和兩個定性條件,即費用最優(yōu)、旅游體驗最好。兩個定性條件沒有具體要求,比較模糊。使用OWA 算子(有序加權(quán)平均算子),明確可定量的評價因素,對使用模擬退火算法生成的有限旅游方案屬性值進行集結(jié)和評價,給出指定評價體系內(nèi)的近似最優(yōu)解。

2.2.2 數(shù)據(jù)采集。2.2.2.1 全國公路道路數(shù)據(jù)收集。過全國最新高速公路里程表,以及互聯(lián)網(wǎng)數(shù)據(jù)得到城市與景區(qū)之間的具體數(shù)據(jù)。道路數(shù)據(jù)分為兩部分,第一部分是城市之間的距離,第二部分是城市與景區(qū)、景區(qū)與景區(qū)之間的距離。第一部分道路數(shù)據(jù),由全國高速里程及途徑城市一覽表獲得。數(shù)據(jù)采集規(guī)則是：與某一城市經(jīng)高速公路直接相連的其他所有城市,均被計入該城市的鄰接表中。此外利用互聯(lián)網(wǎng)收集到全國主要城市之間的高速里程以及對應(yīng)行駛時間。第二部分道路數(shù)據(jù)由官網(wǎng)查詢得到?！度珖糠志皡^(qū)公路道路數(shù)據(jù)整理》,收集到201 個國家5A 級景區(qū)和相關(guān)城市的高速里程數(shù)據(jù)。2.2.2.2 全國高鐵及航班數(shù)據(jù)收集。見《全國部分省會航班航行時間簡表》和《全國部分省會高鐵運行時間簡表》。2.2.2.3 景區(qū)數(shù)據(jù)分析。根據(jù)《全國各省份5A 級景區(qū)分布圖》,了解到201 個國家5A 級景區(qū)的分布信息。5A 級景區(qū)在華北、華東地區(qū)分布較為集中。江蘇省5A 級景區(qū)最多,有19 個,其次為浙江省,有12 個。同時,西部省份景點較少,且地理上分布較為稀疏,兩兩之間距離較遠。

3 模擬退火模型的建立與求解

3.1 模擬退火算法

假設(shè)有一個旅行商人要拜訪n 個城市,他必須選擇所要走的路徑,路徑的限制是每個城市只能拜訪一次,而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。

此種情況下我們可以利用模擬退火算法來解決TSP 問題。TSP 問題是典型的NP 問題,本題題設(shè)要比普通TSP 問題復(fù)雜,因此是比較典型的NP-hard 問題(圖1)。

對于這一NPH 問題,采用以概率1 獲取全局最優(yōu)解的模擬退火算法求取近似最優(yōu)解,然后在多項式時間內(nèi)進行結(jié)果的驗證。對于NP-hard 問題,用一句話概括他們的特征就是NP-hard問題至少和NP 問題一樣難。故可把本問題的定性分成兩個部分,一部分可以用多項式的時間驗證一個代表答案是不是真正的答案,這一部分問題組成了NP-complete 集合。證明一個問題是NP-hard,常用到的歸約(reduction),通常用<=這個符號來表示,如P<=Q,這個就表示可以把P 歸約到Q,當我們要證明一個問題是NP-hard 的時候,通常要做的是找到一個NPC 問題,把這個NPC 問題歸約到NP-hard 上去,即NPC<=NP-hard。歸約主要步驟為：(1)把NPC 的輸入轉(zhuǎn)化到NP-hard 的輸入,即每一個NPC 輸入,實際上都是一個NP-hard 的輸入。(2)說明針對一個NP-hard 的輸出,就能給出一個NPC 的輸出。要證明此問題是NP 問題可通過歸約。TSP 問題是典型的NP-hard 問題,因此此問題是NP-hard 問題。TSP 旅行商問題通過以上兩個主要步驟可以歸約到這個問題上來,并且以上的兩個轉(zhuǎn)化都要在多項式的時間內(nèi)完成,旅游路線的規(guī)劃和設(shè)計也是NP-hard 的。把任何一個NP-hard 的問題歸約到最短公共超序列問題上來,就能證明最短公共超序列問題也是NP-hard 的了。[3]

3.2 基于模擬退火算法模型的求解

對于問題中的理想旅游方案有以下條件：

圖1 P,NP,NP-hard,NPC 問題的關(guān)系

3.2.1 每年外出旅游時間不超過30 天,每年外出旅游次數(shù)不超過4 次；

3.2.2 每個5A 級景區(qū)有最少游覽時間；

3.2.3 行車時間每天限于7:00 至19:00 之間,景區(qū)游覽每天限于8:00 至18:00 之間；

3.2.4 每天駕駛時間不超過8 小時；

3.2.5 全天游覽限制駕駛時間不超過3 小時；

3.2.6 半天游覽限制駕駛時間不超過5 小時；

3.2.7 高速公路上的行車平均速度為90 公里/小時,普通公路上的行車平均速度為40 公里/小時；

3.2.8 各省省會均有24 小時的游覽時間,不包含市區(qū)的景區(qū)。根據(jù)這些限制條件,使用matlab 編程實現(xiàn),初始旅游方案和隨機線路的旅游方案。初始方案用于模擬退火算法的最優(yōu)值初始化,使用先近后遠原則生成近似最優(yōu)解的方案。隨機線路方案用于模擬退火算法進行循環(huán)最優(yōu)解的選擇。每次生成一個隨機序列,包含所有景區(qū)和省會,使用貪心算法及每次出行旅游都盡可能的去最多的景區(qū),最后得到一個完整的旅游線路。由于景區(qū)序列是完全隨機的,所以需要比較多的迭代次數(shù)來保證結(jié)果可以逼近最優(yōu)解。在模型實際求解過程中,使用了如表2所示的參數(shù)控制退火過程。[4]

表2 模擬退火算法參數(shù)

其中,由于此問題的解空間十分巨大,所以為了使降溫過程盡量均勻、緩慢,使用了如表所示的參數(shù)。

基于模擬退火算法的旅游路線規(guī)劃算法流程如圖2 所示。

3.3 數(shù)據(jù)處理

3.3.1 高鐵或動車最短距離矩陣

31 個省會之間高鐵或動車行車時間數(shù)據(jù)表,部分數(shù)據(jù)如表3。

3.3.2 航班最短距離矩陣

31 個省會之間航班行駛時間表,部分數(shù)據(jù)如表4。

3.3.3 5A 級景區(qū)分治數(shù)據(jù)

分治算法中,省會與景區(qū)分治分布部分數(shù)據(jù)如表5。

4 基于OWA 算子的多屬性決策方法

4.1 基于OWA 算子的多屬性決策方法及其基本思想

為下文論述,本部分令 M= {1,2, …, m},N = {1,2, …, n}。

圖2 模擬退火求解算法流程圖

表3 高鐵或動車最短運行時間數(shù)據(jù)簡表

表4 航班最短運行時間數(shù)據(jù)簡表

表5 省會與景區(qū)分治分布數(shù)據(jù)簡表

OWA 算子的特點在于,對數(shù)據(jù) ( a1, a2, …an),按從大到小的順序重新進行排序并通過加權(quán)集結(jié),而且元素aj與wj沒有任何聯(lián)系,只與集結(jié)過程中的第j 個未知有關(guān)(因此加權(quán)向量w 也成為位置向量)。[2]

4.2 基于OWA 算子多屬性決策方法具體步驟

表6

本文中要針對初始最優(yōu)方案以及隨機方案的兩個旅游方案x1,x2進行比較,并抽取下列9 項指標(屬性)進行評估：

u1-旅游總支出；u2-旅游行車交通費占總支出比重；u3-旅游高鐵飛機交通費占總支出比重；u4-旅游省會景區(qū)住宿費占總支出比重；u5-旅游市縣住宿費占總支出比重；u6-旅游總時間；u7-旅游行車時間占總時間比重；u8-旅游高鐵飛機時間占總時間比重；u9-景區(qū)游覽時間占總時間比重；u10-旅游租車次數(shù)。

5 模型結(jié)果分析與驗證

5.1 模型結(jié)果分析

本文的研究內(nèi)容主要解決了在租車、高鐵、飛機多種交通工具可供選擇的情況下,根據(jù)旅游愛好者的出行習慣和偏好,設(shè)計和規(guī)劃旅游的路線問題。

該模型中首先使用Floyd 算法求解任意兩個省會城市之間的最短高鐵和航班路線。利用省會之間高鐵和飛機等更為便捷的交通方式和靈活的異地租車旅游的思路,大大縮短了省會之間的交通代價和對自駕游的限制。在旅游線路的規(guī)劃上使用分治算法將整個國內(nèi)5A 級景區(qū)旅游線路規(guī)劃問題分解為多個省會及附近5A 級景區(qū)線路規(guī)劃的子問題。

5.2 模型結(jié)果驗證

對旅行路線的評價上使用OWA 算子(有序加權(quán)平均算子)方法,對使用模擬退火算法生成的有限旅游方案屬性值進行集結(jié)和評價,最后給出指定評價體系內(nèi)的近似最優(yōu)解。以結(jié)果的方案的一次出行線路為例簡表,如表7。

該次旅行路線為：

西安——昆明——迪慶藏族自治州香格里拉普達措國家公園——麗江玉龍雪山景區(qū)麗江古城景區(qū)——中科院西雙版納熱帶植物園——昆明石林風景區(qū)——大理崇圣寺三塔文化旅游區(qū)——昆明——西寧——青海湖風景區(qū)——西寧市湟中縣塔爾寺景區(qū)——西寧——西安。分析該旅行路線得：該算法模型設(shè)計和規(guī)劃的旅游路線首先從距離西安比較近的景區(qū)開始,然后逐漸向較遠的景區(qū)擴展。每次旅游的景區(qū)相對比較集中,避免因景點之間的距離太遠而造成來回奔波。模型規(guī)劃的旅游路線節(jié)省了出行路上的時間成本和經(jīng)濟成本,提高了旅游者對旅游路線的滿意度。單次出行的總時間適中,既避免了旅游時間過長而造成的旅途勞累,同時又不會因為旅游時間短而達不到調(diào)節(jié)生活的目的。通過分析生活和旅行習慣,及以上結(jié)合Floyd 算法和模擬退火算法并根據(jù)題目條件,使用OWA 算子對模擬退火產(chǎn)生的方案進行了評價。優(yōu)化的算法流程,得到旅游花費總時間為271.5 天左右,共計出游20 次,預(yù)計10 年內(nèi)完成游遍所有5A 級景區(qū)的旅游計劃。總費用大約為30 萬元。

表7 出行線路

5.3 模型推廣可行性分析

本文研究問題的模型是基于Floyd 的任意兩點之間的最短距離優(yōu)化算法,且通過模擬退火方法在對TSP 問題求解的基礎(chǔ)上進一步優(yōu)化,實現(xiàn)了方案尋優(yōu),并通過OWA 有序加權(quán)平均算子對方案進行進一步評價,故該模型不受出發(fā)地點影響,或其他因素影響可以忽略不計,可以推廣為對全國的自駕游愛好者的旅游線路規(guī)劃。通過對于個人自駕偏好的設(shè)置,可以為全國的自駕游愛好者規(guī)劃設(shè)計類似的旅游線路,并以北京為旅游出發(fā)地進行旅游路線規(guī)劃,并提供相應(yīng)的旅游計劃。

5.4 模型推廣過程

本文問題的研究在評價函數(shù)中OWA 有序加權(quán)平均算子的應(yīng)用基礎(chǔ)上,對于自駕游愛好者,將設(shè)定的九個相應(yīng)屬性的類型進行調(diào)整,以符合“自駕游”的個人旅游偏好,對模型進行改進,以推廣到全國自駕游愛好者的旅游路線規(guī)劃模型中。針對初始最優(yōu)方案以及隨機方案的兩個旅游方案x1,x2進行比較,并抽取下列9 項指標(屬性)進行評估：u1-旅游總支出；u2-旅游行車交通費占總支出比重；u3-旅游高鐵飛機交通費占總支出比重；u4-旅游省會景區(qū)住宿費占總支出比重；u5-旅游市縣住宿費占總支出比重旅游總時間；u6-旅游總時間；u7-旅游行車時間占總時間比重；u8-旅游高鐵飛機時間占總時間比重；u9-景區(qū)游覽時間占總時間比重；u10-旅游租車次數(shù)。根據(jù)旅游者的自駕游偏好,將屬性的類型進行調(diào)整,調(diào)整后結(jié)果為：其中成本型屬性包括：u1,u2,u3,u5,u6,u8。效益型屬性包括：u4,u7,u9,u10。在5.4 中,對于不同方案的九種屬性進行數(shù)據(jù)規(guī)范化中,需將屬性的類型針對旅游者個人偏好進行調(diào)整,以使相應(yīng)的屬性類型符合具體情況,為具有相應(yīng)個人偏好的旅游者提供更好旅游體驗的旅游路線規(guī)劃。其他步驟以及評價函數(shù)應(yīng)用大致相同,只需要更改與全國自駕游愛好者偏好相關(guān)的屬性類別就可以將模型進行進一步推廣。

5.5 方案合理性分析

由于OWA 有序加權(quán)平均算子,數(shù)據(jù)按從大到小的順序重新進行排序并通過加權(quán)集結(jié),而且元素與加權(quán)向量沒有任何聯(lián)系,只與集結(jié)過程中的大小位置有關(guān),故當旅游偏好改變時,可以通過提取不同屬性指標值,對屬性的效益型和成本型進行調(diào)整,從而規(guī)劃出更符合旅游者偏好的旅游路線。

6 模型的評價與推廣

6.1 模型評價

6.1.1 模型的優(yōu)點。6.1.1.1 模型運用分治算法,把本問題定性為NP-hard 問題,運用Floyd 求得最小距離矩陣,運用模擬算法進行方案尋優(yōu),具有較強的科學性。6.1.1.2 本文對于以時間為目標,以費用為最低,以旅游體驗為目標的模型建立,充分考慮了所有可能對于旅游路線最優(yōu)化的影響因素。

6.1.2 模型的缺點

本文問題中的旅游路線規(guī)劃模型的求解結(jié)果中,評價算子的加權(quán)向量還可以通過數(shù)據(jù)以及組合數(shù)、三角函數(shù)等方法進行進一步優(yōu)化。使得結(jié)果得到進一步優(yōu)化,與收集數(shù)據(jù)具有更強的聯(lián)系。

6.2 模型改進

模型改進中,可以考慮使用遺傳算法或者神經(jīng)網(wǎng)絡(luò)算法對模擬退火算法進行相應(yīng)優(yōu)化,在評價方面通過組合數(shù)、三角函數(shù)、結(jié)合數(shù)據(jù)等方法,通過更全面的數(shù)據(jù)收集及數(shù)學方法的應(yīng)用,對有序加權(quán)平均算子的加權(quán)向量進行更加科學的確定。此外還可以通過網(wǎng)絡(luò)爬蟲等技術(shù),進行數(shù)據(jù)挖掘,對于高鐵機票等信息進行更為具體的挖掘,通過數(shù)據(jù)庫等技術(shù),可以改進成為實時旅游路線規(guī)劃模型。

6.3 模型推廣

本模型可以通過應(yīng)用和修正,運用到多種行程問題的科學規(guī)劃中,其中也包括從事數(shù)學和計算機研究的專家學者,在涉及自身旅游路線規(guī)劃中學以致用,嘗試理論與實踐的結(jié)合,可以為旅行社和旅游相關(guān)部門決策提供一定參考。

此外,本模型根據(jù)其特性也可以應(yīng)用到對于某地區(qū)某產(chǎn)品的推廣,或者某計劃覆蓋人群的應(yīng)用當中去。