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

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

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