最優旅行方案設計

孫玉靜　王月琨

【摘 要】隨著自由行成為出行的新選擇，制定一個全面的旅游計劃越來越重要，而選擇交通工具、安排酒店和設計旅游路線則是規劃的關鍵。本文將時間與費用問題轉化為換乘次數和站臺數問題，將站臺和所在線路構成換乘矩陣，建立多目標路徑優化模型，運用MATLAB，逐步求解直達路線、換乘一次、兩次及三次路線，結合站臺數，選取最佳路線。采用背包問題與旅行商問題（TSP）相結合的方法，先通過背包問題將所有景點進行分組，再通過TSP問題，將每天的路線進行優化，達到乘車總時間最小，利用Lingo求解。考慮乘車路費與時間，景點門票與酒店價格以及景點游覽時間等因素，建立0-1規劃，將實現費用少、景點多的多目標通過適當的擬合轉化為單目標優化模型，并使用Lingo得出3天內最優的旅游路線與酒店安排。依據游客的游覽興趣，賦予景點門票一定的權重約束，并考慮安排不同酒店的因素，基于問題三的模型，增加優先級約束條件與目標函數，建立多目標規劃之權重最優化模型，采用模型三的方法，利用Lingo求解出最佳路線與酒店安排。

【關鍵詞】多目標規劃；旅行商問題；背包問題；Lingo；MATLAB

一、問題的分析

選擇最優的出行方案。所謂最優的選擇，可以有如下幾種解釋：（1）最節省時間的線路（尤其是存在換乘的情況），（2）最節省費用的線路，（3）將時間與車費做加權平均后的最小值，根據游客個人對時間和金錢的重視程度選擇要搭乘的公交車及其線路。

在限定游覽時間的前提下，為實現費用少、景點多的目標 ，需選擇酒店距離景點較近、每天的景點之間路徑近、景點游覽時間較短且費用較低的酒店和景點。此問題類似最小費用最大流問題，本文建立0-1規劃，使用Lingo得出3天內最優的旅游路線與酒店安排。

二、基本假設

1.假設交通系統始終正常運行，不存在堵車，臨時交通事故，惡劣天氣等情況。

2.假設乘坐一輛車為不換乘，乘坐兩輛車為換乘一次，以此類推。

3.假設游客是理性的，即會從時間最優、價錢最優或者時間與價錢權重最優三種情況下選擇其中之一。

4.假設公交車的行駛速度保持不變。

5.假設游客參觀時間為該景區給定的參觀時間。

6.假設從酒店步行到車站，以及從車站步行到景點的時間忽略不計。

7.假設乘客到起始站可以直接選擇公交車，即不計在起始站的等車時間。

8.假設游客每天的游覽路線是環形的。

三、問題分析與求解

基于預處理矩陣，判斷出發點和目的地之間是否有直達的線路，如有就確定為最優線路，若無就通過MATLAB尋找換乘次數超過一次的所有站點。

尋找換乘站點。把求得的站點與要求的出發點和目的地建立循環，逐個修改起始站點與終止站點的值可求出通過各站點的路線，再將經過所求得的站點的路線與經過起點和終點的路線進行比較，尋找相同的路線，若存在，則這個站點可作已知的起點與終點的中轉站；若不存在中轉站，則調整換乘次數直到可以找到可行的乘車路線為止。在換乘次數盡量最少的原則之下，以從出發地點到達目的地點的總乘車站數為基準，換乘車前后總乘車站數為最少的作為系統的推薦線路，這樣既符合常規，也可能是最優線路。

因此，選取上述三種方法權重最小的作為最有出行線路。從出發地到目的地的所需要的總時間T由兩部分構成：一是公交的行駛時間；二是乘客換乘時的耗時（本題忽略此時間）。公交的行駛時間等于相鄰站點間的平均行駛時間乘以公交行駛的站數，即從出發點到目的地所需總時間為

T=■（mk-1）*t1

建立目標函數

min T

min s（換乘次數）

s.t.0≤s≤2mk≥1

路徑選擇原則具體如下：

在系統中，輸入乘客的起始位置和目的地，為了實現乘客的目標且能使換乘次數少，則可按如下步驟進行搜索[16]；（若乘客所行駛的路線經過某個車站，則為1，否則為0，用C表示）

① 搜索集合A與看是否存在一條路線，使得流線同時經過 a與b 兩種結果。若存在，則說明只要乘車一次就可以到達目的地，乘車路線可為a與b所同時存在的那條線。

② 若①種情況不成立，則需要換車，搜索集合A與看是否存在兩條路線，且在這兩條路線上有相交的車站cap，滿足cap不等于0，如果存在，則說明需要換車一次則可到達目的地，乘車路線為：a → cap → b ，若cap只有一種搜索結果顯示，從a到b的乘車線路就是這種最佳。若不是唯一的，而有多種選擇換乘一次可達目的地，則此時可有K種途徑可以到達目的地，此時就進一步對此K種中轉站進行掃描，輸出站點數最少的一種方式，進而顯示乘坐次數最佳的途徑到達目的地。

③ 如果②都不存在時，說明乘車至少要換兩次，搜索集合A：看是否存在兩個中轉站站點，以及滿足在這三條路線上至少有兩條路線上有公共的車站，若存在，則說明只需換車兩次即可到達目的地。

④ 若換乘兩次未能到達，則需要換乘至少三次才能實現，根據以上同樣的方法，仍然可以搜索出最佳的出行線路。出于對人們的可承受的心理限度的考慮，再基于較優質的交通網絡，換乘次數在此設定時不應大于兩次。

參考文獻：

[1]亓曉同.晏磊.劉琴.黃強.馬俊明.武漢市高校間公交線路的最優化設計.管理科學.2016.

[2]賀國光.胡學年.劉豹.用于公交線路優化設計的四步啟發式算法.系統工程學報.1998.

[3]蘇海濱.王繼東.交通網絡中多路徑優化選擇算法的研究.智能運輸系統與交通工程.2007.