Repair-Based Railway Scheduling System with Cycle Detection

Te-Wei CHIANG  Hai-Yen HAU  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.7   pp.973-979
Publication Date: 1996/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence and Cognitive Science
scheduling,  iterative repair,  local search,  

Full Text: PDF>>
Buy this Article

In this paper, we propose an approach for railway scheduling based on iterative repair, a technique that starts with a complete but possibly flawed schedule and searches through the space of possible repairs. The search is guided by an earliest-conflict-first heuristic that attempts to repair the earliest constraint violation while minimizing the value of objective function. Since cycles may exist among a sequence of repairs during the repair process, a cycle detection and resolution scheme is proposed to prevent infinite loops. Experimental results show that the efficiency of the repair algorithm improves significantly when cycle detection is incorporated.