Distributed search in railway scheduling problems

Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction Problems (CSPs). Solving a general CSP is known to be NP-complete; however, distributed models may take advantage of dividing the problem into a set of simpler inter-connected sub-problems which can be more easily solved. The purpose of this paper is three-fold: first, we present a technique to distribute the constraint network by means of selection of tree structures. Thus, the CSP is represented as a meta-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. Then, a distributed and asynchronous search algorithm (DTS) is presented. DTS is committed to solving the meta-tree CSP structure in a depth-first search tree. Finally, an intra-agent search algorithm is presented. This algorithm takes into account the Nogood_message to prune the search space. We have focused our research on the railway scheduling problem which can be distributed by tree structures. We show that our distributed algorithm outperforms well-known centralized algorithms.