Recent Changes - Search:
AIfall10 /

Real-timeTransportationRouteSelectionWithTrafficConsiderations

Ke Huang
December 4, 2010

Attach:khuang-fp-writeup.pdf

Overview

This project takes the real-time traffic status as a heuristic of the A* search to find a transportation route between two places. It does not only trying to find a shortest path between two places, but also a more plausible route that has a better traffic condition and then can save your time and money.

Screenshot

Concepts Demonstrated

  • The Uniform Cost Search (UCS) algorithm is used to find the shortest route between two places.
  • A* search is used in real-time transportation route selection, and the traffic conditions are used as the heuristic in the search.

Innovation

This real-time route selection algorithm has a global perspective of the real-time traffic status and it can dynamically give us an optimal route from one place to the other. It does not have the disadvantage of traditional shortest or fastest route policies that the ignorance of traffic condition may lead to a bad route or lead to a traffic jam on the main road.

Technology Used Block Diagram

Evaluation of Results

This program can provide us a total time cost and the total distance from the origin to the destination of both the shortest path search and real-time search with traffic considerations. An average running speed will be calculated as well. We can compare the time cost and average speed between two algorithms. A higher average speed and less time cost can be a good guideline of evaluation.

Additional Remarks

  • We created a map file and traffic file to simulate the real problems. The map and traffic file is tentative and they cannot guarantee to be reasonable.
  • In our simulation, we used a concept of "traffic iteration" that it's a static time interval between two rounds of traffic status. In real world, this time interval is dynamic but it will not affect our algorithm. Since each time the traffic changed, the algorithm will find an optimal route according to the current postion and traffic condition.
  • A lots of tests have been done and the test results showed that the dynamic route selection algorithm can provide us a better route most of the time. But if the traffic status changes rapidly it may give us a lower average speed and higher time cost route. There are two reasons that one is the traffic file cannot give us a real simulation of real traffic. Two, we cannot predict the traffic that a current optimal route may have a severe traffic jam. We believe it can do better with a real map and traffic data.
  • This approach can be applied to other networks like telephone, wireless network and Internet network. Especially for the Internet, the backbone routers can use this approach to choose an approach route and load balance the package flow.