For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Repair-Based Railway Scheduling System with Cycle Detection
Te-Wei CHIANG Hai-Yen HAU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/07/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence and Cognitive Science
scheduling, iterative repair, local search,
Full Text: PDF>>
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.