基于OWA 算子改進模擬退火算法的路線規劃研究

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

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

1 概述

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

2 模型假設與問題分析

2.1 模型假設和符號說明

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

2.1.2 符號說明,見表1。

表1 符號說明

2.2 問題分析及數據采集

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

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

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

3.1 模擬退火算法

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

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

對于這一NPH 問題,采用以概率1 獲取全局最優解的模擬退火算法求取近似最優解,然后在多項式時間內進行結果的驗證。對于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 的輸入轉化到NP-hard 的輸入,即每一個NPC 輸入,實際上都是一個NP-hard 的輸入。(2)說明針對一個NP-hard 的輸出,就能給出一個NPC 的輸出。要證明此問題是NP 問題可通過歸約。TSP 問題是典型的NP-hard 問題,因此此問題是NP-hard 問題。TSP 旅行商問題通過以上兩個主要步驟可以歸約到這個問題上來,并且以上的兩個轉化都要在多項式的時間內完成,旅游路線的規劃和設計也是NP-hard 的。把任何一個NP-hard 的問題歸約到最短公共超序列問題上來,就能證明最短公共超序列問題也是NP-hard 的了。[3]

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

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

圖1 P,NP,NP-hard,NPC 問題的關系

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

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

3.2.3 行車時間每天限于7:00 至19:00 之間,景區游覽每天限于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 小時的游覽時間,不包含市區的景區。根據這些限制條件,使用matlab 編程實現,初始旅游方案和隨機線路的旅游方案。初始方案用于模擬退火算法的最優值初始化,使用先近后遠原則生成近似最優解的方案。隨機線路方案用于模擬退火算法進行循環最優解的選擇。每次生成一個隨機序列,包含所有景區和省會,使用貪心算法及每次出行旅游都盡可能的去最多的景區,最后得到一個完整的旅游線路。由于景區序列是完全隨機的,所以需要比較多的迭代次數來保證結果可以逼近最優解。在模型實際求解過程中,使用了如表2所示的參數控制退火過程。[4]

表2 模擬退火算法參數

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

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

3.3 數據處理

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

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

3.3.2 航班最短距離矩陣

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

3.3.3 5A 級景區分治數據

分治算法中,省會與景區分治分布部分數據如表5。

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

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

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

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

表3 高鐵或動車最短運行時間數據簡表

表4 航班最短運行時間數據簡表

表5 省會與景區分治分布數據簡表

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

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

表6

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

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

5 模型結果分析與驗證

5.1 模型結果分析

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

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

5.2 模型結果驗證

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

該次旅行路線為：

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

表7 出行線路

5.3 模型推廣可行性分析

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

5.4 模型推廣過程

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

5.5 方案合理性分析

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

6 模型的評價與推廣

6.1 模型評價

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

6.1.2 模型的缺點

本文問題中的旅游路線規劃模型的求解結果中,評價算子的加權向量還可以通過數據以及組合數、三角函數等方法進行進一步優化。使得結果得到進一步優化,與收集數據具有更強的聯系。

6.2 模型改進

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

6.3 模型推廣

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

此外,本模型根據其特性也可以應用到對于某地區某產品的推廣,或者某計劃覆蓋人群的應用當中去。