Access the full text.
Sign up today, get DeepDyve free for 14 days.
Serafino Cicerone, Gianlorenzo D'angelo, G. Stefano, D. Frigioni, A. Navarra (2009)
Recoverable robust timetabling for single delay: Complexity and polynomial algorithms for special casesJournal of Combinatorial Optimization, 18
Wikepedia , “ Deap learning
constant braking force in the constant force braking phase
A. D’Ariano, D. Pacciarelli, M. Pranzo (2007)
Discrete Optimization A branch and bound algorithm for scheduling trains in a railway network
T. Albrecht, S. Oettich (2002)
A NEW INTEGRATED APPROACH TO DYNAMIC SCHEDULE SYNCHRONIZATION AND ENERGY-SAVING TRAIN CONTROL, 61
M. Carey (1994)
Reliability of interconnected scheduled servicesEuropean Journal of Operational Research, 79
Hai-rong Dong, B. Ning, B. Cai, Z. Hou (2010)
Automatic Train Control System Development and Simulation for High-Speed RailwaysIEEE Circuits and Systems Magazine, 10
iii) The disturbances are small enough which will not lead to network disruption
J. Törnquist, J. Persson (2007)
N-tracked railway traffic re-scheduling during disturbancesTransportation Research Part B-methodological, 41
iv) Only one disturbance happens during a complete test procedure from the first train’s departure to the last train’s arrival
W. Marsden (2012)
I and J
M. Carey, A. Kwieciński (1994)
Stochastic approximation to the effects of headways on knock-on delays of trainsTransportation Research Part B-methodological, 28
T. Albrecht (2004)
REDUCING POWER PEAKS AND ENERGY CONSUMPTION IN RAIL TRANSIT SYSTEMS BY SIMULTANEOUS TRAIN RUNNING TIME CONTROLWIT Transactions on the Built Environment, 74
Cheng Gong, Shiwen Zhang, Feng Zhang, Jianguo Jiang, Xinheng Wang (2014)
An Integrated Energy-Efficient Operation Methodology for Metro Systems Based on a Real Case of Shanghai Metro Line OneEnergies, 7
Valentina Cacchiani, P. Toth (2012)
Nominal and robust train timetabling problemsEur. J. Oper. Res., 219
J. Holland (1992)
Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence
Xin Yang, Xiang Li, Ziyou Gao, Hongwei Wang, T. Tang (2013)
A Cooperative Scheduling Model for Timetable Optimization in Subway SystemsIEEE Transactions on Intelligent Transportation Systems, 14
(2008)
“A genetic approach to robust train timetabling, technical report ARRIVAL-TR-0173 arrival project,”
GitHub Inc
DEAP,
S. Binder, Yousef Maknoon, M. Bierlaire (2017)
The multi-objective railway timetable rescheduling problemTransportation Research Part C-emerging Technologies, 78
Darja Šemrov, R. Marsetič, M. Zura, L. Todorovski, A. Srdić (2016)
Reinforcement learning approach for train rescheduling on a single-track railwayTransportation Research Part B-methodological, 86
(2010)
and Z Hou
M. Carey, A. Kwieciński (1995)
Properties of expected costs and performance measures in stochastic models of scheduled transportEuropean Journal of Operational Research, 83
D. Pacciarelli A. D’Ariano (2007)
A branch and bound algorithm for scheduling trains in a railway network,European Journal of Operational Research, 183
Wenkai Xu, Peng Zhao, Liqiao Ning (2018)
A Practical Method for Timetable Rescheduling in Subway Networks during the End-of-Service PeriodJournal of Advanced Transportation
Peijuan Xu, F. Corman, Q. Peng, X. Luan (2017)
A Timetable Rescheduling Approach and Transition Phases for High-Speed Railway Traffic during DisruptionsTransportation Research Record, 2607
M. Bianchini, F. Scarselli (2014)
On the Complexity of Neural Network Classifiers: A Comparison Between Shallow and Deep ArchitecturesIEEE Transactions on Neural Networks and Learning Systems, 25
Muhammad Khan, Xuesong Zhou (2010)
Stochastic Optimization Model and Solution Algorithm for Robust Double-Track Train-Timetabling ProblemIEEE Transactions on Intelligent Transportation Systems, 11
Li Wang, W. Mo, Yong Qin, Fei Dou, L. Jia (2014)
Optimization Based High-Speed Railway Train Rescheduling with Speed RestrictionDiscrete Dynamics in Nature and Society, 2014
Gerben Scheepmaker, R. Goverde, Leo Kroon (2017)
Review of energy-efficient train control and timetablingEur. J. Oper. Res., 257
Leo Kroon, G. Maróti, M. Helmrich, Michiel Vromans, R. Dekker (2006)
Stochastic Improvement of Cyclic Railway TimetablesEuropean Economics: Microeconomics & Industrial Organization eJournal
Valentina Cacchiani, A. Caprara, M. Fischetti (2012)
A Lagrangian Heuristic for Robustness, with an Application to Train TimetablingTransp. Sci., 46
Selim Dündar, I. Sahin (2013)
Train re-scheduling with genetic algorithms and artificial neural networks for single-track railwaysTransportation Research Part C-emerging Technologies, 27
(2018)
“Line1(Shanghai Metro)”
ii) The adjacent trains run with enough spacing, so we do not consider the blocking conflict during operation
F. Ortega, Miguel Pozo, J. Puerto (2018)
On-Line Timetable Rescheduling in a Transit LineTransp. Sci., 52
Poulami Dalapati, Piyush Agarwal, Animesh Dutta, S. Bhattacharya (2016)
Real-time Rescheduling in Distributed Railway Network: An Agent-Based ApproachArXiv, abs/1607.03340
(1926)
e tractive resistance of electric locomotives and cars
S. Bonser (2020)
FunctionVirtual Vernacular
R. Routledge (2018)
RailwaysDiscoveries and Inventions of the Ninteenth Century
A. Albrecht, P. Howlett, Peter Pudney, Xuan Vu, P. Zhou (2016)
The key principles of optimal train control—Part 1: Formulation of the model, strategies of optimal type, evolutionary lines, location of optimal switching pointsTransportation Research Part B-methodological, 94
Huijun Sun, Jianjun Wu, Hongnan Ma, Xin Yang, Ziyou Gao (2019)
A Bi-Objective Timetable Optimization Model for Urban Rail Transit Based on the Time-Dependent Passenger VolumeIEEE Transactions on Intelligent Transportation Systems, 20
T. Albrecht (2010)
Reducing Power Peaks And Energy ConsumptionIn Rail Transit Systems By Simultaneous TrainRunning Time ControlWIT Transactions on State-of-the-art in Science and Engineering, 39
Xiang Li, Biying Shou, D. Ralescu (2014)
Train Rescheduling With Stochastic Recovery Time: A New Track-Backup ApproachIEEE Transactions on Systems, Man, and Cybernetics: Systems, 44
Christian Liebchen, Michael Schachtebeck, A. Schöbel, S. Stiller, André Prigge (2010)
Computing delay resistant railway timetablesComput. Oper. Res., 37
Constant force braking Constant power braking U − ( v ) = u b U − ( v ) vu b v b
V. Breusegem, G. Campion, G. Bastin (1991)
Traffic modeling and state feedback control for metro linesIEEE Transactions on Automatic Control, 36
speed in switching point (from the constant force accelerating phase to the constant power accelerating phase)
Wikepedia
Deap learning,
Hindawi Journal of Advanced Transportation Volume 2019, Article ID 5174961, 11 pages https://doi.org/10.1155/2019/5174961 Research Article A Real-Time Timetable Rescheduling Method for Metro System Energy Optimization under Dwell-Time Disturbances 1 1 1 1 2 Guang Yang , Junjie Wang , Feng Zhang , Shiwen Zhang , and Cheng Gong School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA Correspondence should be addressed to Feng Zhang; fzhang@sjtu.edu.cn Received 15 April 2019; Accepted 17 August 2019; Published 2 December 2019 Academic Editor: Rakesh Mishra Copyright © 2019 Guang Yang et al. ƒis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Automatic Train Systems (ATSs) have attracted much attention in recent years. A reliable ATS can reschedule timetables adaptively and rapidly whenever a possible disturbance breaks the original timetable. Most research focuses the timetable rescheduling problem on minimizing the overall delay for trains or passengers. Few have been focusing on how to minimize the energy consumption when disturbances happen. In this paper, a real-time timetable rescheduling method (RTTRM) for energy optimization of metro systems has been proposed. ƒe proposed method takes little time to recalculate a new schedule and gives proper solutions for all trains in the network immediately a‘er a random disturbance happens, which avoids possible chain reactions that would attenuate the reuse of regenerative energy. ƒe real-time feature and self-adaptability of the method are attributed to the combinational use of Genetic Algorithm (GA) and Deep Neural Network (DNN). ƒe decision system for proposing solutions, which contains multiple DNN cells with same structures, is trained by GA results. RTTRM is upon the foundation of three models for metro networks: a control model, a timetable model and an energy model. Several numerical examples tested on Shanghai Metro Line 1 (SML1) validate the energy saving e•ects and real-time features of the proposed method. large amount of electric energy every day, there is tremendous 1. Introduction potential of energy conservation in metro transportations. So With rapid development of intelligent transportation, far, there is little research that mentions the topic on how to Automatic Train Systems (ATSs) have attracted much atten- save energy when a metro network encounters disturbances. tion in recent years. A reliable high-level ATS ensures the Di•erent from the traditional TTR problem, the energy-ef- entire railway network to function safely, cost-e•ectively and ¡cient TTR problem consists of two steps. ƒe ¡rst step is to e—ciently under sudden disturbances [1]. Disturbances in build an ošine timetable for optimal use of the total energy metro networks such as temporary platform blockages make of the metro network, which is called Energy-E—cient Train ošine schedules suboptimal for use. Hence, various methods Timetabling (EETT) [9]. In this step, all trains in the network of Train Timetable Rescheduling (TTR) [2–6] have been pro- run with con¡rmed dwell time and no emergencies happen posed to handle unforeseen events which may disturb time- [8]. ƒe second step is to build a real-time timetable to cope table. Prevailing methods for timetable rescheduling can be with sudden disturbances. In this step, proper travel time in classi¡ed into two categories: passenger-oriented and di•erent sections and di•erent trains will be determined and train-oriented. ƒe passenger-oriented research focuses on modi¡ed in real time to minimize the system energy consump- minimizing the total delay time of passengers [4], while the tion a‘er disturbances happen. train-oriented research focuses on minimizing the overall Energy-e—cient TTR problem is a challenging task delays of all trains [7, 8]. However, short delays in one train because of its real-time demand and randomness of distur- may not necessarily arouse block con¥icts of the route ahead, bances. Any disturbance in a metro network can bring a series still, it will inevitably a•ect the energy consumption of the of chain reactions that make the ošine schedule not optimal overall metro network. Since a metro network consumes a any more. Rescheduling timetable is a good solution to avoid 2 Journal of Advanced Transportation the chain reactions and save more energy. EETT methods that Genetic Algorithm (GA) to reschedule the trains on a single are nonreal-time methods cannot be used in the energy-e—- track railway line in Turkey and determined the meets and cient TTR problem. Moreover, disturbances occur randomly passes of the trains in the opposite direction. ƒey designed at di•erent stations on di•erent trains, and the length of delay benchmarking experiments among an Arti¡cial Neural Network is also stochastic. It requires the method having a self-adapt- (ANN), a MIP model and two kinds of GA. ƒey also validated ability that makes the appropriate choice presciently according that GA outperforms the other methods. Šemrov et al. [25] used to the disturbances. a rescheduling method based on reinforcement learning, more Energy-e—cient TTR problem has been rarely mentioned speci¡cally Q-learning, on a real-world railway network in in recent years. Gong et al. [10] proposed an integrated Slovenia. ƒey illustrated that Q-learning leaded to rescheduling Energy-e—cient Operation Methodology (EOM) to compen- solutions that were at least equivalent and o‘en superior to the sate dwell time disturbances in real-time. By reducing the simple First-In-First-Out (FIFO) method and the random walk travel time of the delaying train in the section following a method. Xu et al. [7] proposed a Mixed-Integer Linear Program disturbance, the schedule can be recovered to the original one (MILP) model for the quasi-moving block signaling system to which is optimized by GA. ƒe cost of EOM is that more reduce the ¡nal delay and to solve a real-world instance in energy will be consumed before the recovery of the China. ƒey optimized tra—c in transition from a disordered schedule. condition to a normal condition and analyzed delays in di•erent In this paper, a real-time timetable rescheduling method transition phases. Ortega et al. [4] proposed a biobjective opti- (RTTRM) for energy optimization is proposed. Di•erent from mization method for timetable rescheduling during the end-of- EOM, this method reschedules all trains in the network a‘er service period of a subway, in order to minimize the total a disturbance happens, rather than reschedules the delaying transfer waiting time for all transfer passengers and the devia- train only. ƒe proposed method can ¡nish making decisions tion from the scheduled timetable. immediately a‘er a disturbance happens, attributed to the Albrecht and Oettich [26] ¡rst discussed EETT problem. combinational usage of GA and DNN. Firstly, GA provides a ƒey used a Dynamic Programming (DP) to calculate the series of corresponding energy-optimal timetables for random optimal timetable. ƒe quality criteria of the multiobjective disturbances. ƒen, a decision system based on DNN learns optimization function were the overall waiting time and the from the connection between the random disturbances and energy consumption. Albrecht [27] considered to change the the optimal timetable which are deduced by GA. Finally, the additional running time to the synchronize acceleration and well trained decision system provides proper solutions in dif- the regenerative braking in order to minimize total energy ferent cases of disturbances in real-time. consumption and power peaks. It was the ¡rst to study EETT ƒe remainder of the paper is organized as follows. Section with the regenerative braking. Yang et al. [28] ¡rst described 2 reviews the previous contributions related to TTR and EETT EETT problem in a mathematical programming mode and problem. Section 3 presents the description of a control model, solved this problem by maximizing time overlaps of nearby a timetable model and an energy model in metro system. accelerating and braking trains. Sun et al. [29] developed a Section 4 introduces GA and a decision system to solve the bi-objective timetable optimization model to minimize the energy-e—cient TTR with dwell-time disturbances. In section total passenger waiting time and energy consumption. 5, several experiments based on a real-world network of Shanghai Metro Line 1 (SML1) is presented to validate the proposed method. ƒe ¡nal section concludes the paper. 3. Formulation of Model for Metro Network In this section, three models are formulated: a control model, 2. Literature Review a timetable model, and an energy model, all of which are used to describe the operation process for a metro network. For the Pioneering theoretical works related to TTR problem were ¡rst single-train control model, state variables of trains, such as the carried out by Carey’s group [11–13]. ƒey eliminated the dis- position and the speed, are formulated. For the timetable tribution and propagation of the train delay by using the sequen- model, the departure time and the arrival time for each single tial solution procedures. Törnquist and Persson [14] presented train are calculated. For the energy model, energy exchange a Mixed Integer Programming (MIP) model that took into among trains running in the same network is formulated. account the reordering and rerouting of trains. D’Ariano et al. [15] computed a con¥ict-free train timetable compatible with 3.1. Parameter and Variable. ƒe notation system which the actual status of the railway network and proposed a branch- includes parameters and variables, is presented as follows: and-bound algorithm for minimizing the global secondary : conversion e—ciency of the train traction system delay. Khan and Zhou [16] developed a stochastic optimization (from electricity to mechanical energy). formulation with the purpose of minimizing the total trip time : conversion e—ciency of the train braking system in a published timetable and reducing the expected schedule (from mechanical energy to electrical energy). delay. Cacchiani and Toth [17] classi¡ed approaches of timetable : feedback coe—cient on braking energy. rescheduling into six categories: stochastic optimization [18], : total number of trains in the metro network. light robustness [19], recovery robustness [20], delay manage- : total number of stations. ment [21], bicriteria and Lagrangian-based approaches [22] and meta-heuristics [23]. Dündar and Sahin [24] developed a : index for train, ∈ {1,2,. ..,}. Journal of Advanced Transportation 3 : index for station, ∈ {1,2,. ..,}. +1, : dwell time of train at station + 1. U (v) = u + a : departure instants of train at station . u v a a U (v)= : headway of train . : interstation running time of train running from station to station + 1. U (v) Constant force Constant power total travel time. accelerating accelerating : constant traction force in the constant force accel- erating phase. v v v v v a b lim2 lim1 : constant braking force in the constant force braking phase. Constant force Constant power braking braking v : speed in switching point (from the constant force U (v) accelerating phase to the constant power accelerat- ing phase). u v b b U (v) = u − b U (v)= v : speed in switching point (from the constant power − braking phase to the constant force braking phase). v : cruising speed of train running from station to station + 1. F´µ¶·¸ 1: ƒe bound curves of accelerating phase and braking phase. v : the maximum speed limit between stations. lim1 v : the pull-in speed limit and the pull-out speed limit. lim2 : spacing of the section , + 1. Increase the cruising speed : current position of train . v ηγ , v v : current time of train . c b v : current driving speed of train . Reduce the : traction or braking force per unit mass of train . driving period : resistance per unit mass. o ηγ , t t g: gravity per unit mass. s F´µ¶·¸ 2: ƒe relation between the cruising speed and the periodic 3.2. Assumptions time. (i) ƒe network in the model has narrow spacing (for example Shanghai Metro Line 1). Trains drive in each where (, v) = (), v () for ∈ {1,2,. ..,} and ∈0, . section in a sequence of accelerating-cruising-brak- In Equation (2), =(v) meets Davis’s Equation [30] ing, without the repeated accelerating and braking. (v) = v + v + , (3) (ii) ƒe adjacent trains run with enough spacing, so 1 2 3 we do not consider the blocking con¥ict during where , and are constant parameters. g = g() repre- 1 2 3 operation. sents the gravity per unit mass, which is a piecewise linear (iii) ƒe disturbances are small enough which will not function. = (v, ) ∈ (v), (v) represents the force per − + lead to network disruption. unit mass or acceleration. We assume that is positive in the acceleration phase and negative in the braking phase. Figure (iv) Only one disturbance happens during a complete 1 shows the bound curves of , where (v) is the lower bound test procedure from the ¡rst train’s departure to the and (v) is the upper bound. last train’s arrival. In Figure 1, , , v , v , v , v are constants (v) ƒe disturbances will not happen at the starting lim1 lim2 formulated in advance which obey the motor characteristic station. of a train. According to the theories proposed by the SCG group [31], the maximum acceleration-speedhold- 3.3. Control Model for a Single Train. When driving a train maximum braking strategy is chosen as the optimal driving from =0 to = , according to Newton’s Second Law, the strategy in a period. ƒe traction force meets = (v) in motion equations are the accelerating phase, and the braking force meets = (v) in the braking phase. In the speedhold phase, the traction force changes with gradient to keep the driving speed con- = v, (1) stant, which meets the constraint (v) < < (v). − + According to the functional curves in Figure 1, the expres- sion of variable in six di•erent phases is concluded as = − + g, (2) follows. Accelerating Braking 4 Journal of Advanced Transportation 33kV 33kV Substation Substation Energy ow 1500V Overhead contact line M M Braking Braking Motor Invertor chopper Invertor Motor chopper Pull in Pull out Station Station F´µ¶·¸ 3: Energy exchange between two trains. (a) Constant force accelerating phase: = , >0 where also represents the total simulation period. (b) Constant power accelerating phase: = v /v 3.5. Energy Model for Multiple Trains. Before considering (c) Speedhold phase: =(v) − g() a case of multitrain driving in one network, one should (d) Constant power braking phase: = v /v, <0 ¡rst consider energy regeneration from braking trains. ƒe (e) Constant force braking phase: = braking process converts mechanical energy into electric (f ) Dwelling phase: =0 energy through the overhead contact line. Taking full advantage of this feedback energy can save a large amount ƒe numerical examples based on the data of Shanghai Metro of energy. In most common cases, the feedback energy from Line 1, a network with narrow spacing [10]. Trains drive in braking trains is fully utilized by accelerating trains at the each section in a sequence of accelerating-cruising-braking, same time period. ƒere is another case that energy supply without the repeated accelerating and braking. ƒe cruising exceeds the demand, and extra energy is consumed by the speed v has a one-to-one mapping from the periodic time heating resistors to avoid the voltage increase on the DC , , , . ƒe relation is de¡ned as = v . As shown in side. With the theory shown in Figure 3, it is possible to Figure 2, the area enclosed by the red curve and the axis build an optimal timetable to maximize the utilization of represents the section spacing. If the cruising speed increases, the feedback energy. the periodic time will decrease to keep the section spacing Overall energy consumption of a network is derived as constant. Hence, the arrival time can be deduced from the follows. Calculate the required traction energy and the regen- cruising speed. erated braking energy for train . ƒe traction power at the , , ƒe derivation process of = v is shown in time can be calculated by Appendix A. < 0 (7) ( ) 3.4. Timetable Model for a Single Train. ƒe timetable of a 1 0 ≤ 0, metro-line operation can be modeled as [32] +1, +1, , , where the ¡rst condition denotes train driving in the accel- = + + , (4) erating phase or in the speedhold phase, and the second con- , dition denotes train driving in the braking phase or in the where = at =1. +1, dwelling phase. Hence, by summing over the traction power If a disturbance occurs in a dwell time , then the for train and integrating it for time, total required traction departure instants will be energy for all the trains in the network is acquired +1, , , +1, = + + + . (5) = . ( ) (8) =1 ƒe maximum travel time for whole trains in the metro-line is ƒe braking energy from train at time is −1 , +1, 0 > 0 = + + + , () = (6) (9) =1 −v ≤ 0. 2 Journal of Advanced Transportation 5 ƒe total regenerated energy utilized at time is the minimum stochastic search method for optimization problems inspired between the braking energy feedback and the traction energy, by the process of natural selection. Holland [33] ¡rst used it which is to generate high-quality solutions to optimization problems. With extensive generality and practical applicability, it has obtained considerable success in providing satisfactory solu- (, ) = min (), (). (10) tions to many management problems for railway tra—c. In this =1 =1 paper, GA is used to solve the energy optimization model. ƒe minimum operator is used to distinguish two di•erent 4.1.1. Genotype. ƒe decision variable in this energy conditions. If the traction energy is larger than the regenera- optimization problem is v , a continuous variable changing tive braking energy, the regenerative braking energy will be from v to v . It is di—cult for a genotype covering fully utilized; otherwise if the traction energy is smaller than min max the range of the continuous decision variable. Hence, we the regenerative energy, the extra regenerative braking energy discrete the v , v section and de¡ne a genes set will be consumed by the heating resistors. ƒe total regener- min max g = g g = 0,1,2,..., to correspond the possible values of ative energy for all the trains in the network is the decision variable, where is a positive integer. ƒe possible values of the decision variable is () = (, ). (11) v − v max min v = v + ⋅ g . The net energy consumption for all the trains in the min (14) network is 4.1.2. Chromosomes. A (− 1) × -dimensional matrix is () = − (). (12) used to de¡ne a chromosome, in which is selected from ( ) the genes set g. ƒe objective of energy optimization is to minimize (). = ∈ [1, − 1], ∈ [1, ] , ∈ g. (15) , , ( ) ( ) 4. Energy Optimization with Dwell Time 4.1.3. Initialization. An integer number pop_size is de¡ned as Disturbance the population size of the initial population. pop_size decreases during each successive generation with genetic operators like ƒe objective of the energy-e—cient TTR problem is to min- imize energy consumption by taking full advantage of the crossover and mutation. ( = 0) is de¡ned as the ¡tness function of every individual. An evolutionary computation regenerative braking energy when random disturbances hap- pen. In this paper, a real-time timetable rescheduling method framework based on python named DEAP is used, which contains GA and other advanced evolutionary strategies. ƒe (RTTRM) is proposed to solve the energy-e—cient TTR prob- lem, which combines GA with a decision system, and gives a process of crossover and mutation in GA can be referred to the o—cial documents on Github [34]. proper decision immediately a‘er a random disturbance hap- pens. RTTRM solves the energy-e—cient TTR problem in 4.2. Energy Optimization under Disturbance Situation. ƒe three steps. Firstly, it solves the energy-optimal timetable optimization model mentioned in the second step is under a no-disturbance situation. Secondly, by introducing a formulated as follows: stochastic variable into the dwell time, ensembles of ener- gy-optimal timetable under di•erent disturbances are min () traversed. A decision system based on DNN is trained by the .. ≤ ≤ state variables which are sampled under di•erent disturbances. min max ∀ , , ∈ (1,2,. .., − 2), ∈ (1,2,. ..,) In this step, the schedule before the disturbance instant should 0 0 0 0 +1, +1, , , not be modi¡ed. Lastly, the trained decision system is used to = + + + = , = , 0 0 +1, , , +1, judge which case the disturbance belong to and give an ener- = + + , , gy-optimal solution accordingly. =v (16) v ≤ v ≤ v min max 4.1. Energy Optimization under No-Disturbance Situation. ƒe energy optimization model mentioned in the ¡rst step can be where is not zero but a stochastic variable. GA is also used formulated as follows: to solve the energy optimization problem based on (16). In this situation, the chromosome is not a ( − 1) × dimen- min (=0) sional matrix. ƒe dimension of the chromosome is deter- .. ∈ (1,2,. .., − 1), ∈ (1,2,...,) mined by the value of , . A delay occurs during the time 0 0 +1, , , +1, = + + . , , +1, (13) interval , + + , so the timetable rescheduling , , +1, = v task begins a‘er the instant + + . ƒe optimal inde- v ≤ v ≤ v pendent variables are taken as the reference. Before the delay min max , , happens, the original v deduced from (13) are retained. v ƒis is a one-objective optimization problem with complex a‘er the delay are regarded as the new independent variables constraints that can be appropriately solved by GA. GA is a for (16). Station number 6 Journal of Advanced Transportation Decision network Speed Position Driving state Train number State variables of no-stopping trains DNN Cell DNN Cell DNN Cell DNN Cell DNN Cell DNN Cell Input Voter Selector layers DNN Cell DNN Cell DNN Cell Decide the cruising speed Which train running of the next section at which station DNN Cell DNN Cell DNN Cell (a) NN for the station M and the train N Hidden Output layers layer e detail DNN Cell of a cell (b) F´µ¶·¸ 4: Cruising speed decision system. (a) Structure of decision system and (b) Structure of the DNN cell. 4.3. Deep Neural Network. Deep Neural Network (DNN) [35] selector, a decision network and a voter. Cruising speed has strong generalization ability, and has been widely applied to decision system comes into e•ect a‘er a disturbance occurs. ¡elds including computer vision, speech recognition, natural At the departure instant of each train, the decision system language processing, audio recognition, and board game decides the cruising speed of that train in the next section. ƒe programs, where they have produced results comparable to state variables of other running trains are put into the input and in some cases superior to human experts. Compared with layers. Selector is used to select corresponding DNN cell Shallow Neural Network (SNN) [36], DNN has an excellent according to the train number and the station number at pres- ability of feature learning, and the acquired characteristics ent of the departing train, which e•ectively simpli¡es the can describe the nature of the samples, which is bene¡cial structure of DNN cell. Finally, voter decides the cruising speed to visualization or classi¡cation. ƒe sample capacity and of the departing train. Figure 4(b) shows the detailed structure generalization ability of DNN have been greatly improved for one of the DNN cell, which is trained by GA results at each than SNN. disturbance case. DNN cell is structured according to the In the previous section, a series of sampling data by GA existing sample volume. ƒeoretically, the disturbance cases are obtained, which contains the state variables of all trains in are in¡nite, so the samples obtained by GA are in¡nite. Hence, the network, sampling at each departure instant in di•erent DNN but not SNN is needed to ensure the sample capacity of disturbances, and also contains a series of cruising speed as the decision system. the target of decisions. ƒese data can be used to train a deci- sion system based on DNN which gives wise choice of cruising speed when disturbances happen. Figure 4 displays a structure 5. Experimental Validation of the decision system, which decides cruising speed at each departure instant. In order to validate the real-time timetable rescheduling Figure 4(a) shows the structure of the cruising speed deci- method, a series of numerical experiments are set. ƒe envi- sion system, which contains four parts: an input layers, a ronment for experiments is set in Shanghai Metro Line 1 Journal of Advanced Transportation 7 T¼½¾¸ 1: Optimal timetable of the test segment without disturbance. Dwell time/ Accelerating Cruising time Braking time Cruising speed Section Spacing [m] Train No. headway [s] time [s] [s] [s] [m/s] 1 0 26.5 43.0 19.5 21.36 Xinzhuang to 1458.5 waihuan road 2 120 20.1 61.4 16.3 18 1 20 27.3 25.8 19.9 21.72 Waihuan road to 1125.7 lianhua road 2 20 20.1 43.0 16.3 18 1 20 26.9 19.8 19.7 21.52 Lianhua road to 979.1 jingjiang park 2 20 20.1 34.9 16.3 18 Jingjiang park to 1 20 25.5 41.7 19 20.88 south shanghai 1377.3 2 20 20.1 56.9 16.3 18 railway station South shanghai 1 20 20.1 65.2 16.3 18 railway station to 1526.8 2 20 20.1 65.2 16.3 18.04 caobao road Caobao road to 1 20 20.1 34.1 16 18 shanghai indoor 961.2 2 20 24.6 23.6 18.3 20.4 stadium iterations, the population distribution gradually centralizes. Finally a‘er 15 generations, the population converges at a ¡t- ness value of 286.48 kWh, which is the optimal energy con- sumption without disturbances happen. Example 5.2. ƒis example is based on a two-train network 15th Generation 8th Generation in the 6 sections of SML1. A disturbance is random selected from the discrete point set of (1, 2, . . . , 6s), and the disturbance occurs when Train No. 2 (T2) running at the 2nd station (S2) or at the 3rd station (S3). In each travel, only 3100 1st Generation a disturbance happens. ƒe optimization model is based on Equation (16). In Figure 6, indexes such as energy saving and 0 100 200 300 400 500 600 time consumption are compared between GA and RTTRM. Inviduals ƒe initial population size of GA is set as 200. A‘er 5, 8 and 11 generations, the population size still keeps 200 and the F´µ¶·¸ 5: Population distribution for 1, 10, and 15 generations. ¡tness values gradually improve. Figure 6 (le‘) shows the population distribution in these generations. GA_5gen, GA_8gen and GA_11gen represent the 5th, the 8th and the (SML1), which is one of the oldest metro lines in China. ƒere are totally 28 stations with a daily ridership of over 1,000,000 11th generations o•spring, respectively. Figure 6 (right) shows the calculation time in di•erent methods. passengers [37]. According to the statistical data in peak hours of workday, metro network implement the tight schedule, As shown in Figure 6(a), disturbance occurs in T2S2. ƒe 5th where the average travel time during a section is only 2 min, generation o•spring of GA which distributes below zero, pro- and the uniform interval time between trains is 164 s. At ¡rst, poses a worse strategy than no action. By comparison, the 11th a simple case that two trains run over 6 sections of SML1 which generation has a better performance, which distributed upside to from Xinzhuang to Shanghai Indoor Stadium is analyzed. ƒen the 5th generation and the 8th generation. By comparison a more complex case that three trains run over 13 sections of between the results of RTTRM and the best individual of the 11th SML1, which is from Xinzhuang to Xinzha Road, is analysed. generation by GA, RTTRM averagely saves 0.840% in di•erent Example 5.1. ƒe ¡rst numerical example validates GA in delays, which is lower than GA that saves 1.115% on average. As the energy optimization problem. ƒe experiment is set in shown in Figure 6(b), RTTRM in the T2S3 case has the best per - the 6 sections of SML1. In this case, the headway is set as formance that saves 0.858% energy on average, which is equal to 120 s and the dwell time is set as 20 s. Assuming two trains the best individual of the 11th generation by GA. Comparing driving without disturbance, the energy optimization model from the calculation time both in the Figures 6(a) and 6(b), is based on Equation (13). A‘er 15 generations by GA, the RTTRM has absolute advantage in order of magnitude. optimal timetable is obtained in Table 1. Example 5.3. In this numerical example, RTTRM is validated Figure 5 shows the population distribution of the 1st, 8th in the three-train network in the 13 sections of SML1. In each travel test, a disturbance randomly selected from and 15th generations given by GA. ƒe population distribution of the 1st generation is discrete and stochastic. A‘er 8 (1, 2, . . . , 6s) occurs when the train No.1 stops at the 2nd Fitness 8 Journal of Advanced Transportation –5 600 –10 –15 12 3 45 61 23 45 6 Delays [s] Delays [s] GA_5gen GA_5gen GA_8gen GA_8gen GA_11gen GA_11gen RTTRM RTTRM (a) 10.0 7.5 5.0 2.5 0.0 –2.5 –5.0 –7.5 –10.0 0 12 3456 12 3 45 6 Delays [s] Delays [s] GA_5gen GA_5gen GA_8gen GA_8gen GA_11gen GA_11gen RTTRM RTTRM (b) F´µ¶·¸ 6: Energy saving and time consumption in two-train network. (a) Random delays occur when Train No.2 running at the 2nd station and (b) Random delays occur when Train No. 2 running at the 3rd station. station. Both the GA and the RTTRM are used to generate the comparing Figures 6 and 7, it shows that to increase the number timetable a‘er the delay happens, and then the ¡nal energy of trains in the network, more energy will be saved. According consumption of the metro system is calculated in each strategy to the time consumption statistics, the calculation time to iter- and in each case of delay. ƒe results are shown in Figure 7. ate a suboptimal strategy for the RTTRM is only 0.25 s on aver- age. By comparison, GA takes 4500 s to reach similar e•ects. As can be seen from Figure 7, RTTRM can save 4.354% Example 5.4. ƒis numerical example is based on a three- energy on average in the three-train network, while GA in the 11th generation saves 3.212% energy on average, both of which train network. ƒe changing process of energy consumption during the 13 sections of SML1 among three di•erent save more energy percentage than the two-train network. By Saving energy [kWh] Saving energy [kWh] Time consumption [s] Time consumption [s] Journal of Advanced Transportation 9 0 4000 –50 –100 –150 –200 –250 123 456 123 45 6 Delays [s] Delays [s] GA_5gen GA_5gen GA_8gen GA_8gen GA_11gen GA_11gen RTTRM RTTRM F´µ¶·¸ 7: Energy saving and time consumption in three-train network. T¼½¾¸ 2: Comparison of computation time and energy consump- 3.7s Delay happened at train No.1, the 2nd station tion among di•erent strategies. Index No action GA RTTRM Computation time [s] 0 4512.882 0.203 Energy consumption in 971.763 887.431 887.833 whole journey [kWh] proven to achieve good results in energy saving, but it takes too much time to give a decision. Compared with the two Disturbance happens methods above, RTTRM saves 3.261% of the total energy in this case, and can ful¡ll the real-time requirement in the ener- 0 250 500 750 1000 1250 1500 1750 gy-e—cient TTR problem. Time [s] Table 2 gives the computation time and the total energy No action consumption of these methods. ƒe computation time is GA measured in the CPU Intel i7-4720HQ. RTTRM F´µ¶·¸ 8: Energy consumption during the train driving process in 6. Conclusion di•erent strategies in the case of a random delay happens. In this paper, a real-time timetable rescheduling method for minimizing the overall energy consumption of metro systems methods is compared. ƒe disturbance is set as 3.7 s when under disturbances is proposed. Di•erent from the prevailing Train No.1 stops at the 2nd station. In the ¡rst method, the methods for TTR problem focusing on minimizing the over- train does not take any action when delay occurs. In the all delay, the method focuses on solving energy-e—cient TTR second method, GA is used to give an ošine strategy to cope problems that maximizing the usage of regenerative energy. with delay. In the third method, RTTRM is used to generate ƒe di—culties of energy-e—cient TTR problems are the an optimal timetable in real time. Figure 8 gives the energy demand of real-time response and the randomness of distur- consumption of the whole journey in di•erent methods. bances. Combining GA and DNN, the proposed method can As can be seen from Figure 8, the energy consumption reschedule the timetable in a very short response time and with no-action method maintains as the highest from the have a self-adaptability that is able to make decisions for dif- moment when the delay occurs to the end. ƒe GA method is ferent cases of disturbances. ƒe method is based on three Energy consumption [kWh] Saving energy [kWh] Time consumption [s] 10 Journal of Advanced Transportation , , , , , models: a control model, a timetable model, and an energy where , , , , represent the running distance 1 2 3 4 5 model. ƒe energy model formulates the optimization equa- in the ¡ve phases, which are the constant force acce lerating tions in both cases with and without disturbances. ƒe ran- phase, the constant power accelerating phase, the speedhold domness of dwelling-time disturbances is described in the phase, the constant power braking phase and the constant , , energy model. ƒe most important part of the method is a force braking phase. So the function = v can be GA optimizer and a decision system. GA is used to search an expressed as: optimal timetable for each case of the delay in order to min- v v 1 1 imize the energy consumption as well as extracting the state = v + v variables in each optimal strategy into a training set. ƒe − + g v /v− + g 0 v decision system based on DNN is proposed to give a wise v 0 1 1 + v + v + . advice for the cruising speed according to the state variables v /v− + g − + g v v v samples from GA. (A.9) Several experimental studies are conducted on Shanghai Metro Line 1 to validate the method. Both two-train network Data Availability and three-train network are simulated in the experiments. ƒe results indicate that the decision system is e•ective to select ƒe data used to support the ¡ndings of this study are included suboptimal cruising speed for the energy saving concern. within the article. RTTRM saves 0.840% energy on average in two-train network in the 6 sections of SML1, and saves 4.354% energy on average in three-train network in the 13 sections of SML1. ƒe method Conflicts of Interest only takes 0.010 s in the two-train network and 0.25 s in three- ƒe authors declare that they have no con¥icts of interest. train network on average, which is much faster than GA. A whole journey comparison between RTTRM and GA is done under a 3.7 s disturbance situation. RTTRM saves 3.261% Acknowledgments energy, which is almost equal to GA, but the computation time of the RTTRM is only 0.203 s. ƒe authors would like to acknowledge the fund supported by the Shanghai Shentong Metro Group Co., Ltd., which also provides experimental environment and assistance. ƒe article Appendix was funded by Shanghai Shentong Metro Group Co., Ltd, grant number No. JS-372 KY09R013. Derivation Process According to Equations (1) and (2), the equation is deduced as: References = , (A.1) [1] H. Dong, B. Ning, B. Cai, and Z Hou, “Automatic train control v − + g system development and simulation for high-speed railways,” v IEEE Circuits and Systems Magazine, vol. 10, no. 2, pp. 6–18, 2010. = ⋅ = . (A.2) [2] X. Li, B. Shou, and R. Dan, “Train rescheduling with stochastic v v − + g recovery time: a new track-backup approach,” IEEE Transactions Integral Equation (A.2) as on Systems Man & Cybernetics Systems, vol. 44, no. 9, pp. 1216– 1233, 2017. = v. (A.3) [3] S. Binder, Y. Maknoon, and M. Bierlaire, “ƒe multi-objective − + g railway timetable rescheduling problem,” Transportation ƒe distance in each phase is calculated as: Research Part C Emerging Technologies, vol. 78, pp. 78–94, 2017. v [4] F. A. Ortega, M. A. Pozo, and J. Puerto, “On-line timetable = v, (A.4) rescheduling in a transit line,” Transportation Science, vol. 52, − + g no. 5, pp. 1106–1121, 2018. , [5] L. Wang, W. Mo, Y. Qin, F. Dou, and L. Jia, “Optimization based high-speed railway train rescheduling with speed restriction,” = v, (A.5) v /v− + g Discrete Dynamics in Nature and Society, vol. 2014, Article ID 934369, p. 14, 2014. [6] W. Xu, P. Zhao, and L. Ning, “A practical method for timetable = v, (A.6) rescheduling in subway networks during the end-of-service v /v− + g period,” Journal of Advanced Transportation, vol. 2018, Article ID 5914276, pp. 1–9, 2018. , [7] P. Xu, F. Corman, Q. Peng, and X. Luan, “A timetable = v, (A.7) rescheduling approach and transition phases for high-speed − + g railway tra—c during disruptions,” Transportation Research Record Journal of the Transportation Research Board, vol. 2607, , , , , , = − − − − , (A.8) 3 1 2 4 5 no. 1, pp. 82–92, 2017. Journal of Advanced Transportation 11 [8] P. Dalapati, P. Agarwal, A. Dutta, and S. Bhattacharya, “Real- railways,” Transportation Research Part C: Emerging Technologies, time rescheduling in distributed railway network: an agent- vol. 27, no. 2, pp. 1–15, 2013. based approach,” 2016, https://arxiv.org/abs/1607.03340. [25] D. Šemrov, R. Marsetič, M. Žura, L. Todorovski, and A. Srdic, [9] G. M. S cheepmaker, R. M. P. Goverde, and L. G. Kroon, “Review “Reinforcement learning approach for train rescheduling of energy-eﬃcient train control and timetabling,” European on a single-track railway,” Transportation Research Part B: Journal of Operational Research, vol. 257, no. 2, pp. 355–376, Methodological, vol. 86, pp. 250–267, 2016. [26] T. Albrecht and S. Oettich, “A new integrated approach to [10] C. Gong, S. Zhang, F. Zhang, J. Jiang, and X. Wang, “An dynamic schedule synchronization and energy-saving train integrated energy-eﬃcient operation methodology for metro control,” WIT Transactions on e Built Environment, vol. 61, systems based on a real case of shanghai metro line one,” 2002. Energies, vol. 7, no. 11, pp. 7305–7329, 2014. [27] T . Albrecht, “Reducing power peaks and energy consumption in rail transit systems by simultaneous train running time control,” [11] M. Carey, “Reliability of interconnected scheduled services,” European Journal of Operational Research, vol. 79, no. 1, Computers in Railways, vol. 769, no. 769, pp. 100–107, 2004. pp. 51–72, 1994. [28] X. Yang, X. Li, Z. Gao, H. Wang, and T. Tang, “A cooperative scheduling model for timetable optimization in subway [12] M. Carey and A. Kwieciński, “Stochastic approximation to the eﬀects of headways on knock-on delays of trains,” Transportation systems,” IEEE Transactions on Intelligent Transportation Research Part B: Methodological, vol. 28, no. 4, pp. 251–267, Systems, vol. 14, no. 1, pp. 438–447, 2013. [29] H. Sun, J. Wu, H. Ma, X. Yang, and Z. Gao, “A bi-objective [13] M. Carey and A. Kwieciński, “A properties of expected costs timetable optimization model for urban rail transit based on and performance measures in stochastic models of scheduled the time-dependent passenger volume,” IEEE Transactions on transport,” European Journal of Operational Research, vol. 83, Intelligent Transportation Systems, vol. 20, no. 2, pp. 604–615, no. 1, pp. 182–199, 1994. 2018. [14] J. Törnquist and J. A. Persson, “N-tracked railway traﬃc re- [30] W. J. Davis, “e tractive resistance of electric locomotives and scheduling during disturbances,” Transportation Research Part cars,” General Electric, 1926. B Methodological, vol. 41, no. 3, pp. 342–362, 2007. [31] A. Albrecht, P. Howlett, P. Pudney, X. Vu, and P. Zhou, “e key [15] A. D’Ariano, D. Pacciarelli, and M. Pranzo, “A branch and bound principles of optimal train control part 1: Formulation of the algorithm for scheduling trains in a railway network,” European model, strategies of optimal type, evolutionary lines, location Journal of Operational Research, vol. 183, no. 2, pp. 643–657, of optimal switching points,” Transportation Research Part B: 2007. Methodological, vol. 94, pp. 482–508, 2016. [16] M. B. Khan and X. Zhou, “Stochastic optimization model and [32] V . Van Breusegem, G. Campion, and G. Bastin, “Traﬃc modeling solution algorithm for robust double-track train-timetabling and state feedback control for metro lines,” IEEE Transactions on problem,” IEEE Transactions on Intelligent Transportation Automatic Control, vol. 36, no. 7, pp. 770–784, 1991. Systems, vol. 11, no. 1, pp. 81–89, 2010. [33] J. H. Holland, “Adaptation in natural and artiﬁcial systems: An [17] V . Cacchiani and P. Toth, “Nominal and robust train timetabling introductory analysis with applications to biology, control, and problems,” European Journal of Operational Research, vol. 219, artiﬁcial intelligence,” Ann Arbor, vol. 6, no. 2, pp. 126–137, no. 3, pp. 727–737, 2012. 1975. [18] L. Kroon, G. Maróti, M. R. Helmrich, M. Vromans, and [34] GitHub Inc, “DEAP,” 2019, https://github.com/deap/deap. R. Dekker, “Stochastic improvement of cyclic railway [35] Wikepedia, “Deap learning,” 2019, https://en.wikipedia.org/ timetables,” Transportation Research Part B: Methodological, wiki/Deep_learning. vol. 42, no. 6, pp. 553–570, 2008. [36] M. Bianchini and F. Scarselli, “On the complexity of neural [19] R. K. Ahuja, R. H. Möhring, and D. Z. Christos, Robust and network classiﬁers: a comparison between shallow and deep Online Large-Scale Optimization: Models and Techniques for architectures,” IEEE Transactions on Neural Networks & Transportation Systems, vol. 5868, Springer, 2009. Learning Systems, vol. 25, no. 8, pp. 1553–1565, 2014. [20] S. Cicerone, G. D’Angelo, G. Di Stefano, D. Frigioni, and [37] W ikipedia, “Line1(Shanghai Metro)” , 2018, https://en.wikipedia. A. Navarra, “Recoverable robust timetabling for single delay: org/wiki/Line_1_(Shanghai_Metro). complexity and polynomial algorithms for special cases,” Journal of Combinatorial Optimization, vol. 18, no. 3, pp. 229–257, 2009. [21] C. Liebchen, M. Schachtebeck, A. Schöbel, S. Stiller, and A. Prigge, “Computing delay resistant railway timetables,” Computers & Operations Research, vol. 37, no. 5, pp. 857–868, [22] V. Cacchiani, A. Caprara, and M. Fischetti, “A lagrangian heuristic for robustness with an application to train timetabling,” Transportation Science, vol. 46, no. 1, pp. 124–133, 2012. [23] M. Tormos, A. Lova, Ingolotti, and L. P., “A genetic approach to robust train timetabling, technical report ARRIVAL-TR-0173 arrival project,” 2008. [24] S. Dündar and I. Şahin, “Train re-scheduling with genetic algorithms and artiﬁcial neural networks for single-track International Journal of Advances in Rotating Machinery Multimedia Journal of The Scientific Journal of Engineering World Journal Sensors Hindawi Hindawi Publishing Corporation Hindawi Hindawi Hindawi Hindawi www.hindawi.com Volume 2018 http://www www.hindawi.com .hindawi.com V Volume 2018 olume 2013 www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 Journal of Control Science and Engineering Advances in Civil Engineering Hindawi Hindawi www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 Submit your manuscripts at www.hindawi.com Journal of Journal of Electrical and Computer Robotics Engineering Hindawi Hindawi www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 VLSI Design Advances in OptoElectronics International Journal of Modelling & Aerospace International Journal of Simulation Navigation and in Engineering Engineering Observation Hindawi Hindawi Hindawi Hindawi Volume 2018 Volume 2018 Hindawi www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 www.hindawi.com www.hindawi.com www.hindawi.com Volume 2018 International Journal of Active and Passive International Journal of Antennas and Advances in Chemical Engineering Propagation Electronic Components Shock and Vibration Acoustics and Vibration Hindawi Hindawi Hindawi Hindawi Hindawi www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 www.hindawi.com Volume 2018 www.hindawi.com Volume 2018
Journal of Advanced Transportation – Hindawi Publishing Corporation
Published: Dec 2, 2019
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.