A linear programming based decentralized routing controller for congested highways

Abstract

A decentralized controller for dynamic routing in multidestination trasportation networks is presented. The proposed algorithm is especially suited for congested networks, where the traffic demand is close to or more than (at least for some duration of time, e.g., during a rush hour) the total capacity of the network. The basic aim of the introduced approach is to avoid queue build-up for as large external arrival rates as possible. It is shown that this problem can be formulated as a linear programming problem, and can be solved off-line. The proposed controller is decentralized in the sense that all the on-line computations are done locally at the nodes without any information transfer from the other nodes. Furthermore, no synchronization among the nodes is needed. The controller guarantees stability and clears the queues of the network in finite time assuming that the external arrival rates do not become larger than a maximum value. The controller also avoids looping