Balanced traffic routing: Design, implementation, and evaluation

Navigators based on real-time traffic conditions achieve suboptimal results since, in face of congestion, they greedily shift drivers to currently light-traffic roads and cause new traffic jams. This article presents Themis, a participatory system navigating drivers in a balanced way. By analyzing time-stamped position reports and route decisions collected from the Themis mobile app, the Themis server estimates both the current traffic rhythm and the future traffic distribution. According to the estimated travel time and a popularity score computed for each route, Themis coordinates the traffic between alternative routes and proactively alleviates congestion. Themis has been implemented and its performance has been evaluated in both a synthetic experiment using real data from over 26,000 taxis and a field study. Results from both experiments demonstrate that Themis reduces traffic congestion and average travel time at various traffic densities and system penetration rates.