[pgrouting-dev] Support for Time Constraints

Jay_Mahadeokar · March 27, 2011, 8:48pm

Hi,

I was looking at GSoc 2011 ideas page and Adding support for time constraints seems to be one of the ideas. I read two papers on the topic which are an extension to (two of the current best) techniques for speeding up shortest path algos.

1. Time Dependent Contraction Hierarchies - an extension to contraction hierarchies problem that we have somewhat discussed in the Network layering Support thread, and we have not reached to any specific conclusion there.

2. Time Dependent SHARC Routing - which is an extension to SHARC technique.

I guess, if we implement one of the above preprocessing technique, the extension will be a relatively simple task. Do you have any other approach towards implementing the time constraints? As we have already found, the implementation of the Contraction hierarchies will take significant brainstorming and effort.

–
Regards,
-Jay Mahadeokar

dkastl · March 28, 2011, 2:46pm

Hi Jay,

In my opinion time dependent routing is a nice idea and a feature you can hardly find in existing routing libraries. I haven’t seen any open source implementation yet. Someone else knows one?

Currently pgRouting takes into account the network loaded when running the query. But it could happen, that network conditions change while travelling in the network, right? For example one could reach a road that is closed on certain times.

It could be a very cool feature, if pgRouting could support even changes during travel time. So personally I would prefer such a project idea over one to speed up shortest path computation.

Daniel

2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com>

Hi,

I was looking at GSoc 2011 ideas page and Adding support for time constraints seems to be one of the ideas. I read two papers on the topic which are an extension to (two of the current best) techniques for speeding up shortest path algos.

1. Time Dependent Contraction Hierarchies - an extension to contraction hierarchies problem that we have somewhat discussed in the Network layering Support thread, and we have not reached to any specific conclusion there.

2. Time Dependent SHARC Routing - which is an extension to SHARC technique.

I guess, if we implement one of the above preprocessing technique, the extension will be a relatively simple task. Do you have any other approach towards implementing the time constraints? As we have already found, the implementation of the Contraction hierarchies will take significant brainstorming and effort.

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · March 28, 2011, 3:05pm

Last years GSoC project for OpenGraphRouter [1], implemented multimodal routing and incorporated bus and train schedules along with time dependent routing. So you would say what you start time was and it would then compute the routes based on travel time, between nodes, transfer times at stations, etc. Basically at nodes that were stations, we link in the schedule for that stop and costs to the connecting nodes were dynamically computed from the schedules and the arrival time at the stop. Arrival time was based on your start time plus the travel time to that stop.

[1] http://opengraphrouter.sourceforge.net/

It would be cool if we could use the work done here and migrate that back to pgRouting or integrate it with the contraction highways.

I think the abstraction of this is that we need a method that gets the cost and for regular highway nodes and edges it would mostly just return a static value assigned to that object. But for we had time dependent turn restrictions or we had multimodal station, it would lookup the cost based on a schedule or timetable linked to that object.

This would allow the schedules and timetables to be hidden from the implementation. And different types of objects could point to different methods for computing the costs.

-Steve

On 3/28/2011 10:46 AM, Daniel Kastl wrote:

Hi Jay,

In my opinion time dependent routing is a nice idea and a feature you
can hardly find in existing routing libraries. I haven't seen any open
source implementation yet. Someone else knows one?

Currently pgRouting takes into account the network loaded when running
the query. But it could happen, that network conditions change while
travelling in the network, right? For example one could reach a road
that is closed on certain times.

It could be a very cool feature, if pgRouting could support even changes
during travel time. So personally I would prefer such a project idea
over one to speed up shortest path computation.

Daniel

2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com
<mailto:jai.mahadeokar@gmail.com>>

    Hi,

    I was looking at GSoc 2011 ideas page and Adding support for time
    constraints seems to be one of the ideas. I read two papers on the
    topic which are an extension to (two of the current best) techniques
    for speeding up shortest path algos.

    1. Time Dependent Contraction Hierarchies
    <http://algo2.iti.kit.edu/english/1222.php> - an extension to
    contraction hierarchies problem that we have somewhat discussed in
    the Network layering Support thread, and we have not reached to any
    specific conclusion there.

    2. Time Dependent SHARC Routing
    <http://portal.acm.org/citation.cfm?id=1431038> - which is an
    extension to SHARC technique.

    I guess, if we implement one of the above preprocessing technique,
    the extension will be a relatively simple task. Do you have any
    other approach towards implementing the time constraints? As we
    have already found, the implementation of the Contraction
    hierarchies will take significant brainstorming and effort.

    --
    Regards,
    -Jay Mahadeokar

    _______________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Jay_Mahadeokar · March 29, 2011, 6:41pm

Hi,

I tried to survey existing time dependent routing algorithms that do not do pre-processing as in CH and SHARC. The problem is formally defined in [1]. It gives a bidirectional A* algorithm for time-dependent scenario. The paper is explained in short in [2].

Now, the algorithm discussed there is complex and also involves pre-processing the distances from set of landmark nodes to all other nodes which is used by the potential function in A*.But, the paper states the problem very formally.

Main motivation is: People are not really interested in the distance they travel, but instead they want the route which will lead to their destination quickest (in least time).

For starters, I was thinking of modifying simple dijkstra algorithm for time dependent routing. In simple words, the problem can be framed as follows (For formal problem statement refer [1]):

Each edge has a range of costs associated with it. The cost depends on the start time at which we want to traverse the road which will be governed by the traffic and other parameters. We can assume a function which will return the cost of edge and time required to cross the edge, if we pass the edge id and start time to it.

Im writing down a rough pseudo-code for the dijkstra search:

Note that I have modified lines 3,6,15 and 18 (from the pseudo-code given on wikipedia [3])

 1  **function** Dijkstra(*Graph*, *source* , start_time):

 2      **for each** vertex *v* in *Graph*:           *// Initializations*
 3          dist[*v*] := infinity ;              *// Unknown distance function from source to v*
            time[v] := 0 ;

 4          previous[*v*] := undefined ;         *// Previous node in optimal path from source*
 5      **end for** ;
 6      dist[*source*] := 0 ;                    *// Distance from source to source*

        time[source] := start_time ;
 7      *Q* := the set of all nodes in *Graph* ;
        *// All nodes in the graph are unoptimized - thus are in Q*
 8      **while** *Q* **is not** empty:                 *// The main loop*

 9          *u* := vertex in *Q* with smallest dist[] ;
10          **if** dist[*u*] = infinity:
11              **break** ;                        *// all remaining vertices are inaccessible from source*

12          **fi** ;
13          remove *u* from *Q* ;
14          **for each** neighbor *v* of *u*:         *// where v has not yet been removed from Q.*
15              *alt* := dist[*u*] + dist_between(*u*, *v* , time[u],end_time) ; //end_time returns the time at which we reach v from u            

16              **if** *alt* < dist[*v*]:             *// Relax (u,v,a)*
17                  dist[*v*] := *alt* ;
18                  previous[*v*] := *u* ;
                    time[v] := end_time;

19              **fi**  ;
20          **end for** ;
21      **end while** ;
22      **return** dist[] ;
23  **end** Dijkstra.

This will be a very basic implementation and there will be much scope for improvement and implementation using better and complex techniques as given in [1].

Questions:

@Daniel - Is this somewhat what you are interested in?
Can this be considered as a GSoc project?
pgRouting mainly provides routing for postgres. So, do we assume the data pertaining the time-dependent values for each edge present in the postgres database? If yes we will need to finalise the format of the data stored right?
Is there already a standard format for storing time-dependent edge weights data, or we should assume the function that returns the edge cost as black box and just code the time dependent functionality without worrying as to how the function actually gets the values from (database or somewhere else)

@Stephen - I have not yet looked at the multimodal routing implementation. I guess the idea I have proposed is different from that one right? Will look into it if this one does not shape well.

[1] Bidirectional A∗ Search on Time-Dependent Road Networks
[2] Slide Show of above paper
[3] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Last years GSoC project for OpenGraphRouter [1], implemented multimodal routing and incorporated bus and train schedules along with time dependent routing. So you would say what you start time was and it would then compute the routes based on travel time, between nodes, transfer times at stations, etc. Basically at nodes that were stations, we link in the schedule for that stop and costs to the connecting nodes were dynamically computed from the schedules and the arrival time at the stop. Arrival time was based on your start time plus the travel time to that stop.

[1] http://opengraphrouter.sourceforge.net/

It would be cool if we could use the work done here and migrate that back to pgRouting or integrate it with the contraction highways.

I think the abstraction of this is that we need a method that gets the cost and for regular highway nodes and edges it would mostly just return a static value assigned to that object. But for we had time dependent turn restrictions or we had multimodal station, it would lookup the cost based on a schedule or timetable linked to that object.

This would allow the schedules and timetables to be hidden from the implementation. And different types of objects could point to different methods for computing the costs.

-Steve

On 3/28/2011 10:46 AM, Daniel Kastl wrote:

Hi Jay,

In my opinion time dependent routing is a nice idea and a feature you
can hardly find in existing routing libraries. I haven’t seen any open
source implementation yet. Someone else knows one?

Currently pgRouting takes into account the network loaded when running
the query. But it could happen, that network conditions change while
travelling in the network, right? For example one could reach a road
that is closed on certain times.

It could be a very cool feature, if pgRouting could support even changes
during travel time. So personally I would prefer such a project idea
over one to speed up shortest path computation.

Daniel

2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com

mailto:[jai.mahadeokar@gmail.com](mailto:jai.mahadeokar@gmail.com)>

Hi,

I was looking at GSoc 2011 ideas page and Adding support for time
constraints seems to be one of the ideas. I read two papers on the
topic which are an extension to (two of the current best) techniques
for speeding up shortest path algos.

Time Dependent Contraction Hierarchies

<http://algo2.iti.kit.edu/english/1222.php> - an extension to

contraction hierarchies problem that we have somewhat discussed in
the Network layering Support thread, and we have not reached to any
specific conclusion there.

Time Dependent SHARC Routing

<http://portal.acm.org/citation.cfm?id=1431038> - which is an

extension to SHARC technique.

I guess, if we implement one of the above preprocessing technique,
the extension will be a relatively simple task. Do you have any
other approach towards implementing the time constraints? As we
have already found, the implementation of the Contraction
hierarchies will take significant brainstorming and effort.

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan

eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · March 29, 2011, 8:34pm

Jay,

Currently in pgRouting you can have different cost columns, like distance, traversal time, etc that is stored on the edge. I think that is would be very advantageous with we could pass a pgpsql function to fetch the cost. We could easily set up a standard signature for such a function. like:

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.

Regarding the multi-modal routing, What you proposed is very close to the multimodal implementation. You define a start time and start node and a destination. As the route is evaluated, the time is incremented by the cost of each edge or node. In the multimodal, we had the ability if I'm not mistaken to have a cost at a node, this might have been implemented by adding some segment with the cost on that. This was used for the cost of waiting for a scheduled item, like a bus, train to a stop.

-Steve

On 3/29/2011 2:41 PM, Jay Mahadeokar wrote:

Hi,

I tried to survey existing time dependent routing algorithms that do not
do pre-processing as in CH and SHARC. The problem is formally defined in
[1]. It gives a bidirectional A* algorithm for time-dependent scenario.
The paper is explained in short in [2].

Now, the algorithm discussed there is complex and also involves
pre-processing the distances from set of landmark nodes to all other
nodes which is used by the potential function in A*.But, the paper
states the problem very formally.

*Main motivation is:* People are not really interested in the distance
they travel, but instead they want the route which will lead to their
destination quickest (in least time).

For starters, I was thinking of modifying simple dijkstra algorithm for
time dependent routing. In simple words, the problem can be framed as
follows (For formal problem statement refer [1]):

Each edge has a range of costs associated with it. The cost depends on
the start time at which we want to traverse the road which will be
governed by the traffic and other parameters. We can assume a function
which will return the cost of edge and time required to cross the edge,
if we pass the edge id and start time to it.

Im writing down a rough pseudo-code for the dijkstra search:

Note that I have modified lines 3,6,15 and 18 (from the pseudo-code
given on wikipedia [3])

  1*function* Dijkstra(/Graph/,/source/ , start_time):

  2*for each* vertex/v/ in/Graph/:/// Initializations/
  3 dist[/v/] := infinity ;/// Unknown distance function from source to v/
             time[v] := 0 ;

  4 previous[/v/] := undefined ;/// Previous node in optimal path from source/
  5*end for*;
  6 dist[/source/] := 0 ;/// Distance from source to source/

         time[source] := start_time ;
  7/Q/ := the set of all nodes in/Graph/ ;
         /// All nodes in the graph are unoptimized - thus are in Q/
  8*while* /Q/ *is not* empty:/// The main loop/

  9/u/ := vertex in/Q/ with smallest dist ;
10*if* dist[/u/] = infinity:
11*break* ;/// all remaining vertices are inaccessible from source/

12*fi* ;
13 remove/u/ from/Q/ ;
14*for each* neighbor/v/ of/u/:/// where v has not yet been removed from Q./
15/alt/ := dist[/u/] + dist_between(/u/,/v/ , time[u],end_time) ; //end_time returns the time at which we reach v from u

16*if* /alt/ < dist[/v/]:/// Relax (u,v,a)/
17 dist[/v/] :=/alt/ ;
18 previous[/v/] :=/u/ ;
                     time[v] := end_time;

19*fi* ;
20*end for* ;
21*end while* ;
22*return* dist ;
23*end* Dijkstra.

This will be a very basic implementation and there will be much scope
for improvement and implementation using better and complex techniques
as given in [1].

*Questions*:

1. @Daniel - Is this somewhat what you are interested in?
2. Can this be considered as a GSoc project?
3. pgRouting mainly provides routing for postgres. So, do we assume the
data pertaining the time-dependent values for each edge present in the
postgres database? If yes we will need to finalise the format of the
data stored right?
4. Is there already a standard format for storing time-dependent edge
weights data, or we should assume the function that returns the edge
cost as black box and just code the time dependent functionality without
worrying as to how the function actually gets the values from (database
or somewhere else)

@Stephen - I have not yet looked at the multimodal routing
implementation. I guess the idea I have proposed is different from that
one right? Will look into it if this one does not shape well.

[1] Bidirectional A∗ Search on Time-Dependent Road Networks
<http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.2183%26rep%3Drep1%26type%3Dpdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNFnYYtw2Ap_dNyjbYcaPnmB-bMZOQ&sig2=DTMTucn2TMhT0eXTiqKlTg>
[2] Slide Show of above paper
<http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCAQFjAB&url=http%3A%2F%2Fctw08.dti.unimi.it%2Fslides%2FB5%2FB5-1-Nannicini.pdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNGEl-mbYR1MF9HBKY-dbBxrX8xfcw&sig2=ylApFLDB6FTQNuYUwaPQDQ>
[3] http://en.wikipedia.org/wiki/Dijkstra's_algorithm

On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Last years GSoC project for OpenGraphRouter [1], implemented
    multimodal routing and incorporated bus and train schedules along
    with time dependent routing. So you would say what you start time
    was and it would then compute the routes based on travel time,
    between nodes, transfer times at stations, etc. Basically at nodes
    that were stations, we link in the schedule for that stop and costs
    to the connecting nodes were dynamically computed from the schedules
    and the arrival time at the stop. Arrival time was based on your
    start time plus the travel time to that stop.

    [1] http://opengraphrouter.sourceforge.net/

    It would be cool if we could use the work done here and migrate that
    back to pgRouting or integrate it with the contraction highways.

    I think the abstraction of this is that we need a method that gets
    the cost and for regular highway nodes and edges it would mostly
    just return a static value assigned to that object. But for we had
    time dependent turn restrictions or we had multimodal station, it
    would lookup the cost based on a schedule or timetable linked to
    that object.

    This would allow the schedules and timetables to be hidden from the
    implementation. And different types of objects could point to
    different methods for computing the costs.

    -Steve

    On 3/28/2011 10:46 AM, Daniel Kastl wrote:

        Hi Jay,

        In my opinion time dependent routing is a nice idea and a
        feature you
        can hardly find in existing routing libraries. I haven't seen
        any open
        source implementation yet. Someone else knows one?

        Currently pgRouting takes into account the network loaded when
        running
        the query. But it could happen, that network conditions change while
        travelling in the network, right? For example one could reach a road
        that is closed on certain times.

        It could be a very cool feature, if pgRouting could support even
        changes
        during travel time. So personally I would prefer such a project idea
        over one to speed up shortest path computation.

        Daniel

        2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com
        <mailto:jai.mahadeokar@gmail.com>
        <mailto:jai.mahadeokar@gmail.com>>

        Hi,

        I was looking at GSoc 2011 ideas page and Adding support for time
        constraints seems to be one of the ideas. I read two papers on the
        topic which are an extension to (two of the current best) techniques
        for speeding up shortest path algos.

        1. Time Dependent Contraction Hierarchies
        <http://algo2.iti.kit.edu/english/1222.php> - an extension to

        contraction hierarchies problem that we have somewhat discussed in
        the Network layering Support thread, and we have not reached to any
        specific conclusion there.

        2. Time Dependent SHARC Routing
        <http://portal.acm.org/citation.cfm?id=1431038> - which is an

        extension to SHARC technique.

        I guess, if we implement one of the above preprocessing technique,
        the extension will be a relatively simple task. Do you have any
        other approach towards implementing the time constraints? As we
        have already found, the implementation of the Contraction
        hierarchies will take significant brainstorming and effort.

        --
        Regards,
        -Jay Mahadeokar

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>

        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

        --
        Georepublic UG & Georepublic Japan
        eMail: daniel.kastl@georepublic.de
        <mailto:daniel.kastl@georepublic.de>
        <mailto:daniel.kastl@georepublic.de
        <mailto:daniel.kastl@georepublic.de>>
        Web: http://georepublic.de/>

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

    _______________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Regards,
-Jay Mahadeokar

Jay_Mahadeokar · March 30, 2011, 7:51pm

On Wed, Mar 30, 2011 at 2:04 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Jay,

Currently in pgRouting you can have different cost columns, like distance, traversal time, etc that is stored on the edge. I think that is would be very advantageous with we could pass a pgpsql function to fetch the cost. We could easily set up a standard signature for such a function. like:

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.

Sounds good. Again since the GSoc Application deadline looming on 8th April, can this be considered as a valid GSoc project? If yes, I would start writing down the proposal for the same. Would like to hear thoughts of Daniel or Anton on the same.

Please also suggest any changes / improvements in the idea too

Regarding the multi-modal routing, What you proposed is very close to the multimodal implementation. You define a start time and start node and a destination. As the route is evaluated, the time is incremented by the cost of each edge or node. In the multimodal, we had the ability if I’m not mistaken to have a cost at a node, this might have been implemented by adding some segment with the cost on that. This was used for the cost of waiting for a scheduled item, like a bus, train to a stop.

-Steve

On 3/29/2011 2:41 PM, Jay Mahadeokar wrote:

Hi,

I tried to survey existing time dependent routing algorithms that do not
do pre-processing as in CH and SHARC. The problem is formally defined in
[1]. It gives a bidirectional A* algorithm for time-dependent scenario.
The paper is explained in short in [2].

Now, the algorithm discussed there is complex and also involves
pre-processing the distances from set of landmark nodes to all other
nodes which is used by the potential function in A*.But, the paper
states the problem very formally.

Main motivation is: People are not really interested in the distance
they travel, but instead they want the route which will lead to their
destination quickest (in least time).

For starters, I was thinking of modifying simple dijkstra algorithm for
time dependent routing. In simple words, the problem can be framed as
follows (For formal problem statement refer [1]):

Each edge has a range of costs associated with it. The cost depends on
the start time at which we want to traverse the road which will be
governed by the traffic and other parameters. We can assume a function
which will return the cost of edge and time required to cross the edge,
if we pass the edge id and start time to it.

Im writing down a rough pseudo-code for the dijkstra search:

Note that I have modified lines 3,6,15 and 18 (from the pseudo-code
given on wikipedia [3])

1function Dijkstra(/Graph/,/source/ , start_time):

2for each vertex/v/ in/Graph/:/// Initializations/
3 dist[/v/] := infinity ;/// Unknown distance function from source to v/
time[v] := 0 ;

4 previous[/v/] := undefined ;/// Previous node in optimal path from source/
5end for;
6 dist[/source/] := 0 ;/// Distance from source to source/

time[source] := start_time ;
7/Q/ := the set of all nodes in/Graph/ ;
/// All nodes in the graph are unoptimized - thus are in Q/
8while /Q/ is not empty:/// The main loop/

9/u/ := vertex in/Q/ with smallest dist ;
10if dist[/u/] = infinity:
11break ;/// all remaining vertices are inaccessible from source/

12fi ;
13 remove/u/ from/Q/ ;
14for each neighbor/v/ of/u/:/// where v has not yet been removed from Q./
15/alt/ := dist[/u/] + dist_between(/u/,/v/ , time[u],end_time) ; //end_time returns the time at which we reach v from u

16if /alt/ < dist[/v/]:/// Relax (u,v,a)/
17 dist[/v/] :=/alt/ ;
18 previous[/v/] :=/u/ ;
time[v] := end_time;

19fi ;
20end for ;
21end while ;
22return dist ;
23end Dijkstra.

This will be a very basic implementation and there will be much scope
for improvement and implementation using better and complex techniques
as given in [1].

Questions:

@Daniel - Is this somewhat what you are interested in?

Can this be considered as a GSoc project?

pgRouting mainly provides routing for postgres. So, do we assume the
data pertaining the time-dependent values for each edge present in the
postgres database? If yes we will need to finalise the format of the
data stored right?

Is there already a standard format for storing time-dependent edge
weights data, or we should assume the function that returns the edge
cost as black box and just code the time dependent functionality without
worrying as to how the function actually gets the values from (database
or somewhere else)

@Stephen - I have not yet looked at the multimodal routing
implementation. I guess the idea I have proposed is different from that
one right? Will look into it if this one does not shape well.

[1] Bidirectional A∗ Search on Time-Dependent Road Networks

<http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.2183%26rep%3Drep1%26type%3Dpdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNFnYYtw2Ap_dNyjbYcaPnmB-bMZOQ&sig2=DTMTucn2TMhT0eXTiqKlTg>

[2] Slide Show of above paper

<http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCAQFjAB&url=http%3A%2F%2Fctw08.dti.unimi.it%2Fslides%2FB5%2FB5-1-Nannicini.pdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNGEl-mbYR1MF9HBKY-dbBxrX8xfcw&sig2=ylApFLDB6FTQNuYUwaPQDQ>

[3] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

Last years GSoC project for OpenGraphRouter [1], implemented
multimodal routing and incorporated bus and train schedules along
with time dependent routing. So you would say what you start time
was and it would then compute the routes based on travel time,
between nodes, transfer times at stations, etc. Basically at nodes
that were stations, we link in the schedule for that stop and costs
to the connecting nodes were dynamically computed from the schedules
and the arrival time at the stop. Arrival time was based on your
start time plus the travel time to that stop.

[1] http://opengraphrouter.sourceforge.net/

It would be cool if we could use the work done here and migrate that
back to pgRouting or integrate it with the contraction highways.

I think the abstraction of this is that we need a method that gets
the cost and for regular highway nodes and edges it would mostly
just return a static value assigned to that object. But for we had
time dependent turn restrictions or we had multimodal station, it
would lookup the cost based on a schedule or timetable linked to
that object.

This would allow the schedules and timetables to be hidden from the
implementation. And different types of objects could point to
different methods for computing the costs.

-Steve

On 3/28/2011 10:46 AM, Daniel Kastl wrote:

Hi Jay,

In my opinion time dependent routing is a nice idea and a
feature you
can hardly find in existing routing libraries. I haven’t seen
any open
source implementation yet. Someone else knows one?

Currently pgRouting takes into account the network loaded when
running
the query. But it could happen, that network conditions change while
travelling in the network, right? For example one could reach a road
that is closed on certain times.

It could be a very cool feature, if pgRouting could support even
changes
during travel time. So personally I would prefer such a project idea
over one to speed up shortest path computation.

Daniel

2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com
mailto:[jai.mahadeokar@gmail.com](mailto:jai.mahadeokar@gmail.com)

<mailto:jai.mahadeokar@gmail.com mailto:[jai.mahadeokar@gmail.com](mailto:jai.mahadeokar@gmail.com)>>

Hi,

I was looking at GSoc 2011 ideas page and Adding support for time
constraints seems to be one of the ideas. I read two papers on the
topic which are an extension to (two of the current best) techniques
for speeding up shortest path algos.

Time Dependent Contraction Hierarchies
<http://algo2.iti.kit.edu/english/1222.php> - an extension to

contraction hierarchies problem that we have somewhat discussed in
the Network layering Support thread, and we have not reached to any
specific conclusion there.

Time Dependent SHARC Routing
<http://portal.acm.org/citation.cfm?id=1431038> - which is an

extension to SHARC technique.

I guess, if we implement one of the above preprocessing technique,
the extension will be a relatively simple task. Do you have any
other approach towards implementing the time constraints? As we
have already found, the implementation of the Contraction
hierarchies will take significant brainstorming and effort.

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
<mailto:daniel.kastl@georepublic.de
mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)>
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–

Regards,
-Jay Mahadeokar

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · March 30, 2011, 9:23pm

Jay,

I can not speak for Daniel and Anton but a couple of things:

Given the time schedule, assume you can go ahead with your plan and it can always be tweaked along the way. Hopefully they will be able to respond directly.

Remember that they are currently based out of Japan and given the power problems and infrastructure issues they might have spotty access to the net.

I'm sure they will have some input eventually, but you need to take control of your application and do the best you can given what input you are able to get from us now.

I think it is important that whatever you do, needs to be integrated with pgRouting and you need to make sure you allow for time for that.

Best regards,
-Steve

On 3/30/2011 3:51 PM, Jay Mahadeokar wrote:

On Wed, Mar 30, 2011 at 2:04 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Jay,

    Currently in pgRouting you can have different cost columns, like
    distance, traversal time, etc that is stored on the edge. I think
    that is would be very advantageous with we could pass a pgpsql
    function to fetch the cost. We could easily set up a standard
    signature for such a function. like:

    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.

Sounds good. Again since the GSoc Application deadline looming on 8th
April, can this be considered as a valid GSoc project? If yes, I would
start writing down the proposal for the same. Would like to hear
thoughts of Daniel or Anton on the same.

Please also suggest any changes / improvements in the idea too

    Regarding the multi-modal routing, What you proposed is very close
    to the multimodal implementation. You define a start time and start
    node and a destination. As the route is evaluated, the time is
    incremented by the cost of each edge or node. In the multimodal, we
    had the ability if I'm not mistaken to have a cost at a node, this
    might have been implemented by adding some segment with the cost on
    that. This was used for the cost of waiting for a scheduled item,
    like a bus, train to a stop.

    -Steve

    On 3/29/2011 2:41 PM, Jay Mahadeokar wrote:

        Hi,

        I tried to survey existing time dependent routing algorithms
        that do not
        do pre-processing as in CH and SHARC. The problem is formally
        defined in
        [1]. It gives a bidirectional A* algorithm for time-dependent
        scenario.
        The paper is explained in short in [2].

        Now, the algorithm discussed there is complex and also involves
        pre-processing the distances from set of landmark nodes to all other
        nodes which is used by the potential function in A*.But, the paper
        states the problem very formally.

        *Main motivation is:* People are not really interested in the
        distance
        they travel, but instead they want the route which will lead to
        their
        destination quickest (in least time).

        For starters, I was thinking of modifying simple dijkstra
        algorithm for
        time dependent routing. In simple words, the problem can be
        framed as
        follows (For formal problem statement refer [1]):

        Each edge has a range of costs associated with it. The cost
        depends on
        the start time at which we want to traverse the road which will be
        governed by the traffic and other parameters. We can assume a
        function
        which will return the cost of edge and time required to cross
        the edge,
        if we pass the edge id and start time to it.

        Im writing down a rough pseudo-code for the dijkstra search:

        Note that I have modified lines 3,6,15 and 18 (from the pseudo-code
        given on wikipedia [3])

        1*function* Dijkstra(/Graph/,/source/ , start_time):

        2*for each* vertex/v/ in/Graph/:/// Initializations/
        3 dist[/v/] := infinity ;/// Unknown distance function from
        source to v/
        time[v] := 0 ;

        4 previous[/v/] := undefined ;/// Previous node in optimal path
        from source/
        5*end for*;
        6 dist[/source/] := 0 ;/// Distance from source to source/

        time[source] := start_time ;
        7/Q/ := the set of all nodes in/Graph/ ;
        /// All nodes in the graph are unoptimized - thus are in Q/
        8*while* /Q/ *is not* empty:/// The main loop/

        9/u/ := vertex in/Q/ with smallest dist ;
        10*if* dist[/u/] = infinity:
        11*break* ;/// all remaining vertices are inaccessible from source/

        12*fi* ;
        13 remove/u/ from/Q/ ;
        14*for each* neighbor/v/ of/u/:/// where v has not yet been
        removed from Q./
        15/alt/ := dist[/u/] + dist_between(/u/,/v/ , time[u],end_time)
        ; //end_time returns the time at which we reach v from u

        16*if* /alt/ < dist[/v/]:/// Relax (u,v,a)/
        17 dist[/v/] :=/alt/ ;
        18 previous[/v/] :=/u/ ;
        time[v] := end_time;

        19*fi* ;
        20*end for* ;
        21*end while* ;
        22*return* dist ;
        23*end* Dijkstra.

        This will be a very basic implementation and there will be much
        scope
        for improvement and implementation using better and complex
        techniques
        as given in [1].

        *Questions*:

        1. @Daniel - Is this somewhat what you are interested in?
        2. Can this be considered as a GSoc project?
        3. pgRouting mainly provides routing for postgres. So, do we
        assume the
        data pertaining the time-dependent values for each edge present
        in the
        postgres database? If yes we will need to finalise the format of the
        data stored right?
        4. Is there already a standard format for storing time-dependent
        edge
        weights data, or we should assume the function that returns the edge
        cost as black box and just code the time dependent functionality
        without
        worrying as to how the function actually gets the values from
        (database
        or somewhere else)

        @Stephen - I have not yet looked at the multimodal routing
        implementation. I guess the idea I have proposed is different
        from that
        one right? Will look into it if this one does not shape well.

        [1] Bidirectional A∗ Search on Time-Dependent Road Networks
        <http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.2183%26rep%3Drep1%26type%3Dpdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNFnYYtw2Ap_dNyjbYcaPnmB-bMZOQ&sig2=DTMTucn2TMhT0eXTiqKlTg
        <http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.2183%26rep%3Drep1%26type%3Dpdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNFnYYtw2Ap_dNyjbYcaPnmB-bMZOQ&sig2=DTMTucn2TMhT0eXTiqKlTg>>

        [2] Slide Show of above paper
        <http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCAQFjAB&url=http%3A%2F%2Fctw08.dti.unimi.it%2Fslides%2FB5%2FB5-1-Nannicini.pdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNGEl-mbYR1MF9HBKY-dbBxrX8xfcw&sig2=ylApFLDB6FTQNuYUwaPQDQ
        <http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCAQFjAB&url=http%3A%2F%2Fctw08.dti.unimi.it%2Fslides%2FB5%2FB5-1-Nannicini.pdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNGEl-mbYR1MF9HBKY-dbBxrX8xfcw&sig2=ylApFLDB6FTQNuYUwaPQDQ>>

        [3] http://en.wikipedia.org/wiki/Dijkstra's_algorithm

        On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.com
        <mailto:woodbri@swoodbridge.com>>> wrote:

        Last years GSoC project for OpenGraphRouter [1], implemented
        multimodal routing and incorporated bus and train schedules along
        with time dependent routing. So you would say what you start time
        was and it would then compute the routes based on travel time,
        between nodes, transfer times at stations, etc. Basically at nodes
        that were stations, we link in the schedule for that stop and costs
        to the connecting nodes were dynamically computed from the schedules
        and the arrival time at the stop. Arrival time was based on your
        start time plus the travel time to that stop.

        [1] http://opengraphrouter.sourceforge.net/

        It would be cool if we could use the work done here and migrate that
        back to pgRouting or integrate it with the contraction highways.

        I think the abstraction of this is that we need a method that gets
        the cost and for regular highway nodes and edges it would mostly
        just return a static value assigned to that object. But for we had
        time dependent turn restrictions or we had multimodal station, it
        would lookup the cost based on a schedule or timetable linked to
        that object.

        This would allow the schedules and timetables to be hidden from the
        implementation. And different types of objects could point to
        different methods for computing the costs.

        -Steve

        On 3/28/2011 10:46 AM, Daniel Kastl wrote:

        Hi Jay,

        In my opinion time dependent routing is a nice idea and a
        feature you
        can hardly find in existing routing libraries. I haven't seen
        any open
        source implementation yet. Someone else knows one?

        Currently pgRouting takes into account the network loaded when
        running
        the query. But it could happen, that network conditions change while
        travelling in the network, right? For example one could reach a road
        that is closed on certain times.

        It could be a very cool feature, if pgRouting could support even
        changes
        during travel time. So personally I would prefer such a project idea
        over one to speed up shortest path computation.

        Daniel

        2011/3/28 Jay Mahadeokar <jai.mahadeokar@gmail.com
        <mailto:jai.mahadeokar@gmail.com>
        <mailto:jai.mahadeokar@gmail.com>
        <mailto:jai.mahadeokar@gmail.com
        <mailto:jai.mahadeokar@gmail.com>
        <mailto:jai.mahadeokar@gmail.com
        <mailto:jai.mahadeokar@gmail.com>>>>

        Hi,

        I was looking at GSoc 2011 ideas page and Adding support for time
        constraints seems to be one of the ideas. I read two papers on the
        topic which are an extension to (two of the current best) techniques
        for speeding up shortest path algos.

        1. Time Dependent Contraction Hierarchies
        <http://algo2.iti.kit.edu/english/1222.php> - an extension to

        contraction hierarchies problem that we have somewhat discussed in
        the Network layering Support thread, and we have not reached to any
        specific conclusion there.

        2. Time Dependent SHARC Routing
        <http://portal.acm.org/citation.cfm?id=1431038> - which is an

        extension to SHARC technique.

        I guess, if we implement one of the above preprocessing technique,
        the extension will be a relatively simple task. Do you have any
        other approach towards implementing the time constraints? As we
        have already found, the implementation of the Contraction
        hierarchies will take significant brainstorming and effort.

        --
        Regards,
        -Jay Mahadeokar

dkastl · March 31, 2011, 1:45am

Hi Jay and Steve,

Sorry that replies don’t come that quickly.
Well, let me try to answer all in one email

Remember that they are currently based out of Japan and given the power problems and infrastructure issues they might have spotty access to the net.

We’re still in Japan and have internet as before. Osaka wasn’t/isn’t actually affected directly. But we’re affected by some busy project.

I think it is important that whatever you do, needs to be integrated with pgRouting and you need to make sure you allow for time for that.

+1

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?

Sounds good. Again since the GSoc Application deadline looming on 8th
April, can this be considered as a valid GSoc project? If yes, I would
start writing down the proposal for the same. Would like to hear
thoughts of Daniel or Anton on the same.

Everything that would be an improvement for pgRouting is a valid GSoC project.
If the project plan looks reasonable difficult and doable in the GSoC time frame, then that’s fine.

In the past years I usually found it easy to see, which proposal was written carefully and which one in a rush. Every mentor of the OSGeo organization of GSoC will be able to take a look and give comments, so for pgRouting related proposals it makes it easier for us to defend a nicely written proposal of course.

Questions:

@Daniel - Is this somewhat what you are interested in?

Yes (and I think I can also speak for Anton)

Can this be considered as a GSoc project?

I think so. As I probably mentioned already, it’s important that there will be some nice result to show later. So too ambitious proposals may make us dreaming, but don’t bring anything in the end when they fail.
What is a reasonable proposal depends on each applicant’s skills.

pgRouting mainly provides routing for postgres. So, do we
assume the
data pertaining the time-dependent values for each edge present
in the
postgres database? If yes we will need to finalise the format of the
data stored right?

Is there already a standard format for storing time-dependent
edge
weights data, or we should assume the function that returns the edge
cost as black box and just code the time dependent functionality
without
worrying as to how the function actually gets the values from
(database
or somewhere else)

I think to find some answer to this question should be also seen part of the implementation.
I don’t see a problem to start with some first approach and change it later if there seems to be a better one.

Jay, did I miss something?

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Jay_Mahadeokar · March 31, 2011, 8:57am

On Thu, Mar 31, 2011 at 7:15 AM, Daniel Kastl <daniel@georepublic.de> wrote:

Hi Jay and Steve,

Sorry that replies don’t come that quickly.
Well, let me try to answer all in one email

Remember that they are currently based out of Japan and given the power problems and infrastructure issues they might have spotty access to the net.

We’re still in Japan and have internet as before. Osaka wasn’t/isn’t actually affected directly. But we’re affected by some busy project.

I think it is important that whatever you do, needs to be integrated with pgRouting and you need to make sure you allow for time for that.

+1

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?

Sounds good. Again since the GSoc Application deadline looming on 8th
April, can this be considered as a valid GSoc project? If yes, I would
start writing down the proposal for the same. Would like to hear
thoughts of Daniel or Anton on the same.

Everything that would be an improvement for pgRouting is a valid GSoC project.
If the project plan looks reasonable difficult and doable in the GSoC time frame, then that’s fine.

In the past years I usually found it easy to see, which proposal was written carefully and which one in a rush. Every mentor of the OSGeo organization of GSoC will be able to take a look and give comments, so for pgRouting related proposals it makes it easier for us to defend a nicely written proposal of course.

Questions:

@Daniel - Is this somewhat what you are interested in?

Yes (and I think I can also speak for Anton)

Can this be considered as a GSoc project?

I think so. As I probably mentioned already, it’s important that there will be some nice result to show later. So too ambitious proposals may make us dreaming, but don’t bring anything in the end when they fail.
What is a reasonable proposal depends on each applicant’s skills.

pgRouting mainly provides routing for postgres. So, do we
assume the
data pertaining the time-dependent values for each edge present
in the
postgres database? If yes we will need to finalise the format of the
data stored right?

Is there already a standard format for storing time-dependent
edge
weights data, or we should assume the function that returns the edge
cost as black box and just code the time dependent functionality
without
worrying as to how the function actually gets the values from
(database
or somewhere else)

I think to find some answer to this question should be also seen part of the implementation.
I don’t see a problem to start with some first approach and change it later if there seems to be a better one.

Jay, did I miss something?

You have answered pretty much all the doubts for now. Thanks for the reply! And best luck with your project. (I will keep pinging if any query comes up )

Daniel

–

Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de

Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · March 31, 2011, 2:19pm

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

Jay_Mahadeokar · April 4, 2011, 4:07pm

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@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@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · April 4, 2011, 4:59pm

Jay,

You can sign up here for Navteq Network for Developers:
http://www.nn4d.com/site/global/home/p_home.jsp

This will allow you to download some sample data for a city like Chicago, London, a few others.

Navteq has a very rich road network model that includes turn restrictions and time dependent turn restrictions, road classification, urban/rural and lots of other attributes to help you accurately model the network. You can choose to incorporate as much as you see fit.

The time dependent feeds are typically called traffic feeds, if you are googling for them, and provide near realtime speed information for major roads in and around major cities. Typically they provide a Navteq LINK_ID and a message about it, like the average speed, it a traffic accident or lane closure and potentially volume of traffic. You can then make some assumptions about the about time and speed. You might need some queuing analysis to better understand the impact on traffic flow.

Regards,
-Steve

On 4/4/2011 12:07 PM, Jay Mahadeokar wrote:

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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Regards,
-Jay Mahadeokar

dkastl · April 5, 2011, 5:37am

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@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@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@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · April 5, 2011, 2:35pm

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@gmail.com
<mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

    --
    Regards,
    -Jay Mahadeokar

    _______________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Jay_Mahadeokar · April 7, 2011, 4:35pm

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@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@gmail.com

mailto:[jai.mahadeokar@gmail.com](mailto:jai.mahadeokar@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan

eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Jay_Mahadeokar · May 27, 2011, 3:31am

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@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@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@gmail.com

mailto:[jai.mahadeokar@gmail.com](mailto:jai.mahadeokar@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan

eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · May 27, 2011, 5:11am

Jay,

I think it is generally going to be hard to find a live traffic feed. I'll check out your link below and the Navteq site in the morning too late here to do it now. You might check some of these links:

http://www.google.com/#q=massgis+traffic+data+feeds

-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@gmail.com <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@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@gmail.com
            <mailto:jai.mahadeokar@gmail.com>
            <mailto:jai.mahadeokar@gmail.com
            <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.com
            <mailto:woodbri@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@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>

            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

                --
                Regards,
                -Jay Mahadeokar

                _______________________________________________
                pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>

            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

            --
            Georepublic UG & Georepublic Japan
            eMail: daniel.kastl@georepublic.de
            <mailto:daniel.kastl@georepublic.de>
            <mailto:daniel.kastl@georepublic.de
            <mailto:daniel.kastl@georepublic.de>>
            Web: http://georepublic.de/>

            _______________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

    --
    Regards,
    -Jay Mahadeokar

--
Regards,
-Jay Mahadeokar

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Stephen_Woodbridge1 · May 27, 2011, 1:48pm

Jay,

For Navteq, you need to register as a developer so you can sign into the http://www.nn4d.com/ site and from there you can download sample Navteq data for some cities and some sample traffic data.

http://www.nn4d.com/site/global/build/traffic_apis/services/real_time_traffic/download_center/data_samples/p_data_samples.jsp

You can only download a single city worth of data, so look at what data you need BEFORE you start download data.

I think I would pick Boston or Chicago. They only offer traffic data for: Boston, Chicago, Houston, Los Angeles, SF

City street data:
http://www.nn4d.com/site/global/learn/freesampledata.jsp

Regarding http://bhelp.traffic.com/, this looks like a site that is more geared to the mobile user that needs to see maps and get alerts when roads they commonly use have traffic issues. I do not think this will give you the raw data that would be useful for building time dependent tables.

-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@gmail.com <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@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@gmail.com
            <mailto:jai.mahadeokar@gmail.com>
            <mailto:jai.mahadeokar@gmail.com
            <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.com
            <mailto:woodbri@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@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>

            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

                --
                Regards,
                -Jay Mahadeokar

                _______________________________________________
                pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>

            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

            --
            Georepublic UG & Georepublic Japan
            eMail: daniel.kastl@georepublic.de
            <mailto:daniel.kastl@georepublic.de>
            <mailto:daniel.kastl@georepublic.de
            <mailto:daniel.kastl@georepublic.de>>
            Web: http://georepublic.de/>

            _______________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

    --
    Regards,
    -Jay Mahadeokar

--
Regards,
-Jay Mahadeokar

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Stephen_Woodbridge1 · May 27, 2011, 2:18pm

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@gmail.com <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@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@gmail.com
            <mailto:jai.mahadeokar@gmail.com>
            <mailto:jai.mahadeokar@gmail.com
            <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.com
            <mailto:woodbri@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

Stephen_Woodbridge1 · May 27, 2011, 2:42pm

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@gmail.com <mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@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@gmail.com
<mailto:jai.mahadeokar@gmail.com>
<mailto:jai.mahadeokar@gmail.com
<mailto:jai.mahadeokar@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
<mailto:woodbri@swoodbridge.com
<mailto:woodbri@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev