Graph Theoretic Model And Heuristic Algorithm For The Operation Adjustment Problem Of High-speed Passenger Trains

Because the impact of various factors and unexpected events, train will inevitably be disorders during operation, and it will lead to the actual operation deviated from the planned value. The purpose of train operation adjustment is to run according to the published original timetable when delay occurs. Train operation adjustment is aimed to assure the rate of punctuality by means of changing arrival time, departure time and travel time when delay occurs. Actually, train operation adjustment is a very complex issue, and many factors need to be considered, so it belongs to large-scale combinatorial optimization problems. A wide range of researches on train operation adjustment have been done, although it has achieved remarkable success, some deficiencies still exist in the structural model and algorithm.In this paper, we consider the optimal adjustment problem of train operations in one-track one-way line with automatic block signal system. From the combinatorial optimization and methods of train operation adjustment, combined with the practical situation of railway scheduling and the characteristics and optimization strategies of high-speed passenger railway in China, we modify the traditional train diagram and propose an improved graph theoretic model. And with the minimized weighted sums of departure-arrive delays in all stations and travel delays in all sections as the objective function, we propose the corresponding 0-1 integer programming model. Train operation adjustment is NP-hard problem and needs to meet the real-time requirements and related constraints, and solve the result in a very short time. Therefore, this paper gives an approximation algorithm with high solving speed and accuracy. According to the solving process of heuristic algorithm, we program and solve the given example, get the train timetable and corresponding train diagram of high-speed passenger trains at the different time delays, and then we analyze and compare the numerical results. Overall, the proposed heuristic algorithm can effectively make use of redundancy time in stations and segments to carry out adjustments to decrease possibility of train delay occurring, and cause delay losses of train themselves and their follow-up as small as possible.