最優(yōu)旅行方案設(shè)計

孫玉靜　王月琨

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

【關(guān)鍵詞】多目標(biāo)規(guī)劃；旅行商問題；背包問題；Lingo；MATLAB

一、問題的分析

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

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

二、基本假設(shè)

1.假設(shè)交通系統(tǒng)始終正常運(yùn)行，不存在堵車，臨時交通事故，惡劣天氣等情況。

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

3.假設(shè)游客是理性的，即會從時間最優(yōu)、價錢最優(yōu)或者時間與價錢權(quán)重最優(yōu)三種情況下選擇其中之一。

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

5.假設(shè)游客參觀時間為該景區(qū)給定的參觀時間。

6.假設(shè)從酒店步行到車站，以及從車站步行到景點(diǎn)的時間忽略不計。

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

8.假設(shè)游客每天的游覽路線是環(huán)形的。

三、問題分析與求解

基于預(yù)處理矩陣，判斷出發(fā)點(diǎn)和目的地之間是否有直達(dá)的線路，如有就確定為最優(yōu)線路，若無就通過MATLAB尋找換乘次數(shù)超過一次的所有站點(diǎn)。

尋找換乘站點(diǎn)。把求得的站點(diǎn)與要求的出發(fā)點(diǎn)和目的地建立循環(huán)，逐個修改起始站點(diǎn)與終止站點(diǎn)的值可求出通過各站點(diǎn)的路線，再將經(jīng)過所求得的站點(diǎn)的路線與經(jīng)過起點(diǎn)和終點(diǎn)的路線進(jìn)行比較，尋找相同的路線，若存在，則這個站點(diǎn)可作已知的起點(diǎn)與終點(diǎn)的中轉(zhuǎn)站；若不存在中轉(zhuǎn)站，則調(diào)整換乘次數(shù)直到可以找到可行的乘車路線為止。在換乘次數(shù)盡量最少的原則之下，以從出發(fā)地點(diǎn)到達(dá)目的地點(diǎn)的總乘車站數(shù)為基準(zhǔn)，換乘車前后總乘車站數(shù)為最少的作為系統(tǒng)的推薦線路，這樣既符合常規(guī)，也可能是最優(yōu)線路。

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

T=■（mk-1）*t1

建立目標(biāo)函數(shù)

min T

min s（換乘次數(shù)）

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

路徑選擇原則具體如下：

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

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

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

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

④ 若換乘兩次未能到達(dá)，則需要換乘至少三次才能實現(xiàn)，根據(jù)以上同樣的方法，仍然可以搜索出最佳的出行線路。出于對人們的可承受的心理限度的考慮，再基于較優(yōu)質(zhì)的交通網(wǎng)絡(luò)，換乘次數(shù)在此設(shè)定時不應(yīng)大于兩次。

參考文獻(xiàn)：

[1]亓?xí)酝?晏磊.劉琴.黃強(qiáng).馬俊明.武漢市高校間公交線路的最優(yōu)化設(shè)計.管理科學(xué).2016.

[2]賀國光.胡學(xué)年.劉豹.用于公交線路優(yōu)化設(shè)計的四步啟發(fā)式算法.系統(tǒng)工程學(xué)報.1998.

[3]蘇海濱.王繼東.交通網(wǎng)絡(luò)中多路徑優(yōu)化選擇算法的研究.智能運(yùn)輸系統(tǒng)與交通工程.2007.