最優旅行方案設計

隨着自由行成為出行的新選擇，制定一個全面的旅遊計劃越來越重要，而選擇交通工具、安排酒店和設計旅遊路線則是規劃的關鍵。本文將時間與費用問題轉化為換乘次數和站台數問題，將站台和所在線路構成換乘矩陣，建立多目標路徑優化模型，運用MATLAB，逐步求解直達路線、換乘一次、兩次及三次路線，結合站台數，選取最佳路線。下面是小編整理的最優旅行方案設計，歡迎來參考!

採用揹包問題與旅行商問題（TSP）相結合的方法，先通過揹包問題將所有景點進行分組，再通過TSP問題，將每天的路線進行優化，達到乘車總時間最小，利用Lingo求解。考慮乘車路費與時間，景點門票與酒店價格以及景點遊覽時間等因素，建立0-1規劃，將實現費用少、景點多的多目標通過適當的擬合轉化為單目標優化模型，並使用Lingo得出3天內最優的旅遊路線與酒店安排。依據遊客的遊覽興趣，賦予景點門票一定的權重約束，並考慮安排不同酒店的因素，基於問題三的模型，增加優先級約束條件與目標函數，建立多目標規劃之權重最優化模型，採用模型三的方法，利用Lingo求解出最佳路線與酒店安排。

　　一、問題的分析

選擇最優的出行方案。所謂最優的選擇，可以有如下幾種解釋：（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：看是否存在兩個中轉站站點，以及滿足在這三條路線上至少有兩條路線上有公共的車站，若存在，則説明只需換車兩次即可到達目的地。

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