[pgrouting-dev] Support for Time Constraints

Tue Apr 5 01:37:28 EDT 2011

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.

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.

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 ...

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>

> 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> 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
>>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>

-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110405/0ea834d7/attachment-0001.html