GSoC Ideas: 2018 - pgRouting/pgrouting GitHub Wiki
pgRouting's GSoC Ideas for 2018
So you are interested in becoming a Google Summer of Code student, This is great! but what should you do to improve your chances of being selected? We recommend reading THIS and THIS to start with.
- Remember to be proactive
- Pick a bug or ask for one and work on fixing it so you learn the product and development environment
- Discuss your ideas on the pgrouting-dev list
- The best GSoC idea is YOUR idea! something that you are really interested in developing.
pgRouting project related code:
- osm2pgrouting (C++)
- pgRouting (C++)
- pgroutingLayers for Qgis (python)
To give you an idea about possible pgRouting GSoC topics:
| # | Title | Description | Test |
|---|---|---|---|
| 1 | Make pgRoutingLayer plugin compatible with the new version of QGIS (Python 3) | Rewrite | test |
| 2 | Improve osm2pgrouting import tool for OpenStreetMap data | Rewrite Using libosmium | test |
| 3 | Create a pgrouting2osm export tool so data can be moved to OSRM engine | Design & implement | test |
| 4 | Multi-modal path planning | Design & implement | test |
| 5 | Implement generic driving directions add-on to pgRouting | Design & implement | test |
| 6 | VRP with Multiple Trips | Design & implement | test |
| 7 | VRP Truck & Trailer routing problem | Design & implement | test |
| 8 | VRP Capacitated location routing problem | Design & implement | test |
| 9 | VRP Support for multiple capacities | Design & implement | test |
| 10 | VRP Museum visitor routing problem | Design & implement | test |
| 11 | GRAPH Contraction | Design & implement | test |
| 12 | GRAPH "Chinese Postman Problem" | Design & implement | test |
| 13 | GRAPH Asymmetric TSP | Design & implement | test |
| 14 | GRAPH C++ Boost graph algorithms | Set up the algorithms to be used with pgRouting | test |
Other ideas? We are always interested in other ideas that potential students want to present. So please don't be shy, contact the pgrouting-dev mailing list and introduce yourself and your idea.
pgRouting's GSoC Mentors:
Our mentors can mentor any project.
IMPORTANT Number of projects to be accepted is based on mentor availability
| name | 2018 Availability | Mentor Years | Other |
|---|---|---|---|
| Stephen Woodbridge | 2009~2014 | ||
| Daniel Kastl | YES | 2009~2017 | |
| Vicky Vergara | YES | 2015~2017 | |
| Rohith Reddy | YES | 2017 | GSoC-student 2016 |
| Cayetano Benavent | YES | ||
| Vidhan Jain | YES | GSoC-student 2017 |
Completed in prior years
See a list of projects on pgRouting's Google Summer of Code site.
How to get started
If you're interested, you you should introduce yourself and your project idea on the pgRouting Developer mailing list. Read our wiki pages for developers and debugging and ask for help if you get stuck.
pgRouting application requirements
Have experience with GitHub & Git
- Fork the repository
- Clone the repository
Create Issue on the fork:
Title of Issue: Get familiar with C++
Content of Issue:
- [ ] https://www.youtube.com/watch?v=eidEEmGLQcU
- [ ] https://www.youtube.com/watch?v=u5senBJUkPc
- [ ] https://www.youtube.com/watch?v=YnWhqhNdYyk
- [ ] https://www.youtube.com/watch?v=1OEu9C51K2A
- [ ] https://www.youtube.com/watch?v=xnqTKD8uD64
- [ ] https://www.youtube.com/watch?v=86xWVb4XIyE
- [ ] Make Report
View the videos and make a report of each one
Create Issue on the fork:
Title of Issue: Get familiar with pgRouting on Github
- [ ] Start on develop branch
- [ ] Choose a Good first issue of pgRouting
- [ ] Propose the solution for the issue
- [ ] Submit a pull request to develop.
Note: The pull request might not be accepted, it is just for testing your skills using github and on reading/modifying/understanding the C++ code
Create Issue on the Fork
Other information on the OSGeo Wiki. The GSoC 2018 Ideas page is outdated but still available.
Details of Ideas
Details of idea 1
QGIS 3.0 changing is based on python 3.0, osm2prouting currently is using python 2.7, the code needs to be upgraded to the new python version.
Additionally add support for the proposed functions
Languages: python3, SQL
Details of idea 2
osm2pgrouting to be modernize, by using libosmium which contains an abstration for interacting with OpenStreetMap (OSM) files.
Currently we only read .osm, with a limitted size, by using libosmium we expect to process also available formats.
The way of working will be incremental, by making small spinets to do small basic task, and refining or adding more spinets until the desired functionality is archived.
Details of idea 3
There is no such tool!!!
Some times, people capture locally on the database information that could be exported to osm format, might be because of the desire to contribute to OSM dataset or because of there is a privacy of their data but they want to use other routing tools that use OSM structure.
Testing is to be done by exporting to OSM format, and using the osm2pgrouting tool to import back again.
The minimal requirement is to export ways & nodes that belong to a “Highway” tag
Details of idea 4
Multi modal routing is the transportation under a single trip, but performed with at least two different means of transport.
For example, to go to work: car, bus, pedestrian, subway, pedestrian (route taxi to bus stop, route bus from stop to stop, rout pedestrian from stop to subway, route subway from stop to stop, rout pedestrian from subway to destination)
Coding has two options:
- Develop using current pgRouting tools. (Using SQL)
- Develop using C++ to add to pgRouting functionality
Details of idea 5
There are two kinds of interfaces for an end user, using a map, or using driving directions. go 500 mts, turn left on foo street, go 300 mts, turn right on bar street, destination is in 20 mts
Based on OpenStreetMap data imported with osm2pgRouting, and the results of a Dijkstra query, create a generic driving directions function.
Details of idea 6
Sometimes a vehicle has to load cargo, deliver all the cargo, go back to the base to load more cargo and go back again, with minimal cost, so an optimized route has to be found.
The VRP problems are when dealing with a fleet of vehicles behaving like described above, and are NP-HARD problems, so a local optimization as a result is desired.
Design an implement the fleet behavior using data returned by the pgRouting costMatrix category.
Details of idea 7
Trailer because of width / height dimensions have implicit restrictions based on the angle of the routes. So for example for a u-turn they need to have sufficient space to perform it. In this problem the trailer only does one trip.
The VRP problems are when dealing with a fleet of vehicles behaving like described above, and are NP-HARD problems, so a local optimization as a result is desired.
Design an implement the fleet behavior using data returned by the pgRouting costMatrix category.
Details of idea 8
Consists of opening one or more depots on a given set of a-priori defined depot locations, and designing, for each opened depot, a number of routes in order to supply the demands of a given set of customers.
The VRP problems are when dealing with a fleet of vehicles behaving like described above, and are NP-HARD problems, so a local optimization as a result is desired.
Design an implement the fleet behavior using data returned by the pgRouting costMatrix category.
Details of idea 9
Distribution of products with multiple categories. Where measuring units for each product can be different. For example: Transporting feathers and fabrics, the feathers take a lot of volume and the fabric take a lot of weight, and the vehicle has volume and weight limitation Each vehicle is allowed to have more than one trip.
The VRP problems are when dealing with a fleet of vehicles behaving like described above, and are NP-HARD problems, so a local optimization as a result is desired.
Design an implement the fleet behavior using data returned by the pgRouting costMatrix category.
Details of idea 10
Each visitor group has some exhibit rooms of interest. The visiting route of a certain visitor group requires going through all the exhibit rooms that the group wants to visit. Routes need to be scheduled based on certain criteria to avoid congestion and/or prolonged touring time.
This VRP problem is when dealing with a set of visitor groups behaving like described above, and are NP-HARD problems, so a local optimization as a result is desired.
Design an implement the fleet behavior using data returned by the pgRouting costMatrix category.
Details of idea 11
There are many contraction techniques that are not implemented yet.
Choose only one option of the following:
- Edge contraction
- Contraction Hierarchies
- Area Contraction
Details of idea 12
Find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit. It may be solved in polynomial time. description taken from wikipedia
Details of idea 13
Asymmetric TSP for a directed graph, currently the pgr_TSP only works with a symmetric cost matrix, but in real life “going to”, and “coming from” and some times with great differences.
This problem is NP-HARD problem so a local optimization is what we look for
Details of idea 14
Boost Graph 1.53 is our official minimum version.
It has many already developed general graph algorithms. From this list: at least three algorithms must be implemented. And additionally a function that uses at least on of the implemented algorithm to solve a problem:
- topological_sort
- transitive_closure
- lengauer_tarjan_dominator_tree
- bellman_ford_shortest_paths
- dag_shortest_paths
- kruskal_minimum_spanning_tree
- prim_minimum_spanning_tree
- two_graphs_common_spanning_trees
- random_spanning_tree
- stoer_wagner_min_cut
- etc