Difference between revisions of "OpenRouter 2010 SOC Ideas"
Wiki-Woodbri (talk | contribs) (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...) |
Wiki-Anton (talk | contribs) |
||
| (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 | + | 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. | ||
| − | === | + | === 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 support | + | === 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 === | === Better support for turn restrictions === | ||
| Line 40: | Line 39: | ||
[...] | [...] | ||
| − | == | + | == 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 support | + | === 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 18:17, 23 March 2010
- 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 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:
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
[...]
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 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>