A two-phase mathematical programming approach to rolling stock circulation

This paper considers Rolling Stock Circulation Problem (RSCP) in Japan. RSCP is known as a problem to determine an assignment of rolling stock to trains shown on the timetable. However, previous studies outside Japan cannot be applied to the case in Japan because the management policy for rolling stock in Japan is different from those in previous works. In this paper, we propose a two-phase approach to RSCP in Japanese railways. The problem is to find a schedule to cover all trains on the timetable by train compositions, which are a minimal unit assignable for each train and composed with several carriages. The objective is to minimize the total mileage of ‘out-of-service’ which is train movement carrying no passenger. In the first phase, one-day schedules for each train composition are found. This problem is to find paths in a network, where an intermediate node corresponds to a certain train and an arc corresponds to a possible connection between two trains and the source and sink are dummy nodes corresponding the beginning and ending of a schedule for a certain train composition in a day, respectively. The problem is to find paths by which every node is covered exactly once except for the source and sink node. In the second phase, a schedule circulating these one-day schedules obtained in the first phase is found by solving an integer programming problem so as to satisfy the constraints of the periodic maintenance. Computational experiments are performed based on instances from lines in Japan. The results suggest that our approach is efficient and effective. It can give good schedules in relatively short computing time. Also, we show a minor modification to our approach for giving a better solution for a certain kind of instance.