An Optimal Path-Finding Algorithm in Smart Cities by Considering Traffic Congestion and Air Pollution

Abstract

Finding the shortest and cleanest path in the cities is vital, especially in metropolises. Although several algorithms and some software have been introduced to manage the traffic or suggest a path with minimum traffic congestion, none considers air quality a deciding factor. This paper introduces a novel algorithm to find the shortest path based on traffic congestion and air quality. In the proposed algorithm, the city map is fetched from the Google Map app and is converted into a weighted graph. Traffic data is collected from GPS devices, which will be available through the local cloud services. The C-means clustering method is used to cluster traffic congestion. Also, the air quality information is collected from air pollution monitoring stations. The graph weights are calculated based on both air quality and traffic congestion factors, simultaneously. Finding the shortest path problem is then defined as an optimization problem, and the linear programming method is used to solve it. Finally, the proposed algorithm’s performance is evaluated by finding the shortest path in Tehran, Iran in different scenarios.

Keywords

• Intelligent transport system
• air pollution
• traffic congestion
• C-means clustering