GSoC Ideas: 2019
This page is always work in progress, because we admit new ideas!
- pgRouting's GSoC Ideas for 2019
- pgRouting's GSoC Mentors:
- Completed in prior years
- How to get started
- pgRouting application requirements
- Details of Ideas
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
- OSGeo's GSoC Recommendations for Students and
- pgRouting application requirements 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's projects related language code:
- osm2pgrouting (C++)
- pgRouting (C++)
- pgroutingLayers for Qgis (python 3)
To give you an idea about possible pgRouting GSoC ideas that can be worked:
| # | Title | Description | Test |
|---|---|---|---|
| 1 | Add fucntionality to pgRoutingLayer plugin | Design & implement | 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 | Implement generic driving directions add-on to pgRouting | Design & implement | test |
| 5 | VRP with Multiple Trips | Design & implement | test |
| 6 | VRP Truck & Trailer routing problem | Design & implement | test |
| 7 | VRP Capacitated location routing problem | Design & implement | test |
| 8 | VRP Support for multiple capacities | Design & implement | test |
| 9 | VRP Museum visitor routing problem | Design & implement | test |
| 10 | GRAPH Contraction | Design & implement | test |
| 11 | GRAPH Asymmetric TSP | Design & implement | test |
| 12 | 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.
Our mentors can mentor any project.
IMPORTANT Number of projects to be accepted is based on mentor availability
| name | 2019 Availability | Mentor Years | Other |
|---|---|---|---|
| Stephen Woodbridge | 2009~2014 | ||
| Daniel Kastl | YES | 2009~2018 | |
| Vicky Vergara | YES | 2015~2018 | |
| Rohith Reddy | 2017~2018 | GSoC-student 2016 | |
| Cayetano Benavent | YES | 2018 | |
| Vidhan Jain | 2018 | GSoC-student 2017 | |
| Sourabh Garg | YES | - | GSoC-student 2018 |
See a list of projects on pgRouting's Google Summer of Code site.
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.
- Fork the GSoC-pgRouting repository
- Clone the GSoC-pgRouting repository
- In your clone, add as upstream the pgRouting main repository
Content of Issue:
- [ ] Install requirements
- [ ] build locally pgRouting v2.6
- [ ] build locally pgRouting v3.0-dev
For pgRouting or osm2pgRouting ideas
Content of Issue:
- [ ] https://www.youtube.com/watch?v=eidEEmGLQcU
- [ ] Make Report as comment on this issue
- [ ] https://www.youtube.com/watch?v=u5senBJUkPc
- [ ] Make Report as comment on this issue
- [ ] https://www.youtube.com/watch?v=YnWhqhNdYyk
- [ ] Make Report as comment on this issue
- [ ] https://www.youtube.com/watch?v=1OEu9C51K2A
- [ ] Make Report as comment on this issue
- [ ] https://www.youtube.com/watch?v=xnqTKD8uD64
- [ ] Make Report as comment on this issue
- [ ] https://www.youtube.com/watch?v=86xWVb4XIyE
- [ ] Make Report as comment on this issue
View the videos and make a report of each one
For pgRoutingLayer ideas
- Fork the GSoC-pgRoutingLayer repository
- Clone the GSoC-pgRoutingLayer repository
- in the clone, add as upstream GSoC-pgRoutingLayer
- Create the issue in your fork Content of Issue:
- [ ] Install requirements
- [ ] build locally pgRoutingLayer
For pgRoutingLayer ideas Content of Issue: TBD
View the videos and make a report of each one
Title of Issue: Get familiar with pgRouting on Github
- [ ] Start on develop branch
- [ ] Make up an issue (on GSoC-project)
- [ ] Propose the solution for the issue you made up
- [ ] 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
- Details of idea 1
- Details of idea 2
- Details of idea 3
- Details of idea 4
- Details of idea 5
- Details of idea 6
- Details of idea 7
- Details of idea 8
- Details of idea 9
- Details of idea 10
- Details of idea 11
- Details of idea 12
Add functionality ot the pgRoutingLayer (https://www.qgis.org/en/site) is based on python 3.0, pgRouting is preparing for the version 3.0 and only functions that are going to be included as official that currently are proposed or experimental can be added.
Also, we would like to have dropdowns for selecting tables, schemas, columns in the GUI. currently they are text boxes.
Documentation on the functions implemented is needed, and modifications to existing documentation is needed when the dropdowns are implemented.
Languages: python3, SQL
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.
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
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.
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.
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.
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.
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.
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.
There are many contraction techniques that are not implemented yet.
Choose only one option of the following:
- Edge contraction
- Contraction Hierarchies
- Area Contraction
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
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
- two_graphs_common_spanning_trees
- etc
