MODELLING AND SOLVING THE TRAIN STOP DEPLOYMENT PLANNING PROBLEM

摘要

When an accident occurs on a railway line, it results in every succeeding train stopped at appropriate locations. It is a difficult task for train dispatchers to determine how to rearrange train operations since there are many constraints such that a local train should not block the track for succeeding express trains: such problems are termed as deployment planning of suspended trains or train stop deployment planning problem. In this paper, we modelled a problem as a Petri-net model and formalized it as an integer-programming problem. Based on the modelling and formalization, we introduced an algorithm to locate the suspended train operations appropriately. The algorithm comprises two different stages. At the initial stage, it tries to find an optimized deployment. If the first attempt failed to find a feasible solution, the algorithm alleviates such a constraint that the train must stop at a station provided with a platform. Then, the algorithm tries to find a solution of the alleviated problem at the second stage. As a result, the algorithm is able to find a substantial deployment of train stops. Several numerical experiments with available data have proved that the algorithm works effectively to find a practical solution to the problem.