考慮換乘站點時間權(quán)重的公交時刻表優(yōu)化

張 姚，曹振宇

考慮換乘站點時間權(quán)重的公交時刻表優(yōu)化

張 姚，曹振宇

（1. 西南交通大學(xué)，交通運輸與物流學(xué)院，成都 611756；2. 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室，成都 611756）

不同公交線路間的有效換乘是提高城市公共交通系統(tǒng)運行效率、減少乘客換乘等待時間的重要環(huán)節(jié), 其核心是確定合理的公交發(fā)車時刻表。首先, 針對國內(nèi)外公交時刻表優(yōu)化設(shè)計現(xiàn)狀進(jìn)行分析, 提出不同出行目的乘客出行時間效用值不同的概念, 將其與換乘站點重要度結(jié)合考慮, 構(gòu)建出了考慮換乘站點時間權(quán)重的最小化乘客換乘等待時間的優(yōu)化設(shè)計模型, 并利用遺傳算法對算例中的公交時刻表進(jìn)行優(yōu)化。與現(xiàn)有模型比較分析可知所建立的優(yōu)化模型能減少公交網(wǎng)絡(luò)總換乘等待時間，且換乘站點的時間權(quán)重越大, 該站點的換乘等待時間就越小, 與實際情況相符。

交通工程；換乘等待時間；公交時刻表優(yōu)化；遺傳算法；站點時間權(quán)重

0 引 言

公交線路時刻表設(shè)計問題是在一個特定的時間段內(nèi)，決策單條線路的各車次到達(dá)或離開站點的時間，以權(quán)衡服務(wù)水平和運營成本。按照決策變量的類型，可以將時刻表優(yōu)化設(shè)計分為兩種形式：① 優(yōu)化發(fā)車間隔時間或發(fā)車頻率；② 優(yōu)化車輛到站或離站時間。根據(jù)已有調(diào)查顯示，公交出行乘客更加關(guān)注總的出行花費時間，而不是步行時間、換乘時間或車內(nèi)乘車時間。隨著城市規(guī)模的不斷擴(kuò)大，換乘必將成為乘客公交出行的一部分，考慮公交時刻表協(xié)同優(yōu)化設(shè)計，即同時決策各線路車次從始發(fā)站的發(fā)車時間，使得不同線路的車輛協(xié)同到達(dá)換乘站點，減少乘客換乘等待時間[1]。

國內(nèi)外針對公交時刻表設(shè)計與優(yōu)化的研究相對較為成熟，但同時考慮站點效益值的研究還很少。2014年，Jens Parbo等[2]提出考慮乘客出行路徑選擇與換乘總等待時間最少的雙層優(yōu)化模型，并采用啟發(fā)式算法進(jìn)行模型優(yōu)化求解。Rapp[3]以公交線網(wǎng)中換乘延誤最小為目標(biāo)、公交運營成本為約束條件，使用交互式繪圖法確定發(fā)車時間間隔。W. Domschke[4]在發(fā)車頻率已知的情況下提出一種發(fā)車時刻的二次可導(dǎo)數(shù)學(xué)模型，目標(biāo)是在換乘站點同步到達(dá)時間，以便減少乘客的等待時間。Ceder[5]提出公交網(wǎng)絡(luò)同步性最大化的時刻表制訂，使同時到達(dá)網(wǎng)絡(luò)連接點的公交車數(shù)量最大。2012年，Omar J.Ibarra- Rojas[6]提出考慮車輛協(xié)同到達(dá)時間窗的最大化車輛協(xié)同到站次數(shù)的公交時刻表協(xié)同模型，并采用GAMS/ CPLEX進(jìn)行優(yōu)化，求解效率得到改善。劉志剛 等[7]建立車輛調(diào)度和時刻表生成的雙層規(guī)劃模型以解決區(qū)域公交調(diào)度問題，上層模型為以最小化線路所需車輛數(shù)和總空駛時間為目標(biāo)，下層模型以最小化乘客換乘時間為目標(biāo)。陳石等[8, 9]提出建立以協(xié)調(diào)公交時刻表與單線原始時刻表偏差最小，區(qū)域換乘不滿意度最小的多目標(biāo)模型，從到站準(zhǔn)點率、行程時間可靠度、服務(wù)間隔可靠度三方面調(diào)整公交發(fā)車時間間隔。田啟華等[10]設(shè)置駐站時間松弛變量，以車輛在樞紐點相遇次數(shù)最大為目標(biāo)函數(shù)，求解最佳發(fā)車時間和駐站時間。岳大振[11]以各時段發(fā)車間隔為決策變量，建立了基于乘客到站率的目標(biāo)函數(shù)，為公交智能調(diào)度提供了思路。

總的說來，現(xiàn)有研究已開始關(guān)注以最小化乘客換乘等待時間為目標(biāo)函數(shù)的公交網(wǎng)絡(luò)時刻表協(xié)同優(yōu)化設(shè)計問題，但由于設(shè)計優(yōu)化問題涉及多個目標(biāo)，且這些目標(biāo)相互沖突，學(xué)者在建立模型的過程中考慮換乘站點重要程度的研究較少，未考慮乘客出行行為對公交時刻表的約束。在實際運行過程中，不同出行需求的乘客，對換乘時間的要求不同，往往需要重點考慮換乘需求較大的換乘站點。因此，本文提出不同出行目的乘客出行時間效用值不同的概念，將其與換乘站點重要度結(jié)合考慮，構(gòu)建出了考慮換乘站點時間權(quán)重的最小化乘客換乘等待時間的優(yōu)化設(shè)計模型，利用遺傳算法對算例中的公交時刻表進(jìn)行優(yōu)化，并通過與已有研究結(jié)果對比分析驗證該模型對時刻表優(yōu)化的效果。

1 模型的建立

1.1 模型假設(shè)

考慮到公交車輛調(diào)度受多種外部因素的影響，在進(jìn)行時刻表優(yōu)化設(shè)計時需要針對研究問題進(jìn)行相應(yīng)簡化，因此，本文做出如下假設(shè)：

① 公交車按照發(fā)車時間表準(zhǔn)時發(fā)車，途中沒有堵車及意外事故，即假設(shè)車輛在各路段的行駛時間是固定的；

② 為避免不同線路車輛在換乘站點發(fā)生串車現(xiàn)象，乘客換車的車輛與正乘坐車輛先后到達(dá)換乘站點的時間間隔應(yīng)大于某一預(yù)先設(shè)定的值，并且乘客的換乘等待時間要小于預(yù)先設(shè)定的最大換乘等待時間；

③ 不考慮非換乘車站對行程時間的影響；

④ 假設(shè)不同時段發(fā)車間隔不同；

⑤ 運營車輛全部為全程車；

⑥ 乘客不會因為車輛擁擠而不上車，即不考慮車輛容量問題。

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

以線路車次的發(fā)車時間作為決策變量，建立的公交發(fā)車時刻表設(shè)計優(yōu)化模型，主要考慮換乘站點的效用值，以最小化加權(quán)換乘等待時間為目標(biāo)函數(shù)，具體數(shù)學(xué)表達(dá)式如下：

（1）乘客協(xié)調(diào)換乘等待時間

Tab.1 Beta values and share of trips

1.3 約束條件

本文主要考慮的約束條件為公交發(fā)車時間間隔約束、換乘等待時間協(xié)調(diào)性約束。

（1）公交發(fā)車時間間隔約束：考慮不均勻發(fā)車時間間隔的公交時刻表優(yōu)化設(shè)計，為避免發(fā)車時間間隔變化太大，缺少一定規(guī)律，影響乘客出行，發(fā)車時間間隔存在最大發(fā)車間隔與最小發(fā)車間隔：

其中，為一個較大的正數(shù)；

1.4 模型分析

已有相關(guān)文獻(xiàn)提出固定發(fā)車間隔下的公交網(wǎng)絡(luò)時刻表設(shè)計是一個NP-complete問題[12-14]。Ibarra-Rojas et al.[1]進(jìn)一步解釋了不固定發(fā)車時間間隔，以最大化車輛協(xié)同到達(dá)換乘站點的公交網(wǎng)絡(luò)時刻表設(shè)計問題是一個NP-complete問題。在以上研究的基礎(chǔ)上，本文考慮乘客出行目的和以最小化乘客換乘時間的時刻表優(yōu)化問題為一個非線性非凸的混合整數(shù)優(yōu)化問題，約束條件較多。對于這種復(fù)雜的非線性混合整數(shù)優(yōu)化問題，不適合大規(guī)模遍歷求解，傳統(tǒng)優(yōu)化算法較難得到該問題的精確結(jié)果，考慮使用現(xiàn)代尋優(yōu)算法求解模型的局部最優(yōu)解甚至全局最優(yōu)解。目前的尋優(yōu)求解算法主要有：遺傳算法[15]、模擬退火算法[16]、蟻群算法[17]等。其中，遺傳算法由于具有較強的全局搜索能力和魯棒性被廣泛應(yīng)用，本文考慮采用遺傳算法尋求近似最優(yōu)解。

2 模型求解

步驟1 基于參考文獻(xiàn)[14,18]中提到的針對發(fā)車時間可行解的空間特征，計算每個車次所有可行的發(fā)車時間、到站時間和協(xié)同時間窗。

步驟2 根據(jù)約束條件刪除每隊不可能協(xié)同達(dá)到的兩車次對應(yīng)的決策變量和約束，從而減少問題的求解空間。

步驟4 交叉操作。任選兩個有換乘關(guān)系的個體，從兩個個體中隨機(jī)挑選線路進(jìn)行交換，生成兩個新的個體，為保證交叉變異后的個體是可行解，變異基因必須符合約束條件，即：

步驟5 變異操作。任選個體內(nèi)的一條線路，改變線路的發(fā)車時間，為保證變異后的個體是可行解，變異基因必須符合約束條件。

3 算例設(shè)計及分析

圖1 算例的線路結(jié)構(gòu)

采用遺傳算法求解該模型，計算結(jié)果如表2所示。將本文的算例數(shù)據(jù)帶入?yún)⒖嘉墨I(xiàn)[6]和參考文獻(xiàn)[14]的優(yōu)化模型中，求解換乘等待時間。求解結(jié)果表明發(fā)車間隔時間在時間段[9, 11]范圍內(nèi)，最優(yōu)解目標(biāo)函數(shù)值為547 min，低于其他相關(guān)文獻(xiàn)中求解出的最低值562 min，表明利用本文提出的模型和算法可以得到整個公交線網(wǎng)總的換乘時間最小的公交發(fā)車時刻表。從換乘時間相關(guān)性分析，本文考慮了每個換乘站影響系統(tǒng)總換乘等待時間的權(quán)重不同，即每個換乘站點的換乘等待時間的權(quán)重系數(shù)不同，本文中三個換乘站點權(quán)重系數(shù)分別為1.22、1.00、1.05，因此在進(jìn)行時刻表協(xié)調(diào)優(yōu)化時盡量減少換乘站點1的換乘等待時間，最大程度減少系統(tǒng)總的換乘等待時間。

表2 算例結(jié)果對比

Tab.2 Comparison results for models

圖2為發(fā)車間隔在9 min到11 min區(qū)間波動時，歷代解集所對應(yīng)的最小目標(biāo)函數(shù)值。由圖2可知，遺傳算法收斂速度較快，在第45代左右即達(dá)到相對較優(yōu)解，最終目標(biāo)函數(shù)值從1 600 min平穩(wěn)下降至547 min。

調(diào)整發(fā)車時間間隔的最大值和最小值，改變線路的初始發(fā)車時刻，利用遺傳算法求解不同發(fā)車間隔情況下的目標(biāo)函數(shù)值，得到三種不同發(fā)車時間間隔情況下歷代解集所對應(yīng)的最小目標(biāo)函數(shù)值。由圖3可知，算法能較快收斂至統(tǒng)一解。

圖2 算例收斂過程

從乘客總換乘等待時間這一指標(biāo)分析該模型的有效性。從表2可以看出，與文獻(xiàn)[6]相比，本文提出的模型科學(xué)合理的綜合考慮了不同類型乘客出行時間權(quán)重，重點考慮重要換乘站點的換乘等待時間，有針對性地調(diào)整發(fā)車時間間隔，從而進(jìn)一步減少了乘客總的換乘等待時間，以此驗證了模型的有效性。

4 結(jié) 論

本文以總換乘等待時間最小化為目標(biāo)，建立了綜合考慮換乘站點時間重要程度的時刻表優(yōu)化方法，以公交發(fā)車時間間隔、換乘等待時間協(xié)調(diào)性為約束條件，采用遺傳算法對其進(jìn)行優(yōu)化求解，驗證了模型的有效性。

（1）數(shù)值算例分析表明，換乘站點的時間權(quán)重越大，優(yōu)化后該站點的換乘等待時間相對減少，這與實際協(xié)調(diào)重要換乘站點換乘的情況相符合。

（2）為了與已有研究相對比，本文以總換乘時間減少為衡量標(biāo)準(zhǔn)，驗證模型的有效性。后續(xù)研究應(yīng)通過數(shù)據(jù)采集獲取線路實際運行數(shù)據(jù)，結(jié)合人工調(diào)查獲取乘客實際等待時間，檢驗?zāi)Ｐ偷臅r效性；現(xiàn)有模型是以確定的車輛行駛時間為基礎(chǔ)進(jìn)行設(shè)計的，這與實際車輛運行狀況不符，進(jìn)一步研究工作可以考慮車輛行駛時間不確定性下的時刻表優(yōu)化問題。

[1] IBARRA-ROJAS O J, RIOS-SOLIS Y A. Synchronization of bus timetabling[J]. Transportation Research Part B: Methodological, 2012, 46(5): 599-614.

[2] PARBO J, NIELSEN O A, PRATO C G. User perspectives in public transport timetable optimisation[J]. Transportation Research Part C: Emerging Technologies, 2014, 48: 269-284.

[3] RAPP M H. Man-machine interactive transit system planning[J]. Socio-Economic Planning Sciences, 1972, 6(1): 95-123.

[4] DOMSCHKE W. Schedule synchronization for public transit networks[J]. Operations-Research-Spektrum, 1989, 11(1): 17-24.

[5] CEDER A, GOLANY B, Tal O . Creating bus timetables with maximal synchronization[J]. Transportation Research, Part A: Policy and Practice, 2001, 35(10): 913-928.

[6] IBARRA-ROJAS O J, RIOS-SOLIS Y A. Synchronization of bus timetabling[J]. Transportation Research Part B: Methodological, 2012, 46(5): 599-614.

[7] 劉志剛, 申金升. 區(qū)域公交時刻表及車輛調(diào)度雙層規(guī)劃模型[J]. 系統(tǒng)工程理論與實踐, 2007, 27(11): 135-141.

[8] 陳石. 區(qū)域公交時刻表生成的模型與方法研究[D]. 北京: 北京交通大學(xué), 2009.

[9] 劉環(huán)宇. 基于可靠性的公交時刻表優(yōu)化設(shè)計研究[D]. 北京: 北京交通大學(xué), 2010.

[10] 田啟華, 陳艷艷. 區(qū)域公交協(xié)調(diào)調(diào)度優(yōu)化算法研究[J]. 交通運輸系統(tǒng)工程與信息, 2011, 11(4): 160-165.

[11] 岳大振. 基于乘客到站率的公交發(fā)車時刻表優(yōu)化研究[D]. 濟(jì)南: 山東大學(xué), 2014.

[12] ODIJK M A . A constraint generation algorithm for the construction of periodic railway timetables[J]. Transportation Research Part B: Methodological, 1996, 30(6): 0-464.

[13] 李東序. 優(yōu)先發(fā)展城市公共交通是一項重要戰(zhàn)略[J]. 城市交通, 2007, 5(1): 17-19.

[14] 吳影輝, 唐加福. 考慮不均勻發(fā)車間隔的公交網(wǎng)絡(luò)時刻表優(yōu)化模型[J]. 東北大學(xué)學(xué)報: 自然科學(xué)版, 2016, 37(4): 461-466.

[15] 孫紅, 譚笑. 遺傳算法在車輛調(diào)度優(yōu)化問題中的研究[J]. 計算機(jī)工程與應(yīng)用, 2010, 46(24): 246-248.

[16] 劉學(xué)智, 袁榮湘, 劉滌塵. 模擬退火算法在輸電網(wǎng)絡(luò)擴(kuò)展規(guī)劃中的應(yīng)用[J]. 電力系統(tǒng)及其自動化學(xué)報, 2010, 22(2): 11-14.

[17] 郭茜, 聶潤兔, 王超. 蟻群算法在解決空中交通飛行沖突中的應(yīng)用[J]. 交通運輸工程與信息學(xué)報, 2009, 7(2): 116-119.

[18] WU Y, TANG J, YU Y, et al. A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time[J]. Transportation Research Part C: Emerging Technologies, 2015, 52: 15-31.

Optimization Model for Public Transport Timetable with the Time Weight of Transfer Station

ZHANG Yao，CAO Zhen-yu

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National Engineering Laboratory of Integrated Transportation Big Data Application Technology, Chengdu 611756, China)

Effective transfer between different bus lines is an important aspect of improving the operation efficiency of urban public transport systems and reducing the waiting time for passenger transfer. To address these concerns, it is crucial that efficacious schemes should be implemented. In this respect, this study examines the status of domestic and international bus schedule optimization in detail. The concept of utility values for different travel times is then proposed for different travel purposes. This is considered in conjunction with the importance of the transfer station. An optimal design model for minimizing the passenger transfer waiting time by considering the utility value of the transfer station is constructed, and a genetic algorithm is developed in this study. Compared to existing models, the results show that the optimization model established in this report can reduce the total transfer waiting time of the public transport network. Moreover, the larger the time utility value of the transfer station, the smaller the transfer waiting time of the station, which is consistent with the actual situation.

traffic engineering; transfer waiting time; bus schedule optimization; genetic algorithm; time-weight transfer station

U491.51

A

10.3969/j.issn.1672-4747.2020.01.010

1672-4747（2020）01-0077-07

2019-03-10

重慶市交通運輸工程重點實驗室開放基金（2018TE04）

張姚（1995—），女，西南交通大學(xué)碩士研究生，研究方向：智能交通和城市公共交通，E-mail：1530496857@qq.com。

張姚，曹振宇. 考慮換乘站點時間權(quán)重的公交時刻表優(yōu)化[J]. 交通運輸工程與信息學(xué)報，2020，18（1）：77-82, 98.

（責(zé)任編輯：劉娉婷）