Author(s)

DAISUKE TATSUI, TAKETOSHI KUNIMATSU & TAKASHI SAKAGUCHI

Abstract

It is important for railway operators to make suitable timetables. On the assumption that passengers’ train paths are invariant even if the timetable changes, the timetables are determined according to the various statistical data under the current timetable. In planning the timetable, it is difficult to grasp the change of passengers’ paths due to timetable modifications because it is too complex. In this paper, we propose a framework of timetabling with due consideration of the path change and propose a practical timetabling system which can quickly estimate the congestion of each train by using passengers’ origin–destination (OD) data collected by automatic ticket checkers. With the system, timetable planners can interactively make and modify timetables by trial and error while confirming the congestion, and finally, they can reach the most preferable one. In order to realize such an interactive system, it is important to develop a fast estimation algorithm of train congestion. We developed a new shortest path search algorithm to determine which trains each passenger gets on. The algorithm devised based on the Dijkstra method has two features. First, the shortest path search from each node to all the destination stations in the composed graph network is executed only once. Second, overlapping the path searches are omitted using stored information of the shortest paths which have already been searched. By applying this algorithm, it took only about 10 s to estimate the train congestion under a timetable of the whole day on an urban commuter line.

Keywords

Dijkstra method, estimation of congestion, interactive system, passengers’ path, shortest path search, timetabling