[pgrouting-dev] Time dependent data and input format

[Stephen Woodbridge]

Jay,

On 4/29/2011 5:34 PM, Jay Mahadeokar wrote:
> Hi,
>
> Lets use this thread for discussion on following points:
>
> 1. What should be the input format for time dependent data?
>
> 2. What are the options to obtain real world time dependent data? If it
> is not freely available, then what are the alternatives to test our
> code?  (randomly generated time dependent data would be rather inadequate)

There are probably fewer free time dependent data source available than 
others, but one that we could potentially use is MassGIS

http://www.mass.gov/mgis/laylist.htm

Look at the infrastructure section and specifically:

# MassDOT Roads - Updated October 2009
# Highway Exits and Routemarker Locations
# Census 2000 TIGER Roads
# Trains
# MBTA Rapid Transit
# MBTA Bus Routes and Stops
# Ferry Routes
# Boston Harbor Water Taxi Stops

This should give use a variety of infrastructure networks that we would 
need to augment with schedule information.

We can get the MBTA bus and train schedules online also.

http://www.mbta.com/

We looked at these doing the multimodal routing last year.

We should be able to find similar data for some other large cities. I 
have not looked for data for say Mumbai or other cities in India but you 
might have some luck if this is of interest.


If you are interested in working with Navteq data, you can register here:

http://www.nn4d.com/site/global/home/p_home.jsp

and then download a city worth of their data, which is primarily 
oriented to the navigable road networks and traffic feeds, but is 
probably less interesting than MassGIS above. The think that would be 
interesting with the Navteq data is that it has the time dependent turn 
restrictions.

We currently only support turn restriction in the shooting start 
algorithm but I would love to see the turn restriction time dependent or 
not get implemented in Dijkstras or A-Star with a clean simple mechanism 
for loading the turn restrictions.



> *Input format for time dependent data:

I would think that you need:

   start_time_and_date,
   start_location,
   end_location,
   options

It you wanted to get fancy, it might be nice to be able to do the 
reverse and say:

   start_location,
   end_location,
   arrival_time,
   options

In this version you would have to figure on the route starting at the 
end and working backwards to the start location to figure on the route 
and the required start time.

> *There has already been a brief discussion on this topic before. A quick
> recap:
>
> According to Stephen:
>
>     * It is better to assume data to be present in a simpler model that
>       is easy to work.
>     * It is better to have 5 simple to work with tables than 1-2 complex
>       ones.
>     * We can then provides data loaders that will convert the data from
>       different format into our designed model.
>
> Daniel had listed many possible scenarios in which time-dependent
> shortest path can be applicable.
>
> *Some Ideas:
>
> *The edge cost will eventually be a function of following (please feel
> free to add any new points):
>
>     * Time
>     * Vehicle type
>
> For time, each discrete time interval can have one entry per edge. If we
> assume t time intervals (which can be as small as 5 minutes as available
> in commercial Navteq time dependent data) there would be |E| * t entries.
>
> For vehicle type again if we consider v vehicle types, there will be
> total |E| * t * v entries.
>
> So, besides the edges table that has entries for every edge and other
> edge related information (like ways in Barcelona dataset), we can have
> another table with columns:
>
>     * EdgeID
>     * vehicleType
>     * TimeInstant
>     * Cost
>
> Once / if we are able to acquire any real world time dependent data, we
> can then write data loaders that would convert the data into our format.
>
> Comments / improvements welcome.

Ok, I want to go back to the purpose of my original statements about 
tables. I'm working under the follow assumptions about how thing will work.

User - application developer, the person build an application using our 
finished pgRouting product.

Client - the person using the application built by "User"

1. the User will take data like from MassGIS and load the network data 
and prep it for pgRouting.
2. the User will take the MBTA bus and train and subway schedules and 
load them into tables the closely reflect the underlying schedule data.
3. the User will develop a stored procedure to read the schedule data 
and morph it into some predefined notion whatever that might be. This 
could be to load it into a more normalized table or it might be to 
service a specific query and return a normalized record.
4. the Client make a route request
5. a wrapper script queries the networks and the schedules and this data 
gets built into a temporary boost graph structures to service this request.
6. results are returned to the Client and stuff is cleaned up.

I think this is basically the same flow we use today in pgRouting with 
the exception of the schedules or whatever time dependent data we have.

And with we are not using schedules and only looking at time dependent 
turn restrictions and oneway streets then I think using the same 
approach is still valid but instead of loading schedule information, we 
would load the turn restriction.

Thoughts?

Regards,
   -Steve

> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev