Towards a (Max,+) Control Theory for Public Transportation Networks
Towards a (Max,+) Control Theory for Public Transportation Networks
复制标题
公共交通网络的 (Max, ) 控制理论
DOI：
10.1023/a:1011225209640
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
R. D. Vries
中科院分区：
文献类型：
--
作者：
B. Heidergott;R. D. Vries
我们考虑公共交通网络的建模和分析，如铁路或地铁网络，由时间表管理。具体来说，我们研究了一般运输网络的(max,+)-线性模型，从而给出了（max,+）代数的基本思想的自包含介绍。我们详细阐述了(max,+)-模型隐含的代数结构，以在确定性和随机情况下制定（和解决）控制问题。这里的控制问题是一列火车是否应该等待延误的联运火车。我们的目标是在保持尽可能多的连接的同时最小化延迟在网络中的传播。对于确定性控制问题，我们提出了一些关于使用(max,+)-技术来分析延迟传播的最新想法。此外，我们还展示了如何使用(max,+)-代数来大幅减少确定性控制问题的搜索空间。对于随机控制问题，我们考虑控制问题的参数化版本，也就是说，我们通过实值参数（如Θ）来描述控制策略。找到最优控制就变成了一个关于Θ的优化问题。我们通过将预期性能相对于Θ的导数的估计量纳入随机近似算法来解决这个问题。
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.