A constraint-based interactive train rescheduling tool

C. K. Chiu, C. M. Chou, J. H.M. Lee, H. F. Leung, Yiu Wing LEUNG

Research output: Contribution to journalJournal articlepeer-review

27 Citations (Scopus)


In this paper, we report, the design and implementation of a constraint-based interactive train rescheduling tool, a project in collaboration with the International Institute for Software Technology, United Nations University (UNU/IIST), Macau. We formulate train rescheduling as constraint satisfaction and describe a constraint propagation approach for tackling the problem. Algorithms for timetable verification and train rescheduling are designed under a coherent framework. Formal correctness properties of the rescheduling algorithm are established. We define two optimality criteria for rescheduling that correspond to minimizing the number of station visits affected and passenger delay respectively. Two heuristics are then proposed to speed up and direct the search towards optimal solutions. The feasibility of our proposed algorithms and heuristics are confirmed with experimentation using real-life data.

Original languageEnglish
Pages (from-to)167-198
Number of pages32
Issue number2
Publication statusPublished - 2002

Scopus Subject Areas

  • Software
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Artificial Intelligence

User-Defined Keywords

  • Constraint propagation
  • Search heuristics
  • Train rescheduling


Dive into the research topics of 'A constraint-based interactive train rescheduling tool'. Together they form a unique fingerprint.

Cite this