公交線網(wǎng)及發(fā)車頻率同步優(yōu)化研究

陳 巍，黃丹芮，吳 奇，

?

公交線網(wǎng)及發(fā)車頻率同步優(yōu)化研究

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

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

出行時(shí)間是從乘客角度評(píng)價(jià)公交系統(tǒng)合理性的重要指標(biāo)，在規(guī)劃層面出行時(shí)間主要與公交線網(wǎng)和發(fā)車頻率設(shè)計(jì)有關(guān)?，F(xiàn)有的研究主要是依據(jù)已有站點(diǎn)及規(guī)劃線路數(shù)量首先確定公交線網(wǎng)方案，然后設(shè)計(jì)每條線路的發(fā)車頻率，但將線網(wǎng)規(guī)劃和發(fā)車頻率分開設(shè)計(jì)導(dǎo)致最終得到的結(jié)果不是整體最優(yōu)。據(jù)此，本文構(gòu)建了公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型，在此基礎(chǔ)上設(shè)計(jì)遺傳算法實(shí)現(xiàn)模型求解，并引用一實(shí)際歷史案例對(duì)公交線網(wǎng)及發(fā)車頻率同步優(yōu)化方法進(jìn)行驗(yàn)證。結(jié)果表明，該方法能夠?yàn)橐?guī)劃區(qū)域設(shè)計(jì)出乘客出行時(shí)間最小化的公交線網(wǎng)以及與公交線網(wǎng)相匹配的發(fā)車頻率方案。

城市交通；同步優(yōu)化；遺傳算法；公交線網(wǎng)及發(fā)車頻率；公交規(guī)劃

0 引 言

乘客出行時(shí)間是衡量公交系統(tǒng)合理化的最重要指標(biāo)[1]，對(duì)于站點(diǎn)布局確定的規(guī)劃區(qū)域乘客出行時(shí)間主要包括兩個(gè)部分：達(dá)到公交站點(diǎn)的等待時(shí)間和上車之后乘坐公交到達(dá)目的站點(diǎn)的在車行駛時(shí)間[1,2]。等待時(shí)間主要與線路發(fā)車頻率有關(guān)，站點(diǎn)間的行駛時(shí)間與公交線網(wǎng)布局有關(guān)，如何確定最佳的線網(wǎng)布局及相應(yīng)的發(fā)車頻率是公交規(guī)劃過程中的重要部分[3-5]?，F(xiàn)有研究主要采用分階段優(yōu)化方式，對(duì)于如何根據(jù)出行需求來(lái)確定線網(wǎng)布局和發(fā)車頻率，尚缺乏統(tǒng)一協(xié)調(diào)研究[6]。據(jù)此本文構(gòu)建公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型并設(shè)計(jì)相應(yīng)算法求解該問題。

1 問題描述

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

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

現(xiàn)有的公交線網(wǎng)和發(fā)車頻率設(shè)計(jì)分階段進(jìn)行。但出行時(shí)間與公交線網(wǎng)設(shè)計(jì)及發(fā)車頻率都有關(guān)，文獻(xiàn)[16]認(rèn)為發(fā)車頻率和線網(wǎng)同步設(shè)計(jì)更加合理，并基于已經(jīng)形成的線路集，篩選線路組合成最優(yōu)化方案。文獻(xiàn)[16]中仍然是發(fā)車頻率和線網(wǎng)分別進(jìn)行優(yōu)化，但考慮了兩者解的組合進(jìn)行優(yōu)化，隨著線網(wǎng)規(guī)模擴(kuò)大，其可行線路數(shù)量呈指數(shù)增長(zhǎng)，對(duì)于一定規(guī)模的城市，要找出組合優(yōu)化解非常困難，工作量巨大。

根據(jù)上述分析，本文以出行時(shí)間最小化為目標(biāo)構(gòu)建公交線網(wǎng)與發(fā)車頻率同步優(yōu)化模型，并設(shè)計(jì)遺傳算法實(shí)現(xiàn)問題求解。與現(xiàn)有的分階段設(shè)計(jì)研究不同，本文采用線網(wǎng)與發(fā)車頻率同步生成策略，能夠?qū)崿F(xiàn)公交線網(wǎng)與發(fā)車頻率同步優(yōu)化，適應(yīng)于大規(guī)模線網(wǎng)設(shè)計(jì)。

2 模型構(gòu)建

公交線網(wǎng)及線路發(fā)車頻率同步優(yōu)化問題是公交線網(wǎng)優(yōu)化和發(fā)車頻率優(yōu)化問題的組合問題，目的是為了獲取規(guī)劃區(qū)域最佳線網(wǎng)布局及與線網(wǎng)中每條線路相匹配的發(fā)車頻率。根據(jù)文獻(xiàn)[17-19]相關(guān)研究，模型假設(shè)如下：

2.1 模型假設(shè)

（1）規(guī)劃區(qū)域站點(diǎn)布局及規(guī)劃線路條數(shù)已知；

（2）乘客的到達(dá)隨機(jī)；

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

（4）乘客優(yōu)先選擇直達(dá)線路；

（5）車輛?？繒r(shí)間忽略不計(jì)；

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

（7）乘客優(yōu)先選擇有直達(dá)線路的出行方案。

2.2 公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型構(gòu)建

根據(jù)相關(guān)概念可知，乘客出行時(shí)間最小化是公交線網(wǎng)及發(fā)車頻率設(shè)計(jì)的最主要目標(biāo)。依據(jù)文獻(xiàn)[16]研究，乘客出行時(shí)間由到站等待時(shí)間和在車運(yùn)行時(shí)間構(gòu)成，公交線網(wǎng)和發(fā)車頻率同步優(yōu)化比分階段設(shè)計(jì)公交線網(wǎng)和發(fā)車頻率更加合理，本文構(gòu)建公交線網(wǎng)和發(fā)車頻率同步優(yōu)化模型如下：

2.2.1 目標(biāo)函數(shù)

（1）公交到站等待時(shí)間模型構(gòu)建

等待時(shí)間是指乘客到站后等待任意一輛覆蓋乘客出行OD的車輛。當(dāng)假設(shè)乘客服從隨機(jī)到達(dá)規(guī)律時(shí)，根據(jù)文獻(xiàn)[1]可知，乘客平均等待時(shí)間為：

總的等待時(shí)間計(jì)算如下：

（2）在車運(yùn)行時(shí)間模型構(gòu)建

在車運(yùn)行時(shí)間是指，乘客從起始公交車站上車后到目的公交站點(diǎn)下車期間公交運(yùn)行時(shí)間，與起始站點(diǎn)和終點(diǎn)站點(diǎn)的公交線路長(zhǎng)度及公交本身速度有關(guān)。乘客總的公交運(yùn)行時(shí)間為：

（3）公交線網(wǎng)與發(fā)車頻率同步優(yōu)化模型

根據(jù)上述分析可知，目標(biāo)函數(shù)為

2.2.2 約束條件p

根據(jù)文獻(xiàn)[1]中公交線網(wǎng)模型約束和發(fā)車頻率相關(guān)研究，結(jié)合公交線網(wǎng)與發(fā)車頻率同步優(yōu)化實(shí)際問題，構(gòu)建約束條件如下：

3 公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型求解算法

公交線網(wǎng)及發(fā)車頻率同步優(yōu)化本身屬于NP-Hard問題，傳統(tǒng)的算法很難得到整個(gè)規(guī)劃區(qū)域的最佳線網(wǎng)布局及相應(yīng)發(fā)車頻率的方案。針對(duì)該問題，有關(guān)研究表明利用遺傳算法迭代優(yōu)化的性質(zhì)能夠很好求解該問題。據(jù)此本文設(shè)計(jì)遺傳算法求解該問題，遺傳算法求解流程如圖1所示。

圖1 遺傳算法求解流程圖

Step1：通過前期工作確定規(guī)劃區(qū)域站點(diǎn)數(shù)量、線路條數(shù)、站點(diǎn)間距離等相關(guān)數(shù)據(jù)，作為數(shù)據(jù)輸入；

Step3：依據(jù)乘客優(yōu)先選擇直達(dá)線路及以最短路出行條件的假設(shè)原則，分配乘客客流；

Step4：根據(jù)公式（4）計(jì)算種群內(nèi)每個(gè)公交線網(wǎng)的適應(yīng)度值；

Step5：對(duì)算法是否停止做出判斷,如果停止則輸出優(yōu)化結(jié)果，如果未停止則進(jìn)行下一步；

Step6：依據(jù)選擇規(guī)則和設(shè)定的交叉變異概率,選擇公交線網(wǎng)進(jìn)行相關(guān)的交叉變異操作，得到與原種群規(guī)模一致的新的公交線網(wǎng)和相應(yīng)發(fā)車頻率方案；

Step7：對(duì)公交線網(wǎng)子代及其父代按目標(biāo)函數(shù)值大小進(jìn)行排序，取目標(biāo)函數(shù)值大的作為新的種群，并轉(zhuǎn)至Step3。

4 算例分析

（1）算例條件說明

該方法將應(yīng)用至一個(gè)如圖2所示的包含8個(gè)節(jié)點(diǎn)的線網(wǎng)，其中站點(diǎn)間的運(yùn)行時(shí)間以及站點(diǎn)間客流OD如表1所示，該算例與文獻(xiàn)[1]一致。本算例中規(guī)劃線路數(shù)量為12條，發(fā)車間隔最小為4 min，最大發(fā)車間隔為20 min，每條線路最少站點(diǎn)數(shù)為3，最大站點(diǎn)數(shù)為4，整個(gè)線網(wǎng)車輛配備總數(shù)量不超過120輛。

圖2 算例站點(diǎn)及道路布局圖

表1 公交站點(diǎn)OD矩陣表

（2）將算例的已知條件代入本文構(gòu)建的公交線網(wǎng)和發(fā)車頻率同步優(yōu)化模型，運(yùn)用Matlab編寫模型求解，求得最終結(jié)果如見表2：

表2 線路及發(fā)車頻率優(yōu)化結(jié)果

Tab.2 Optimized results

（3）結(jié)果分析

① 通過對(duì)模型求解得到了公交線網(wǎng)與發(fā)車頻率同步最優(yōu)化方案，最終得到如表2所示的12條線路的具體線路方案以及每條線路相應(yīng)的發(fā)車間隔，基于最短路以及優(yōu)先選擇直達(dá)出行的原則，滿足整個(gè)出行需求總的出行時(shí)間為439 172 min。

② 通過公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型及相應(yīng)的算法，可以同時(shí)得到等待時(shí)間最小化的公交線網(wǎng)及相應(yīng)的發(fā)車頻率方案，將以往分階段進(jìn)行的公交線網(wǎng)優(yōu)化及發(fā)車頻率優(yōu)化結(jié)合進(jìn)行整體優(yōu)化，得到整體最優(yōu)解，防止分階段進(jìn)行產(chǎn)生局部最優(yōu)解。

5 結(jié) 論

不同于以往對(duì)公交線網(wǎng)及發(fā)車頻率分階段優(yōu)化，本文結(jié)合乘客出行時(shí)間與公交線網(wǎng)和發(fā)車頻率的設(shè)計(jì)關(guān)系，構(gòu)建公交線網(wǎng)及發(fā)車頻率同步優(yōu)化模型，依據(jù)模型設(shè)計(jì)相應(yīng)求解算法，實(shí)現(xiàn)了公交線網(wǎng)及發(fā)車頻率同步優(yōu)化，并結(jié)合歷史案例，驗(yàn)證了本方法的可行性和合理性。

[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—），男，漢族，四川廣安人，碩士，重慶城市交通研究院有限責(zé)任公司交通規(guī)劃師，研究方向?yàn)楣步煌ㄒ?guī)劃。

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

陳巍，黃丹芮，吳奇. 公交線網(wǎng)及發(fā)車頻率同步優(yōu)化研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2018, 16(2): 112-116.