Towards a (Max,+) Control Theory for Public Transportation Networks

We consider the modelling and analysisof public transportation networks, such as railway or subwaynetworks, governed by a timetable. Specifically, we study a (max,+)-linearmodel of a generic transportation network and thereby give aself-contained introduction to the key ideas underlying the (max,+)algebra. We elaborate on the algebraic structure implied by the(max,+)-model to formulate (and solve) the control problem inthe deterministic as well as in the stochastic case. The controlproblem is here whether a train should wait on a connecting trainwhich is delayed. Our objective is then to minimise the propagationof the delay through the network while maintaining as many connectionsas possible. With respect to the deterministic control problem,we present some recent ideas concerning the use of (max,+)-techniquesfor analysing the propagation of delays. Moreover, we show howone can use the (max,+)-algebra to drastically reduce the searchspace for the deterministic control problem. For the stochasticcontrol problem, we consider a parameterised version of the controlproblem, that is, we describe the control policy by means ofa real-valued parameter, say . Finding theoptimal control is then turned into an optimisation problem withrespect to . We address the problem by incorporatingan estimator of the derivative of the expected performance withrespect to into a stochastic approximationalgorithm.