An optimal rescheduling for online train traffic control in disturbed situations

A practical method for generating optimal schedules for online train traffic control in disturbed situations is proposed. This scheduling problem is formulated to a 0-1 mixed integer programming problem. The method of solution proposed here is mainly divided into two parts: the first part generates a suboptimal solution by a heuristic method based upon "Production System", and the second produces an optimal one by the branch-and-bound method using the above sub-optimal value for the initial bound. It is shown that each subproblem generated in the second part, which is a linear programming problem, can be easily calculated without using the ordinary simplex method. Some examples show that the proposed method has enough efficiency for practical use in both computational time and storage.