Difference between revisions of "OpenRouter 2010 SOC Ideas"

From OSGeo
Jump to navigation Jump to search
(New page: * Back to the main OSGeo Google Summer of Code 2010 wiki page. * Back to the main OSGeo Google Summer of Code 2010 Ideas wiki page. = OpenRouter 2010 SOC Ideas = Enter ideas for...)
 
 
(3 intermediate revisions by 2 users not shown)
Line 10: Line 10:
 
You can find the source code, tutorials, the project mailing list and various other information at the links above.
 
You can find the source code, tutorials, the project mailing list and various other information at the links above.
  
To give you an idea about some possible SoC projects, here are some suggestions:
+
To give you an idea about possible SoC projects, here are some suggestions:
 
 
  
  
Line 20: Line 19:
 
So far pgRouting doesn't provide a bi-directional shortest path search implementation.
 
So far pgRouting doesn't provide a bi-directional shortest path search implementation.
  
=== Traveling Salesperson solver enhancement ===
+
=== Add support for time constraints ===
  
The current pgRouting Traveling Salesperson implementation doesn't allow to return to the start point.  
+
Real-time shortest path searches are not implemented yet in pgRouting. What if network conditions change during a trip? An example could be train or bus schedules or time restrictions in road networks. Currently pgRouting algorithms don't take into account these changes.  
  
=== OpenStreetMap data import tool improvement ===
+
=== Network layering support ===
  
The recently contributed OpenStreetMap data import tool has a couple of limitations, such as supported attributes, memory management, cross-platform support, etc..  
+
This idea is a quite a challenging task. Network layering would allow the routing algorithm to change from more to less dense networks to enable long-distance routing.  
  
=== Add support for time constraints ===
+
=== Add Highway Hierarchies routing support ===
  
Real-time shortest path searches are not implemented yet in pgRouting. What if network conditions change during a trip? An example could be train or bus schedules or time restrictions in road networks. Currently pgRouting algorithms don't take into account network these changes.  
+
Add support for routing based on Highway Hierarchies based on algorithms developed by P. Sanders and D. Schultes.
  
=== Network layering support ===
+
=== K-Shortest Path support ===
  
This idea is a quite a challenging task. Network layering would allow the routing algorithm to change from more to less dense networks to enable long-distance routing.  
+
Add support for K-Shortest Path search. That is, not only the shortest path is to be determined, but also the second shortest, the third shortes, and so up to the K-th shortest path.
  
 
=== Better support for turn restrictions ===  
 
=== Better support for turn restrictions ===  
Line 40: Line 39:
 
[...]
 
[...]
  
=== Explicator for driving directions ===  
+
== OpenGraphRouter related ideas ==
  
[...]
+
Continue work on this new general purpose OpenSource Routing library that is designed to be modular and reusable and could be used with or without a database.
 +
 
 +
=== Improve existing Driving Directions Module ===
 +
 
 +
Improve the existing driving direction support and add support for richer information available through the Navteq data model.
  
 +
=== Add Turn restriction support based on Navteq data model ===
  
== OpenGraphRouter related ideas ==
+
Add support for turn restrictions based on the Navteq data model.
  
=== General purpose Routing library ===
+
=== Add support for TeleAtlas data ===
  
Continue work on this new general purpose OpenSource Routing library that could be more modular and reusable and could be used with or without a database?
+
Add support for TeleAtlas data. This would include writing a data loader, adding support to the driving directions module and anything else related to supporting TeleAtlas data.
  
Add support for turn restrictions based on the Navteq data model.
+
=== Add Highway Hierarchies routing support ===
  
 
Add support for routing based on Highway Hierarchies based on algorithms developed by P. Sanders and D. Schultes.
 
Add support for routing based on Highway Hierarchies based on algorithms developed by P. Sanders and D. Schultes.
 +
 +
=== Implement a graph storage based on a database ===
 +
 +
We currently store the graph in our own set of files that facilitate quick access. We would like to have the option of storing the data in a database. Graph structures are not inherently relation so it is like that data will need to be stored in blobs of some type, but that is open to discussion. The goal of this task would be to design an appropriate structure, and write the C++ classes that would manage moving data in and out of these structures and updating them if needed.
 +
 +
=== Lots of other options ===
  
 
There are a lot of other possibilities that we would be happy to discuss with any students interested.
 
There are a lot of other possibilities that we would be happy to discuss with any students interested.
 
  
 
= Mentor Candidates =
 
= Mentor Candidates =
Line 63: Line 72:
  
 
* Stephen Woodbridge <woodbri (at) swoodbridge (dot) com>
 
* Stephen Woodbridge <woodbri (at) swoodbridge (dot) com>
 +
* Daniel Kastl <daniel.kastl (at) georepublic (dot) de>
 +
* Anton Patrushev <anton.patrushev (at) georepublic (dot) co (dot) jp>
  
 
[[Category:Google Summer of Code]]
 
[[Category:Google Summer of Code]]

Latest revision as of 02:17, 24 March 2010

OpenRouter 2010 SOC Ideas

Enter ideas for development projects here. Note these are just suggestions - students are welcome to propose projects based on their own interests that relate to OpenRouter. Our current efforts are based on the following projects:

* pgRouting. This routing library provides routing functionality to PostGIS/PostgreSQL.
* OpenGraphRouter. This project is a C++ library and tools to build a commercial grade routing engine.

You can find the source code, tutorials, the project mailing list and various other information at the links above.

To give you an idea about possible SoC projects, here are some suggestions:


pgRouting related ideas

Implement a bi-directional shortest path algorithm

So far pgRouting doesn't provide a bi-directional shortest path search implementation.

Add support for time constraints

Real-time shortest path searches are not implemented yet in pgRouting. What if network conditions change during a trip? An example could be train or bus schedules or time restrictions in road networks. Currently pgRouting algorithms don't take into account these changes.

Network layering support

This idea is a quite a challenging task. Network layering would allow the routing algorithm to change from more to less dense networks to enable long-distance routing.

Add Highway Hierarchies routing support

Add support for routing based on Highway Hierarchies based on algorithms developed by P. Sanders and D. Schultes.

K-Shortest Path support

Add support for K-Shortest Path search. That is, not only the shortest path is to be determined, but also the second shortest, the third shortes, and so up to the K-th shortest path.

Better support for turn restrictions

[...]

OpenGraphRouter related ideas

Continue work on this new general purpose OpenSource Routing library that is designed to be modular and reusable and could be used with or without a database.

Improve existing Driving Directions Module

Improve the existing driving direction support and add support for richer information available through the Navteq data model.

Add Turn restriction support based on Navteq data model

Add support for turn restrictions based on the Navteq data model.

Add support for TeleAtlas data

Add support for TeleAtlas data. This would include writing a data loader, adding support to the driving directions module and anything else related to supporting TeleAtlas data.

Add Highway Hierarchies routing support

Add support for routing based on Highway Hierarchies based on algorithms developed by P. Sanders and D. Schultes.

Implement a graph storage based on a database

We currently store the graph in our own set of files that facilitate quick access. We would like to have the option of storing the data in a database. Graph structures are not inherently relation so it is like that data will need to be stored in blobs of some type, but that is open to discussion. The goal of this task would be to design an appropriate structure, and write the C++ classes that would manage moving data in and out of these structures and updating them if needed.

Lots of other options

There are a lot of other possibilities that we would be happy to discuss with any students interested.

Mentor Candidates

The following individuals are potentially willing to serve as OpenRouter/pgRouting mentors or co-mentors.

  • Stephen Woodbridge <woodbri (at) swoodbridge (dot) com>
  • Daniel Kastl <daniel.kastl (at) georepublic (dot) de>
  • Anton Patrushev <anton.patrushev (at) georepublic (dot) co (dot) jp>