Time Dependent Shortest Path Algorithm Overview

As mentioned in my last post, I will be doing Google Summer of code project for pgRouting. Here, I will give an overview of the algorithm implementation.

pgRouting is a C++ library that provides routing functionality for postgres. I will be extending it so that it can support time dependent routing. An abstract overview of the idea is:

• The time dependent data will be queried from postgres database.
• Using the information, a graph will be generated
• The core time dependent dijkstra algorithm will be run on the graph
• The result will be returned

The input to a time-dependent shortest path problem is a directed network G = (N,A) and an arrival time function aij(t) for every arc  (i, j) ∈ A. The quantity aij(t) gives the time of arrival at j if one departs from i at time t. It is assumed that aij(t) ≥ t.
The function aij(t)−t gives the travel time along arc (i, j) if one departs at time t.

If aij(t) is non-decreasing for all (i, j) ∈ A, we say that G is a FIFO network, since in this case commodities will travel through arcs in a First-In-First-Out manner. If this is not the case the problem will be NP Complete. We will therefore assume that G is a FIFO network.

Let P(s, d) denote the set of paths between a source node s and a destination node d. The function EAsd(t) = min{ap(t) : p ∈P(s, d)} gives the earliest arrival time at node d if one leaves s at time t

The pseudo-code for solving the Single source – destination query is as follows:

Initialization:

For all i ∈ N\{s} : EAsi(t)←∞
EAss(t)←t
S ←N

Main Loop:

While S != ∅
Select i ∈ S minimizing EAsi(t) S ←S\{i}
For all j such that (i, j) ∈ A
EAsj(t)←min{EAsj(t), aij(EAsi(t))}

This will be basically a SQL C function for postgres. More updates to follow…

IITK Hall – 4, Second home!

In IIT Kanpur, we call hostels – Halls of Residence. I live in Hall-4 and it is one of the most beautiful places where you can wish to live. The following quote taken directly from the new Hall-4 website.

Almost centrally located amongst the student hostels of IIT Kanpur, Hall 4 enjoys a unique repute of having most of the distinguished alumni of the institute as its ex-residents. The spirit of Hall 4 lies in its policy of social activism, intellectual contribution and the diverse tapestry of cultural fragrance. Said to possess some of the most forthright group of students, the Hall has in the past taken major social initiatives and proposed solutions to the institute regarding various issues including the proposal of a new mess model. The Hall is proud to have the student gymkhana constitution being modelled after its own constitution.

The hustle and bustle that goes on in the Hall quad goes on to late nights and sometimes even very early mornings, accompanied by sips of tea and coffee in the Hall 4 canteen. A very different and focused group of students carry on playing shots at the Billiard room, which is the only such facility in any of the student hostels of the institute. While the residents of the Hall have taken patents for their research work and contribute to various symposiums, conferences and journals in academics, an interdisciplinary camaraderie is also seen amongst the residents of the hall.

Things which I like here?

• Mess Food – It is awesome. Before coming here I had heard stories of people describing how ugly hostel food is. Believe me, I love it here. (Specially Friday night). Have a look into the Hall 4 Mess menu. (mouth watering )
• Facilities – You name any sport and you can play it here. Facilities are really awesome. Since it is the oldest hostel in IITK, it does not have the modern spacious feel to it as some of the newer halls do, but still I like it!
• Canteen – If you ever get bored of mess food, you have the canteen! Beautifully located near the lawn, it is the perfect place to have the “DPs” after midnight! All the birthday celebrations and the GPLs are done here. Special mention to Ranjit who brings the DP and the new “Rahul”.

 

PS: I will duly remove the above quotes if I am not allowed to copy the content here. Please mention it as a comment.