公交線路的最優(yōu)選擇

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

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

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

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

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

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

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

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

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

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

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