王志美，張星臣，陳軍華，蓋振州

（北京交通大學交通運輸學院，北京100044）

基于可變客流的接運公交網(wǎng)絡優(yōu)化

王志美*，張星臣，陳軍華，蓋振州

（北京交通大學交通運輸學院，北京100044）

在充分考慮目的地非地鐵站的變動客流和搭乘固定公交的既有客流基礎上，基于多對多客流模式，以管理者、出行者和社會運營費用的總費用最小為目標，構建接運公交線路的優(yōu)化模型.模型考慮了原本私家車出行客流和固定公交出行客流選擇接運公交出行的可能性，應用Logit模型進行流量分配，并采用遺傳算法對問題求解，獲得了最優(yōu)的接運公交網(wǎng)絡，變動客流在接運公交網(wǎng)絡中的第一公交站和換乘的地鐵站.研究結果表明，接運公交線路方案與其占全程廣義出行費用的比例密切相關，故有必要將其從全程視角進行優(yōu)化.

城市交通；接運公交；遺傳算法；可變客流；固定公交

1 引言

隨著城市規(guī)模和人口數(shù)量的不斷擴大和增長，交通擁堵、環(huán)境污染等問題越來越嚴重.如何將私家車客流吸引到公共交通（包括公交和地鐵網(wǎng)絡）已成為關注熱點.而在平峰時段，固定公交的開行間隔較長，造成了較長的等待時間.與地鐵線路銜接的接運公交不僅彌補固定公交的上述缺陷，而且能節(jié)省運營費用.因而，接運公交線路優(yōu)化問題成為當前國內(nèi)外學者的研究熱點，主要基于解析方法[1,2]和網(wǎng)絡優(yōu)化方法[3-5]進行研究.

服務于地鐵線路的接運公交設計問題主要從單一類型交通模式和多種類型交通模式的角度出發(fā).單一類型交通模式的接運公交設計問題最早被Kuah等[3]和Maritins等[4]提出.kuah等以乘客和管理者視角的總費用最小為目標，優(yōu)化與鐵路線路相接運的公交線路結構和運行頻率；Martins等對Kuah等提出的問題進行擴展，建立了兩階段模型且設計了更好的優(yōu)化算法對問題進行優(yōu)化. Wirasinghe等[5]通過構建數(shù)學模型解決影響地鐵與公交系統(tǒng)協(xié)調問題，并分析了地鐵站站距、接運公交服務區(qū)域及列車開行頻度3個關鍵因素對優(yōu)化結果的影響.由于該問題是NP難題，難以在現(xiàn)實網(wǎng)絡上求解.而Kuan等[6,7]通過啟發(fā)式或混合算法的角度對問題進行研究.上述研究均假定客流的發(fā)到站為公交站和鐵路/地鐵站，且客流量為定量，而本文研究認為：

（1）部分目的地非地鐵站的客流為變動客流，其是否選擇接運公交和地鐵出行，取決于公共交通和私家車廣義出行成本的權衡.

（2）乘客可選擇的第一公交站為一個備選集，而非指定站.乘客需在權衡走行距離和等待時間的基礎上選擇合適的第一公交站.

（3）也考慮了原由固定公交線路運送的客流被接運公交吸引的可能性.

多種類型的交通模式包括低成本小運量的接運公交，出租車及私家車等.著眼于多種類型交通模式接運網(wǎng)絡設計問題的研究主要有Shariat等[8]和Ohaymany等[9].他們也是假定客流的出發(fā)和到達站已知，應用蟻群算法求解多種模式并存的接運網(wǎng)絡優(yōu)化問題.本文研究同多種類型交通模式接運公交網(wǎng)絡研究，考慮變動公交，固定公交和私家車共存情形，但認為客流可選擇的換乘地鐵站不是固定的，而是隨接運公交網(wǎng)絡的變化而變化，取決于優(yōu)化的接運公交方案和其將要搭乘的第一公交站方案.

綜上，本研究考慮了多種類型交通模式并存情形，在不確定的公交站與地鐵站間的OD流基礎上，構建數(shù)學模型和應用遺傳算法求解接運公交優(yōu)化方案.

2 問題描述及模型構建

2.1 問題描述

本節(jié)以圖1為例對問題進行闡述.圖1中共有私家車、固定公交、接運公交和地鐵四種交通方式，其中，固定公交和接運公交均與地鐵網(wǎng)絡銜接.已知區(qū)域1為私家車和固定公交客流的產(chǎn)生域，區(qū)域2為私家車客流的吸引域，也為市中心.在這樣的網(wǎng)絡中，私家車客流和固定公交客流均多了一種出行選擇，即搭乘接運公交—地鐵（—接運公交）的方式出行.本文要解決的問題是在哪些線路上建立接運公交，在哪些線路上取消固定公交，使得原本私家車出行和固定公交出行客流出行成本，運營公司的管理成本和社會成本之和最小.

圖1 乘客出行鏈示意圖Fig.1 Passenger routing chain

2.2 模型假設

（1）每條接運線路僅能銜接一個鐵路站，且其經(jīng)過的公交站均停車；

（2）每個公交車站最多能?？恳粭l接運線路；

（3）乘客只選擇與出發(fā)地相鄰的其中一個公交站；

（4）從出發(fā)地到地鐵站區(qū)域，假定客流不存在換乘；

（5）每個接運線路有最遠距離、最大停站次數(shù)、最長時間、最大能力等約束；

（6）設初始存在兩種類型的客流，私家車和固定公交出行客流，他們的備選出行方案均由接運公交替代一部分或全部行程.

2.3 模型構建

（1）集合.

Q,Q′——私家車和固定公交客流需求集合, q∈Q，q′∈Q′；

u(q)——編號為q的OD對客流量；

p(q),d(q)——分別為第q支OD流的接客點(出發(fā)地)和送客點(目的地)；

o(r),d(r)——分別為線路r的始發(fā)站和終到站；N1,

N2——分別為區(qū)域1和區(qū)域2中的公交站集合；

N3——地鐵站集合；

R1,R2——分別為區(qū)域1和區(qū)域2可能的接運公交線路集合；

R3——鐵路線路上服務的列車??；

R4——區(qū)域1的固定公交線路集合；

adj(p(q))——與接客點p(q)相鄰的所有公交站集合；

adj(d(q))——與目的地d(q)相鄰的所有公交站集合.

（2）輸入?yún)?shù)和變量.

W——網(wǎng)絡中接運公交的最大數(shù)量；

fmax——每個接運公交的最大開行頻度；

smax——每個接運公交的最多停站次數(shù)；

kcap——每個接運公交的能力；

Nr——第r個線路能分配的最大車輛數(shù)；

Lmax——每個接運公交的最長里程；

lr——接運公交r的運行距離；

tir——線路r上i節(jié)點到線路終到站的時間；

tr——線路r總消耗時間.

（3）決策變量.

Yr——如果接運線路r（屬于區(qū)域1,2,3）在i站?？浚瑒t取值為1，否則取值為0；

Xq——如果第q支客流被第r條接運線路運送，則取值為1，否則取值為0；

δr——如果第r條接運線路開行，則取值為1，否則取值為0；

πP(q),i——如果與第q支客流出發(fā)點p(q)相鄰的公交站i為第一出發(fā)站，則取值為1，否則為0；

fr——接運公交r的開行頻度.

（4）接運公交客流需求.

①私家車客流選擇接運公交的概率.

原有私家車出行的乘客選擇接運公交出行的概率表示為

式中ubqus是在“出發(fā)地→公交站→地鐵站→公交站→目的地”這一出行鏈上的廣義費用，表示為

②固定公交客流選擇接運公交的概率.

原固定公交出行的乘客選擇接運公交方式出行概率表示為

（5）目標函數(shù).

目標函數(shù)中的費用包括3個方面：接運公交和固定公交的管理費用、用戶費用和社會費用，γ1,γ2,γ3為上述3種費用的權重.

①管理費用.

接運公交和固定公交的管理費用可被描述為正比于車輛運行距離，可表示為

②用戶費用.

乘客選擇私家車、接運公交和固定公交出行所耗費的總費用表示為

③社會成本.

私家車出行和乘坐接運公交出行所消耗的社會資源不同，社會成本以乘客消耗的總資源最小為目標，表示為

（6）約束條件.

①OD客流的約束.

式（13）保證了任意的q在區(qū)域1內(nèi)有連續(xù)的出行鏈.若某個公交站屬于與出發(fā)地相鄰的公交站集合，且被選為第一公交站，則該OD必須從該公交站搭乘一條公交線路到達地鐵站；式（14）保證了與“地鐵站至終到站”這一行程鏈相關的公交線路的接續(xù).

②客流與接運公交線路的關系約束.

式（15）保證了客流能夠選擇公共交通出行的前提是運行對應的接運公交線路.

③接運公交線路的其他約束條件.

式（16）～式（21）分別為線路最大開行頻度、最大車輛數(shù)約束、最長運送時間、運送距離、最大運送能力和最多停站次數(shù)約束.

3 求解方法

該問題是路徑生成問題的擴展，路徑優(yōu)化問題已經(jīng)證實可被元啟發(fā)式方法求解，取得較好效果.本文以應用較為廣泛的遺傳算法為求解方法，用以確定接運線路的起點、終點及沿途?？空?，線路的開行頻度，客流分配方案等.具體求解過程如圖2所示.

圖2 算法流程圖Fig.2 The program flow chart of GA

本問題的一個解由若干組接運線路組成，每組線路由線路開行頻度及線路的?？空緲嫵?，如圖3所示.為簡化問題，這里用每條線路分配的車輛數(shù)替代開行頻度.開行頻度和車輛數(shù)的關系可表示為

圖3 染色體解碼方式圖Fig.3 Chromosome representation of problem

式中Vn表示分配到線路n上的車輛數(shù)；Tn表示線路n一個周轉時長.

該問題初始解的生成，適應值的表示方式及交叉變異操作可參照文獻[6].本文在配流處理上與文獻[6]有所不同，采取的策略為：

（1）將與居民住地相鄰公交站點按照走行距離從近到遠的順序排列，作為乘客選擇其出發(fā)站及走行時間的依據(jù).

（2）利用Logit模型，與備選的私家車出行及固定公交線路出行方案進行合理分配.在配流過程中，假定對應線路上的能力充足；分配結束后，將能力約束函數(shù)以懲罰項的形式計算入適應值函數(shù)中.

4 案例分析

假設平峰時段客流由家出發(fā)，去往目的地，目的地在市中心.市中心區(qū)域接運地鐵線路的固定公交線路開行頻度與高峰時段相同，即認為每個地鐵站運送到目的地的出行時間為常數(shù).

以圖4為例，已知站1～7為接客區(qū)域的公交站點，站8～10為鐵路站點，站11～13為到達區(qū)域（市中心）的公交站點，連線上的數(shù)字為站間距.各地鐵站至到達域公交站點的運送時間和費用如表1所示；原乘坐私家車出行的客流數(shù)據(jù)、行駛時間、費用等如表2所示.同時，假定接客區(qū)當前僅有一條固定公交線路5→4→3→8，在該線路上從站5、4、3分別去往站8的客流量為25，30，33人.固定公交的平均運行速度設為20 km/h.

圖4 案例示意圖Fig.4 A network for case study

表1 鐵路站至各到達站的運送時間和費用Table 1Travel cost and time from stations to destination stops

表2 原自駕出行的客流量、行駛時間和費用參數(shù)Table 2The volume of passenger,travel time and cost for each private car OD demand

4.1 相關參數(shù)定義及求解效果分析

在遺傳算法里，染色體種群的規(guī)模設置為50，交叉概率、變異概率分別取0.6、0.2，染色體集合的最大規(guī)模設為100.當算法進化迭代次數(shù)達到500次，或染色體集合在連續(xù)迭代的100次計算中維持不變時，停止計算并認為算法達到收斂.接運公交線路相關的費用參數(shù)參照相關文獻，取值如表3所示.

表3 費用參數(shù)取值Table 3The value of parameters

以上述數(shù)據(jù)作為模型的輸入?yún)?shù)，經(jīng)遺傳算法求解，得到優(yōu)化方案.遺傳算法求解的效果如圖5所示.

圖5 遺傳算法進化曲線Fig.5 Evolution curve of genetic algorithm

由圖5可以看出，在總步數(shù)不超過500次，而近似最優(yōu)解的值超過100次未改變，算法終止.個體目標值隨著遺傳代數(shù)的增加逐步下降并趨于穩(wěn)定，表明本文給出的遺傳算法具有較好的收斂性，總可以得到一個近似最優(yōu)解.

4.2 方案分析

經(jīng)過優(yōu)化計算，得到的最優(yōu)接運公交線路及由每條接運公交線路運送的客流信息如表4和表5所示.

（1）接運公交最優(yōu)的開行路線.

表4 最優(yōu)的開行路線Table 4The optimal feeder lines

（2）乘坐接運公交的客流信息.

表5 乘客的出行方案Table 5Routing strategy for each OD demand

由表4可知，當前網(wǎng)絡上共開行了3條線路，保證了路網(wǎng)中的客流均能從出發(fā)站運送到地鐵站.由表5可知，出發(fā)地序號為6的客流從公交站7始發(fā)，出發(fā)地序號為7的客流從公交站6始發(fā).客流運送方案由出發(fā)地至其相鄰公交站的距離以及接運線路方案共同確定的.

（3）選擇私家車出行的客流比例.

在客流的分配方案已知的基礎上，進一步統(tǒng)計每支客流中仍然選擇私家車出行的比例，如表6所示.

表6 現(xiàn)有方案下私家車的出行比Table 6A proportional value for OD demands traveling by private car based on current feed bus strategy

由表6可知，有7支OD流不到20%的流量選擇私家車出行；有4支OD流的私家車出行比例在20%～30%之間；有2支OD流超出30%的乘客選擇私家車出行；序號為9的OD流仍選擇私家車出行比例較高.

（4）仍然選擇固定公交出行的客流比例.

依據(jù)當前的接運公交網(wǎng)絡可知，原乘坐固定公交的OD流3-8，4-8，5-8均多了一種出行選擇——乘坐接運公交.其在接運公交上所選擇的線路如表7所示.依據(jù)兩種出行方式的廣義出行費用，確定了分配到接運公交上的流量比例.配流結果表明，接運公交的開行，也會對固定公交流量起到分流作用.因而，有必要將固定公交線路方案考慮在內(nèi)，制定經(jīng)濟可行的接運線路.

表7 原固定公交客流轉移路線及流量信息Table 7The alternative route and proportional value for demands original on fixed bus

4.3 靈敏度分析

由于本文從乘客全程的出行廣義費用視角出發(fā)，研究接運公交方案.通過變化“地鐵→到達站”這段行程的廣義出行費用（從減少20%到增加20%），發(fā)掘其對接運公交方案的開行輛數(shù)及吸引的客流量產(chǎn)生的影響，結果如圖6所示.

圖6 后半程費用變化與接運公交開行方案的關系Fig.6 The relationship between the last part of journey and feeder bus strategy

由圖6可知，接運公交的開行輛數(shù)和吸引的客流量比例隨后半程費用的增加而減少.由于每輛接運公交容量一定，故其開行輛數(shù)與后半程廣義費用非線性化增長.由此揭示接運公交的吸引客流量與其占全程出行費用比例相關，應將其作為全程廣義出行費用的一部分進行優(yōu)化方案.

5 研究結論

本文在多對多客流模式前提下，以目的地非地鐵站的私家車客流和搭乘固定公交的既有客流為模型的研究對象，構建了接運公交網(wǎng)絡線路優(yōu)化模型，使得管理者、出行者及社會角度的總費用最小，優(yōu)化出了變動客流的接運公交網(wǎng)絡第一公交站和換乘的地鐵站.模型考慮了原本私家車和固定公交客流選擇接運公交出行的可能性，采用Logit模型進行流量分配，使得接運公交方案與乘客的出行選擇交互作用.采用了遺傳算法對問題求解，方案結果表明，接運公交的開行可吸引多數(shù)的私家車客流到公交系統(tǒng)，且接運公交出行所消耗的廣義費用占全程的比例影響著乘客的出行抉擇；固定公交線路客流分流到接運公交的比例與方案相關.

[1]Xiong J,Guan W,Song L Y,et al.Optimal routing design of a community shuttle formetro stations[J]. Journal of Transportation Engineering,2013,139(12): 1211-1223.

[2]Chien S I,Spasovic L N,Elefsiniotis S S,et al. Evaluation of feeder bus systems with probabilistic timevarying demands and nonadditive time costs[J].Transit: Bus Transit and Maintenance,Paratransit,and New Technology,2001,(1760):47-55.

[3]Kuah G K,Perl J.Optimization of feeder bus routes andbus-stopspacing[J].JournalofTransportation Engineering-Asce,1988,114(3):341-354.

[4]Martins C L,Pato M V.Search strategies for the feeder bus network design problem[J].European journal of operational research,1998,106(2-3):425-440.

[5]Wirasinghe S C,Hurdle V F,Newell G F.Optimal parametersforacoordinated rail and bus transit system[J].Transportation Science,1977,11(4):359-374.

[6]Kuan S N,Ong H L,Ng K M.Solving the feeder bus network design problem by genetic algorithms and ant colonyoptimization[J].AdvancesinEngineering Software,2006,37(6):351-359.

[7]Kuan S N,Ong H L,Ng K M.Applying metaheuristics to feeder bus network design problem[J].Asia-Pacific Journal of Operational Research,2004,21(4):543-560. [8]Shariat Mohaymany A,Gholami A.Multimodal feeder networkdesignproblem:antcolonyoptimization approach[J].JournalofTransportationEngineering, 2010,136(4):323-331.

[9]TahooriniaM M,Mohaymany A S,GholamiA. Designing a multimodal feeder network by covering stops with different modes[J].Canadian Journal of Civil Engineering,2014,41(1):87-96(10).

Feeder Bus Network Design Based on Variable Demand

WANG Zhi-mei,ZHANG Xing-chen,CHEN Jun-hua，GAI Zhen-zhou
(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

This study takes account of the private car demands whose destinations are not subway station and the demands taking the fixed bus lines originally,develops a feeder bus network optimal model with the minimum cost of passengers,operators and social for many-to-many travel demand.Logit model is applied to redirect private car demand between private car and feeder bus line,fixed bus line demand between feeder bus and fixed bus line.A genetic algorithm is developed to solve the problem.The results show that the model constructed in this paper and the applied genetic algorithm can obtain optimal feeder bus lines,the first bus station and transfer subway station for originally private car demand.The solution result shows that the feeder bus line strategies have a close relationship with the percentage of the whole traveling chain costs.

urban traffic;feeder bus;genetic algorithm;variable demand;fixed bus

1009-6744（2015）05-0128-08

U268.6

A

2015-05-12

2015-08-19錄用日期：2015-08-27

國家自然基金資助項目（U1361114）；國家自然基金青年基金項目（71401006）；北京交通大學基本科研業(yè)務項目（2015JBM059）.

王志美（1984-），河南民權人，博士后. ＊

wzm_sxhd@163.com