A model, algorithms and strategy for train pathing

This paper sets out a model, algorithms and strategies for the train pathing and timetabling problem for rail lines of the type normally found in Britain and Europe; that is, lines having separate tracks for trains in each direction. As the pathing problem is combinatorially difficult, it proposes solution heuristics and strategies analogous to those which have enabled ‘expert’ train pathers to plan large-scale complex rail systems by traditional manual graphical methods. This approach also has the potential advantage of facilitating user interaction, understanding and acceptance. The paper reports computational results for several examples. Without the above strategies, even very small problems are found to be intractable. With these strategies realistic size problems could be solved in acceptable times, while exploring more options and trade-offs than do traditional methods. More work is needed and the paper suggests natural extensions, and directions for further research and development.