Dynamic Optimal Model and Algorithm for Realtime Train Dispatching System on Single-track Railway

摘要

Computer aided decision system of real time adjusting train schedule is a key part of Railway Computer Aided Traffic Control and Dispatching System. In this paper, the mixed 0-1 linear programming model for adjusting train schedule on single-track railway is set up under the constraints of the station track and the locomotive capacity. Since the complexity of the train schedule adjustment problem is NPC, an effective large system decomposition algorithm, namely Dynamic Area Local Optimal Algorithm is proposed. Branch and bound strategy is used to optimize the local problem. Optimal rules of trains meeting and overtaking location are studied and presented. Effective algorithms with time complexity O(n) and O(pn) are given for feasibility of station track requirement of train operation plan and for adjusting the locomotive routing respectively.