竇雪萍　 過秀成　 龔小林

(東南大學(xué)交通學(xué)院, 南京 210096)

?

面向協(xié)同調(diào)度的公交時刻表魯棒優(yōu)化模型

竇雪萍 過秀成 龔小林

(東南大學(xué)交通學(xué)院, 南京 210096)

為實現(xiàn)公共交通網(wǎng)絡(luò)協(xié)同調(diào)度,以網(wǎng)絡(luò)內(nèi)總換乘負(fù)效用最小為目標(biāo),構(gòu)建了考慮公交車輛運行隨機性的時刻表魯棒優(yōu)化模型．線路間換乘銜接關(guān)系、公交車輛首站計劃發(fā)車時刻、站點間運行時間和站點處?？繒r間為模型主要輸入?yún)?shù),用于求解各線路首站計劃發(fā)車時刻最優(yōu)偏移量．由于所建優(yōu)化模型為非凸規(guī)劃模型,設(shè)計了包含蒙特卡洛仿真方法的遺傳算法以獲取模型近似最優(yōu)解．最后,基于算例驗證了公交時刻表魯棒優(yōu)化模型與遺傳算法的可行性．結(jié)果表明,與現(xiàn)有時刻表相比,優(yōu)化后時刻表可減少約22%的總換乘負(fù)效用,能有效改善公交網(wǎng)絡(luò)內(nèi)換乘服務(wù).此外，與枚舉算法求解結(jié)果的對比分析驗證了遺傳算法可行且高效．

協(xié)同調(diào)度;公交時刻表;魯棒優(yōu)化模型;換乘負(fù)效用;遺傳算法

公交網(wǎng)絡(luò)內(nèi)換乘的便捷性是居民出行選擇公交時考慮的關(guān)鍵服務(wù)質(zhì)量因素．在提供可達(dá)且便捷的換乘路徑的基礎(chǔ)上,實施網(wǎng)絡(luò)協(xié)同調(diào)度是減少換乘等待時間、緩解換乘不便最簡單有效的應(yīng)對措施．隨著信息技術(shù)的發(fā)展,公共交通系統(tǒng)智能化調(diào)度已具備良好基礎(chǔ)條件,因此面向換乘銜接問題編制出利于協(xié)同調(diào)度的時刻表具有重要的現(xiàn)實意義．

面向協(xié)同調(diào)度的時刻表設(shè)計優(yōu)化問題已獲得學(xué)者們的廣泛關(guān)注,或以不同線路車輛同時到達(dá)換乘站點的次數(shù)最多為目標(biāo)[1-3],或以不同線路間換乘等待時間最小為目標(biāo)[4-9],提出了不同的多線路協(xié)同調(diào)度時刻表優(yōu)化方法．既有研究中多根據(jù)換乘客流歷史數(shù)據(jù)確定線路間存在換乘關(guān)系的車次和站點,而獲取各站點換乘客流數(shù)據(jù)將耗費公交企業(yè)大量時間與資源,且高昂的建模成本使得此類模型在實踐中難以被廣泛應(yīng)用．另一方面,為了降低模型求解難度,建模時多以換乘等待時間均值衡量換乘過程中乘客所感知的負(fù)效用,即以換乘等待時間期望值最小為優(yōu)化目標(biāo)．然而,換乘等待時間均值最小但波動顯著的時刻表并非理想調(diào)度方案．

本文擬利用不等式約束確定存在換乘關(guān)系的車次,改進(jìn)既有研究中關(guān)于換乘車次識別及其相應(yīng)換乘等待時間計算的方法;并以換乘等待時間期望值與其平均偏差值加權(quán)和最小為優(yōu)化目標(biāo)構(gòu)建魯棒優(yōu)化模型,以衡量由于公交運行隨機性引起的換乘等待時間的波動性；同時給出可行高效的求解算法．

1　模型構(gòu)建

1.1問題描述

為減少乘客換乘等待時間,需調(diào)整線路發(fā)車時刻．令xr為線路r在研究時段內(nèi)各車次首站計劃發(fā)車時刻的整體偏移量(即發(fā)車間隔保持不變),為模型的決策變量．為了保證時刻表調(diào)整方案在實際調(diào)度中易于執(zhí)行,將時刻表偏移量xr設(shè)為以min為單位的整數(shù)變量．

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

為使優(yōu)化后時刻表盡量減小換乘等待時間的波動性,將時刻表魯棒優(yōu)化模型的目標(biāo)函數(shù)表示成

(1)

式中,u為網(wǎng)絡(luò)內(nèi)總換乘負(fù)效用;ηl為情景l(fā)的發(fā)生概率;fl為情景l(fā)下網(wǎng)絡(luò)內(nèi)總換乘等待時間;λ為平衡隨機等待時間期望值及其平均偏差值的非負(fù)權(quán)重系數(shù)．

1.3約束條件

采用粗選II的泡沫作為給礦進(jìn)行二段精選試驗，主要考察了再磨細(xì)度對精礦指標(biāo)的影響。再磨細(xì)度試驗結(jié)果見圖11。從圖中可知，隨著再磨細(xì)度的增加，精礦產(chǎn)品中銅、鉬品位逐漸升高，但是作業(yè)回收率呈下降趨勢，可見再磨細(xì)度在-0.043mm占82%左右時選礦指標(biāo)較好。

式(2)給定了整數(shù)決策變量xr的取值范圍,即所提出的時刻表優(yōu)化模型旨在通過適當(dāng)微調(diào)研究時段內(nèi)現(xiàn)有時刻表以減少網(wǎng)絡(luò)內(nèi)線路間總換乘負(fù)效用,故對企業(yè)運營調(diào)度成本的影響可忽略不計．

(2)

(3)

(4)

對于確定的al和dl,網(wǎng)絡(luò)內(nèi)總換乘等待時間fl可按下式進(jìn)行計算:

(5)

(6)

(7)

(8)

(9)

另外,不同情景的發(fā)生概率必須滿足

(10)

2　求解算法

所構(gòu)建的公交時刻表魯棒優(yōu)化模型為非凸規(guī)劃模型,可利用啟發(fā)式算法求解．考慮到運行時間的隨機性,設(shè)計了包含蒙特卡洛仿真方法的遺傳算法求解模型．遺傳算法主要用于生成不同的時刻表調(diào)整方案．基于給定的時刻表調(diào)整方案,蒙特卡洛仿真方法主要用于計算相應(yīng)的目標(biāo)函數(shù)值．

(11)

包含蒙特卡洛仿真方法的遺傳算法的具體求解步驟如下:

① 產(chǎn)生包含N個染色體的初代種群,各染色體代表各調(diào)整方案,令迭代次數(shù)z=1．

② 利用交叉、變異生成新的染色體,納入既有種群．

3　算例分析

以4條(僅考慮了早高峰客流集中的4個行車方向)具有換乘關(guān)系的公交線路構(gòu)成的網(wǎng)絡(luò)為例驗證上述優(yōu)化模型的有效性和求解算法的可行性．公交線路沿線換乘站點及其相互間換乘關(guān)系見圖1(圖中省略了非換乘站點)．為簡化計算,本例中僅考慮了線路間同站換乘的情況．選取的研究時段為早高峰時段中的1h．假設(shè)研究時段內(nèi)各線路各車次發(fā)車時刻均已知(見表1)．

圖1　公交線路換乘關(guān)系圖

線路發(fā)車時刻B107:00,07:12,07:24,07:36,07:48B207:00,07:12,07:24,07:36,07:48B307:00,07:11,07:22,07:33,07:44,07:55B407:00,07:10,07:20,07:30,07:40,07:50

3.1結(jié)果分析

通過試算確定遺傳算法的交叉率Pc和變異率Pm分別為0.65和0.20．種群規(guī)模N為100,種群最大迭代次數(shù)zmax設(shè)為500．蒙特卡洛仿真方法的樣本規(guī)模L為50．由圖2可知,換乘負(fù)效用值隨著迭代次數(shù)的增加逐步下降,進(jìn)化至第18代時已趨于穩(wěn)定(蒙特卡洛仿真的隨機性導(dǎo)致相同染色體對應(yīng)的換乘負(fù)效用存在差異,故曲線呈現(xiàn)波動性穩(wěn)定),表明求解模型時遺傳算法具有較好的收斂性．

圖2　遺傳算法進(jìn)化曲線

由遺傳算法獲取的各線路時刻表偏移量為:線路B1和B2各車次均需提前6min從首站發(fā)車;而線路B3和B4各車次均需延遲5min從首站發(fā)車．此時刻表調(diào)整方案下對應(yīng)的換乘負(fù)效用為281.75min．而當(dāng)按照現(xiàn)有時刻表運行時乘客所感知的換乘負(fù)效用為363.34min,因此與現(xiàn)有時刻表相比優(yōu)化后時刻表可降低約22%的總換乘負(fù)效用,有效改善網(wǎng)絡(luò)內(nèi)換乘服務(wù)．

3.2算法驗證

根據(jù)4個整數(shù)決策變量的取值范圍,可知共有20 449組調(diào)整方案．對所有方案進(jìn)行枚舉并采用蒙特卡洛仿真方法計算目標(biāo)函數(shù)值,得到換乘負(fù)效用的最小值為294.64min,最大值為405.44min,均值為356.74min．表2僅列出了排在前5位的換乘負(fù)效用值(按從小到大排序)及其對應(yīng)各線路時刻表偏移量．

表2　各線路時刻表偏移量　min

枚舉算法得到的第5位調(diào)整方案與遺傳算法得到的調(diào)整方案相同．盡管兩者方案相同,但由于蒙特卡洛仿真的隨機性使得其各自對應(yīng)的換乘負(fù)效用值存在微小差異．另外,由表2可知前5位換乘負(fù)效用值之間的差異基本可忽略不計,即利用含蒙特卡洛仿真方法的遺傳算法可以獲取模型近似最優(yōu)解．對表2和圖2進(jìn)行綜合分析后可知，該遺傳算法可行且高效．

4　結(jié)語

本文通過構(gòu)建面向網(wǎng)絡(luò)協(xié)同調(diào)度要求的時刻表魯棒優(yōu)化模型,計算使網(wǎng)絡(luò)內(nèi)總換乘負(fù)效用最小的各線路時刻表研究時段內(nèi)整體偏移量(即發(fā)車間隔固定不變)．模型中考慮了公交車輛運行的隨機性,利用包含蒙特卡洛仿真方法的遺傳算法可獲取近似最優(yōu)解．算例結(jié)果表明,與現(xiàn)有時刻表相比,優(yōu)化后的時刻表能有效減少網(wǎng)絡(luò)內(nèi)約22%的總換乘負(fù)效用,與枚舉算法求解結(jié)果的對比分析則驗證了遺傳算法可行且高效．然而在建模過程中對部分情況進(jìn)行了簡化,如假定車輛承載能力總能滿足需求、未考慮換乘站點重要度差異等,下一步將著力完善該優(yōu)化模型以使其能適應(yīng)更復(fù)雜的需求特征與公交網(wǎng)絡(luò)．

References)

[1]Lee K K T, Schonfeld P. Optimal slack time for timed transfers at a transit terminal [J].JournalofAdvancedTransportation, 1991, 25(3): 281-308. DOI:10.1002/atr.5670250304.

[2]Ceder A, Golany B, Tal O. Creating bus timetables with maximal synchronization [J].TransportationResearchPartA:PolicyandPractice, 2001, 35(10): 913-928. DOI:10.1016/s0965-8564(00)00032-x.

[3]Ibarra-Rojas O J, Rios-Solis Y A. Synchronization of bus timetabling [J].TransportationResearchPartB:Methodological, 2012, 46(5): 599-614. DOI:10.1016/j.trb.2012.01.006.

[4]Cevallos F, Zhao F. Minimizing transfer times in public transit network with genetic algorithm [J].TransportationResearchRecord:JournaloftheTransportationResearchBoard, 2006, 1971: 74-79. DOI:10.3141/1971-11.

[5]劉志剛, 申金升, 王海星, 等. 基于協(xié)同發(fā)車的區(qū)域公交時刻表生成模型研究[J]. 交通運輸系統(tǒng)工程與信息, 2007, 7(2): 109-113. DOI:10.3969/j.issn.1009-6744.2007.02.019.

Liu Zhigang, Shen Jinsheng, Wang Haixing, et al. Regional public transportation timetabling model with synchronization [J].JournalofTransportationSystemEngineeringandInformationTechnology, 2007, 7(2): 109-113. DOI:10.3969/j.issn.1009-6744.2007.02.019. (in Chinese)

[6]Shafahi Y, Khani A. A practical model for transfer optimization in a transit network: Model formulations and solutions [J].TransportationResearchPartA:PolicyandPractice, 2010, 44(6): 377-389. DOI:10.1016/j.tra.2010.03.007.

[7]Tuzun Aksu D, Yilmaz S. Transit coordination with heterogeneous headways [J].TransportationPlanningandTechnology, 2014, 37(5): 450-465. DOI:10.1080/03081060.2014.912419.

[8]Parbo J, Nielsen O A, Prato C G. User perspectives in public transport timetable optimisation [J].TransportationResearchPartC:EmergingTechnologies, 2014, 48: 269-284. DOI:10.1016/j.trc.2014.09.005.

[9]曹志超, 袁振洲, 李得偉. 城市軌道交通同步協(xié)調(diào)的優(yōu)化模型[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2016, 46(1): 221-225.

Cao Zhichao, Yuan Zhenzhou, Li Dewei. Synchronization and coordination optimization model of urban rail transit[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2015, 46(1): 221-225. (in Chinese)

[10]王殿海, 湯月華, 陳茜, 等. 基于GPS數(shù)據(jù)的公交站點區(qū)間行程時間可靠性影響因素[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2015, 45(2): 404-412. DOI:10.3969/j.issn.1001-0505.2015.02.036.

Wang Dianhai, Tang Yuehua, Chen Qian, et al. Influence factors of GPS-based bus travel time reliability between adjacent bus stations [J].JournalofSoutheastUniversity(NaturalScienceEdition), 2015, 45(2): 404-412. DOI:10.3969/j.issn.1001-0505.2015.02.036. (in Chinese)

[11]Ma Z, Ferreira L, Mesbah M, et al. Modeling distributions of travel time variability for bus operations [J].JournalofAdvancedTransportation, 2015, 50(1): 6-24. DOI:10.1002/atr.1314.

Robust timetable optimization model for coordinated scheduling in a bus network

Dou Xueping Guo Xiucheng Gong Xiaolin

(School of Transportation, Southeast University, Nanjing 210096, China)

To achieve coordinated scheduling in a bus network, a robust timetable optimization model considering the randomness of bus operation is formulated with the objective of minimizing total transfer disutility. Transfer relations, scheduled terminal departure times, practical bus travel times between any two successive stops, and dwell times at stops are used as the main input parameters of the model to seek the optimal offset times of scheduled terminal departure times. Due to the non-convex characteristic of the developed optimization model, a genetic algorithm coupled with a Monte Carlo simulation method is proposed to obtain the near optimal solution to the robust model. Finally, a numerical experiment is carried out to evaluate the applicability of the robust timetable optimization model and the genetic algorithm. The results indicate that the timetables optimized by the proposed model can effectively reduce transfer disutility by about 22% and thus improve interline transfer service. Moreover, compared with the enumeration algorithm, the genetic algorithm is effective and efficient.

coordinated scheduling; bus timetable; robust optimization model; transfer disutility; genetic algorithm

10.3969/j.issn.1001-0505.2016.05.036

2016-01-14.作者簡介: 竇雪萍(1988—),女,博士生;過秀成(聯(lián)系人),男,博士,教授,博士生導(dǎo)師,seuguo@163.com.

江蘇省交通科學(xué)研究計劃資助項目(09R04).

U121

A

1001-0505(2016)05-1110-05

引用本文: 竇雪萍,過秀成,龔小林.面向協(xié)同調(diào)度的公交時刻表魯棒優(yōu)化模型[J].東南大學(xué)學(xué)報(自然科學(xué)版),2016,46(5):1110-1114. DOI:10.3969/j.issn.1001-0505.2016.05.036