Models for predicting traffic

Title: Models for predicting traffic.

Author(s): Ángela Jiménez-Casas (Universidad Pontificia de Comillas), Aníbal Rodríguez-Bernal (Universidad Complutense de Madrid-ICMAT)..

Source: Mathematical Methods in the Applied Sciences, Volume 40, Issue 11. Pages 3982–4000.

Date of publication: 30th of july 2017.

Abstract: In today’s society, objects, goods, supplies and information are constantly being moved around through distribution networks. These include, for example, internet comunication, the delivery of merchandise, the motion of vehicles, aircraft and so on. Yet in spite of the diversity of these examples, they can all be approximated, modelled and dealt with mathematically in a more or less unified way.

In their article “Some general models of traffic flow in an isolated network”, Ángela Jiménez-Casas, a researcher at the Universidad Pontificia de Comillas (UPoC) and Aníbal Rodríguez-Bernal, a professor at the Universidad Complutense de Madrid (UCM) and ICMAT member, describe these general processes in which traffic is carried on networks connected to emitter/receiver control centres along traffic paths.

The network along which traffic passes is represented by a graph consisting of a series of nodes (emitter/receiver traffic control centres) interconnected by means of oriented routes or paths. This means that a route that joins node A with node B can be differentiated from another route linking node B with node A; in mathematical terms they are represented by oriented edges. It is along these edges that certain objects travel between the nodes. The objects leave some nodes and travel towards other nodes, and they may remain in a node for a certain time before leaving again for another. This motion of objects on the graph is denoted as traffic.

The nature of the objects under consideration and the way they travel along the network are certainly different from one case to another, and this difference translates into different types of mathematical models. In the article in question, the authors consider that the traffic on the network obeys the following principles:

  • The nodes are connected together by well-defined oriented edges along which the objects travel. Traffic occurs only along these edges.
  • There is at most only one oriented edge between two different nodes.
  • The path of each object on the graph originates at one of the nodes (departure node) and ends at another node (arrival node). Each object many remain “stored” at one node before travelling to another node.
  • Only objects that have previously been at a departure node can travel along one edge of the graph.

    These straightfoward principles described some types of traffic very well; for example, aircraft travelling between airports, trains between stations, ships between sea ports and supply dis- tribution networks. In other cases, such as cars travelling along streets and roads, it is difficult to accommodate them to these principles because cars are able to stop at any point before arriving at their destination, and thus do not flow from node to node without stopping. The same may be said of the flow of bits on the internet, since new packets of bits may originate in any computer connected to the network and no departure node exists. Further more, between two computers connected to the network, there is no single path that carries information from one computer to another. Despite these limitations, these ideas can be used to model a large number of such situations

    To this may be added a fifth principle, which enables the model to be simplified in an initial approximation:

  • Any object takes a known and constant amount of time to travel along an edge joining any two nodes. Likewise, the time that any object remains stored at one of the nodes before continuing is fixed.

These principles can be translated directly to a series of integral equations that describe at each moment the number of objects present on any edge and at any node. Only new magnitudes appear in the equations, and they are the rates at which objects at one node leave for another. These departure rates are the number of objects that leave (to each of the other nodes) per unit of time. They are defined at each moment by controllers located at each node. These departure rates being known, the traffic flow on the network can be determined at each moment in time with the sole knowledge of how many objects there are at each node and along each edge.

The next step consists in the assumption that the departure rates are calculated in terms of the traffic values (that is, the number of objects at each node and on each edge), so that a system of supervision (either automatic or human) for the traffic can be designed. This introduces into the problem the decision operators at each of the nodes, which on the basis of the traffic information determine the departure rates. This then makes the above-mentioned integral equations implicit. These are equations in which the unknown functions satisfy certain relations that involve them themselves. Thus, they are neither “cleared” nor given by an explicit formula that can be computed.

The existence of solutions to this system is demonstrated in the article. In this model, the decision operators use the traffic information in a period of time to determine the departure rates at a given moment. This transforms the implicit integral equa- tions into delayed functional equations in which the value of an unknown at a given moment is determined by the value of the unknown at a certain time or previous period of time.

The case in which the information used by the decision operator is only the number of objects at that node serves to reduce the number of unknowns in the problem, since the traffic along the edges is explicitly determined by the number of objects at each node.

Certain general conditions (known as Lipschitzianity conditions) for the decision operators are assumed in this article, in which it is shown that the resulting models are well thought out and obey the principle of fleet conservation; that is, that the number of objects travelling through the network does not depend on time. The authors have analyzed in greater detail some cases of linear decision operators in the nodes, for which they have studied some properties of time-independent solutions, the socalled equilibrium solutions. They have also demonstrated that if non-updated traffic information is used for decision-making the system may crash in a finite period of time, in the sense that the number of objects at a node becomes negative. On the other hand, if up-to-date traffic information is used for decision-making, solutions exist for all times. This means that traffic flow over the network will function at all times with the chosen set of automatic decision-making rules.

The models outlined in this article differ from previous ones that describe the spatial distribution of objects along the edges of the graph, in which the unknown functions therefore incorporate a spatial as well as a temporal dependence. This means that the resulting models become systems of first-order partial differential equations in the graph, which enables the spatial behaviour of traffic to be described as well as predicting and controlling spatial gridlock (bottlenecks), and thus making it possible to study both the causes and solutions by means of mathematical models.

On the basis of these results, the researchers could consider the design of automated rules of decision-making to enable traffic on the network to behave in a predetermined manner. Operation- al restrictions could also be introduced into the problem, such as limiting the maximum volume of traffic at each node and/or edge and studying the long-term behaviour of traffic for some reasonable class of decision operators. Likewise, it would be interesting to analyze the case in which the journey time of each edge is not constant, but rather a random variable with small fluctuations on a mean value.