求解公交最優(yōu)線路的改進(jìn)最小換乘算法

求解公交最優(yōu)線路的改進(jìn)最小換乘算法

隨著中國城市化進(jìn)程的加快，公共交通網(wǎng)絡(luò)變得越來越復(fù)雜。在如此多的公交線路中,從某城市里的某一個位置坐公交車到另一個位置的路線是多樣化的,如何在如此龐大的出行方案中找到一條最佳路線滿足當(dāng)時的需求,很有現(xiàn)實意義。這方面的研究起始于20世紀(jì)70年代,也提出了多種理論模型,得到了一些應(yīng)用,這些算法都各有優(yōu)缺點,有的算法較復(fù)雜,有的算法思路明晰但計算量大1模型的分析和建立1.1建立線路最佳線路的準(zhǔn)則綜合公交網(wǎng)絡(luò)的特點,同時參考公交乘客出行心理的調(diào)查,考慮方便、舒適程度等影響公交出行的重要因素,可建立公交線路中的最佳線路的準(zhǔn)則是:1)換乘次數(shù)盡可能少;2)出行耗時盡可能少;3)出行費(fèi)用盡可能少。1.2點和終點路線公交網(wǎng)絡(luò)是由公交線路及公交站點組合而成,它包括出行區(qū)域、線路和公交站點。首先將公交網(wǎng)絡(luò)抽象成一個圖,圖的頂點表示站點,圖的邊表示連接相鄰站點的線路。當(dāng)選擇出行起點到出行終點的一條通路時,則依次從起點開始尋找相鄰站點,通過邊將經(jīng)過的站點連接起來,構(gòu)成起點與終點的一條路線。為了方便路線集合、圖以及換乘矩陣、線路矩陣的表示,設(shè)該公交網(wǎng)絡(luò)共有N個站點,S為所有站點集合,Si∈S(i=1,2,…,N),對B題中給出的公汽線路理解為1單行線的劃分SiSj…Sk,Si表示線路的起始站,Sk表示線路的終點站。考慮到公交網(wǎng)絡(luò)的方向性給路徑搜索帶來的不方便,可以把單行線看成兩條經(jīng)過的站點為SiSj…Sk和Sk…SjSi的線路,從而將單行線劃分為上行線和下行線。2k-1sk對于有k個站點的環(huán)行線S1S2…Sk-1Sk,可換為k條路線,依次為S2…Sk-1SkS1,S3…SkS1S2,…,SkS1S2…Sk-1。1.3出行預(yù)算系統(tǒng)要尋找公交網(wǎng)絡(luò)中任意兩點間的最佳路線,其核心是線路選擇的模型與算法,包括起始站—終到站之間的最佳路線,換乘的次數(shù)及換乘地點,出行總時間,出行總費(fèi)用等。1提取線路li的方法,將每條線路根據(jù)2007年數(shù)學(xué)建模競賽B題所給的520條公交線路,3957個公交站點,設(shè)該公交網(wǎng)絡(luò)共有l(wèi)條線路,L為所有公汽線路集合,Li∈L(i=1,2,…,l),運(yùn)用Excel,Word,Access軟件對每條線路Li,依次將線路上的站點號提取出來,按照線路的標(biāo)號i構(gòu)成行下標(biāo),而第i行的元素(第二列起)則是經(jīng)過線路Li的所有站點Sj;同時將不同的線路類型用不同的數(shù)字表示,放在矩陣的第一列,其中1表示上行線,2表示下行線,3表示環(huán)形線,4表示單行往返線。這樣就構(gòu)成含有線路類型、線路號和每一條線路上的所有站點的鏈路矩陣A,A(:,1)表示每條公交線的線路類型;A(i,:)表示第i號公交線經(jīng)過的所有有序站點。2lj各承擔(dān)線路號在得到鏈路矩陣A的基礎(chǔ)上,運(yùn)用Matlab軟件對鏈路矩陣進(jìn)行變換,編程得到換乘矩陣C。其中C(Si,Lj)表示第Si個站點在第Lj公交路線上,這樣矩陣每行的公交線路號按照從小到大排列,且公交線路號L與列坐標(biāo)i相同,缺省線路號用零填充。其矩陣形式為CSi×Lj=(cij)3957×520C(Si,:)=(L1,L2,…,Li,…,L520)其中:若Si是線路Lj的站點,則cij=Lj,否則cij=0。3起始點si到終止點sk的變換Si到終止點Sk的線路通過對換乘矩陣中Si和Sk所對應(yīng)的線路號進(jìn)行逐層遞歸搜索,可得到起始點Si到終止點Sk的經(jīng)過m次換乘的所有路線。由于在實際生活中乘客的心里所能承受的換乘次數(shù)是有限的,據(jù)相關(guān)調(diào)查顯示,乘客一般所能接受的換乘次數(shù)在2次以內(nèi),因此求解問題所提供的需求時,只考慮了換乘次數(shù)在2次之內(nèi)的路線,從而可得到在限制換乘次數(shù)條件下的路線集合X1。4線路之間的分別計算在對每條路線所經(jīng)過的站點數(shù)進(jìn)行計算時,必須根據(jù)線路的類型來分別計算。例如計算線路Li中從起始站點Si與終止站點Sj之間的站點數(shù)s,具體方法為如果li是單向線若i>j,說明Li是在單行線的原路返回線,則站點數(shù)s=|j-i|;若i<j,說明Li是單行線,則s=j-i。如果li是環(huán)形線設(shè)線路Li上的所有站點數(shù)為b,則有s=b-(j-i)。5路線運(yùn)行時間通過對題目的分析,從起始站Si到終點站Sk的總時間是與他所經(jīng)過的總站點數(shù)和換乘次數(shù)相關(guān)的。由于在從起始站Si站到終點站Sk站的路線方案中存在著在某個站點要進(jìn)行換乘的問題,即經(jīng)過的各條線路的站點數(shù)是不相同的,因此可以按換乘點來分段計算每條換乘路線中所經(jīng)過的站點數(shù)。由題目知起點站的等待時間為為3min,相鄰站點間的行駛時間為3min,換乘一次需要的時間為5min,則可求出一條路線上的總出行時間,其計算公式為:總出行時間=等待時間+行駛時間+換乘時間。例如,從起始站Si站到終點站Sk站的其中一條路線為SiSk=(Li(Si,…,Si+n),Lj(Sj,…,Sj+s),Lm(Sm,…,Sk))一共經(jīng)過了2次換乘,這條路線就將分為3段來計算每段的站點數(shù)及運(yùn)行時間。第一段:從起始站Si乘坐第Li路車到達(dá)站點Sj,Sj是第一個換乘點,則經(jīng)過的站點數(shù)為i+n-i=n個,則t1=3×n;第二段:從站點Sj乘坐Lj路車到達(dá)站點Sm,Sm是第二個換乘點,則經(jīng)過的站點數(shù)為j+s-j=s個,t2=3×s;第三段:從站點Sm乘坐Lm路車到達(dá)終點站Sk,則經(jīng)過的站點數(shù)為k-m個,則t3=3×(n-m)。經(jīng)過以上分析,得到從起始站Si站到終點站Sk站的總出行時間模型為???????T=min(3+3×∑i=1m+1ti+5×m)m≤nn=(0,1,2,?),m{Τ=min(3+3×∑i=1m+1ti+5×m)m≤nn=(0,1,2,?),m為最小換乘次數(shù)(1)為了得到更優(yōu)的路線,可以對總的出行時間T進(jìn)行限制(例如T<50min),就能得到從起始站Si站到終點站Sk站的較優(yōu)的路線集合X2。6線路整體費(fèi)用的計算根據(jù)題意可知道,每條線路的費(fèi)用的計算方法必須根據(jù)線路票價制定方式(單一票價1元,分段計價)來確定費(fèi)用,具體的方法為(同樣以線路Li為例):①若Li為單一票價,此時不需要考慮在線路Li上起始站點Si與終止站點Sk之間的站點數(shù)s,無論站點數(shù)的取值為多少,費(fèi)用m=1。②若Li為分段計價,此時需考慮在線路Li上起始站點Si與終止站點Sk之間的站點數(shù)s,當(dāng)0<s≤20時,m=1;20<s≤40時,m=2;s>40時,m=3。先判定每段路線的票價的制定方式來確定出各個段的費(fèi)用(mi),最后累加得到從起始站Si站到終點站Sk站的各條路線的總費(fèi)用(M):M=minL∈X2∑i=1m+1mi(2)Μ=minL∈X2∑i=1m+1mi(2)其中,X2為最小換乘次數(shù)下時間最短的線路集合。在線路集合X2中計算得到每條線路的總費(fèi)用,再根據(jù)實際將每條線路的總費(fèi)用設(shè)定在一定的范圍內(nèi)來減少從起始站Si站到終點站Sk站的線路數(shù),從而得到了最佳路線集合X3。2改進(jìn)的最小換乘算法下面,用改進(jìn)的最小換乘算法對以上模型求解,具體算法如下:步驟一利用鏈路矩陣與換乘矩陣的變換,采用迭代搜索法求解任意兩點間換乘m次的從起始站Si站到終點站Sk站的所有線路(m=0,1,2,…)。要求任意起始站Si站到終點站Sk站之間所經(jīng)過的線路,則在換乘矩陣C中開始搜索。1)若存在C(Si,Lj)=C(Sk,Lj)≠0,則表示起始站Si站和終點站Sk站可以直達(dá),其所乘坐的線路為Lj,即Si到Sk的線路為:Lj:Si→Sk;2)若C(Si,Lj)≠C(Sk,L′j),(Si∈S,L′j∈L),則表示起始站Si站和終點站Sk站之間不能直達(dá),必須經(jīng)過換乘才能到達(dá)。如在換乘矩陣C中有C(Si,Lr)=C(Sj,Lr)≠0,C(Sj,Lm)=C(Sk,Lm)≠0則表明起始站Si站和終點站Sk站經(jīng)過一次換乘就可以到達(dá),換乘的第二條路線為Lm,換乘點為Sj,于是得到起始站Si站到終點站Sk站所經(jīng)過的路線為:L:Si→Sj→Sk。按照以上同樣的方法就可得到經(jīng)過換乘m次后,一定能夠在C中的某一列C(Sn,Lr)=C(Sk,Lr)≠0,找到從起始站Si站到終點站Sk站所經(jīng)過的線路,如果一直搜索完都沒找到,則說明起始站Si站無論經(jīng)過多少次換乘都不能到達(dá)終點站Sk站?？紤]出行時間、費(fèi)用和方便性等綜合因素,對最小換乘算法進(jìn)一步改進(jìn)。步驟二計算步驟一所得到的每條線路的總出行時間,利用時間限制模型(1)對步驟一得到的線路進(jìn)行第一次篩選,經(jīng)篩選后得到的路線集合為X2。步驟三計算步驟二的各條路線出行的總費(fèi)用M,利用費(fèi)用模型(2)進(jìn)行二次篩選,這樣經(jīng)過第二次篩選后得到的路線集合為X3,即X3為從起始站Si站到終點站Sk站最佳路線集合。針對題目給出的6對起始點,用改進(jìn)的換乘算法編程求出換乘次數(shù)在2次以內(nèi)的從起始站Si站到終點站Sk站所經(jīng)過的路線X1,結(jié)果見表1。通過表1給出的這6對起始點的最佳路線,也驗證了新算法的有效性。3虛擬的公汽站間的偏轉(zhuǎn)當(dāng)公汽線路中加進(jìn)了地鐵路線時,可以將地鐵路線視為公汽線路。將地鐵T1與T2線換乘公汽信息整合到站點線路組成的換乘矩陣C中,得出一個新的換乘矩陣C′。由于每個地鐵站通過與多個公汽站的換乘關(guān)系把同一個地鐵所對應(yīng)的公汽站間的聯(lián)系建立了起來,可以理解此時公汽站間的轉(zhuǎn)乘是通過他們所對應(yīng)的地鐵來直接實現(xiàn)的。因為轉(zhuǎn)乘的實現(xiàn)沒有通過某一條具體的公汽或地鐵路線,所以將此類轉(zhuǎn)乘定義為虛轉(zhuǎn)乘,即把中轉(zhuǎn)