On large scale max-plus algebra models in railway systems

A large scale model of time table of all train connections of the whole Dutch railway system will be given in terms of the max-plus algebra. We will design a timetable from the premises that the "lines" (i.e. route structure) are fixed and the numbers of trains along each line are given. Besides, the travelling times between stations are assumed to be fixed. Such a model is written as a set of first order difference equations in the so-called max-plus algebra. This model turns out to be high dimensional, and sparse matrices techniques are used for the calculation of the critical circuit of the system. This critical circuit is a measure for the performance of the total system. We also study the optimal allocation of trains (when the total number of trains along all lines is given, but not the a priori distribution over these lines). Copyright (C) 1998 IFAC.