社區(qū)公交接駁地鐵路徑優(yōu)化研究

熊 杰,關(guān) 偉,黃愛玲

(北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100044)

社區(qū)公交接駁地鐵路徑優(yōu)化研究

熊 杰,關(guān) 偉*,黃愛玲

(北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100044)

社區(qū)公交在公共交通運(yùn)輸服務(wù)體系中起著重要的微循環(huán)作用,其路徑的優(yōu)化問題對于出行者及運(yùn)營企業(yè)均具有重要意義.本文在給定的路網(wǎng)條件下,首先從路段角度定義了路段的需求潛力指標(biāo),并以最大化路徑需求潛力為目標(biāo)建立目標(biāo)函數(shù),并兼顧路徑旅行時(shí)間及圈點(diǎn)線路約束建立了求解一條圈點(diǎn)線路的數(shù)學(xué)模型.在求解過程中,本文設(shè)計(jì)了一套路段交叉變異算法并利用遺傳算法實(shí)現(xiàn)了模型的啟發(fā)式求解.最后,本文以北京天通苑社區(qū)為例,利用該社區(qū)居民的出行數(shù)據(jù)并分別應(yīng)用遺傳算法及深度優(yōu)先搜索算法對服務(wù)于該社區(qū)的公交路徑進(jìn)行優(yōu)化設(shè)計(jì).實(shí)驗(yàn)結(jié)果表明,遺傳算法在該實(shí)例中已得到最優(yōu)解,證明遺傳算法在求解該問題上具備可行性.

綜合交通運(yùn)輸;路徑優(yōu)化;遺傳算法;社區(qū)公交;接駁;地鐵

1 引 言

近年來城市近郊大型社區(qū)規(guī)模不斷擴(kuò)大,衍生出大量地鐵出行需求,不同交通方式間的換乘問題也日益顯著.而社區(qū)公交由于其自身機(jī)動(dòng)、靈活的特點(diǎn),在公共交通系統(tǒng)中起著不可替代的微循環(huán)作用.因此對社區(qū)公交開行路徑進(jìn)行優(yōu)化,以使其能夠更好地與地鐵相接駁,對于提高公共交通系統(tǒng)的整體運(yùn)營效率以及降低社區(qū)居民出行成本都有著重要意義.

在過去幾十年中,國內(nèi)外許多學(xué)者都對類似于社區(qū)公交服務(wù)性質(zhì)的機(jī)動(dòng)班車的行車路徑進(jìn)行過大量研究.機(jī)動(dòng)班車路徑的優(yōu)化研究依賴于特定的路網(wǎng)結(jié)構(gòu)條件,以往文獻(xiàn)中對于路網(wǎng)結(jié)構(gòu)的設(shè)定主要分為三種情況:基于簡化的路網(wǎng)結(jié)構(gòu)、半現(xiàn)實(shí)路網(wǎng)結(jié)構(gòu),以及現(xiàn)實(shí)路網(wǎng)結(jié)構(gòu).基于簡化的路網(wǎng)結(jié)構(gòu)往往將路網(wǎng)簡化為由若干條水平與豎直的道路構(gòu)成,進(jìn)而設(shè)計(jì)出一條或多條相互平行的班車路徑. Chang 和 Schonfeld[1]提出了在一個(gè)簡單的長方形服務(wù)區(qū)域內(nèi)設(shè)計(jì)班車路徑問題,并指出多對一的需求模式對于服務(wù)質(zhì)量和費(fèi)用都具有一定彈性; Chien 和 Schonfeld[2]提出了一種用于優(yōu)化一條鐵路線路與 多 條 公 交支 線相 互換 乘的 模型;Chien等[3]比較了服務(wù)于一個(gè)矩形區(qū)域的固定和靈活支線服務(wù),并得出最好的方案為在高峰時(shí)期運(yùn)行傳統(tǒng)班車服務(wù),而在非高峰時(shí)期運(yùn)行機(jī)動(dòng)支線服務(wù).類似文獻(xiàn)還可參見 Chang 和 Lee[4],Chang 和 Yu[5].

基于半現(xiàn)實(shí)路網(wǎng)結(jié)構(gòu)的班車路線優(yōu)化問題所給出的服務(wù)區(qū)域大多為不完全網(wǎng)格結(jié)構(gòu),而班車開行路徑必須沿可行駛路段進(jìn)行延伸,因此最終生成的班車路徑往往并非一條直線,也打破了簡化路網(wǎng)結(jié)構(gòu)下線路間相互平行或垂直的格局.Chien[6], Chien 等[7]設(shè)計(jì)了一種網(wǎng)格狀路網(wǎng)條件下服務(wù)于綜合交通換乘中心的公交支線的生成方法,并考慮了地理?xiàng)l件、客流量及預(yù)算限制等約束條件; Ceder[8]提出了班車的潛在需求指標(biāo)這一概念,并以需求指標(biāo)最大化為原則建立模型,之后應(yīng)用分階段、多目標(biāo)的原則設(shè)計(jì)了一套班車管理運(yùn)營系統(tǒng),并從智能化、可視化等方面對系統(tǒng)進(jìn)行了檢驗(yàn).

基于現(xiàn)實(shí)路網(wǎng)結(jié)構(gòu)的班車路線優(yōu)化問題完全以實(shí)際路網(wǎng)為基礎(chǔ),在處理該類問題時(shí),一般先將路網(wǎng)節(jié)點(diǎn)進(jìn)行編號,而后進(jìn)行路段間關(guān)聯(lián)性分析,進(jìn)而將節(jié)點(diǎn)按照一定順序相連接形成可行解,之后一般根據(jù)目標(biāo)函數(shù)的表達(dá)形式并通過遺傳算法搜尋近似最優(yōu)解.Fan 和 Machemehl[9]對可變需求下公交路徑優(yōu)化問題的潛在特性進(jìn)行了較深入分析,并提出了一種多目標(biāo)非線性混合整數(shù)規(guī)劃模型; Shrivastava 和 Mahony[11]對接運(yùn)于某一火車站的若干條公交支線進(jìn)行了路徑及行車時(shí)刻表的優(yōu)化研究,并根據(jù)已有火車運(yùn)行時(shí)刻表對接運(yùn)公交支線的發(fā)車間隔進(jìn)行調(diào)整,最終同時(shí)生成了優(yōu)化的公交路徑及時(shí)刻表.類似文獻(xiàn)還可參見Shrivastava 和Dhingra[11-12].

本文以現(xiàn)實(shí)路網(wǎng)條件為基礎(chǔ),在對給定路網(wǎng)下具體路段進(jìn)行分析時(shí),定義了路段的需求潛力指標(biāo).在建模過程中,以最大化整條路徑的需求潛力為目標(biāo),兼顧路徑走行時(shí)間約束與圈點(diǎn)線路的特征條件約束,構(gòu)建了一種求解圈點(diǎn)線路的數(shù)學(xué)模型.在模型求解中,利用 GA 的算法思想并對選擇、交叉及變異算子進(jìn)行了設(shè)計(jì),實(shí)現(xiàn)了模型的求解.最后,利用通過手機(jī)基站得到的天通苑社區(qū)內(nèi)部早高峰出行 OD 數(shù)據(jù),對該區(qū)域內(nèi)進(jìn)行了圈點(diǎn)線路的優(yōu)化設(shè)計(jì),證明了模型與算法的可行性.

2 模型建立

社區(qū)公交線路設(shè)計(jì)原則應(yīng)為,盡可能用較短的線路走行時(shí)間搭載盡可能多的旅客到達(dá)相鄰的地鐵站點(diǎn).本文以路段為研究對象,并針對路段定義了路段開行公交的潛在需求這一指標(biāo),如式(1)所示:式中 pdij為 路 段 (i,j) 開 行 公 交 的 潛 在 需 求; popij為路段 (i,j) 所集結(jié)的出行需求;為路段(i,j) 所吸引的乘客至該路段的平均距離;lij為路段 (i,j) 至接駁站點(diǎn)距離,本文假設(shè)其為路段中點(diǎn)至接駁站點(diǎn)的直線距離.

由式(1)可知,路段潛在客流需求與相應(yīng)集結(jié)區(qū)內(nèi)出行需求、路段至接駁站點(diǎn)距離成正比(由于路段距地鐵站點(diǎn)越遠(yuǎn),乘坐公交出行需求越大),而與集結(jié)區(qū)內(nèi)乘客步行至該路段的平均距離成反比.

另外,為方便計(jì)算區(qū)域內(nèi)各路段所集結(jié)的客流需求 (popij)及各路段對應(yīng)的乘客平均距離,需首先對研究區(qū)域進(jìn)行交通出行小區(qū)劃分.交通出行小區(qū)為具有一定出行關(guān)聯(lián)度和相似度的節(jié)點(diǎn)集合,且隨時(shí)間、關(guān)聯(lián)度和相似度的變化而變化,它反映了該區(qū)域內(nèi)居民出行的特征.本文對研究區(qū)域進(jìn)行小區(qū)劃分正是為了利用小區(qū)內(nèi)出行具有關(guān)聯(lián)度及相似度的特性,方便地將區(qū)域內(nèi)客流需求匹配至相應(yīng)路段.而區(qū)域的小區(qū)劃分情況勢必會決定客流匹配結(jié)果,進(jìn)而對本文后續(xù)計(jì)算產(chǎn)生重要影響,在實(shí)際工程操作中,應(yīng)按以下原則對區(qū)域進(jìn)行出行小區(qū)劃分:

(1)同質(zhì)性與穩(wěn)定性.同一出行小區(qū)內(nèi)部應(yīng)盡量具有相似的出行特性,如相似的出行強(qiáng)度、交通狀態(tài)等,且各小區(qū)的出行情況不會隨時(shí)間出現(xiàn)頻繁變動(dòng),應(yīng)保持相對穩(wěn)定或呈現(xiàn)周期性變化規(guī)律.

(2)小區(qū)的面積及數(shù)量應(yīng)適當(dāng).如分區(qū)過大,則同一區(qū)域內(nèi)的出行需求很難被集計(jì)加載至某一特定路段,反之則會加大計(jì)算的繁復(fù)程度,失去出行小區(qū)劃分的意義.因此需結(jié)合區(qū)域內(nèi)道路網(wǎng)的具體情況及客流走行距離綜合考慮小區(qū)的劃分情況.

(3)控制區(qū)內(nèi)出行的比例.由于區(qū)內(nèi)出行數(shù)據(jù)無法被分配到路網(wǎng),因此過高的區(qū)內(nèi)出行比例將使分配結(jié)果無法真實(shí)反映區(qū)域出行情況,原則上,區(qū)內(nèi)出行比例應(yīng)控制在 5%-15%.

(4)當(dāng)區(qū)域內(nèi)存在地鐵站、大型公交樞紐站點(diǎn)時(shí),應(yīng)盡量保證這些設(shè)施處于相應(yīng)出行小區(qū)內(nèi)部,避免被不同小區(qū)分割.

基于上述原則,在實(shí)際出行小區(qū)劃分時(shí),首先應(yīng)對區(qū)域內(nèi)居民出行情況進(jìn)行充分調(diào)查,調(diào)查對象為去往相應(yīng)地鐵站的居民,掌握其到達(dá)地鐵站前的出行信息;之后可利用空間聚類分析的方法將具有相似出行特性的個(gè)體劃定在同一出行小區(qū)之內(nèi),進(jìn)而實(shí)現(xiàn)區(qū)域內(nèi)出行小區(qū)的劃分.本文為簡化起見,將研究區(qū)域進(jìn)行網(wǎng)格化處理,即將每一網(wǎng)格視為一個(gè)交通出行小區(qū),如圖1 所示,并提出如下假設(shè):

(1)同一網(wǎng)格內(nèi)的乘客均被匹配至同一路段,不同網(wǎng)格的乘客可分配至不同路段;

(2)各網(wǎng)格內(nèi)乘客至匹配路段的距離為從網(wǎng)格中點(diǎn)至相應(yīng)路段的最短距離.

基于此,本文利用 Logit模型將各網(wǎng)格內(nèi)的乘客分配至區(qū)域內(nèi)唯一路段,分配概率如式(2)所示:

式中 P(k,ij) 為網(wǎng)格 k 被分配至路段(i,j) 的概率;為網(wǎng)格k內(nèi)乘客匹配至路段(i,j) 的距離;A為區(qū)域內(nèi)路段集合.

圖1 研究區(qū)域示例Fig.1 Example of study area

因此,按照式(2)可將各網(wǎng)格分配按照一定概率至區(qū)域內(nèi)唯一路段,進(jìn)而求得各路段所吸引的客流量及所對應(yīng)平均匹配距離:式中 popk為網(wǎng)格 k 內(nèi)客流需求;U 為區(qū)域內(nèi)所有網(wǎng)格集合. 如果網(wǎng)格 k 被分配至路段(i,j),則f(k,ij)= 1,否則 f(k,ij)= 0.

在路徑生成方面,本文借鑒 Ceder[13]中生成一條圈點(diǎn)線路的模型,設(shè) G={N,A} 表示某區(qū)域內(nèi)路段集合,N表示節(jié)點(diǎn)集合,A 表示路段集合.而每條路段 (i,j) 都對應(yīng)一個(gè)平均旅行時(shí)間 tij和需求潛力指標(biāo) pdij.求解模型可產(chǎn)生一條開始并終止于接駁地鐵站點(diǎn) n1的圈點(diǎn)線路.該模型可使乘客的潛在需求量達(dá)到最大,同時(shí)又滿足最大旅行時(shí)間T的限制,因此模型描述如下:

約束條件:

式(6)表示線路最大旅行時(shí)間約束;式(7)-式(8)為在路網(wǎng)中新建一條圈點(diǎn)線路的限制條件,式(7)表示進(jìn)出每個(gè)節(jié)點(diǎn)的路段數(shù)量守恒,式(8)保證了線路閉合;式(9) 中 yij=1 表示路段 (i,j) 為路徑的一部分,反之 yij=0.

3 遺傳算法求解

在應(yīng)用遺傳算法(GA)求解路徑前,首先將實(shí)際路網(wǎng)拓?fù)錇閮H由若干水平及豎直道路組成的簡單路網(wǎng).而由于圈點(diǎn)線路具有起止于同一點(diǎn)且閉合的特性,因此在生成道路時(shí)可將拓?fù)浜蟮穆肪W(wǎng)以某邊界為軸進(jìn)行對稱操作,之后按照一定順序(如從左至右)對線路進(jìn)行生成.例如圖1 中路網(wǎng)可拓?fù)洳⒁杂疫吔鐬檩S進(jìn)行對稱,得圖2所示路網(wǎng).

圖2 路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖示例Fig.2 Example of the topological structure of network

在圖2所示路網(wǎng)條件下,社區(qū)公交的開行路徑只能沿實(shí)線進(jìn)行延伸,本文規(guī)定路徑的生成方向?yàn)橛勺笾劣?因此可將路段中各節(jié)點(diǎn)按照所能提供的走向不同進(jìn)行分類并賦值.具體情況如圖3所示,可將路網(wǎng)中所有節(jié)點(diǎn)按照所能提供走向的不同分為8 種情況,并分別賦予 0-7 中的一個(gè)數(shù)值,且每種情況唯一對應(yīng)一種線路走向集合,線路的基本走向分為向上、向右、向下 3 種,分別賦予數(shù)值 1,2, 3.因此,由路徑的生成表示法得到的最終路徑表達(dá)形式為由數(shù)字 1,2,3 組成的長度不定的矩陣.例如,圖2中路網(wǎng)及路徑矩陣如圖2中所示.

圖3 節(jié)點(diǎn)及走向賦值情況Fig.3 Assignment of nodes and directions

上述方法可對給定拓?fù)渎肪W(wǎng)下任意路徑進(jìn)行表示與生成,因此為遺傳操作打下基礎(chǔ).之后,直接以線路矩陣 route 作為染色體進(jìn)行選擇、交叉與變異操作.在遺傳操作中,適應(yīng)度函數(shù)直接選取為模型目標(biāo)函數(shù),并采用輪盤賭思想,即個(gè)體被選擇概率與其潛在客流需求成正比.假設(shè)種群規(guī)模為NIND,遺傳代溝為 GGAP, 第 i 個(gè)個(gè)體適應(yīng)度為pdij,則每個(gè)個(gè) 體 被選擇 的概率最終選出 NIND′=NIND × GGAP 個(gè)個(gè)體進(jìn)行后續(xù)的交叉與變異操作.

在交叉操作中,確定兩條路徑能在點(diǎn)O處交叉需同時(shí)滿足以下4項(xiàng)條件:

(1) 兩條路徑至少存在一個(gè)公共點(diǎn) O;

(2)兩條路徑在公共點(diǎn) O 的前段與后段均不可完全重合;

(3)當(dāng)兩條路徑在某豎直路段部分或完全重合而O點(diǎn)恰好位于重合路段上時(shí),不可直接在O點(diǎn)進(jìn)行交叉,需同時(shí)對一條子路段的末尾與另一條子路段的起始元素進(jìn)行不斷剔除,直至交叉后路段中不包含[1 3] 或[3 1] 子段為止;

(4)新生成路徑應(yīng)滿足最大旅行時(shí)間約束,否則視兩路徑不可交叉.

交叉操作的具體步驟如下:

(1)設(shè)定交叉率 Pc,最大嘗試交叉次數(shù) Nm;

(2) 對變量 l 取 1 至 NIND′重復(fù)步驟(3)-(5);

(3)隨機(jī)生成一個(gè) 0,1 之間的數(shù) pick,若 pick≤ Pc,進(jìn)行步驟(4),否則返回步驟(2);

(4)隨機(jī)選取兩條路徑,按照一定順序檢驗(yàn)兩路徑公共點(diǎn),判斷各公共點(diǎn)是否滿足上述 4項(xiàng)條件,若滿足,則在該點(diǎn)進(jìn)行交叉,返回步驟(2),否則嘗試交叉次數(shù)加1,進(jìn)行步驟(5);

(5)判斷嘗試交叉次數(shù)是否大于 Nm,若是,該循環(huán)下交叉失敗,返回(2),否則返回(4).

在變異階段,染色體均為代表線路的 route 矩陣,若隨機(jī)改變其中某元素的值,會導(dǎo)致使新生成染色體無法再表示一條可行路徑,因此在變異中采取重新生成新路徑替換被選擇路徑的方法.具體步驟如下:

(1)定義變異率 Pm;

(2)對變量 l取 1 至 NIND′重復(fù)步驟(3);

(3)隨機(jī)生成一個(gè)0,1之間的數(shù)pick′,若pick′≤ Pm,則隨機(jī)生成一條線路,并檢驗(yàn)該線路是否滿足旅行時(shí)間約束條件,若滿足,用該線路替換第 l條線路,否則繼續(xù)隨機(jī)生成線路直到滿足條件為止.

最后將經(jīng)過選擇、交叉及變異后得到的NIND′個(gè)個(gè)體插入到父代中.插入時(shí)仍基于個(gè)體適應(yīng)度大小對其進(jìn)行插入,即新產(chǎn)生路徑的潛在客流需求越大,則被插入到父代的概率越大,父代中路徑的潛在客流需求越小,則被新路徑替換的概率越大.最終仍得到 NIND 個(gè)個(gè)體作為子代,以保證種群規(guī)模不變.

4 實(shí)例分析

選擇北京市天通苑社區(qū)為試驗(yàn)區(qū)域,地鐵5號線垂直穿過該區(qū)域,并設(shè)地鐵天通苑站為接駁站點(diǎn).首先,利用該區(qū)域內(nèi)手機(jī)基站的記錄信息得到一天內(nèi)各基站至接駁站點(diǎn)間的 OD 數(shù)據(jù).該區(qū)域共被六個(gè)基站所覆蓋,其編號分別為 683、684、658、659、660、661,各基站覆蓋范圍可參見圖4.各基站信息如表1 所示(表中客流需求數(shù)據(jù)為 2012.2.3-2012.2.9 日全日 OD 數(shù)據(jù)并取平均,并假設(shè)產(chǎn)生或到達(dá)區(qū)域 683 的客流均為乘坐地鐵客流,基站面積及出行數(shù)據(jù)均由中國移動(dòng)提供).但由基站所劃分的出行小區(qū)形狀不規(guī)則且面積較大,很難細(xì)致地將出行信息加載至各路段,因此采用區(qū)域網(wǎng)格化的方法,將該區(qū)域劃分為 20×20 個(gè)網(wǎng)格,每個(gè)網(wǎng)格實(shí)際代表一個(gè) 150 m ×120 m 的矩形出行小區(qū),如圖4 所示.

圖4 天通苑社區(qū)基站分布及路網(wǎng)示意圖Fig.4 Service areas of base stations and network of Tian TongYuan Community

表1 各基站輻射區(qū)域面積及出行需求Table1 Value of each service area and traffic demand

假設(shè)各基站內(nèi)出行客流密度一致,結(jié)合表1數(shù)據(jù)與式(2),可計(jì)算得到各網(wǎng)格的路段匹配情況,各網(wǎng)格客流需求,以及各網(wǎng)格至路段的匹配距離.之后假定公交車運(yùn)行速度為 14 km/h,得到各路段旅行時(shí)間.再利用式(1)、式(3)、式(4)計(jì)算得到各路段所集結(jié)的客流需求 popij,各路段所對應(yīng)乘客的平均匹配距離,最終計(jì)算出各路段開行公交的需求潛力指標(biāo),相關(guān)數(shù)據(jù)見表2( 假設(shè) pdij=pdji,因此表2僅記錄單向路段各指標(biāo)數(shù)值).

表2 各路段相關(guān)數(shù)據(jù)Table2 Some related data of each route segment

基于天通苑實(shí)際路網(wǎng)圖建立拓?fù)渎肪W(wǎng)圖(現(xiàn)實(shí)路網(wǎng)中不存在的路段用虛線連接),之后以右側(cè)邊界為軸對拓?fù)渎肪W(wǎng)圖進(jìn)行對稱操作,并將潛在客流需求數(shù)據(jù)加載至相應(yīng)路段,如圖5所示.

圖5 對稱后的拓?fù)鋱D及路段潛在客流需求指標(biāo)Fig.5 Symmetrical topological structure and potential passenger demand of each segment

在進(jìn)行遺傳操作中,相關(guān)參數(shù)取值如下:種群規(guī)模 NIND=40,最大遺傳代數(shù) MAXGEN=20,代溝 GGAP=0.9,最大嘗試交叉次數(shù)Nm=20,交叉率Pc=0.7,變異率 Pm=0.4,并設(shè)定最大旅行時(shí)間T=75 min,得到路徑潛在客流需求迭代曲線,如圖6所示.

圖6 潛在客流需求迭代曲線Fig.6 Iterative curve of total potential passenger demand

如圖6 所示,目標(biāo)函數(shù)在遺傳至第 10 代后趨于穩(wěn)定,最大潛在客流需求值為 2 898.7 人.并同時(shí)得到相應(yīng)路徑的 route 矩陣為 route*=[3 3 2 1 2 2 2 1 1 2 3 3 3 2 1 1 2 2 3 2 3 2 1 1],相應(yīng)拓?fù)鋱D中的路徑如圖7所示.

同時(shí)輸出式(5)中變量 yij的取值,如表3 所示.

圖7 拓?fù)鋱D中最優(yōu)路徑Fig.7 Optimal route in topological network

表3 yij取值列表Table3 Values of yij_

表3中,若 yij=1,則表明有向線段 (i,j) 為實(shí)際路網(wǎng)下最優(yōu)路徑的一部分,因此依照表3結(jié)果并結(jié)合圖7,逆著拓?fù)鋱D的生成方法可將拓?fù)鋱D中最優(yōu)路徑還原至現(xiàn)實(shí)路網(wǎng)中,如圖8所示.

圖8 實(shí)際路網(wǎng)中最優(yōu)路徑Fig.8 Optimal route in realistic network

為證明遺傳算法所得解的準(zhǔn)確性,在拓?fù)渎肪W(wǎng)下應(yīng)用深度優(yōu)先搜索算法(DFS)遍歷所有可行路徑,共生成路徑 576 條(按照一定順序),其中 565條滿足最大旅行時(shí)間約束.對所有滿足最大旅行約束時(shí)間的路徑計(jì)算其潛在客流需求指標(biāo),并繪制成折線圖如圖9所示.

圖9 利用 DFS 生成所有可行路徑的潛在客流需求Fig.9 Potential passenger demands of all routes obtained by DFS

由圖9可知,遺傳算法所得最大目標(biāo)函數(shù)值與遍歷搜索所得值相等(均為 2 898.7),且相對應(yīng)的最優(yōu)路徑相同,因此可認(rèn)為遺傳算法已在該實(shí)例中得到最優(yōu)解.而遺傳算法對于更大規(guī)模的路網(wǎng)在計(jì)算效率上也存在較大優(yōu)勢. ________________________________________________________________________

5 研究結(jié)論

本文首先定義了路段潛在客流需求指標(biāo),用以衡量某路段在某一區(qū)域內(nèi)吸引乘客的能力,并基于此指標(biāo)建立了求解一條最優(yōu)圈點(diǎn)線路的數(shù)學(xué)模型.在模型求解中,首先提出了路網(wǎng)的變化方法及路徑的生成方法,進(jìn)而設(shè)計(jì)交叉與變異算子以實(shí)現(xiàn)遺傳算法在路徑優(yōu)化問題上的求解.最后,通過實(shí)例證明了上述模型及算法的可行性,并通過遺傳算法與深度優(yōu)先搜索運(yùn)算結(jié)果的比較,證明了遺傳算法的準(zhǔn)確性.而對于更加復(fù)雜路網(wǎng)情況下,遺傳算法在解決路徑優(yōu)化問題上所能達(dá)到的精度及計(jì)算效率的提高程度則是今后研究的重點(diǎn).

[1] Chang S K,Schonfeld P M.Multiple period optimization of bus transit systems[J].Transportation Research, 1991,25B:453-478.

[2] Chien S,Schonfeld P M.Optimization of grid transit system in heterogeneousurban environment[J]. Journal of Transportation Engineering,1997,123(1): 28-35.

[3] Chien S I,Spasovic L N,Elefsiniotis S S,et al. Evaluation of feeder bus systems with probabilistic time-varying demands and non-additive time costs[J]. Transportation Research Record,2001,1760:47-55.

[4] Chang S K J,Lee C J.Welfare comparison of fixedand flexible-route bus systems[J].Transportation Research Record,1993,1390:16-22.

[5] Chang S K,Yu W J.Comparison of subsidized fixedand flexible-route bus system[J].Transportation Research Record,1996,1557:15-20.

[6] Chien S.Optimization of headway,vehicle size and route choice for minimum cost feeder service[J]. Transportation Planning and Technology,2005,28: 359-380.

[7] Chien S,Yang Z,Hou E.Genetic algorithm approach for transit route planning and design[J].Journal of Transportation Engineering,2001,127:200-207.

[8] Ceder A.Stepwise multi-criteria and multi-strategy design of public transit shuttles[J].Journal of Multi-Criteria Decision Analysis,2009,16:21-38.

[9] Fan W,Machemehl R B.Optimal transit route network design problem with variable transit demand: genetic algorithm approach [J]. Journal of Transportation Engineering,2006,132(1):40-51.

[10] Shrivastava P,Mahony M O.A model for development of optimized feeder routes and coordinated schedules-A genetic algorithms approach[J].Transport Policy, 2006,13:413-425.

[11] Shrivastava P,Dhingra S L.Development of feeder routes for suburban railway stations using a heuristic approach[J].Journal of Transportation Engineering, 2001,127:334-341.

[12] Shrivastava P,Dhingra S L.Development of coordinated schedules using genetic algorithms[J].Journal of Transportation Engineering,2002,128:89-96.

[13] Ceder A.Public transit planning and operation:theory, modelingand practice[M]. Burlington, MA: Elsevier,2007.

Research on Optimal Routing of Community Shuttle Connect Rail Transit Line

XIONG Jie,GUAN Wei,HUANG Ai-ling
(MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University,Beijing 100044,China)

Community shuttle plays an important role in the efficient operation of public transit microcirculation.The optimization of community shuttle routes is also an important work to enable community shuttles to connect rail lines well.This paper defines the potential passenger demand indicators from the view of segments in a given network first,then aims at generating a cyclic route with the objective of maximizing the potential passenger demand,considering the maximum travel time constrain and the characteristics of the cyclic routes.In solving the problem,a set of algorithm for crossover and mutation of route segments is presented,by this a genetic algorithm(GA)can be carried out smoothly to solve the problem as a heuristic algorithm.At last,a case study of Tiantongyuan Community in Beijing is presented.GA and a depth first search(DFS)are both presented to work out the optimal shuttle route serviced for the community based on the passenger count data.The results show that the solution obtained by GA is the optimal route in this case, so GA is feasible in solving this kind of problem.

integrated transportation;route optimization;genetic algorithm;community shuttle; connection;transit line

1009-6744(2014)01-0166-08

U121

A

2013-05-30

2013-08-18錄用日期:2013-08-29

國家自然科學(xué)基金(71131001-2);“973”國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(2012CB725403-5);北京交通大學(xué)優(yōu)秀博士生科技創(chuàng)新基金資助項(xiàng)目(2013YJS045).

熊杰(1988-),男,黑龍江哈爾濱人,博士生.*通訊作者:weig@bjtu.edu.cn