A Constraint Satisfaction Method for Train Assignment Problem


Ryuji TSUCHIYA, Hiroyasu OSADA
This paper proposes a constraint satisfaction method which is applicable to the train assignment problem. The ultimate goal of train assignment is to find an optimal (or near-optimal) assignment of "physical " trains to a set of train usage patterns. Our method is based on goal-directed search. Required properties of good solutions are captured as a goal and the generation of a goal invokes a constraint propagation procedure which tries to satisfy the specified goal. Our program proved to generate satisfactory solutions in a reasonably short period of time.