Rush Hour – in depth

Algorithm

We use the A* algorithm along with backtracking, for searching the best path from source to destination. We want to find the path that takes the minimum time.

  • Let f(x) be the time function that we want to minimize using A*.

f(x) = g(x) + h(x), whereg(x) = distance(A,B)/TrafficSpeed(A,B) and the heuristic

h(x) = distance(B, GoalNode)/SpeedLimit

distance(A,B) = the great circle distance between point A and the neighbor point B,

TrafficSpeed(A,B) = speed of traffic between points A and B, obtained from Here Traffic API.

SpeedLimit is in kmph, and is obtained from the OSM database.

The great circle distance is the shortest distance between two points on the surface of a sphere.

It is given by the following formula:

where Φ1, 𝝺1 and Φ2, 𝝺2  are the latitude and longitude of points 1 and 2 and ΔΦ and Δ𝝺 are their absolute differences. Δ𝞼 is the central angle between them.

  • We start searching for the path at the start of the departure window. This is important because we will need the approximate traffic data at that particular time, which we solicit from the API. We keep searching for a path which starts in the user’s departure window and ends within the user’s arrival window. We have a lookup table, which has the traffic information for the whole day, at one minute intervals. We will need this to get the traffic information at different points in time.
  • h(x) is admissible as the great circle distance (analogous to Euclidean distance) will always be smaller than actual path distance and the speed limit will always be greater than the actual speed of the vehicle.
  • As mentioned above, we sometimes ran into dead-ends while searching for the best path. In such cases, we backtrack on the path which has been searched until then, until we are able to provide an alternate path to search on. Sometimes, the dead-ends are too far along a way, and backtracking will take a lot of time. Case in point – by mistake the search got onto a railway track, and the dead-end was encountered a long way away from the beginning of that track, where we could have gone on an alternate route. Backtracking took a lot of time, time we could have saved. In such cases, we tag the beginning node of the railway track with some tag. Then while searching for the path, we check for this tag and don’t go there if this tag is present.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s