A constraint-based interactive train rescheduling tool

被引：22
作者：
Chiu C.K. [1 ]
Chou C.M. [1 ]
Lee J.H.M. [1 ]
Leung H.F. [1 ]
Leung Y.W. [1 ]
机构：
[1] Department of Computer Science and Engineering, Chinese University of Hong Kong, Shatin, N.T.
来源：
Constraints | 2002年 / 7卷 / 02期
关键词：
Constraint propagation; Search heuristics; Train rescheduling;
D O I：
10.1023/A:1015109732002
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：167 / 198
页数：31
相关论文
共 61 条
[1]  
Baptiste P., Le Pape C., Disjunctive constraints for manufacturing scheduling: Principles and extensions, Proceedings of the Third International Conference on Computer Integrated Manufacturing, (1995)
[2]  
Bessiere C., Cordier M., Arc-consistency and arc-consistency again, Proceedings of AAAI-93, pp. 108-113, (1993)
[3]  
Bisiani R., Beam search, Encyclopedia of Artificial Intelligence, pp. 56-58, (1987)
[4]  
Bitner J., Reingold E.M., Backtrack programming techniques, Communications of the ACM, 18, pp. 651-655, (1985)
[5]  
Borning A., Freeman-Benson B., Wilson M., Constraint hierarchies, Lisp and Symbolic Computation, 5, 3, pp. 223-270, (1992)
[6]  
Carey M., Extending a train pathing algorithm from one-way to two-way track, Transportation Research, 28 B, pp. 395-400, (1994)
[7]  
Carey M., A model and strategy for train pathing, with choice of lines, platforms and routes, Transportation Research, 28 B, pp. 333-353, (1994)
[8]  
Carey M., Lockwood D., A model, algorithm and strategy for train pathing, Journal of Operational Research Society, 46, pp. 988-1005, (1995)
[9]  
Cheng Y., Hybrid simulation for resolving resource conflicts in train traffic rescheduling, Computers in Industry, 35, 3, pp. 233-246, (1998)
[10]  
Chiang T.W., Hau H.Y., Railway scheduling system using repair-based approach, Proceedings: Seventh International Conference on Tools with Artificial Intelligence, pp. 71-78, (1995)
1234567