UWE Bristol Scientist publishes book exploring practical applications of graph theory

Posted on
Image showing the book cover

UWE Bristol’s Dr Vadim Zverovich, Senior Lecturer in Operational Research, has recently had his new book published – Modern Applications of Graph Theory. The book discusses many cutting-edge applications of graph theory, such as traffic networks, navigable networks and optimal routing for emergency response, placement of electric vehicle charging stations, and graph-theoretic methods in molecular epidemiology. Due to the rapid growth of research in this field, the focus of the book is on the up-to-date development of these applications and the mathematical methods used to tackle them.

One of the topics discussed in the book is devoted to the well-known Braess’ paradox in traffic networks. Braess’ Paradox illustrates situations when the addition of another road link or route, with the intention of improving traffic flow, actually has the opposite effect of causing more congestion. This is because drivers generally choose their own driving routes when making their travel plans, without thinking about the traffic flow for all drivers, so that the road system as a whole does not operate optimally.

Deeper insight into this paradox from the viewpoint of the structure and characteristics of road networks may help transport planners to avoid the occurrence of Braess-like situations in real-life networks. If the analysis of all performance measures in a road network is done before the construction of a new road, then a huge amount of money and time can be saved. One relevant example is a demolition of a motorway section in Seoul in 2003, which improved travel time in the local network and resulted in a restoration of a river under the motorway (see Figure 2). The demolition and restoration costs were £201 million, not including very high construction expenses and upkeep of the river. Although it is generally believed that this is a real-life example of Braess’ paradox, it was not proved mathematically that the paradox actually occurred in this road network.

“The Cheonggyecheon river in Seoul: before (left picture) and after (right picture)

A generally accepted belief is that Braess’ paradox is wide spread. This was confirmed by some researchers who claimed that the likelihood of the paradox is 50%, or even higher under some assumptions. However, Dr Zverovich proved mathematically that typical probabilities for Braess’ paradox to occur in classical road network configurations do not exceed 10%.  In addition, the probability of Braess’ paradox to occur is 6% in the classical network configuration consisting of motorway sections and class A roads. Notice that for traffic networks consisting of motorway sections, class A roads or a mixture of both, statistical tests showed that the distribution of parameters of travel time functions follow the Erlang-k distribution for small values of k.

Examples of the Erlang-k distribution for the parameters of travel time functions of motorway sections and class A roads.

Congratulations to Dr Vadim Zverovich on his recent book success.