地铁快慢车运行计划综合优化模型
|
摘要
为了综合优化地铁快慢车运行计划,建立了综合求解列车开行方案、停站方案和时刻表的优化模型;分析了地铁列车停站、区间运行、快慢车运行组织与客流出行等特点,构建了快慢车运行计划的约束条件,设计了综合协调优化列车运行时间和运输成本的目标函数,建立了完整的地铁快慢车运行计划优化模型;分析了模型特点及其复杂度,设计了两阶段近似算法求解模型,第1阶段根据乘客能够忍耐的最大候车时间推算出慢车的开行列数,同时将其均匀分布在编制时段范围内,并对初始时刻表进行合理调整,第2阶段采用CPLEX求解器求解地铁快慢车运行计划;针对上海地铁16号线,对其早高峰7:00~9:00下行方向的快慢车运行计划进行编制试验。试验结果表明:快慢车运行计划中共开行列车30列,其中快车11列,慢车19列,完成9次越行,87次跨站不停车,快车全程最大节约时间为628s,约降低4.1%,总旅行时间节约4 450s;根据客流需求在1∶1~1∶2之间灵活安排快慢车开行比例;根据各车站上下车客流需求灵活安排快车停站方案,快车之间停站方案不固定;随着列车规模的增大,模型求解时间大幅增长,当规模达到一定程度时,需设计更为高效的求解算法。
In order to optimize express/local train operation schedule of metro,an integrated calculation optimization model of train operation scheme,stop schedule plan and timetable was established.The characteristics of train stop,interstation running,express/local train operation organization and passenger travelling were analysed.The constraint conditions of operation plan of express/local train were built,and an objective function of comprehensive coordination optimization of train operation time and transportation cost was designed.The integrated operation plan optimization model of metro express/local train was established,and a two-stage approximate algorithm was designed to solve the model.At the first stage,according to the maximum waiting time that passengers can endure,the number of local trains can be calculated.The local trains were required to evenly depart in the considered time horizon,then the initialtimetable was reasonably adjusted.At the second stage,the express/local train operation schedule was solved by using CPLEX solver.Aiming at Shanghai Metro Line 16,the express/local train operation schedule experiment was worked out during morning peak 7:00-9:00 in down direction.Experimental result shows that 30 trains operate in the express/local train operation schedule,including 11 express trains and 19 local trains.9 times of overtaking and 87 times of skip-stopping are accomplished,the maximum saving time of express train during whole journey is 628 s,reduces about 4.1%,and the total travel time saves 4 450 s.The ratio of express/local trains are flexibly assigned between 1∶1-1∶2 according to the passenger demands.The stopping scheme of express trains are flexibly assigned according to the inflow and outflow demands of passenger at each station,and their stopping schemes are not constant.The computing time turns to be much longer as the train scale gets larger,so a more effective algorithm need to be designed when the scale increases to a certain extent.
In order to optimize express/local train operation schedule of metro,an integrated calculation optimization model of train operation scheme,stop schedule plan and timetable was established.The characteristics of train stop,interstation running,express/local train operation organization and passenger travelling were analysed.The constraint conditions of operation plan of express/local train were built,and an objective function of comprehensive coordination optimization of train operation time and transportation cost was designed.The integrated operation plan optimization model of metro express/local train was established,and a two-stage approximate algorithm was designed to solve the model.At the first stage,according to the maximum waiting time that passengers can endure,the number of local trains can be calculated.The local trains were required to evenly depart in the considered time horizon,then the initialtimetable was reasonably adjusted.At the second stage,the express/local train operation schedule was solved by using CPLEX solver.Aiming at Shanghai Metro Line 16,the express/local train operation schedule experiment was worked out during morning peak 7:00-9:00 in down direction.Experimental result shows that 30 trains operate in the express/local train operation schedule,including 11 express trains and 19 local trains.9 times of overtaking and 87 times of skip-stopping are accomplished,the maximum saving time of express train during whole journey is 628 s,reduces about 4.1%,and the total travel time saves 4 450 s.The ratio of express/local trains are flexibly assigned between 1∶1-1∶2 according to the passenger demands.The stopping scheme of express trains are flexibly assigned according to the inflow and outflow demands of passenger at each station,and their stopping schemes are not constant.The computing time turns to be much longer as the train scale gets larger,so a more effective algorithm need to be designed when the scale increases to a certain extent.
引文
[1]NIU Hui-min,ZHOU Xue-song.Optimizing urban rail timetable under time-dependent demand and oversaturated conditions[J].Transportation Research Part C:Emerging Technologies,2013,36:212-230.
[2]NIU Hui-min,ZHOU Xue-song,GAO Ru-hu.Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns:nonlinear integer programming models with linear constraints[J].Transportation Research Part B:Methodological,2015,76:117-135.
[3]YIN Jia-teng,TANG Tao,YANG Li-xing,et al.Energyefficient metro train rescheduling with uncertain time-variant passenger demands:an approximate dynamic programming approach[J].Transportation Research Part B:Methodological,2016,91:178-210.
[4]YIN Jia-teng,YANG Li-xing,TANG Tao,et al.Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization:mixedinteger linear programming approaches[J].Transportation Research Part B:Methodological,2017,97:182-213.
[5]唐海川,王青元,冯晓云.地铁列车追踪运行的节能控制与分析[J].铁道学报,2015,37(1):37-43.TANG Hai-chuan,WANG Qing-yuan,FENG Xiao-yun.Energy saving control of metro train tracing operation[J].Journal of the China Railway Society,2015,37(1):37-43.(in Chinese)
[6]胡文斌,孙其升,吕建国,等.基于节能的地铁列车时刻表优化[J].城市轨道交通研究,2016(5):67-73.HU Wen-bin,SUN Qi-sheng,LU Jian-guo,et al.Energy conversation based on the optimization of train timetable[J].Urban Mass Transit,2016(5):67-73.(in Chinese)
[7]HUANG Ye-ran,YANG Li-xing,TANG Tao,et al.Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks[J].Energy,2017,138:1124-1147.
[8]YANG Li-xing,QI Jian-guo,LI Shu-kan,et al.Collaborative optimization for train scheduling and train stop planning on high-speed railways[J].Omega,2016,64:57-76.
[9]HASSANNAYEBI E,ZEGORDI S H,YAGHINI M.Train timetabling for an urban rail transit line using a lagrangian relaxation approach[J].Applied Mathematical Modelling,2016,40(23/24):9892-9913.
[10]WANG Yi-hui,TANG Tao,NING Bin,et al.Passengerdemands-oriented train scheduling for an urban rail transit network[J].Transportation Research Part C:Emerging Technologies,2015,60:1-23.
[11]YUE Yi-xiang,WANG Shi-feng,ZHOU Lei-shan,et al.Optimizing train stopping patterns and schedules for highspeed passenger rail corridors[J].Transportation Research Part C:Emerging Technologies,2016,63:126-146.
[12]GAO Yuan,KROON L,SCHMIDT M,et al.Rescheduling a metro line in an over-crowded situation after disruptions[J].Transportation Research Part B:Methodological,2016,93:425-449.
[13]ZHAN Shu-guang,KROON L G,VEELENTURF L P,et al.Real-time high-speed train rescheduling in case of a complete blockage[J].Transportation Research Part B:Methodological,2015,78:182-201.
[14]李伟,徐瑞华,朱炜.运行延误下地铁换乘站多线协同客流处置方法[J].同济大学学报:自然科学版,2015,43(2):239-244.LI Wei,XU Rui-hua,ZHU Wei.Multi-line cooperation method for passenger flow disposal in metro transfer station under train delay[J].Journal of Tongji University:Natural Science,2015,43(2):239-244.(in Chinese)
[15]江志彬,季婷婷.基于客流影响的城市轨道交通列车运行调整策略[J].城市轨道交通研究,2014(1):39-42.JIANG Zhi-bin,JI Ting-ting.URT train regulation strategy based on passenger flow influence[J].Urban Mass Transit,2014(1):39-42.(in Chinese)
[16]JIANG Feng,CACCHIANI V,TOTH P.Train timetabling by skip-stop planning in highly congested lines[J].Transportation Research Part B:Methodological,2017,104:149-174.
[17]王婵婵,陈菁菁.城市轨道交通列车延误时多线换乘站跳停方案研究[J].城市轨道交通研究,2014(12):69-72.WANG Chan-chan,CHEN Jing-jing.On the skip-stop schemes at rail transit transfer station in case of train delay[J].Urban Mass Transit,2014(12):69-72.(in Chinese)
[18]KANG Liu-jiang,ZHU Xiao-ning.Strategic timetable scheduling for last trains in urban railway transit networks[J].Applied Mathematical Modelling,2017,45:209-225.
[19]KANG Liu-jiang,MENG Qiang.Two-phase decomposition method for the last train departure time choice in subway networks[J].Transportation Research Part B:Methodological,2017,104:568-582.
[20]KANG Liu-jiang,WU Jian-jun,SUN Hui-jun,et al.A case study on the coordination of last trains for the Beijing subway network[J].Transportation Research Part B:Methodological,2015,72:112-127.
[21]王智鹏,罗霞.城市轨道交通快慢车停站方案优化[J].华南理工大学学报:自然科学版,2015,43(12):91-98.WANG Zhi-peng,LUO Xia.Stopping schedule optimization of express/local trains in urban rail transit[J].Journal of South China University of Technology:Natural Science Edition,2015,43(12):91-98.(in Chinese)
[22]谭小土.城市轨道交通快慢车运行组织研究[D].成都:西南交通大学,2014.TAN Xiao-tu.Research of express-local train operation organization in urban rail transit[D].Chengdu:Southwest Jiaotong University,2014.(in Chinese)
[23]王琳.城市轨道交通快慢车运营组织研究[D].北京:北京交通大学,2013.WANG Lin.Study on operation organization of the express/local train for urban rail transit[D].Beijing:Beijing Jiaotong University,2013.(in Chinese)
[24]张琛,韩宝明,张琦.轨道交通机场线快慢车停站方案优化方法[J].都市快轨交通,2015,28(5):67-70.ZHANG Chen,HAN Bao-ming,ZHANG Qi.Optimization methods of express and local train skip-stop scheme on airport rail line[J].Urban Rapid Rail Transit,2015,28(5):67-70.(in Chinese)
[25]陈晓峰.上海轨道交通16号线快慢车运行方案研究[J].城市轨道交通研究,2014(5):68-72.CHEN Xiao-feng.On express/slow train operation program on Shanghai Rail Transit Line 16[J].Urban Mass Transit,2014(5):68-72.(in Chinese)
[2]NIU Hui-min,ZHOU Xue-song,GAO Ru-hu.Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns:nonlinear integer programming models with linear constraints[J].Transportation Research Part B:Methodological,2015,76:117-135.
[3]YIN Jia-teng,TANG Tao,YANG Li-xing,et al.Energyefficient metro train rescheduling with uncertain time-variant passenger demands:an approximate dynamic programming approach[J].Transportation Research Part B:Methodological,2016,91:178-210.
[4]YIN Jia-teng,YANG Li-xing,TANG Tao,et al.Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization:mixedinteger linear programming approaches[J].Transportation Research Part B:Methodological,2017,97:182-213.
[5]唐海川,王青元,冯晓云.地铁列车追踪运行的节能控制与分析[J].铁道学报,2015,37(1):37-43.TANG Hai-chuan,WANG Qing-yuan,FENG Xiao-yun.Energy saving control of metro train tracing operation[J].Journal of the China Railway Society,2015,37(1):37-43.(in Chinese)
[6]胡文斌,孙其升,吕建国,等.基于节能的地铁列车时刻表优化[J].城市轨道交通研究,2016(5):67-73.HU Wen-bin,SUN Qi-sheng,LU Jian-guo,et al.Energy conversation based on the optimization of train timetable[J].Urban Mass Transit,2016(5):67-73.(in Chinese)
[7]HUANG Ye-ran,YANG Li-xing,TANG Tao,et al.Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks[J].Energy,2017,138:1124-1147.
[8]YANG Li-xing,QI Jian-guo,LI Shu-kan,et al.Collaborative optimization for train scheduling and train stop planning on high-speed railways[J].Omega,2016,64:57-76.
[9]HASSANNAYEBI E,ZEGORDI S H,YAGHINI M.Train timetabling for an urban rail transit line using a lagrangian relaxation approach[J].Applied Mathematical Modelling,2016,40(23/24):9892-9913.
[10]WANG Yi-hui,TANG Tao,NING Bin,et al.Passengerdemands-oriented train scheduling for an urban rail transit network[J].Transportation Research Part C:Emerging Technologies,2015,60:1-23.
[11]YUE Yi-xiang,WANG Shi-feng,ZHOU Lei-shan,et al.Optimizing train stopping patterns and schedules for highspeed passenger rail corridors[J].Transportation Research Part C:Emerging Technologies,2016,63:126-146.
[12]GAO Yuan,KROON L,SCHMIDT M,et al.Rescheduling a metro line in an over-crowded situation after disruptions[J].Transportation Research Part B:Methodological,2016,93:425-449.
[13]ZHAN Shu-guang,KROON L G,VEELENTURF L P,et al.Real-time high-speed train rescheduling in case of a complete blockage[J].Transportation Research Part B:Methodological,2015,78:182-201.
[14]李伟,徐瑞华,朱炜.运行延误下地铁换乘站多线协同客流处置方法[J].同济大学学报:自然科学版,2015,43(2):239-244.LI Wei,XU Rui-hua,ZHU Wei.Multi-line cooperation method for passenger flow disposal in metro transfer station under train delay[J].Journal of Tongji University:Natural Science,2015,43(2):239-244.(in Chinese)
[15]江志彬,季婷婷.基于客流影响的城市轨道交通列车运行调整策略[J].城市轨道交通研究,2014(1):39-42.JIANG Zhi-bin,JI Ting-ting.URT train regulation strategy based on passenger flow influence[J].Urban Mass Transit,2014(1):39-42.(in Chinese)
[16]JIANG Feng,CACCHIANI V,TOTH P.Train timetabling by skip-stop planning in highly congested lines[J].Transportation Research Part B:Methodological,2017,104:149-174.
[17]王婵婵,陈菁菁.城市轨道交通列车延误时多线换乘站跳停方案研究[J].城市轨道交通研究,2014(12):69-72.WANG Chan-chan,CHEN Jing-jing.On the skip-stop schemes at rail transit transfer station in case of train delay[J].Urban Mass Transit,2014(12):69-72.(in Chinese)
[18]KANG Liu-jiang,ZHU Xiao-ning.Strategic timetable scheduling for last trains in urban railway transit networks[J].Applied Mathematical Modelling,2017,45:209-225.
[19]KANG Liu-jiang,MENG Qiang.Two-phase decomposition method for the last train departure time choice in subway networks[J].Transportation Research Part B:Methodological,2017,104:568-582.
[20]KANG Liu-jiang,WU Jian-jun,SUN Hui-jun,et al.A case study on the coordination of last trains for the Beijing subway network[J].Transportation Research Part B:Methodological,2015,72:112-127.
[21]王智鹏,罗霞.城市轨道交通快慢车停站方案优化[J].华南理工大学学报:自然科学版,2015,43(12):91-98.WANG Zhi-peng,LUO Xia.Stopping schedule optimization of express/local trains in urban rail transit[J].Journal of South China University of Technology:Natural Science Edition,2015,43(12):91-98.(in Chinese)
[22]谭小土.城市轨道交通快慢车运行组织研究[D].成都:西南交通大学,2014.TAN Xiao-tu.Research of express-local train operation organization in urban rail transit[D].Chengdu:Southwest Jiaotong University,2014.(in Chinese)
[23]王琳.城市轨道交通快慢车运营组织研究[D].北京:北京交通大学,2013.WANG Lin.Study on operation organization of the express/local train for urban rail transit[D].Beijing:Beijing Jiaotong University,2013.(in Chinese)
[24]张琛,韩宝明,张琦.轨道交通机场线快慢车停站方案优化方法[J].都市快轨交通,2015,28(5):67-70.ZHANG Chen,HAN Bao-ming,ZHANG Qi.Optimization methods of express and local train skip-stop scheme on airport rail line[J].Urban Rapid Rail Transit,2015,28(5):67-70.(in Chinese)
[25]陈晓峰.上海轨道交通16号线快慢车运行方案研究[J].城市轨道交通研究,2014(5):68-72.CHEN Xiao-feng.On express/slow train operation program on Shanghai Rail Transit Line 16[J].Urban Mass Transit,2014(5):68-72.(in Chinese)