Towards a (Max,+) control theory for public transportation networks

We consider the modelling and analysis of public transportation networks, s uch as railway or subway networks, governed by a timetable. Specifically, w e study a (max,+)-linear model of a generic transportation network and ther eby give a self-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 in the deterministic as well as in the stochastic case. The control problem is here whether a trai n should wait on a connecting train which is delayed. Our objective is then to minimise the propagation of the delay through the network while maintai ning as many connections as possible. With respect to the deterministic con trol problem, we present some recent ideas concerning the use of (max,+)-te chniques for analysing the propagation of delays. Moreover, we show how one can use the (max,+)-algebra to drastically reduce the search space for the deterministic control problem. For the stochastic control problem, we cons ider a parameterised version of the control problem, that is, we describe t he control policy by means of a real-valued parameter, say theta. Finding t he optimal control is then turned into an optimisation problem with respect to theta. We address the problem by incorporating an estimator of the deri vative of the expected performance with respect to theta into a stochastic approximation algorithm.