Models And Algorithms For Urban Rail Transit Train Timetable Optimization

In urban rail transit systems,train timetable is the basis for transportation operations.As the scale of urban rail transit network continues developing,and passenger demand of rail transit systems continues increasing,train timetable(re)scheduling has become a large and integrated optimization problem.However,due to major passenger demand fluctuations and frequent train interactions,the train timetable optimization problem has still been deemed complex and received considerable attention from both researchers and engineers.To further investigate the train timetable optimization problems,this dissertation proposes a discrete time-based network that discretized system elements.Based on the definition and characteristics of the network's elements,this dissertation then formulates the optimization models and designs corresponding algorithms.The content consists of integrated optimization and train flow simulation at the train scheduling stage,and delay identification and propagation analysis,as well as train flow adjustment at the train rescheduling stage.Specifically,the main works and contributions of this dissertation are as follows.1.This dissertation improves the discrete time-space graph proposed by Caprara et al.(2002),and analyzes the train dwell process based on time-varying passenger demand and passenger boarding/alighting rates.Based on the discrete time-space graph,this dissertation formulates the optimization model,whose objectives include passenger time cost,energy cost,and train cost associated with fleet size.The model considers the effects of frequency on those objectives.In addition,the solution approach in this dissertation consists of branch and bound,frequency determining and rolling optimization,which is effective and efficient for scheduling trains.Particularly,the rolling optimization method considers the property of the objective function,and reflects the effects of different factors on departure headways,such as passenger demand and train travel time.Numerical results demonstrate that the proposed model accurately depicts the impact of peak-hour passenger demand on train dwell time.The proposed solution approach responds well to passenger demand distribution,and can save up to 95%computation time compared to classic algorithms such as generic genetic algorithm and integrated Augmented Lagrangian-Pattern Search algorithm.Besides,the non-cyclic timetables obtained in this dissertation can save up to 9.09%passenger wait time compared to classic algorithms,and up to 27.37%passenger wait time compared to cyclic timetables,while the given passenger demand is satisfied,and the energy and train costs are nearly the same.2.Based on train dynamic equations,this dissertation proposes a discretetime-operation graph whose horizontal axis represents discrete time and vertical axis represents train control,which describes the relation between speed profile and energy consumption.Based on this graph,this dissertation analyzes train dynamic characteristics,formulates the simulation model,and proposes a simulation algorithm that considers energy-efficient train control and line constraints.Numerical results show that the proposed simulation method is effective and efficient to simulate train motions under different line conditions.Compared to the best results obtained by classic methods,the simulation results obtained in this dissertation can save up to 3%energy without considering line constraints,and up to 10%energy when line constraints are considered.In addition,the simulation results in this dissertation have advantages in issues including safety,passenger comfort and practicality.The simulation results can be used to test the robustness of timetables,and provide decision support for further train timetable optimization.3.Based on the train operation data with discrete time,this dissertation proposes a train state graph whose horizontal axis represents discrete time and vertical axis represents train index.In the graph,nodes represent critical elements during train running,and arcs represent relations between those elements.Based on different definitions of nodes and arcs in the rail network scenario and the urban rail transit scenario,this dissertation formulates different optimization models in both scenarios.Then,a critical path algorithm is designed,which traces back along the nodes and arcs until the primary delay is found.Based on the search result,the propagation of primary delays can be analyzed.Numerical examples indicate that the proposed critical path algorithm accurately finds primary delays,and the path elements provide delay information including the affected times,train indexes and section/station indexes,which is crucial for delay propagation analysis and further rescheduling.In addition,after the primary delays are dealt with,the reduction rates of energy and travel time can be more than 20%and 10%,respectively.4.Based on the train state graph,this dissertation proposes a train rescheduling model,and a two-stage optimization algorithm.In the first stage,the critical path algorithm is further improved,which can search the delays in parallel among simulation results.Different critical paths provide different delay information associated with different primary delays.In the second stage,this dissertation designs a hybrid genetic algorithm integrated with the information search process.The hybrid genetic algorithm uses critical path results as input,and set the minimum gene values based on the simulation results.In this way,the algorithm not only reduces the scale of decision variables,but also reaches the convergence faster.Numerical results demonstrate that the proposed algorithm is effective and efficient to reschedule affected trains with practicality(least changes),while considering both optimization objectives and train control.Compared to the original timetable,the rescheduled timetable in this dissertation saves more than 15%delay and energy costs.Compared to the generic genetic algorithm,the proposed algorithm saves more than 75%computation time,and reduces 10%more total cost.