A Constraint-Based Interactive Train Rescheduling Tool

. In this paper, we formulate train rescheduling as constraint satisfaction problem and describe a constraint propagation approach to tackle it. Algorithms for timetable verifications and train rescheduling are designed under a coherent framework. We define two optimality criteria that correspond to minimizing passenger delay and the number of station visit modifications respectively for rescheduling. Two heuristics are then proposed to speed up and direct the search towards the optimal solutions. The feasibility of our proposed algorithms and heuristics are confirmed with experimentation using real-life data. Keywords: Rescheduling, Constraint Propagation, Variable and Value Ordering 1 Introduction The PRaCoSy (People's Republic of China Railway Computing System) project [10] is undertaken by the International Institute for Software Technology, United Nations University (UNU/IIST). The aim of the project is to develop skills in software engineering for automation in the Chinese Rai..