A Balanced Traffic Routing Using the Bio-inspired Traversing and Marking Metaheuristics

Received: 5 October 2019 Accepted: 13 December 2019 Recent research focuses on crossing and marking the nodes of a directed graph when it comes to shortest path algorithms. Such behavior is common to animals. Each animal marks its territory using different types of techniques such as smell and sound. In this work, the main idea is to create four populations of marking individuals, two of them looking for the “source—destination” route, and the other two looking for the opposite route. The simultaneous search of these two itineraries (alternating) or one after the other (sequential) are the two variants of this algorithm. To find a route in the urban road network, two populations cooperate, one is installed in the source node and the other is placed in the destination node. As long as there are no meetings between individuals from these two populations, they progress alternately. The first meeting points between individuals form feasible and optimal paths between the starting point and the ending point. Experimental results show that work-linked research is faster, but its risks being blocked, due to competition between individuals on the same path. However, the sequential search is more efficient and it has managed to have all the optimal solutions.