綜合換乘次數(shù)及距離因素的公交網(wǎng)絡(luò)出行路徑選擇模型

綜合換乘次數(shù)及距離因素的公交網(wǎng)絡(luò)出行路徑選擇模型

在現(xiàn)有的公共交通條件下，合理的公共交通線路將有助于選擇出發(fā)時(shí)間、路線和乘客配置。公交出行路徑選擇實(shí)質(zhì)上是研究乘客出行在公交網(wǎng)上的分布規(guī)律,即研究乘客給出起迄點(diǎn)后,如何自動(dòng)生成最優(yōu)的出行路徑方案。城市公交線網(wǎng)是分布在城市道路網(wǎng)上的,它是若干不同公交線路的集合。每條公交線路又是由起迄點(diǎn)及其間的若干個(gè)空間位置不同的站點(diǎn)連接而成,因此在龐大復(fù)雜的公交線網(wǎng)中,乘客從任意起點(diǎn)出發(fā)到目的地之間路徑的選擇不是惟一的。文獻(xiàn)對(duì)乘客的出行心理進(jìn)行了調(diào)查分析,其結(jié)果表明,“換乘次數(shù)”是大部分公交乘客在選擇出行方案時(shí)首先考慮的因素,“出行距離最短”為第二目標(biāo)?，F(xiàn)有的出行路徑選擇模型多為基于上述三種目標(biāo)的單一模型,并且現(xiàn)有最短路徑算法基本上是在道路網(wǎng)上進(jìn)行的,不可能直接應(yīng)用于公交網(wǎng)絡(luò)尋優(yōu),且公交網(wǎng)絡(luò)也不同于一般的道路網(wǎng)絡(luò)。本文在討論公交網(wǎng)絡(luò)特性的基礎(chǔ)上,提出適于公交網(wǎng)絡(luò)的數(shù)據(jù)組織,研究綜合換乘次數(shù)及距離因素的出行路徑選擇模型,并提供算法的實(shí)現(xiàn)。1公共交通網(wǎng)絡(luò)的特點(diǎn)公交網(wǎng)絡(luò)不同于一般的道路交通網(wǎng)絡(luò),它有如下特點(diǎn)。1各控制點(diǎn)的連通城市道路網(wǎng)絡(luò)中的道路交叉點(diǎn)無(wú)差異地連接著與該路口連通的多條路段,在道路網(wǎng)上連通的兩結(jié)點(diǎn),在公交網(wǎng)上不一定連通,如有道路連接而無(wú)公交車(chē)到達(dá)的某兩點(diǎn)。在公交網(wǎng)絡(luò)中,多條公交線路雖然可以相交于空間上的同一個(gè)點(diǎn),但是該點(diǎn)不一定是公交?？空军c(diǎn),或者不是同時(shí)有站點(diǎn),因而不同公交線路在此是不連通的。公交網(wǎng)絡(luò)中結(jié)點(diǎn)的連通狀態(tài)有三種:①同路公交路段的連通;②不同公交線路路段在同一點(diǎn)通過(guò)換乘實(shí)現(xiàn)連通;③不同公交線路路段在不同點(diǎn)的連通,此種情況需要換乘多次車(chē),增加了時(shí)間的消耗。2空間屬性的模擬①空間位置特性。在同一道路上行駛的不同公交線路在行程上是有部分重疊的,但各自的站點(diǎn)不可能完全重疊,因而在公交網(wǎng)絡(luò)分析中,就要求把空間上適當(dāng)距離內(nèi)的異線近鄰?fù)军c(diǎn)按一定原則抽象成網(wǎng)絡(luò)圖上的相關(guān)結(jié)點(diǎn),從而模擬不同公交線路之間的換車(chē)情況。②一對(duì)多屬性。在公交網(wǎng)絡(luò)中,結(jié)點(diǎn)與屬性之間為一對(duì)多的關(guān)系。道路網(wǎng)中空間位置和屬性相同的同名站點(diǎn),在公交網(wǎng)絡(luò)中因位于不同的公交線路而性質(zhì)和權(quán)值可能不一樣。在公交網(wǎng)絡(luò)描述中,可用結(jié)點(diǎn)權(quán)函數(shù)設(shè)置不同的值來(lái)模擬實(shí)際情況。3條道路網(wǎng)中弧段與線路之間關(guān)系在公交網(wǎng)絡(luò)中,弧段與屬性之間為一對(duì)多的關(guān)系。如在城市中,一般情況下,一路公交線路有兩個(gè)行駛方向,因而在圖結(jié)點(diǎn)上,每個(gè)方向上各有一條出邊和入邊,共四條邊。而同一條道路上有若干條公交線路,因而對(duì)于相鄰兩站點(diǎn)之間就有多條弧段的情形,弧段數(shù)由通過(guò)的公交線路數(shù)n決定。一般情況下為num=2n。有著相同空間位置的弧段,可用弧段結(jié)構(gòu)惟一地確定,當(dāng)為每條道路網(wǎng)中的弧段匹配上公交屬性時(shí),弧段與屬性之間為一對(duì)多的關(guān)系。為了表達(dá)這種一對(duì)多的關(guān)系,當(dāng)每條公交線路通過(guò)這段弧段時(shí),都需要重復(fù)記錄弧段的空間信息,這就會(huì)產(chǎn)生大量的冗余數(shù)據(jù)。4方向和停靠站點(diǎn)不完全重疊實(shí)際的公交線路是有方向的,起點(diǎn)和終點(diǎn)決定了公交線路的行駛路徑和方向。不同的公交線路有不同的行駛路線和方向,即使同一路公交車(chē),其上行車(chē)和下行車(chē)行駛的路徑和停靠站點(diǎn)也可能不完全重疊,所以公交網(wǎng)絡(luò)圖應(yīng)是有方向的,這種方向性無(wú)法用邊的有向性來(lái)體現(xiàn)。所以在公交網(wǎng)絡(luò)中,應(yīng)引入有向線路集,而空間位置相同的結(jié)點(diǎn)和弧段的性質(zhì)和權(quán)值在不同線路上是不同的,另外,在同一道路上平行行駛的多條線路的?？空军c(diǎn)和數(shù)目是不同的,這些差異只有在有向線中才能體現(xiàn)。2公交網(wǎng)絡(luò)模型的描述2.1線路之間的賦權(quán)圖在GIS網(wǎng)絡(luò)分析中,地理網(wǎng)絡(luò)總可以映射為一個(gè)有向圖。同理,為了合理地選擇公交出行路徑,根據(jù)上述分析,把公交網(wǎng)絡(luò)映射為G=(V,E,R,Wv,We),其中,G為有向賦權(quán)圖;V表示網(wǎng)絡(luò)上所有結(jié)點(diǎn)即公交站點(diǎn)的集合,一個(gè)公交站點(diǎn)可能是多條線路的上下客站點(diǎn);E表示網(wǎng)絡(luò)上所有邊(連接任意兩個(gè)公交站點(diǎn)之間的弧段)的集合,若A站點(diǎn)與B站點(diǎn)是n條線路的相鄰上下客站點(diǎn),那么A與B之間至多有2n條連接邊;R表示網(wǎng)絡(luò)上連接起迄點(diǎn)間所有結(jié)點(diǎn)的公交線路Ri的集合;Wv是結(jié)點(diǎn)的非負(fù)權(quán)值;We是邊的非負(fù)權(quán)值。最優(yōu)出行路徑就是指乘客從起始點(diǎn)到終迄點(diǎn)所選擇的一系列連通結(jié)點(diǎn)組成的距離最短的路段及最少換乘的公交線路的集合。2.2基于控制函數(shù)的限制用幾何描述的公交網(wǎng)絡(luò)由線性特征和點(diǎn)狀特征組成,是實(shí)際地理特征的圖形化表示。結(jié)點(diǎn)-弧段聯(lián)合結(jié)構(gòu)是GIS表達(dá)道路網(wǎng)絡(luò)的一種常用邏輯數(shù)據(jù)模型,該模型用一組弧段組成,而弧段由構(gòu)成網(wǎng)絡(luò)線的一組有序坐標(biāo)對(duì)組成,其中弧段的兩個(gè)端點(diǎn)稱(chēng)為結(jié)點(diǎn),與線性特征相關(guān)的屬性信息存儲(chǔ)在與弧段相關(guān)聯(lián)的屬性表中。針對(duì)以上公交網(wǎng)絡(luò)特性分析,傳統(tǒng)的結(jié)點(diǎn)-弧段圖結(jié)構(gòu)在描述公交網(wǎng)絡(luò)、表達(dá)公交線路站點(diǎn)及弧段多屬性方面存在一定的問(wèn)題,并且不利于最優(yōu)出行路徑及換乘方案的查詢(xún),所以本文對(duì)該模型作了必要的擴(kuò)展,用結(jié)點(diǎn)-弧段-有向線聯(lián)合結(jié)構(gòu)來(lái)表示復(fù)雜的公交網(wǎng)絡(luò),在該結(jié)構(gòu)中引入了一個(gè)新的數(shù)據(jù)類(lèi)型——有向線來(lái)對(duì)應(yīng)公交網(wǎng)絡(luò)中的公交線路,同一公交線路的上行線和下行線用不同的有向線來(lái)描述。在每條有向線的內(nèi)部:①通過(guò)結(jié)點(diǎn)索引區(qū)分線路的起始站點(diǎn)、中間站點(diǎn)和目的站點(diǎn),從而為結(jié)點(diǎn)賦權(quán);②弧段-屬性的一對(duì)多關(guān)系被轉(zhuǎn)化成有向線-屬性的一對(duì)一關(guān)系,這樣,屬性數(shù)據(jù)的存儲(chǔ)就克服了冗余;③選擇需要?？康恼军c(diǎn)作為有向線的結(jié)點(diǎn),把經(jīng)過(guò)但不?？康恼军c(diǎn)作為其弧段內(nèi)點(diǎn);④實(shí)際上,有向線采用索引方法記錄了結(jié)點(diǎn)和弧段的索引,不需要記錄有向線所經(jīng)由的各個(gè)結(jié)點(diǎn)和弧段的空間位置,也不需要對(duì)底層的幾何要素作任何修改,可以很好地維護(hù)原有圖層的拓?fù)潢P(guān)系。通過(guò)對(duì)結(jié)點(diǎn)-弧段-有向線邏輯結(jié)構(gòu)的描述,可用公交站點(diǎn)表、站點(diǎn)與站點(diǎn)之間的連接弧段表、公交線路表來(lái)拓?fù)浔硎竟贿壿嬀W(wǎng)絡(luò),如圖1所示。3基于最短路徑的轉(zhuǎn)換模式公交出行路徑的選擇就是用戶(hù)從起點(diǎn)出發(fā)到目的地,究竟選擇乘坐哪路公交車(chē),如何換乘才最方便。因此,現(xiàn)在的問(wèn)題是在已經(jīng)建立好的公交網(wǎng)絡(luò)上尋找一條換乘次數(shù)最少、距離最短的路徑?，F(xiàn)有的出行路徑選擇算法一般有兩種模式:①以換乘次數(shù)為代價(jià)換取空間上的距離最短;②以算法搜索時(shí)間為代價(jià)換取換乘次數(shù)最少。在模式①中,起迄點(diǎn)之間的最短路徑已確定,需要在該路徑上匹配公交線路實(shí)現(xiàn)兩點(diǎn)之間的連通,搜索效率較高,但結(jié)果不一定理想。因?yàn)橐粭l路徑路程值最短,但必須轉(zhuǎn)乘多次車(chē)才能到達(dá),而另一條路徑路程較長(zhǎng),卻只要轉(zhuǎn)乘較少次車(chē)就能達(dá)到,那么乘客大部分會(huì)選擇后者,因?yàn)閾Q乘所帶來(lái)的不便和不可預(yù)期的等待時(shí)間往往是人們力圖避免的。所以很多學(xué)者采用模式②,在這種模式中,需要集合的逐步擴(kuò)展、排序、求交等,對(duì)于小城市的公交網(wǎng)絡(luò)可能在搜索時(shí)間和空間上可以忍受,但對(duì)復(fù)雜而龐大的大城市公交網(wǎng)絡(luò)來(lái)說(shuō),對(duì)每條公交線路進(jìn)行操作是不太現(xiàn)實(shí)的,并且該種模式并不考慮距離。也就是說(shuō),只要起迄點(diǎn)之間通過(guò)較少換乘能實(shí)現(xiàn)連通,無(wú)論多長(zhǎng)的距離都是允許的。但在人們的實(shí)際出行中,還是希望能快速地(一般可通過(guò)距離來(lái)體現(xiàn))到達(dá)目的地,并且在城市道路規(guī)劃中,公交網(wǎng)絡(luò)的線路分布一般都是基于最短路徑布線的。所以,本文針對(duì)人們的出行心理、公交線網(wǎng)的實(shí)際布線原則以及在筆者已有的研究基礎(chǔ)上,提出了一種在基于最短路徑上對(duì)集合向外擴(kuò)展、兩個(gè)集合之間逐漸逼近的搜索方法。在算法中,判斷的原則是優(yōu)先考慮換乘次數(shù)少的路徑,在換乘次數(shù)相同的情況下,再考慮出行距離最短。根據(jù)圖2所示的公交網(wǎng)絡(luò),由最短路徑上映射的公交線路和公交站點(diǎn)建立它們之間的關(guān)聯(lián)矩陣C,C={Cij|Ri∈R,i=1,2,…,n;Pj∈P,j=1,2,…,m},Cij為站點(diǎn)權(quán)值,可根據(jù)相應(yīng)的站點(diǎn)性質(zhì)由權(quán)函數(shù)賦值。簡(jiǎn)單情況下,若Ri路公共汽車(chē)在Pj站點(diǎn)處停靠,則Cij=1,否則Cij=0。在行駛方向上,對(duì)C矩陣逐列累加求和得到一新矩陣T,T={Tij|Tij=∑k=1iCkj?j=1?2???n}{Τij|Τij=∑k=1iCkj?j=1?2???n},C和T如圖3所示。算法基本思想為:①根據(jù)T判斷是否有直達(dá)車(chē),R1為直達(dá)車(chē),則為最優(yōu)方案;②如果不滿(mǎn)足①(假設(shè)R1不存在),擴(kuò)展起點(diǎn)線路集合,即搜索通過(guò)該點(diǎn)的任意路徑上所有公交線路的總和Ak{R2,R3,R4,R6}和終點(diǎn)集合Ck{R3,R5,R7},并判斷是否有相交線路集合,{R3}為交集,則R3為非最短路徑上的直達(dá)方案;③如果不滿(mǎn)足②(假設(shè)R3不存在),根據(jù)T判斷在最短路徑上是否有換乘一次的方案(無(wú))。如果A、B之間有直達(dá)車(chē),在B點(diǎn)處對(duì)Ak集合部分(同時(shí)通過(guò)A、B的線路集合{R2,R6})向外擴(kuò)展成Bk{R2,R6,R7,R8},Bk為通過(guò)B點(diǎn)的所有公交線路集合,它逐漸向Ck{R5,R7}逼近,最終到達(dá)Ck,即有交集{R8}。因此,從起點(diǎn)A處乘R2、R6,在B處換乘R8,可到達(dá)終點(diǎn)C。4判斷直達(dá)情況的情況具體的算法步驟如圖4所示。從圖4可看出,在討論N=2時(shí),必須調(diào)用N=1的情況;在討論N=1時(shí),必須判斷直達(dá)的情況,以此類(lèi)推。顯然,這是一個(gè)遞歸問(wèn)題。第N次換車(chē)表示為第N-1次換車(chē)的函數(shù),而第N-1次換車(chē)的情況仍然不知道,還要回推到第N-2次換車(chē),直到知道直達(dá)的情況。5最佳乘車(chē)方案本文的算法已應(yīng)用于Atlas2000中,在該電子地圖中,只要輸入起點(diǎn)和終點(diǎn)的信息,就可獲得兩點(diǎn)之間的最短路徑及出行路徑選擇方案。從提供的乘車(chē)方案看,該軟件能實(shí)現(xiàn)整條換乘線路的展示,具有一定的優(yōu)先推薦能力,在相同換乘條件下,基于最短路徑上換乘次數(shù)最少的選擇應(yīng)是最佳方案,并提供