A Model,Algorithms and Strategy for Train Pathing

We set 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 we propose 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. We report computational results for several examples. Without the above strategies we found even very small problems intractable. With these strategies we could solve realistic size problems in acceptable times, while exploring more options and trade-offs than do traditional methods. More work is needed and we suggest natural extensions, and directions for further research and development.