[pgrouting-dev] Support for Time Constraints
Jay Mahadeokar
jai.mahadeokar at gmail.com
Thu Jun 2 22:35:15 EDT 2011
Hi Daniel,
On Fri, Jun 3, 2011 at 7:45 AM, Daniel Kastl <daniel at georepublic.de> wrote:
> Hi Jay,
>
> Maybe I'm wrong, but I'm not sure it's really necessary to have "live"
> traffic feeds available to make use of TDSP.
> It will be hard to get such data for free and it's difficult to guess how
> such data might be organized.
>
> But for my understanding "time-dependent" doesn't need to go that far to
> support such kind of feeds.
> Time constraints can be simple access restrictions to parts of your network
> at certain times for example.
>
> Test data can be very simple at the beginning and self made in my opinion.
> If at a later time it appears that there is functionality missing to support
> traffic feeds, then this can be added at a later time.
>
>
So for some sample data these cases come to my mind:
>
> - highways in urban areas have a speed limit during night times to
> reduce the noise
> - some roads in city centers are closed for cars during business hours
> - roads may have different cost in each direction in the morning, when
> people drive to work, and in the evening when the drive back home.
>
> In Germany these three examples are common and will also be available in
> OSM someday, I guess.
>
> What do you think?
>
I agree. I have the same application in mind when it comes to time-dependent
shortest paths. But again, its difficult to obtain this data. One
work-around is that I can use the pgRouting-workshop "ways" table, and
generate an additional time-dependent-cost table with random travel times
for every edge_id, say for 24 - hour time cycles, intervals of 1 hour each.
This can serve as good enough test data I think. We can also add some more
logic to randomness and say tune the travel_times according to rush hours
etc, (but that wont affect the algorithm, just the output! )
I was more interested in real-world actual data, than randomly generated
data because that would also be useful in my college thesis work in future.
But from GSoc point of view, such data would be a luxury!
> Daniel
>
> 2011/5/27 Jay Mahadeokar <jai.mahadeokar at gmail.com>
>
>> 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
>> > 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> 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>>
>>>>>
>>>>> 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>> 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 <mailto:
>>>>> 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 <mailto:pgrouting-dev at lists.osgeo.org
>>>>> >
>>>>>
>>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Georepublic UG & Georepublic Japan
>>>>> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de
>>>>> >
>>>>> Web: http://georepublic.de <http://georepublic.de/>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> pgrouting-dev mailing list
>>>>> pgrouting-dev at lists.osgeo.org
>>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>>>
>>>>
>>>> _______________________________________________
>>>> pgrouting-dev mailing list
>>>> pgrouting-dev at lists.osgeo.org
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>>
>>>
>>>
>>>
>>> --
>>> Regards,
>>> -Jay Mahadeokar
>>>
>>>
>>
>>
>> --
>> 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
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110603/1e5dcb18/attachment-0001.html
More information about the pgrouting-dev
mailing list