[pgrouting-dev] Support for Time Constraints

[Stephen Woodbridge]

Correction: TMC - Traffic Message Channel or Traffic Management Center

On 5/27/2011 10:18 AM, Stephen Woodbridge wrote:
> Jay,
>
> Trying to narrow down some google searches this looks like it might have
> some promising candidates:
>
> http://www.google.com/#q=traffic+data+feed+data+standards+tmc+adms
>
> ADMS - Archived Data Management Systems
> TMC - Traffic control centers
>
> This looks like a potential site for getting archived real-time data:
> https://pems.eecs.berkeley.edu/?redirect=%2F%3Fdnode%3DState
> http://pems.dot.ca.gov/
>
> So from a project point of view, I'm not sure it is a good idea to spend
> much time research potential data sources and coding tools to summarize
> the data into tables. While this is clearly interesting and might be a
> good ideas after GSoC, I think it might be a huge time sync and it would
> be better to just make some test networks by hand.
>
> One of the problems you will run into with most if not all of these
> sites, is mapping sensors to edges. This might not be hard if the supply
> the lat/lon of the sensor, but in may cases I think they just supply a
> textual description of the sense and you have to map that to a edge.
>
> -Steve
>
> On 5/26/2011 11:31 PM, Jay Mahadeokar wrote:
>> Hi,
>>
>> We had discussed some possible ways of getting the test time-dependent
>> data, but reached no particular solution.
>>
>> I found this link: http://bhelp.traffic.com/
>>
>> It a Navteq service and provides live traffic information. You need to
>> login, and then you can browse live traffic.
>> You can select each road and get following info:
>>
>> - Jam factor
>> - Drive time now
>> - delay
>> - speed limit
>> - average speed
>>
>> I guess, this is exactly what we need. Even if we can record the
>> drive-time now, for each road at intervals of 1 hour each for a
>> particular city, we will have significant time dependent data.
>>
>> I browsed the website but did not find any link where this data is made
>> available. Is there any way to record this data? Any starting points?
>>
>> On Thu, Apr 7, 2011 at 10:05 PM, Jay Mahadeokar
>> <jai.mahadeokar at gmail.com <mailto:jai.mahadeokar at gmail.com>> wrote:
>>
>> Hello all,
>>
>> Just an update - as Daniel suggested I posted a query about
>> time-Dependent data in OSM routing list. It seems they dont have
>> such data, but people have posted some things that might be useful
>> for us in future. Here is link to the discussion -
>> http://lists.openstreetmap.org/pipermail/routing/2011-April/001127.html
>> You may want to have a look there.
>>
>> Sorry for the delayed replies, presently, I am a bit occupied by
>> college submissions. I will go through the links and the ideas
>> proposed here by Daniel and Steve soon. As already said I guess we
>> need to put a lot of thought in designing the data model, that would
>> be easy for users to use, robust and flexible for different
>> applications, and at the same time efficient in terms of query and
>> processing time. I will try and come up with thoughts on that soon.
>>
>> Regarding Navteq data, the website says that only one data-set will
>> be allowed to download. So, I was wondering which data should be
>> preferred. Also, there are various data-formats that Navteq provides
>> data in. Steve, have you downloaded any data which specifically has
>> time-dependent edge weights?
>>
>> Though we will not want the module to follow Navteq standards, any
>> time-dependent data would be very helpful for me, since I also want
>> to try out some heuristics on that as part of my thesis. The work
>> done by R. Geisberger, P. Sanders and others is experimented on the
>> Germany data provided by PTV AG
>> http://www.ptvag.com/company/contact/. I have requested them data
>> for research purposes. Have you worked with their data by any chance?
>>
>> Regards,
>>
>>
>> On Tue, Apr 5, 2011 at 8:05 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> On 4/5/2011 1:37 AM, Daniel Kastl wrote:
>>
>> Hi Jay,
>>
>> As Steve said, Navteq sample data is one possibility ... and
>> it's better
>> than nothing ;-)
>>
>> Well, I think we should avoid to support a single data
>> provider, because
>> who tells that the format they defined several years ago is
>> the most
>> suitable one. It might work perfectly for Navteq and road
>> networks in
>> countries they are operating, but this doesn't say there
>> won't be a more
>> clever way to store such an information.
>> I think it will be always necessary to transform data into a
>> format
>> pgRouting algorithms can handle. So it's OK in my opinion to
>> define some
>> convenient format if there isn't an existing standard
>> already (which
>> doesn't exist afaik).
>> But Navteq is good data for testing, I agree. For the
>> beginning I think
>> it might be even too complex model, as Steve mentioned there
>> are even
>> time dependent turn restrictions.
>>
>>
>> I think that the value in looking at Navteq is not to use it
>> all, but that it is a concrete data model that expresses all the
>> various routing characteristics that you might run into in other
>> data sets. Navteq has been the basis for almost all routing
>> solution during the past 10-15 years. There are now others like
>> TeleAtlas, and even OSM. So look it over and use as much or as
>> little as you need to get started. Designing a data model is
>> very complex and you can not do it in the abstract - you need to
>> know what you are modeling.
>>
>> As far as defining an data model that is easy for users to work
>> with, keep the tables simple to understand and load with data.
>> It is better to have 5 simple to work with tables than 1-2
>> complex ones. If you need to transform the data inside then have
>> a preparation function that reads the user tables and applies
>> them to the graph. So examples of user tables might be:
>>
>> o bus, train, ferry, airline schedules
>> o live traffic data table
>> o historical speed estimates by day/time (as Daniel mentions below)
>> o transfer rules - required pre-deparature arrival time when
>> transferring to a different transportation mode and
>> post-scheduled arrival wait time when transferring from a mode.
>> EG, must arrive at airport 2 hr before flight departure and
>> allow 45 mins after arrival to collect baggage or longer on
>> international flights. (this might not apply to your specific
>> problem)
>>
>>
>>
>> A good place to discuss such a question might be also the
>> "OSM routing"
>> mailing list. In the worst case nobody will answer. But
>> maybe you will
>> start a long discussion as there are several people very
>> interested in
>> routing related topics. OSM data would be nice, if we could
>> make use of
>> it, but I fear that not many mappers really think about
>> time-dependent attributes. Probably in Germany you can find
>> such a data.
>>
>>
>> Yes, working with OSM is another good possibility.
>>
>>
>> I thought a bit about some possible cases for time dependent
>> road networks:
>>
>> * In Japan a big issue for navigation software are so
>> called "School
>> Zones", which are areas around schools obviously,
>> which are closed
>> for motorized traffic at certain times in the morning.
>> * In Europe I know about pedestrian areas for example,
>> which can be
>> used for delivery of goods after regular business
>> hours. Or heavy
>> trucks are not allowed to access roads during certain
>> times.
>> * Some highways/roads in Germany have a speed limit
>> during night time
>> * Ferry services might only operate during day time (so
>> if you
>> missed the last ferry, you might have to take a longer
>> way)
>> * In Japan they have so called VICS data
>> (http://www.mlit.go.jp/road/ITS/conf/2006/ts20.pdf)
>> collected from
>> road sensors, which can tell the typical speed on
>> roads during
>> certain hours.
>>
>> ... and so on ...
>>
>>
>> One last thought on loading data. I work a lot with Navteq and
>> LOTS of other data sets. The one common theme that I come back
>> to is that I create data loaders for the various data sets I
>> work with so I can load the data into the database and I always
>> end up transforming the data into a simpler model that is easy
>> to work with and then used by whatever application I am working
>> on. Sometimes I transform the data in the loader and sometimes I
>> just load it raw and transform it in the database and then drop
>> the raw data tables.
>>
>> Hope this helps,
>> -Steve
>>
>>
>> I think what pgRouting is currently missing are some sort of
>> "unit
>> tests" on some test network. This can be a regular grid with
>> costs
>> assigned, that model a certain routing case. It would be really
>> convenient to have something like this.
>>
>> Daniel
>>
>>
>> 2011/4/5 Jay Mahadeokar <jai.mahadeokar at gmail.com
>> <mailto:jai.mahadeokar at gmail.com>
>> <mailto:jai.mahadeokar at gmail.com
>> <mailto:jai.mahadeokar at gmail.com>>>
>>
>> Hi,
>>
>> Since we will be working on time-dependent shortest path
>> problem, I
>> was wondering if time-dependent geographic data is
>> freely available
>> for research purposes. [1] states that we witness an
>> increasing
>> number of navigation service providers (such as Navteq and
>> TeleAtlas) have started releasing their time-dependent
>> travel-time
>> datasets for road networks at high-resolution temporal
>> granularity
>> as fine as one sample for every five minutes.
>>
>> I guess that data is not freely available. Anyways, if
>> you know such
>> data-source can you please direct me? Besides this
>> project, I am
>> also working on some new heuristics for time-dependent
>> shortest path
>> as part of my thesis and the data would be really
>> helpful for my work.
>>
>> Thanks.
>>
>> [1] http://portal.acm.org/citation.cfm?id=1869865
>>
>>
>> On Thu, Mar 31, 2011 at 7:49 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>> <mailto:woodbri at swoodbridge.com
>> <mailto:woodbri at swoodbridge.com>>> wrote:
>>
>> On 3/30/2011 9:45 PM, Daniel Kastl wrote:
>>
>>
>> float cost := getEdgeCost(time,
>> vehicle_type,
>> node_from,
>> node_to);
>>
>> or something like that. Where time
>> could be NULL
>> for some
>> default
>> behavior, or a value that would be
>> used to
>> figure out the cost.
>> vehicle_type might be helpful if
>> there are
>> multiple costs to
>> traverse a link based on say, car,
>> carpool, bus,
>> truck, walking,
>> taxi, etc. This could also be used
>> to implement
>> the rules
>> for bus
>> and train lines.
>>
>>
>> I think one of the difficulties with routing
>> topic is that
>> everyone
>> (also myself) immediately think about routing in
>> terms of
>> vehicle types.
>> It's the easiest example to explain pgRouting,
>> but I think
>> one premise
>> of pgRouting is that it should work for any kind
>> of network.
>> Let's say
>> your network would be the human nervous system.
>> What is a
>> vehicle there?
>> Well, probably changing "vehicle_type" to
>> "speed" would make
>> sense, right?
>>
>>
>> Sorry for using vehicle as the selector maybe
>> "service_type"
>> would be better, but the point is not the name,
>> "speed" is
>> equally misleading, the point is to be able to be
>> able to pass a
>> selector to the under lying function so that based
>> on the
>> selector we can compute an appropriate cost.
>>
>> For my vehicle routing example, I chose: car,
>> carpool, bus,
>> truck, walking, taxi, etc. because these might have
>> different
>> rules associated to them. The selector values would be
>> appropriate to the model that you were working with.
>>
>> car vs carpool vs bus - many cities have HOV lanes
>> that bus and
>> carpool can use but not single occupancy cars. We
>> might want to
>> allocate a higher speed to those lanes vs the normal
>> lanes
>> during rush hours. Emergency vehicles many be
>> allowed to make
>> u-turns on highways that other vehicles can not
>> make. Trucks
>> might be banned from some streets so need to be costed
>> appropriately, etc.
>>
>> If we had a live traffic feed information linked to
>> segment ids
>> in another table, The cost function could be
>> implemented to
>> check that table and if a record exists then use that
>> information or return the standard information. By
>> keeping this
>> data in a separate table that is presumably much
>> smaller and
>> dynamic than the street records it would make it
>> much easier and
>> more cost effective to make dynmaic changes to that
>> table and to
>> hide (abstract away complexity) by using a cost function
>> supplied to the underlying code.
>>
>> -Steve
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev