Train schedule diagrams, in which versatile information about train operation is contained, are by far the most important charts in railways. Although it has become popular to draw them by computers, their outputs often have deficiencies such as train numbers overlap. We regard the train schedule diagram drawing problem as a sort of the edge label placement problem, where a train line is labeled with the corresponding train number at an appropriate position. In order to determine the appropriate positions of labels, we have introduced static penalty and dynamic penalty. And we have developed two algorithms:one, and algorithm based on GA and the other, that based on probabilistic local search. Both algorithms search for an appropriate arrangement of labels such that the weighted total penalties become the minimum. We confirmed that the both algorithms work effectively through experiments using actual train schedule data.

Copyright (c) 2006 Railway Technical Research Institute