Research About Branch-and-bound-based Real-time Train Predictive Scheduling

Centralized Traffic Control System(CTC), or Centralized Train Control System, is a general term of the technical equipments by which the control center can manage the signaling devices and command train operation in the dispatching area. In China, under the complex railway network, composed of high-or middle-speed passenger trains and low-speed freight trains, train operation is often disturbed by the complicated conditions and then deviates from the scheduled timetable. Potential collision and crash accidents would happen if there was no rescheduled train operation plan. So, when the actual train operation'deviates from the original one, the optimization computing should be required accomplishing for the train operation adjusted schedule by CTC system in real time so as to satisfy the real-time and optimality requirements.The paper attempts to propose the theory and methodology with regard to the real-time train predictive scheduling based on the branch-and-bound approach. The main contents are as follows:(1) Based on the job-shop scheduling theory and alternative graph theory, the mathematical description and model for train operation and scheduling have been established. The passing of a train through a particular block section is called an operation. The operating time is the travel time in the block section. There is a basic constraint in the model that a block section can only be occupied at most by one train at the same time. In the end, the branch-and-bound rules have been proposed to simplify the computing based on the model.(2) Associated with the typical examples, the main idea of branch-and-bound algorithm is expatiated. Then, the branch-and-bound algorithm is applied to the train scheduling. When a potential conflict in front of the running train is predicted, the branch-and-bound algorithm is applied to search the optimal solution for rescheduling train operation plan. In the search process, the upper bound and lower bound of the train travel time, as well as the alternative-graph-based branch-and-bound rules, are used to cut the branches dissatisfying the conditions to reduce the search time and ensure the real-time character of train scheduling. The algorithm realization is represented, and its feasibility is testified utilizing illustrative examples.(3) According to the coordination of the regional and global scheduling, multi-region coordination principle is elaborated. In the principle, a node deletion rule is expressed to simplify the alternative graph model. A border graph model is generalized from the simplified global graph model. Finally, according to the border graph model we can judge whether it is coordinate or not between regions'schedules. This has been testified through resolving the illustrative examples.(4) Using C++language, the train operation dispatching simulation platform has been built in the MFC environment. On the platform, we simulate a big railway network and do an experiment. The feasibility of the model and algorithm proposed in this paper has been proved.