Author(s)

H Izumi & N Tomii

Abstract

Train schedule diagrams, in which various kinds of information about the train operation is illustrated, are by far the most important charts in railways. Although it has become popular to draw them by computers, train schedule diagrams drawn by computers often have defects such as train numbers overlap or train numbers are not so well arranged. We regard the train schedule diagram drawing problem as a sort of edge label placement problem, where a train number is put to the line that denotes the corresponding train as its label. We introduce two types of penalties, namely a static penalty that is calculated from the absolute position of a label and a dynamic penalty that is calculated from the whole arrangement of the labels considering the interrelationship between labels. We have developed a GA based algorithm which searches for an arrangement of labels such that the weighted sum of the static penalty and the dynamic penalty becomes the minimum. We confirmed that the algorithm works effectively through experiments using actual train schedule data.

Keywords