公交線網及發車頻率同步優化研究

陳 巍，黃丹芮，吳 奇，

?

公交線網及發車頻率同步優化研究

陳 巍1，黃丹芮2，吳 奇2，

（1. 重慶城市交通研究院有限責任公司，重慶 400020；2. 西南交通大學，交通運輸與物流學院，成都 610031)

出行時間是從乘客角度評價公交系統合理性的重要指標，在規劃層面出行時間主要與公交線網和發車頻率設計有關?，F有的研究主要是依據已有站點及規劃線路數量首先確定公交線網方案，然后設計每條線路的發車頻率，但將線網規劃和發車頻率分開設計導致最終得到的結果不是整體最優。據此，本文構建了公交線網及發車頻率同步優化模型，在此基礎上設計遺傳算法實現模型求解，并引用一實際歷史案例對公交線網及發車頻率同步優化方法進行驗證。結果表明，該方法能夠為規劃區域設計出乘客出行時間最小化的公交線網以及與公交線網相匹配的發車頻率方案。

城市交通；同步優化；遺傳算法；公交線網及發車頻率；公交規劃

0 引 言

乘客出行時間是衡量公交系統合理化的最重要指標[1]，對于站點布局確定的規劃區域乘客出行時間主要包括兩個部分：達到公交站點的等待時間和上車之后乘坐公交到達目的站點的在車行駛時間[1,2]。等待時間主要與線路發車頻率有關，站點間的行駛時間與公交線網布局有關，如何確定最佳的線網布局及相應的發車頻率是公交規劃過程中的重要部分[3-5]?，F有研究主要采用分階段優化方式，對于如何根據出行需求來確定線網布局和發車頻率，尚缺乏統一協調研究[6]。據此本文構建公交線網及發車頻率同步優化模型并設計相應算法求解該問題。

1 問題描述

早期的公交線網規劃沒有考慮發車頻率，主要是將直達最大化的線網布局作為最佳方案。如文獻[7-9]以換乘最小化直達最大化為目標得到公交線網布局方案，但僅僅用可達性作為公交線網規劃依據不能夠完整體現出行者需求；文獻[10]提出以出行時間設計公交線網，但文中雖然考慮了以時間成本為目標函數來優化公交線網，但在出行時間中線路發車頻率是重要影響因子，文中缺乏線網布局和發車頻率的同步優化。本文以出行時間為目標，構建公交線網及發車頻率同步優化模型，并設計求解優于其他算法的遺傳算法實現問題求解。

發車頻率設計研究可以分為兩個階段，早期的發車頻率是依據單條線路客流量，權衡車輛配備費用及乘客等待時間設計發車頻率[11,12]，但依據單線路的發車頻率設計方法忽略了公交線路在運營過程中線路之間相互影響關系。文獻[13]提出公交線網發車頻率設計應該考慮公交線路之間的相互關系，以公交線網為對象設計發車頻率比單線路設計更加符合實際情況。文獻[14,15]指出公交線網發車頻率設計為NP-Hard問題，考慮問題復雜性設計了遺傳算法實現了問題的求解。

現有的公交線網和發車頻率設計分階段進行。但出行時間與公交線網設計及發車頻率都有關，文獻[16]認為發車頻率和線網同步設計更加合理，并基于已經形成的線路集，篩選線路組合成最優化方案。文獻[16]中仍然是發車頻率和線網分別進行優化，但考慮了兩者解的組合進行優化，隨著線網規模擴大，其可行線路數量呈指數增長，對于一定規模的城市，要找出組合優化解非常困難，工作量巨大。

根據上述分析，本文以出行時間最小化為目標構建公交線網與發車頻率同步優化模型，并設計遺傳算法實現問題求解。與現有的分階段設計研究不同，本文采用線網與發車頻率同步生成策略，能夠實現公交線網與發車頻率同步優化，適應于大規模線網設計。

2 模型構建

公交線網及線路發車頻率同步優化問題是公交線網優化和發車頻率優化問題的組合問題，目的是為了獲取規劃區域最佳線網布局及與線網中每條線路相匹配的發車頻率。根據文獻[17-19]相關研究，模型假設如下：

2.1 模型假設

（1）規劃區域站點布局及規劃線路條數已知；

（2）乘客的到達隨機；

（3）乘客平均等待時間為相鄰兩輛車間隔時間的一半；

（4）乘客優先選擇直達線路；

（5）車輛?？繒r間忽略不計；

（6）乘客出行線路選擇是基于最短路原則；

（7）乘客優先選擇有直達線路的出行方案。

2.2 公交線網及發車頻率同步優化模型構建

根據相關概念可知，乘客出行時間最小化是公交線網及發車頻率設計的最主要目標。依據文獻[16]研究，乘客出行時間由到站等待時間和在車運行時間構成，公交線網和發車頻率同步優化比分階段設計公交線網和發車頻率更加合理，本文構建公交線網和發車頻率同步優化模型如下：

2.2.1 目標函數

（1）公交到站等待時間模型構建

等待時間是指乘客到站后等待任意一輛覆蓋乘客出行OD的車輛。當假設乘客服從隨機到達規律時，根據文獻[1]可知，乘客平均等待時間為：

總的等待時間計算如下：

（2）在車運行時間模型構建

在車運行時間是指，乘客從起始公交車站上車后到目的公交站點下車期間公交運行時間，與起始站點和終點站點的公交線路長度及公交本身速度有關。乘客總的公交運行時間為：

（3）公交線網與發車頻率同步優化模型

根據上述分析可知，目標函數為

2.2.2 約束條件p

根據文獻[1]中公交線網模型約束和發車頻率相關研究，結合公交線網與發車頻率同步優化實際問題，構建約束條件如下：

3 公交線網及發車頻率同步優化模型求解算法

公交線網及發車頻率同步優化本身屬于NP-Hard問題，傳統的算法很難得到整個規劃區域的最佳線網布局及相應發車頻率的方案。針對該問題，有關研究表明利用遺傳算法迭代優化的性質能夠很好求解該問題。據此本文設計遺傳算法求解該問題，遺傳算法求解流程如圖1所示。

圖1 遺傳算法求解流程圖

Step1：通過前期工作確定規劃區域站點數量、線路條數、站點間距離等相關數據，作為數據輸入；

Step3：依據乘客優先選擇直達線路及以最短路出行條件的假設原則，分配乘客客流；

Step4：根據公式（4）計算種群內每個公交線網的適應度值；

Step5：對算法是否停止做出判斷,如果停止則輸出優化結果，如果未停止則進行下一步；

Step6：依據選擇規則和設定的交叉變異概率,選擇公交線網進行相關的交叉變異操作，得到與原種群規模一致的新的公交線網和相應發車頻率方案；

Step7：對公交線網子代及其父代按目標函數值大小進行排序，取目標函數值大的作為新的種群，并轉至Step3。

4 算例分析

（1）算例條件說明

該方法將應用至一個如圖2所示的包含8個節點的線網，其中站點間的運行時間以及站點間客流OD如表1所示，該算例與文獻[1]一致。本算例中規劃線路數量為12條，發車間隔最小為4 min，最大發車間隔為20 min，每條線路最少站點數為3，最大站點數為4，整個線網車輛配備總數量不超過120輛。

圖2 算例站點及道路布局圖

表1 公交站點OD矩陣表

（2）將算例的已知條件代入本文構建的公交線網和發車頻率同步優化模型，運用Matlab編寫模型求解，求得最終結果如見表2：

表2 線路及發車頻率優化結果

Tab.2 Optimized results

（3）結果分析

① 通過對模型求解得到了公交線網與發車頻率同步最優化方案，最終得到如表2所示的12條線路的具體線路方案以及每條線路相應的發車間隔，基于最短路以及優先選擇直達出行的原則，滿足整個出行需求總的出行時間為439 172 min。

② 通過公交線網及發車頻率同步優化模型及相應的算法，可以同時得到等待時間最小化的公交線網及相應的發車頻率方案，將以往分階段進行的公交線網優化及發車頻率優化結合進行整體優化，得到整體最優解，防止分階段進行產生局部最優解。

5 結 論

不同于以往對公交線網及發車頻率分階段優化，本文結合乘客出行時間與公交線網和發車頻率的設計關系，構建公交線網及發車頻率同步優化模型，依據模型設計相應求解算法，實現了公交線網及發車頻率同步優化，并結合歷史案例，驗證了本方法的可行性和合理性。

[1] CEDER A. Public transit planning and operation: theory, modeling and practice[M]. Elsevier: Butterworth Heinemann, 2007.

[2] SZETO W Y, WU Y. A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong[J]. European Journal of Operational Research, 2011, 209(2): 141-155.

[3] NIKOLI? M, TEODOROVI? D. A simultaneous transit network design and frequency setting: computing with bees[J]. Expert Systems with Applications, 2014, 41(16): 7200-7209.

[4] LI Y, XU W, HE S. Expected value model for optimizing the multiple bus headways[J]. Applied Mathematics and Computation, 2013, 219(11): 5849-5861.

[5] VERBAS ? ?, MAHMASSANI H S. Exploring trade-offs in frequency allocation in a transit network using bus route patterns: methodology and application to large-scale urban systems[J]. Transportation Research Part B: Methodological, 2015, 81(1): 577-595.

[6] ARBEX R O, CUNHA C B D. Efficient transit network design and frequencies setting multi-objective optimizationby alternating objective genetic algorithm[J]. Transportation Research Part B: Methodological, 2015, 81(1): 355-376.

[7] BAAJ M H, MAHMASSANI H S. An aI‐based approach for transit route system planning and design[J]. Journal of Advanced Transportation, 1991, 25(2): 187-209.

[8] BAAJ M H, MAHMASSANI H S. Hybrid route generation heuristic algorithm for the design of transit networks[J]. Transportation Research Part C: Emerging Technologies, 1995, 3(1): 31-50.

[9] NES V, HAMERSLAG R, IMMERS R. Design of public transport networks[J]. Mathematical Models, 1988.

[10] MARTíNEZ H, MAUTTONE A, URQUHART M E. Frequency optimization in public transportation systems: formulation and metaheuristic approach[J]. European Journal of Operational Research, 2014, 236(1): 27-36.

[11] NEWELL G F. Dispatching policies for a transportation route[J]. Transportation Science, 1971, 5(1): 91-105.

[12] SALZBORN F J M. Optimum bus scheduling[J]. Transportation Science, 1972, 6(2): 137-148.

[13] HAN A F, WILSON N H M. The allocation of buses in heavily utilized networks with overlapping routes[J]. Transportation Research Part B: Methodological, 1982, 16(3): 221-232.

[14] LI Y, XU W, HE S. Expected value model for optimizing the multiple bus headways[J]. Applied Mathematics and Computation, 2013, 219(11): 5849-5861.

[15] WU J, SONG R, WANG Y, et al. Modeling the coordinated operation between bus rapid transit and bus[J]. Mathematical Problems in Engineering, 2015, 2015(1): 1-7.

[16] OUYANG Y, NOURBAKHSH S M, CASSIDY M J. Continuum approximation approach to bus network design under spatially heterogeneous demand[J]. Transportation Research Part B: Methodological, 2014, 68: 333-344.

[17] KIM M E, SCHONFELD P. Integration of conventional and flexible bus services with timed transfers[J]. Transportation Research Part B: Methodological, 2014, 68(1): 76-97.

[18] AMIRIPOUR S M M, CEDER A A, MOHAYMANY A S. Designing large-scale bus network with seasonal variations of demand[J]. Transportation Research Part C: Emerging Technologies, 2014, 48(1): 322-338.

[19] CHEW J S C, LEE L S, SEOW H V. Genetic algorithm for biobjective urban transit routing problem[J]. Journal of Applied Mathematics, 2013, 2013(1): 1-15.

（中文編輯：李愈）（英文審改：孫湛博）

Simultaneous Optimization of Transit Network and Frequency

CHEN Wei1，HUANG Dan-rui2，WU Qi2

（1. Chongqing Urban Transportation Research Institute Co. Ltd, Chongqing 400020, China;2. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China）

Passengertravel time is an important evaluation index for public transportation system. At the planning level, the design of transit network and frequency are mainly based on passenger travel time. Existing research usually conducts the transit network design and timetabling through separate tasks. This scheme, however, usually leads to sub-optimal conditions. This paper constructs a model to simultaneously optimize transit network and timetabling. Genetic algorithm-based solution approach is then proposed. The feasibility of the model is tested using a real world case.

urban traffic; simultaneous optimization; genetic algorithm; transit network and frequency; transit planning

1672-4747（2018）02-0112-05

U491

A

10.3969/j.issn.1672-4747.2018.02.018

2017-03-13

陳?。?989—），男，漢族，四川廣安人，碩士，重慶城市交通研究院有限責任公司交通規劃師，研究方向為公共交通規劃。

黃丹芮（1994—），女，漢族，四川樂山人，西南交通大學交通運輸與物流學院碩士研究生。

陳巍，黃丹芮，吳奇. 公交線網及發車頻率同步優化研究[J]. 交通運輸工程與信息學報, 2018, 16(2): 112-116.