Optimizing Flexible Train Timetables By Using Alternating Direction Method Of Multipliers

As the most important parts of railway operations and managements,the train timetable is the directive document for coordinating the transportation and production activities of different departments and various types of work,it is also an important bridge between railway operators and travelers.The train timetabling problem is restricted by many complicated constraints and it has been recogonized as an intractable problem in the filed of transportation.In order to decrease the complexity of train timetabling problem,some man-made and relatively thin contraints are imposed to the scheduled trains.However,these enforced and unpractical restrictions limit the utilization of railway capacity,and further lead to a satisfactory optimization plan is difficult to be obtained in the congested rail corridor.In addition,the train scheduling problem is often optimized independently,that is,it only make decision for the train departure and arrival times at each station and other close-related operation processes are ignored.Based on the system-optimized approach,this dissertation particularly proposes a kind of flexible train scheduling optimization framework and investigates the integrated mathematical model for train timetabling and various operation processes.Specifically,the main concerns of the research can be concluded as follows.(1)The precise sovling method based on commercial optimization solver is studied.A general mixed integer programming model is developed by introducing a binary variable on the train departure sequence.The mathematical model considers the actual constraints such as train overtakings,safety operations,train stop patterns and train departure time windows constraints,etc.On the basis of analyzing the complexity of the model,the general optimization solver CPLEX is used to solve the addressed problem.The computational results demonstrate that the precise method is only suitable for the small and medium scale instances,however,more efficient approach should be designed for large scale problems.(2)The train timetable optimization approach based on Lagrangian relaxation is presented.For the existing train scheduling framework,the space-time network is established to illustrate the train transfer of space and time location.By further,the various constraints of train scheduling are converted into the restricted relationship and the essential safety operation constrains are transformed into the incompatible relation among different arcs.Correspondingly,the original optimization objective is translated into the cost of arcs occupied by trains.The Lagrangian relaxation method is used to decompose the original problem into a series of shortest path problems for single train.The computational results show that the traditional optimization framework limits the choice of train path in constructed network,as results,a more flexible and practical optimization framework should be designed.(3)A priority-based alternating direction method of multipliers(ADMM)for flexible train scheduling problems is performed.In order to fundamentally get out of the thorny trouble of the traditional train scheduling,this dissertation proposes a flexible scheduling framework that extends narrow time limitations to one-hour periods.A group of incompatible constraints with a more compact form is formulated to mirror the coupling relation between train headway and regularity requirements.An improved ADMM approach is introduced to relax,agument,linearize and decompose the original problem.A priority-based search sequence is employed by applying the associated dual costs during the solution of train-lever path subproblems individually.Finally,the effectiveness and availability of the proposed approach is demonstrated by a set of numerical experiments.(4)Integrated optimization method for flexible train timetabling and arrival-departure track utilization planning is developed.Under the flexible train timetabling framework,the influence of arrival-departure track utilization planning is considered to assign a feasible station path for each train.A kind of extend space-time network is designed to illustrate the space-time transaction and station track occupation for a train.An incompatible set is introduced to illustrate the coupling relation among each train to occupy the space-time and station resources.Under the optimization framework of ADMM approach,a kind of more reliable heuristic algorithm for generation the local upper bound is proposed.The effectiveness of the proposed approach is verified by a real-world instance.(5)Collaborative optimization method for flexible train timetabling and rolling stock scheduling is studied.A state-space-time three-dimensional network is constructed to capture the space-time path and state selection,which state dimension represents the operation segment of trains.In order to improve the computing efficiency,a kind of network reduction technique is proposed,correspondingly,a specific shortest path algorithm with restrictive conditions is presented.Finally,a heuristic optimization framework based on ADMM method is designed,and its effectiveness is demonstrated by numerical experiments.