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

竇雪萍　 過秀成　 龔小林

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

?

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

竇雪萍 過秀成 龔小林

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

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

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

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

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

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

1　模型構(gòu)建

1.1問題描述

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

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

為使優(yōu)化后時(shí)刻表盡量減小換乘等待時(shí)間的波動(dòng)性,將時(shí)刻表魯棒優(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)總換乘等待時(shí)間;λ為平衡隨機(jī)等待時(shí)間期望值及其平均偏差值的非負(fù)權(quán)重系數(shù)．

1.3約束條件

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

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

(2)

(3)

(4)

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

(5)

(6)

(7)

(8)

(9)

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

(10)

2　求解算法

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

(11)

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

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

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

3　算例分析

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

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

線路發(fā)車時(shí)刻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代時(shí)已趨于穩(wěn)定(蒙特卡洛仿真的隨機(jī)性導(dǎo)致相同染色體對(duì)應(yīng)的換乘負(fù)效用存在差異,故曲線呈現(xiàn)波動(dòng)性穩(wěn)定),表明求解模型時(shí)遺傳算法具有較好的收斂性．

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

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

3.2算法驗(yàn)證

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

表2　各線路時(shí)刻表偏移量　min

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

4　結(jié)語(yǔ)

本文通過構(gòu)建面向網(wǎng)絡(luò)協(xié)同調(diào)度要求的時(shí)刻表魯棒優(yōu)化模型,計(jì)算使網(wǎng)絡(luò)內(nèi)總換乘負(fù)效用最小的各線路時(shí)刻表研究時(shí)段內(nèi)整體偏移量(即發(fā)車間隔固定不變)．模型中考慮了公交車輛運(yùn)行的隨機(jī)性,利用包含蒙特卡洛仿真方法的遺傳算法可獲取近似最優(yōu)解．算例結(jié)果表明,與現(xiàn)有時(shí)刻表相比,優(yōu)化后的時(shí)刻表能有效減少網(wǎng)絡(luò)內(nèi)約22%的總換乘負(fù)效用,與枚舉算法求解結(jié)果的對(duì)比分析則驗(yàn)證了遺傳算法可行且高效．然而在建模過程中對(duì)部分情況進(jìn)行了簡(jiǎn)化,如假定車輛承載能力總能滿足需求、未考慮換乘站點(diǎ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ū)域公交時(shí)刻表生成模型研究[J]. 交通運(yùn)輸系統(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é)報(bào)(自然科學(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ù)的公交站點(diǎn)區(qū)間行程時(shí)間可靠性影響因素[J]. 東南大學(xué)學(xué)報(bào)(自然科學(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.作者簡(jiǎn)介: 竇雪萍(1988—),女,博士生;過秀成(聯(lián)系人),男,博士,教授,博士生導(dǎo)師,seuguo@163.com.

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

U121

A

1001-0505(2016)05-1110-05

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