公交線路的最優(yōu)選擇摘要本文對(duì)乘公交、看奧運(yùn)這一實(shí)際問題進(jìn)行了深入的研究，首先對(duì)公交乘客進(jìn)行了調(diào)查，得出影響乘客出行的三個(gè)主要因素分別為：換乘次數(shù)、出行時(shí)間、出行費(fèi)用，通過《北京公交系統(tǒng)（BRT）調(diào)研報(bào)告》【1】的統(tǒng)計(jì)結(jié)果，得出出行時(shí)間最短是乘客出行考慮的最主要因素，其次是換乘次數(shù)和出行費(fèi)用（由于費(fèi)用比較少，以出行時(shí)間和換乘次數(shù)為主），然后建立的多目標(biāo)規(guī)劃模型，從而確定了出行者對(duì)路線的所有選擇方案。對(duì)于問題一：我們僅考慮公交線路，考慮到人們的心理因素，人們對(duì)換乘次數(shù)有一個(gè)最大的承受上限，不能無(wú)限制的換乘下去，所以我們限定最大換乘次數(shù)為2，即最多利用3條公交線路從起點(diǎn)站到達(dá)終點(diǎn)站，分別建立出行時(shí)間和乘車minT=X（m-1）*t+1*s+（t-1）（s+1）k1337k=1費(fèi)用多目標(biāo)模型為：minsminp=XpABk

k=1然后把520條公交線路讀入到MATLAB當(dāng)中，用MATLAB編程編程求解得到換乘1次和換乘2次6對(duì)起始站一終點(diǎn)站的最優(yōu)路線。僅在此給出S3359-S1828的最佳路線：表1：換乘1次時(shí)S3359-S1828的最優(yōu)線路方案起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站線路2時(shí)間（分）費(fèi)用（元）S3359S1828L436（下）S1784L167（下）1013表2：換乘2次時(shí)S3359-S1828的最優(yōu)線路方案起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時(shí)間費(fèi)用S3359S1828L015（下）S2903L027（環(huán)）S1784L167（下）733其余結(jié)果見正文對(duì)于問題二：要求同時(shí)考慮公汽與地鐵線路，我們同樣建立了多目標(biāo)模型，我們首先將增加的地鐵線路信息添加到問題1建立的兩個(gè)矩陣中，利用與問題1相似的編程思路，求解得到換乘1次和換乘2次時(shí)6對(duì)起始站一終到站之間的最佳路線。S3359-S1828的最佳路線與問題1的相同，其余結(jié)果見正文。對(duì)于問題三：要求同時(shí)考慮公汽、地鐵和步行，我們建立了全局替換模型和局部替換模型。最后我們對(duì)模型進(jìn)行了推廣，給出了線路的“滿載度”的定義，在考慮“滿載度”之后，建立了新的模型。關(guān)鍵詞：多目標(biāo)規(guī)劃 調(diào)查MATLAB滿載度

關(guān)鍵詞：多目標(biāo)規(guī)劃 調(diào)查MATLAB滿載度1.1.問題重述問題的相關(guān)背景：我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。乘公交，看奧運(yùn)的相關(guān)信息：1.2.1基本參數(shù)設(shè)定：相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間）：3分鐘相鄰地鐵站平均行駛時(shí)間（包括停站時(shí)間）：2.5分鐘公汽換乘公汽平均耗時(shí)地鐵換乘地鐵平均耗時(shí)地鐵換乘公汽平均耗時(shí)公汽換乘地鐵平均耗時(shí)5分鐘（其中步行時(shí)間2分鐘）公汽換乘公汽平均耗時(shí)地鐵換乘地鐵平均耗時(shí)地鐵換乘公汽平均耗時(shí)公汽換乘地鐵平均耗時(shí)4分鐘（其中步行時(shí)間2分鐘）7分鐘（其中步行時(shí)間4分鐘）6分鐘（其中步行時(shí)間4分鐘）公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0?20站：1元；21?40站：2元；40站以上：3元地鐵票價(jià)：3元（無(wú)論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎn)化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合1.2.2公交線路及相關(guān)信息（見數(shù)據(jù)文件B2007data.rar）需要解決的問題：?jiǎn)栴}一：僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附件中的相關(guān)數(shù)據(jù)，利用所得到的模型與算法，求出以下6對(duì)起始站一終到站之間的最佳路線（要有清晰的評(píng)價(jià)說明)。(1)、S3359-S1828(4)、S0008-S0073(2)、S1557-S0481 (3)、S0971-S0485(5)、S0148-S0485 (6)、S0087—S3676問題二：同時(shí)考慮公汽與地鐵線路，解決以上問題。問題三：假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。問題分析本文需要對(duì)乘公交、看奧運(yùn)這一實(shí)際問題進(jìn)行了深入的研究，設(shè)計(jì)出一種線路選擇的算法，這種算法應(yīng)該能滿足不同用戶的需求，能夠從復(fù)雜的網(wǎng)絡(luò)中找到

H：他按乘方便費(fèi)用低用戶所需要的線路。我們首先對(duì)乘客的心理進(jìn)行研究的調(diào)查，H：他按乘方便費(fèi)用低用戶所需要的線路。我們首先對(duì)乘客的心理進(jìn)行研究的調(diào)查，根據(jù)《北京公交系統(tǒng)（BRT）調(diào)研報(bào)告》【1】的統(tǒng)計(jì)結(jié)果，得到左邊的餅狀圖：間。由此我們得到影響他們乘坐公交的主要因素：出行時(shí)間、換乘次數(shù)。對(duì)于問題一：我們只需考慮公交的情況，在文本文檔公汽線路信息中一共給出了520條公汽線路，3957個(gè)公汽站點(diǎn)。我們分別分析出行時(shí)間、換乘次數(shù)、乘車費(fèi)用，從而使建立目標(biāo)函數(shù)，分別使出行時(shí)間最短、換乘次數(shù)最少、乘車費(fèi)用最少。考慮到人們的心理因素，人們對(duì)換乘次數(shù)有一個(gè)最大的承受上限，不能無(wú)限制的換乘下去，所以我們限定最大換乘次數(shù)為2,即最多利用3條公交線路從起點(diǎn)站到達(dá)終點(diǎn)站。分別考慮在換乘次數(shù)為0丄2時(shí)時(shí)間最短和乘車費(fèi)用最少，時(shí)間的花費(fèi)主要來(lái)自公交正常行駛的時(shí)間以及換乘公交時(shí)所花費(fèi)的時(shí)間。因此我們需要考慮在公交網(wǎng)絡(luò)什么時(shí)候換乘，什么時(shí)候不需要換乘從而達(dá)到花費(fèi)時(shí)間最少。乘車費(fèi)用的差異主要來(lái)自選擇分段計(jì)價(jià)下乘坐站數(shù)的不同以及選擇不同的換乘方案等。對(duì)于問題二：我們的主要任務(wù)是在第一問的基礎(chǔ)上修正我們構(gòu)造的矩陣，以及考慮不同乘車情況下?lián)Q乘時(shí)間的影響。從而建立乘車時(shí)間最短、乘車次數(shù)最少、費(fèi)用最少的多目標(biāo)模型，然后對(duì)模型進(jìn)行求解，得出最優(yōu)的乘車路線。對(duì)于問題三：此問題是在第二問的基礎(chǔ)上，又加入了一個(gè)條件就是考慮所有站點(diǎn)間的步行時(shí)間，從而使從起始站到終點(diǎn)站所需的時(shí)間最短、換乘次數(shù)最少（步行f乘車或乘車f步行，考慮在內(nèi)），從而建立一個(gè)多目標(biāo)模型。模型假設(shè)1） 出行者在所經(jīng)過的站點(diǎn)中，不允許兩次經(jīng)過相同的站點(diǎn)。2） 公交與地鐵換乘距離固定，換乘、步行時(shí)間固定。3） 出行者換乘時(shí)，不受人群擁擠、交通堵塞等現(xiàn)象的影響且均能乘到相應(yīng)線路的公汽或地鐵。4） 數(shù)據(jù)文件B2007data.rar所給數(shù)據(jù)準(zhǔn)確無(wú)誤。5） 假設(shè)公交車和地鐵不存在因?yàn)榇钶d人數(shù)滿載而使市民無(wú)法搭載的情況。6） 考慮到乘車方便，假設(shè)乘客的最大換乘次數(shù)為2。7） 公交在終點(diǎn)處的停留時(shí)間和在站點(diǎn)停留的時(shí)間相同。8） 所有站點(diǎn)之間的步行時(shí)間均已知。9） 公交行駛速度遠(yuǎn)大于步行速度。10） 第三問中步行到車站算一次換乘。符號(hào)說明A:站點(diǎn)的起點(diǎn)B:站點(diǎn)的終點(diǎn)P:起始站A到終點(diǎn)B的費(fèi)用ABa:從起點(diǎn)站到終點(diǎn)站經(jīng)過的站點(diǎn)個(gè)數(shù)（i二1,分別代表公交、地鐵）ib:從起點(diǎn)站到終點(diǎn)站所需的換乘次數(shù)（j=1，分別代表公交、地鐵）jC：換乘點(diǎn)（j=1，分別代表公交、地鐵）id:起點(diǎn)到次起點(diǎn)之間的站點(diǎn)數(shù)（包括起始點(diǎn)，下面三個(gè)相同）1e:次終點(diǎn)到終點(diǎn)之間的站點(diǎn)數(shù)jm:乘客第k次乘坐公交時(shí)所乘坐的站數(shù)（包含起點(diǎn)、終點(diǎn)站，由假設(shè)6k知k可取1，2，3）s:換乘次數(shù)h:次起點(diǎn)到次終點(diǎn)之間的站點(diǎn)數(shù)ijT:公交從起始站到終點(diǎn)站所需的時(shí)間L:包含所有起點(diǎn)的向量AL:包含所有終點(diǎn)的向量Bt:相鄰公汽站平均行駛時(shí)間1t:相鄰地鐵站平均行駛時(shí)間2t:公汽換乘公汽平均耗時(shí)3t:地鐵換乘地鐵平均耗時(shí)4t:地鐵換乘公汽平均耗時(shí)5t:公汽換乘地鐵平均耗時(shí)6t:公汽與公汽、地鐵與地鐵站間的步行耗時(shí)7t:公汽與地鐵站間的步行耗時(shí)8t:任意兩站之間的步行時(shí)間ij問題一的求解5.1模型一的建立從起點(diǎn)站到終點(diǎn)站的所需要的總時(shí)間T由兩部分構(gòu)成:一是公交的行駛時(shí)間；二是乘客換乘時(shí)的耗時(shí)。公交的行駛時(shí)間等于相鄰站點(diǎn)間的平均行駛時(shí)間乘

以公交行駛的站數(shù)，即￡(m-1)*tk1k=1換乘時(shí)間題目已經(jīng)給出，等車時(shí)間為換乘時(shí)間減去步行時(shí)間，即t*s+(t-1)(s+1),因此從起點(diǎn)站到終點(diǎn)站所需的總時(shí)間為：337T=￡(m-1)*t+1*s+(t-1)(s+1)k 1 3 3 7k=1乘客從起點(diǎn)A到終點(diǎn)B的所需要的總費(fèi)用PA為乘坐每一輛公交所需費(fèi)用的加和。乘坐公汽時(shí)的收費(fèi)分為兩種情況：一種是單一票價(jià)的，無(wú)論乘坐多少站均收費(fèi)1元；另一種是分段計(jì)價(jià)，分段計(jì)價(jià)的票價(jià)為：0?20站：1元；21?40站：2元；40站以上：3元。將收費(fèi)方式用數(shù)學(xué)表達(dá)式表示可寫成以下的形式：'1 乘客第k次乘坐的公汽為單一票價(jià)時(shí)P=<mk 2^ 乘客第k次乘坐的公汽為分段計(jì)價(jià)時(shí)其中：表示對(duì)翁上取整,即取不小于m其中：表示對(duì)翁上取整,即取不小于m的最小整數(shù)。乘客從起點(diǎn)A到終點(diǎn)B的所需要的總費(fèi)用碁為乘坐每一輛公交所需費(fèi)用的加和，即:AB=￡npABkk=1選擇最優(yōu)公交線路的目標(biāo)有三個(gè)：一為乘車時(shí)間最少，二為需要費(fèi)用最少三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型：目標(biāo)函數(shù)：minT=(mk=minT=(mk=1minsminpAB=￡nk=10<s<2pk一1)*t+1*s+(t一t)(s+1)k 1 3 3 7s.t.<乘客第k次乘坐的公汽為單一票價(jià)時(shí)mk20乘客第k次乘坐的公汽為分段票價(jià)時(shí)5.2模型一的求解時(shí)間的求解：a)0次換乘，即h豐0,d=0,e=0時(shí)間的求解：a)0次換乘，即h豐0,d=0,e=0時(shí),ijijT二t*(h-1)+(t-1)1ij37b)1次換乘，即h豐0,d豐0,e二0時(shí)，即乘坐2次車ijijIt*(d+h一2)+2*(t一t)+1I1iij 3 7 3t*(e+h一2)+2*(t-1)+11iij 3 7 3c)2次換乘，即h豐0,d豐0,e豐0時(shí)，即乘坐3次車ijijT=t*(d+e+h一3)+3*(t—t)+1*21jiij 3 7 3化簡(jiǎn)得：'t*hI1ijt*(d+h)+1I1iij3t*(e+h)+11iij3t*(d+e+h)+2t1jiij3通過編程計(jì)算出結(jié)果后代入公式計(jì)算的到用時(shí)最短的路徑。公交查詢系統(tǒng)查詢的步驟如下：第一步：先查找出包含起始點(diǎn)在內(nèi)的所有路徑信息M，再?gòu)睦锩娌檎页霭麬含終點(diǎn)B的路徑，然后計(jì)算出各條路徑的時(shí)間，選擇用時(shí)最短的路徑并列出汽車的路線編號(hào)和站點(diǎn)信息；如果沒有找到符合條件的路徑，則轉(zhuǎn)入第二步；第二步：首先列出包括起點(diǎn)在內(nèi)的所有線路信息組成數(shù)據(jù)庫(kù)M，再列出包A括終點(diǎn)在內(nèi)的所有路線組成數(shù)據(jù)庫(kù)M，然后檢索兩種路線里面的交叉點(diǎn)即為換B乘點(diǎn)，若未檢測(cè)到有交叉點(diǎn)則轉(zhuǎn)入第三步；第三步：遍歷包含起點(diǎn)的所有路徑L，遍歷包含終點(diǎn)的所有路徑L，然后AB遍歷所有的路徑，找出能在L和L建立聯(lián)系的點(diǎn)列（h,h），若未檢測(cè)到，則A B ij停止檢索，顯示無(wú)結(jié)果。然后通過MATLAB編程得到起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站線路2時(shí)間（分）費(fèi)用（元）1S3359S1828L436(下)S1784L167(下)10132S1557S0481無(wú)3S0971S0485L013(下)S2184L417(下)1283

4S0008S0073L159（上）S0291L058（下）8325S0148S0485無(wú)6S0087S3676L454（上）S3496L209（下）652表1：換乘1次時(shí)6對(duì)起始站一終點(diǎn)站的最佳路線起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時(shí)間費(fèi)用1S3359S1828L015（下）S2903L027（環(huán)）S1784L167（下）7332S1557S0481L084（下）S1919L189（下）S3186L460（下）10633S0971S0485L013（上）S1609L140（下）S2654L469（上）10634S0008S0073L043（下）S1383L296（環(huán)）S2184L345（上）6735S0148S0485L308（上）S0036L156（上）S2210L417（下）10636S0087S3676L021（下）S0088L231（環(huán)）S0427L097（上）463表2：換乘2次時(shí)6對(duì)起始站一終點(diǎn)站的最佳路線5.3結(jié)果分析：以上我們分別給出了6對(duì)站點(diǎn)之間換乘1次和換乘2次的最佳路線，下面將綜合評(píng)價(jià)這些最佳路線的優(yōu)劣。首先列表比較兩種情況下最佳路線的時(shí)間和費(fèi)用：123456、.1?>萬(wàn)案時(shí)間費(fèi)用時(shí)間費(fèi)用時(shí)間費(fèi)用時(shí)間費(fèi)用時(shí)間費(fèi)用時(shí)間費(fèi)用換乘1次1013無(wú)1283832無(wú)652換乘2次733106310636731063463表3：兩種方案最佳路線的時(shí)間、費(fèi)用對(duì)比表我們發(fā)現(xiàn)除第2與第4對(duì)站點(diǎn)之間只有換乘兩次的路線之外，其余的4對(duì)站點(diǎn)的時(shí)間最優(yōu)解均在換乘2次時(shí)出現(xiàn)，而費(fèi)用的最優(yōu)解一般在換乘1次時(shí)出現(xiàn)。以第4對(duì)站點(diǎn)的最佳路線為例：換乘1次的時(shí)間83分鐘大于換乘2次的時(shí)間67分鐘，但換乘1次的費(fèi)用2元小于換乘2次的費(fèi)用3元，兩者之間誰(shuí)更優(yōu)呢？而第1對(duì)站點(diǎn)，換乘1次的時(shí)間101分鐘大于換乘2次的時(shí)間73分鐘，換乘1次的費(fèi)用3元等于換乘2次的費(fèi)用3元，但就可以說換乘2次的最佳路線比換乘1次的最佳路線更優(yōu)嗎？但換乘1次比換乘2次的換乘次數(shù)少。經(jīng)過以上的分析我們認(rèn)為每對(duì)站點(diǎn)之間的兩組最佳路線各有優(yōu)劣，對(duì)于不同目標(biāo)，它們都有可能是最優(yōu)解。還原到題目的背景信息：某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)，我們建議在系統(tǒng)界面上給出一個(gè)查詢條件，乘客可以自行選擇是根據(jù)時(shí)間、費(fèi)用和換乘其中的哪一個(gè)為首要目標(biāo)進(jìn)行查詢，系統(tǒng)根據(jù)首要目標(biāo)，選擇輸出最佳路線。問題二的求解6.1模型二的建立在問題1的基礎(chǔ)上增加了地鐵線路，乘車時(shí)間和乘車費(fèi)用的表達(dá)式都將改變。在從起點(diǎn)A到終點(diǎn)B的所需要的總時(shí)間T由二部分構(gòu)成：一是公交的行駛AB

時(shí)間；二是乘客換乘時(shí)的耗時(shí)，包括換乘時(shí)的步行時(shí)間和等待時(shí)間。公交的行駛時(shí)間等于相鄰站點(diǎn)間的平均行駛時(shí)間乘以公交行駛的站數(shù)，但公交此時(shí)分為公汽和地鐵，而且兩者相鄰站點(diǎn)間的平均行駛時(shí)間不同：為t和t。每一次乘坐公交12的行駛時(shí)間可表示為以下形式：m*tk1m*tk1m*tk2乘客第k次乘坐的公交為公汽時(shí)次的換乘時(shí)換乘也存在5種情況，5種換乘的時(shí)間分別為：t,t,t,t,2t。每次的換乘時(shí)34566間表示如下：乘客第k次換乘為公汽換乘公汽t4T換k t4T換k 5t62*t6乘客第k次換乘為地鐵換乘公汽乘客第k次換乘為公汽換乘地鐵乘客第k次換乘為公汽換乘公汽需要地鐵總的耗時(shí)T可以用下面的表達(dá)式來(lái)表示:ijT二乙T+ZTAB 換kk=1 k=1乘客從起點(diǎn)i到終點(diǎn)j的所需要的總費(fèi)用P為乘坐每一輛公交所需費(fèi)用的加ij和。乘坐公汽時(shí)的收費(fèi)分為兩種情況:一種是單一票價(jià)的，無(wú)論乘坐多少站均收費(fèi)1元；另一種是分段計(jì)價(jià)，分段計(jì)價(jià)的票價(jià)為：0?20站：1元；21?40站：2元；40站以上:3元。乘坐地鐵時(shí)單一票價(jià):3元（無(wú)論地鐵線路間是否換乘）將兩種收費(fèi)方式用數(shù)學(xué)表達(dá)式表示可寫成以下的形式：‘1 乘客第k次坐的公交為單一票價(jià)的公汽時(shí)[m]乘客第k次坐的公交為分段票價(jià)的公汽時(shí)P=120k3 乘客第k次乘坐的公交為地鐵且為公汽換乘的地鐵時(shí)0 乘客第k次乘坐的公交為地鐵且為地鐵換乘的地鐵時(shí)其中：関表示對(duì)m上取整，即取不小于分的最小整數(shù)。乘客從起點(diǎn)A到終點(diǎn)B的所需要的總費(fèi)用PAB為乘坐每一輛公交所需費(fèi)用的加和，即:np=LpAB kk=1選擇最優(yōu)公交線路的目標(biāo)有三個(gè)：一為乘車時(shí)間最少，二為需要費(fèi)用最少三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型：

S.t.<目標(biāo)函數(shù)為:minTS.t.<目標(biāo)函數(shù)為:minT=》T+藝TAB換kk=1%k=1minP=ZpAB kk=1mins20乘客第k次坐的公交為單一票價(jià)的公汽時(shí)乘客第k次坐的公交為分段票價(jià)的公汽時(shí)乘客第k次乘坐的公交為地鐵且為公汽換乘的地鐵時(shí)乘客第k次乘坐的公交為地鐵且為地鐵換乘的地鐵時(shí)6.2模型二的求解據(jù)分析，只考慮公交時(shí)，從起點(diǎn)A到終點(diǎn)B的途徑有以下4種：直達(dá)、一次換乘、兩次換乘。下面分別分析這幾種途徑所花費(fèi)的時(shí)間和所需的換乘次數(shù)：當(dāng)把換乘次數(shù)最少作為首要條件考慮時(shí)，搜索過程如下：第一步：同樣建立包含起始點(diǎn)和終點(diǎn)的路徑信息矩陣M和M，將兩矩陣A B里面所有的站點(diǎn)建立成二維向量；第二步：在所有的路徑信息中查找包含第一步中二維向量的路徑信息，包括中間站點(diǎn)；第三步：根據(jù)第二步中所找到的信息，計(jì)算出每一種情況所需的時(shí)間T，找出最少的時(shí)間并列出換乘點(diǎn)。時(shí)間的求解：1.d=0,h豐0,e=0時(shí)，時(shí)間為：i ij j直達(dá)：t*(h-1)+(t+1)TOC\o"1-5"\h\zv 2 ij 68換乘：t*(h—1)+2tJ 2 ij 6d豐0,h豐0,e=0時(shí)，時(shí)間為：i ij j起始站到次起點(diǎn)站之間是地鐵時(shí)，即d為地鐵站：j「地鐵不換乘：t*(d—1)+1*(h—1)+1+12 2i 1ij 6 5］地鐵換乘：t*(d—1)+1*(h—1)+1+1+12i 1ij 6 5 4次起點(diǎn)到次終點(diǎn)之間是地鐵時(shí)，即h為地鐵站：ij「地鐵不換乘：t*(h—1)+1*(d—1)+1+1+(t—t)2 2ij 1j 58 3 7丨地鐵換乘：t*(h—1)+1*(d—1)+1+1+(t—t)+12ij 1j 5 4 3 7 8d=0,h豐0,e豐0時(shí)，時(shí)間與情況2相同。ij jd豐0,h豐0,e豐0時(shí)，時(shí)間為：i ij j起始站到次起點(diǎn)站之間是地鐵時(shí)，即d為地鐵站：j〔地鐵不換乘：t*(d—1)+1*(h+e—2)+1+1+12 2i 1 ijj 6 5 3丨地鐵換乘：t*(d—1)+1 *(h +e—1)+1 +1 +1 +12i 1ijj 6 5 3 8次起點(diǎn)到次終點(diǎn)之間是地鐵時(shí)，即h為地鐵站：ij「地鐵不換乘：t*(h—1)+1*(d+e—2)+1+2t2 2ij 1jj 1 6丨地鐵換乘：t*(h—1)+1*(d+e—2)+1+2t+12j 1jj 1 6 8次終點(diǎn)到終點(diǎn)之間是地鐵時(shí)，即e為為地鐵站時(shí)：j「地鐵不換乘：t*(e—1)+1*(d+h—2)+1+1+1+12j 1ij 13 6 4］地鐵換乘：t*(e—1)+1*(d+h—2)+1+1+1+1+12j 1ij 1 3 6 4 8在考慮以換乘次數(shù)最少為首要條件的情況下搜索出最少的換乘次數(shù)并列出換乘點(diǎn)和所經(jīng)過的站點(diǎn)的信息。第一步：搜索搜有公交信息(假設(shè)搜到地鐵信息時(shí)可對(duì)應(yīng)的搜到與該地鐵站相連接的公交站點(diǎn)信息，故可將此類站點(diǎn)看做一個(gè)站點(diǎn)。)，找出所有包含起點(diǎn)的公交信息組合成數(shù)據(jù)庫(kù)Ma，在數(shù)據(jù)庫(kù)□里面搜索終點(diǎn)站，若能搜索到，則輸出結(jié)果，若不能，則轉(zhuǎn)入第二步；第二步:按照第一步的假設(shè)，搜索出包含終點(diǎn)在內(nèi)的公交信息組合成數(shù)據(jù)庫(kù),在數(shù)據(jù)庫(kù)口和Mb里面查找有無(wú)相交點(diǎn)，若無(wú)，則進(jìn)入第三步。

第三步：列出數(shù)據(jù)庫(kù)「71和MB之間的二維站點(diǎn)向量（h,h），搜索所有的路徑信息，若包含這些而二維點(diǎn)，則輸出，若沒有，顯示無(wú)結(jié)果。然后通過MATLAB求解得到：起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站線路2時(shí)間（分）費(fèi)用（元）最優(yōu)目標(biāo)1S3359S1828L436（下）S1784L167（下）1013同時(shí)2S1557S0481無(wú)3S0971S0485L013（下）S2184L417（下）1283同時(shí)4S0008S0073L159（上）S0291L058（下）832同時(shí)5S0148S0485無(wú)6S0087S3676（D36）L021（上）S0630（D29）T2334時(shí)間6S0087S3676L454（上）S3496L209（下）652費(fèi)用表4：換乘1次時(shí)6對(duì)起始站一終點(diǎn)站的最佳路線起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時(shí)間費(fèi)用最優(yōu)目標(biāo)1S3359S1828L015（下）S2903L027（環(huán)）S1784L167（下）733同時(shí)2S1557S0481L084（下）S1919L189（下）S3186L460（下）1063同時(shí)3S0971S0485L094（上）S0567T1S0466L051（上）965時(shí)間L013（下）S2517L296（環(huán)）S2480L417（下）1063費(fèi)用4S0008S0073L200（上）S2534T1S0609L057（上）65.55時(shí)間L198（上）S1691L296（環(huán)）S2184L345（上）673費(fèi)用5S0148S0485L024（下）S1487T1S0466L051（上）87.55時(shí)間L308（上）S0036L156（上）S3332L417（下）1063費(fèi)用6S0087S3676L216（下）S0400L099（上）S3874T241.55時(shí)間L021（下）S0088L231（環(huán)）S0427L097（上）463費(fèi)用表5：換乘2次時(shí)6對(duì)起始站一終點(diǎn)站的最佳路線6.3結(jié)果分析：由問題1的評(píng)價(jià)中得到的結(jié)論：當(dāng)一條路線的時(shí)間、費(fèi)用和換乘次數(shù)均比另一條路線少時(shí)，認(rèn)為這條路線更優(yōu)，可以將第6對(duì)站點(diǎn)間換乘2次時(shí)得到的時(shí)間和費(fèi)用的最佳路線排除。7?問題三的求解7.1模型三的建立問題三中要求在同時(shí)考慮公汽與地鐵線路和步行的情況下，給出任意兩公汽站點(diǎn)之間線路選擇的一般數(shù)學(xué)模型。問題三與問題二的目標(biāo)相同，還是時(shí)間最少與費(fèi)用最少。首先我們來(lái)分析一下步行的意義。根據(jù)假設(shè)，步行速度和公汽的速度差距還是很大的，因此如果乘客是沿著公交線路長(zhǎng)距離行走那么步行耗時(shí)將大大多于乘

車耗時(shí)，那么在什么樣的情況下步行比乘車更好呢？我們總結(jié)了兩種情況：一，公汽存在繞路的情況，即實(shí)際A,B兩站點(diǎn)距離很近，而公汽并不直接連接兩站卻因?yàn)槠渌蚶@行其他站點(diǎn)才到達(dá)，在這種情況下由步行從A站到B站的時(shí)間可能會(huì)比乘坐公交的時(shí)間短。二，雖然步行到其他公汽站點(diǎn)的時(shí)間變長(zhǎng)了，但是經(jīng)過步行我們可能找到新的行車線路，如果步行時(shí)間加上新線路的時(shí)間少于原線路的時(shí)間時(shí)，即：T+T <T步行 新路線 原路線時(shí)，步行就是有意義的。從起點(diǎn)A到終點(diǎn)B的所需要的總時(shí)間T由二部分構(gòu)成：一是公交的行駛時(shí)AB間；二是乘客換乘時(shí)的耗時(shí)。。公交的行駛時(shí)間等于相鄰站點(diǎn)間的平均行駛時(shí)間乘以公交行駛的站數(shù)，但公交此時(shí)分為公汽和地鐵，而且兩者相鄰站點(diǎn)間的平均行駛時(shí)間不同：為t和t。每一次乘坐公交的行駛時(shí)間可表示為以下形式:12換乘存在m*tk換乘存在m*tk1m*tk2乘客第k次乘坐的公交為公汽時(shí)況， 9種換乘的時(shí)間分別為t,t,t,t,2t,t+(t—t),t+(t—t),t+(t—t),t+(t—t)。每一次的換乘時(shí)34566ij37ij47ij47ij37間表示如下：每一次的換乘時(shí)間表示如下：t 乘客第k次換成為公汽換成公汽3t 乘客第k次換成為地鐵換成地鐵4t 乘客第k次換成為地鐵換成公汽5t 乘客第k次換成為公汽換成地鐵6<2*t 乘客第k次換成為公汽換成公汽需要地鐵6t + (t — t ) 乘客第k次換乘為公汽換成步行再換成公汽TOC\o"1-5"\h\zij 3 7t + (t — t ) 乘客第k次換乘為地鐵換成步行再換成地鐵ij 4 7t + (t — t ) 乘客第k次換乘為公汽換成步行再換成地鐵ij 4 7t + (t — t ) 乘客第k次換乘為地鐵換成步行再換成公汽ij 3 7綜上總的耗時(shí)T可以由下面的表達(dá)式來(lái)表示：ijT二藝T+ETAB 行k 換kk=1 k=1乘客從起點(diǎn)A到終點(diǎn)B的所需要的總費(fèi)用P為乘坐每一輛公交所需費(fèi)用的AB

加和。乘坐公汽時(shí)的收費(fèi)分為兩種情況：一種是單一票價(jià)的，無(wú)論乘坐多少站均收費(fèi)1元；另一種是分段計(jì)價(jià)，分段計(jì)價(jià)的票價(jià)為：0?20站：1元；21?40站:元；40站以上：3元。乘坐地鐵時(shí)單一票價(jià)：3元（無(wú)論地鐵線路間是否換乘）將兩種收費(fèi)方式用數(shù)學(xué)表達(dá)式表示可寫成以下的形式：‘1 乘客第k次坐的公交為單一票價(jià)的公汽時(shí)p_[m]乘客第k次坐的公交為分段票價(jià)的公汽時(shí)k乘客第k次乘坐的公交為地鐵且為公汽換乘的地鐵時(shí)0 乘客第k次乘坐的公交為地鐵且為地鐵換乘的地鐵時(shí)其中：Fz]表示對(duì)m上取整，即取不小于m的最小整數(shù)。乘客從起點(diǎn)A到終L20」 20 20點(diǎn)B的所需要的總費(fèi)用鼻為乘坐每一輛公交所需費(fèi)用的加和，即:np_LpAB kk_1選擇最優(yōu)公交線路的目標(biāo)有三個(gè)：一為乘車時(shí)間最少，二為需要費(fèi)用最少三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型：目標(biāo)函數(shù)為：minT_》T+藝TAB換kk_1%?k_1minp_乙pAB kk_1mins'0<s<2m>1kS.t.<S.t.<P_k