OpenRouter 2010 SOC Ideas

• 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:

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>