A new Probabilistic Extension of Dijkstra’s Algorithm to simulate more realistic traffic flow in a smart city.

Abstract

Dijkstra’s algorithm to solve the shortest path problem (SPP) is a very well-known algorithm. When applied to real situations, although the shortest path can be computed with Dijkstra’s algorithm, it is not always the one that is chosen. In traffic situations, for example, the driver may not know the exact length of the lanes or the shortest path to follow. Even more compelling is the fact that although the driver knows the shortest route, he/she may prefer choosing a different route. In this paper we present the new algorithm PEDA (Probabilistic Extension of Dijkstra’s Algorithm) which introduces probabilistic changes in the weight of the edges and also in the decisions when choosing the shortest path. When PEDA is applied to traffic flow, more realistic simulations, in which the shortest path is not always chosen, are obtained. This more accurately simulates the more normal behavior of drivers. As an example of an application, we introduce the ATISMART+ model, an extension of the ATISMART model, where an accelerated-time simulation of car traffic in a smart city was described. In that previous work, all cars in the system used Dijkstra’s algorithm to choose improved ATISMART+ model, for accelerated time simulations of traffic flow in smart cities, uses the new PEDA algorithm. The results obtained show that ATISMART+ produces more realistic simulations considering different drivers’ behaviors.