GSoC Ideas: 2022
This page is always a work in progress because we admit new ideas!
- pgRouting's GSoC Mentors:
- Introduction
- Summary of Ideas
- pgRouting application requirements
- Details of Ideas
Our mentors can mentor any project (unless otherwise stated).
| Name | 2022 Availability | Mentor Years | Other |
|---|---|---|---|
| Stephen Woodbridge | 2009~2014 | Retired Ex-PSC | |
| Daniel Kastl | YES | 2009~2021 | PSC |
| Vicky Vergara | YES | 2015~2021 | PSC |
| Rohith Reddy | 2017~2018 | GSoC-student 2016 + PSC | |
| Cayetano Benavent | 2018~2020 | PSC | |
| Vidhan Jain | 2018 | GSoC-student 2017 | |
| Sourabh Garg | 2019 | GSoC-student 2018 | |
| Aasheesh Tiwari | 2020 | GSoC-student 2018 | |
| Rahul Chauhan | 2021 | GSoC-student 2017, 2018 | |
| Ashraf Hossain | 2021 | GSoC-student 2009, 2011 | |
| Ashish Kumar | YES | GSoC-student 2020, 2021 | |
| Veenit Kumar | YES | GSoC-student 2021 |
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.
We like contributions on the pgRouting's products:
- osm2pgrouting (C++ & SQL)
- pgRouting (C & C++ & SQL)
- vrpRouting (C & C++ & SQL)
- pgroutingLayers for Qgis (python 3 & SQL)
- Number of projects to be accepted is based on mentor availability
- Review the timeline (alternate link). This year you can spread your coding period over a period of 12 weeks to 22 weeks (June 13 - September 12 up to November 21), plan your proposal accordingly.
- Regardless of the product, in order for the mentors to consider the proposal,
the pgrouting application requirements must be finished and well documented inside the proposal.
- Help for finishing these tasks will be provided by a mentor in pgrouting's gitter channel
- It is not forbidden that you guide each other
- It is forbidden to copy/paste from each other's proposal.
- It is forbidden to copy/paste from a past year's proposal.
The projects are of multiple sizes, classified as medium (~175 hours) or large (~350 hours). Choose accordingly, based on your availability. To give you an idea about possible pgRouting GSoC ideas that can be worked upon:
| # | Title | Duration | Description |
|---|---|---|---|
| 1 | Add functionality to pgRoutingLayer plugin | 175/350 hours | Design & implement |
| 2 | GRAPH C++ Boost graph algorithms | 175/350 hours | Set up the algorithms to be used with pgRouting |
| 3 | Workshop for Jupyter Notebook | Develop an interactive pgRouting workshop using Jupyter Notebook | |
| 4 | Tour recommendation algorithm | Implement an algorithm that recommends routes/tours | |
| 5 | Add VROOM Plan mode functionality in vrpRouting | Set up the VROOM plan mode & use it on a function | |
| 6 | Multi-modal path planning | Design & implement | |
| 7 | Time Dependent shortest path algorithm | Design & implement | |
| 8 | Create a Web API for pgRouting - pg_routeserv | Develop the Web API on top of pg_featureserv | |
| 9 | Add Google OR Tools functionality in vrpRouting | Set up Google OR Tools & use it on a function | |
| 10 | Implement generic driving directions add-on to pgRouting | Design & implement | |
| 11 | Improve osm2pgrouting import tool for OpenStreetMap data | Rewrite Using libosmium | |
| 12 | Create a pgrouting2osm export tool so data can be moved to OSRM engine | Design & implement | |
| 13 | Graph Asymmetric TRSP | Design & implement | |
| 14 | Graph Contraction | Design & implement | |
| 15 | Graph C++ VRP Algorithms | Design & implement |
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.
See a list of projects on pgRouting's Google Summer of Code site.
If you're interested, you should introduce yourself and your project idea on the pgRouting Developer mailing list and pgrouting's gitter channel. Read our wiki pages for developers and debugging and ask for help if you get stuck.
- Open an issue on GSoC-pgRouting repository.
Put the following Content inside the Issue:
- [ ] Intent of application
- [ ] Experience with GitHub & Git
- [ ] Build locally pgRouting
- [ ] Get familiar with C++
- [ ] Get familiar with pgRouting
For the Intent of Application, please write a paragraph about yourself in a comment of this issue.
Create a new issue on your fork with the following content:
- [ ] Fork the [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository
- [ ] activate issues in your fork
- [ ] open an issue in your fork and put this content on the issue
- [ ] Clone your fork repository in your computer
- [ ] Create remote named `upstream` pointing to https://github.com/pgRouting/GSoC-pgRouting
- [ ] checkout to the `develop` branch of `upstream`
- [ ] create new branch with name `<your-git-nick>-test`
- [ ] Edit `doc/src/pgRouting-introduction.rst` and put your name on contributor
- [ ] push the newly created branch with the change
- [ ] Create a pull request to https://github.com/pgRouting/GSoC-pgRouting
- [ ] put link of the PR and of the issue on a comment on the issue you created on [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository
Note: The pull request will not be honored, it is just for testing your skills using Git/GitHub
Create a new issue on your fork with the following content:
- [ ] Install requirements
* Look in the documentation what are the requirements
- [ ] Copy/Paste in a comment of this issue the compilation
- [ ] Put the link of this issue on a comment of the issue of task 1
Create a new issue on your fork with the following content:
- [ ] https://www.youtube.com/watch?v=eidEEmGLQcU
- [ ] Make Report
- [ ] https://www.youtube.com/watch?v=u5senBJUkPc
- [ ] Make Report
- [ ] https://www.youtube.com/watch?v=YnWhqhNdYyk
- [ ] Make Report
- [ ] https://www.youtube.com/watch?v=1OEu9C51K2A
- [ ] Make Report
- [ ] https://www.youtube.com/watch?v=xnqTKD8uD64
- [ ] Make Report
- [ ] https://www.youtube.com/watch?v=86xWVb4XIyE
- [ ] Make Report
- [ ] Put the link of this issue on a comment of the issue of task 1
View the videos and make a:
- one page
- handwritten
report of each one, Take a picture and add the picture of the report in a comment
Create a new issue on your fork with the following content
- [ ] Follow the [workshop](https://workshop.pgrouting.org/2.6/en/index.html) up to chapter 8
- [ ] Use OSGeoLive or your own computer
- [ ] Instead of `city_routing` use `<your-git-nick>-routing`
- [ ] Make 3 screenshots of your work, make sure that `<your-git-nick>-routing` is visible
- [ ] Put the link of this issue on a comment of the issue of task 1
The section must contain the links to the 5 issues and to the pull request
- 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
- Details of idea 13
- Details of idea 14
- Details of idea 15
Add functionality to the pgRoutingLayer (175/350 hours)
Currently, there are only these supported functions
The latest documentation has many more functions that can be added to the pgRoutingLayer plugin.
Many of the functions work in a similar way. For example the pgr_fooCost work similarly
In your proposal:
- You will determine at least two similar functions (175 hours), or four similar functions (350 hours) that are not yet implemented on pgRoutingLayer.
- Include reasons why you think the functions are similar.
- The details of the idea will be in the form of Proposed User's Documentation.
From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code
- User's Documentation
- Comments on code when needed
Languages needed for this idea: python3, SQL
GRAPH C++ Boost graph algorithms (175/350 hours)
From Boost Graph 1.56 which is the official minimum version since v3.2. In section 22 (Algorithms), there is a list of algorithms from where:
- Sparse Matrix Ordering Algorithms
- Graph Metrics
- and many more sections
Have algorithms not yet been implemented on pgRouting
For the proposal choose one algorithm (175 hours) or two algorithms (350 hours) that are not yet implemented in pgRouting.
The proposal must include:
- All requirements from GSoC
- All requirements from OSGeo
- The details of the algorithm need to have
- Section: Testing data
- Section: Proposed Documentation
Consider that the expected products at the end of GSoC are:
- Self Documented Code
- User's Documentation
- Simple pgtap tests
The section must have the following statements
- Link to the Boost example
- CREATE
- INSERT
- SELECT
- A drawing representing the created graph (can be hand made as Graphs do not have geometries)
That will allow mentors to test data
Try to make it look like a pgRouting function documentation
Normally the Boost algorithms come with an example, base your proposal on that example's graph
Example:
From
You would need to CREATE TABLE foo ... and INSERT INTO foo ... a PostgreSQL/pgRouting representation of the graph in the example (remember that on C/C++ counting start from 0, but on PostgreSQL counting start from 1)
Pair edges[14] = { Pair(0,3), //a-d in PostgreSQL -> (1,4)
Pair(0,5), //a-f
Pair(1,2), //b-c
...
Pair(5,7), //f-h
Pair(6,7) }; //g-h
Then test that the query can be executed and give a result with pgr_dijkstra:
SELECT * FROM pgr_dijkstra('SELECT * FROM foo', 1, 7);
Develop an interactive pgRouting workshop using Jupyter Notebook
Jupyter Notebooks are a popular tool to do interactive computing across dozens of programming languages.
The Jupyter Notebook is an open-source web application that allows you to create and share documents that contain live code, equations, visualizations and narrative text. This makes it an interesting candidate to learn pgRouting as an alternative to the existing workshop.
In your proposal:
- Give an overview of the workshop content, the data used, the software used, etc.
- Demonstrate that you have practical experience with Jupyter Notebooks and that you know how to run interactive SQL queries on PostgreSQL/PostGIS/pgRouting.
- The details of the idea will be in the form of Proposed User's Documentation.
- Be clear of the limits of the proposal.
From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.
Consider that at the expected products at the end of GSoC are:
- A Jupyter Notebook with an interactive workshop to learn pgRouting
- Notebook ready to be published and shared
- User's documentation
Tour recommendation algorithm
Think of a use case, where you want to know get a route/tour recommendation of a certain time/length/etc.., for example to do a sightseeing tour, a jogging/cycling course, a patrol route or something similar. This can be a round tour with same start and end point, or the start point can be different from the end point of the tour.
In your proposal:
- Provide the design of the tour recommendation algorithm and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User's Documentation.
- Be clear of the limits of the proposal.
Talk with Vicky and Daniel as Georepublic has implemented such an algorithm for a customer use case, so we can discuss with you about your idea.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Add VROOM Plan mode functionality in vrpRouting
VROOM is a "well known" project for VRP problem. The use of the heuristics used by VROOM using data from the database is of great interest.
VROOM has two solving modes - Default VRP and the Plan mode. The functions for the Default VRP mode are already present in vrpRouting. Add a function for the Plan mode to vrpRouting.
The plan mode aims at choosing ETA for all route steps. Apart from the original parameters, the function should also take an additional parameter containing the description of the expected route of each vehicle. All constraints in input implicitly become soft constraints. The output is a set of routes matching the expected description while minimizing timing violations and reporting all constraint violations. The output must contain additional columns describing the violation cause and the optional duration.
Additionally, look at the VROOM example_3.json and example_3_sol.json as an example for the plan mode.
In your proposal:
- Give an overview of VROOM and its terminology.
- Use VROOM terminology for plan mode and port it into a function design in the vrpRouting extension
- The details of the idea will be in the form of Proposed User's Documentation.
- Be clear of the limits of the proposal.
- To make your pgtap tests use a 5 pick & deliver set of orders from the li & lim benchmark tests. Get the smallest test lc101.txt port the information to a suitable graph. You can use a graph tool of your preference to plot the nodes, their position and join with a line the pickup with the delivery.
From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of vrpRouting. The VROOM functions already present in vrpRouting start with the vrp_vroom prefix.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Multi-modal path planning
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
This functionality was implemented in GSoC 2011, but was not added to pgRouting. Things have changed since then, so it will be implemented from scratch, following the current pgRouting coding practices. You can refer to these wiki pages for hints: Multi modal Public Transit Routing and Transit Routing Tutorial, but please don't directly copy/paste from these pages into your proposal.
In your proposal:
- Provide the design of the tour recommendation algorithm and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Time Dependent shortest path algorithm
Time Dependent shortest path algorithm tries to find the shortest path between the nodes, considering the fact that costs may change during moving along the path. The current functions in pgRouting only take into account the costs at a certain time.
Extend the pgRouting library to support time-dependent shortest path routing where the edge weights are function of time and other parameters. Unlike static scenario, where the edge weights do not change here, we assume that the weights change according to time. So, while traversing any edge, the algorithm must consider the cost of edge at that instant of time.
This functionality was implemented in GSoC 2011, but was not added to pgRouting. Things have changed since then, so it will be implemented from scratch, following the current pgRouting coding practices. You can refer to these wiki pages: Time dependent Dynamic Shortest Path, TDSP Details and TDSP Tutorial and Example, but please don't directly copy/paste from these pages into your proposal.
In your proposal:
- Provide the design of the tour recommendation algorithm and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Create a Web API for pgRouting - pg_routeserv
pg_featureserv is a lightweight RESTful geospatial feature server for PostGIS, written in Go. It helps to easily expose any PostgreSQL function written in a particular format as a RESTful API, returning GeoJSON.
pg_featureserv contains an example that demonstrates how pgr_dijkstra can be exposed over the web for generating a point-to-point route. The example creates a routing function named postgisftw.boston_find_route in PostgreSQL using pgr_dijkstra. pg_featureserv converts this function to an API endpoint /functions/boston_find_route/items.json that returns GeoJSON when called from an API client.
The main purpose of pg_routeserv would be:
- Mechanism to load data into a suitable database schema (or specify how the data should be stored)
- Allow to make requests from applications (API)
- Have a simple demo using the service
In your proposal:
- Give an overview of
pg_featureserv. - Provide the design and plan of the implementation
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, Go, JS)
- User's Documentation
- Comments on code when needed
Languages needed for this idea: SQL, Go, JS.
The majority of work would require using SQL to create functions suitable for pg_featureserv. Any changes related to the pg_featureserv code would require using Golang. Finally, the demo application would require HTML/CSS/JS.
Add Google OR Tools functionality in vrpRouting
Google Optimization Tools (alternate link), a.k.a., OR-Tools, is an open-source, fast and portable software suite for solving combinatorial optimization problems.
Extend the vrpRouting library to add the Google OR Tools functionality in the form of vrpRouting functions.
In your proposal:
- Use the Google OR-Tools terminology and port it into a function design in the vrpRouting extension
- Give an overview of Google OR-Tools, and demonstrate that you are familiar with using the Google OR-Tools library in C++.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Implement generic driving directions add-on to pgRouting
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.
In your proposal:
- Provide the design and plan of the implementation
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Improve osm2pgrouting import tool for OpenStreetMap data
osm2pgrouting is the import tool for OpenStreetMap data to pgRouting database. It needs to be modernized, by using libosmium which contains an abstraction for interacting with OpenStreetMap (OSM) files.
Currently we only read .osm, with a limited size, by using libosmium we also expect to process other available formats.
The way of working will be incremental, by making small snippets to do small basic task, and refining or adding more snippets until the desired functionality is archived.
In your proposal:
- Provide the design and plan of the implementation
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Create a pgrouting2osm export tool so data can be moved to OSRM engine
There is no such tool!!!
Sometimes, people capture locally the database information that could be exported to osm format. This might be because of the desire to contribute to OSM dataset or because of the privacy of their data but they want to use other routing tools that use OSM structure. So, a tool is needed that can export the pgRouting data to osm format.
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.
In your proposal:
- Provide the design and plan of the implementation
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Graph Asymmetric TRSP
Currently the function pgr_TSP only works with a symmetric cost matrix. In real life situations, “going to”, and “coming from” have sometimes large differences. This idea involves implementing an asymmetric TSP for a directed graph.
This problem is NP-HARD problem so a local optimization is what we look for.
In your proposal:
- Provide the design of the algorithm and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Graph Contraction
There are many contraction techniques that are not implemented yet.
Choose only one from the following:
- Edge contraction
- Contraction Hierarchies
- Area Contraction
In your proposal:
- Provide the design of the contraction technique chosen and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
Graph C++ VRP Algorithms
The VRP problems are the problems that deal with a fleet of vehicles with some constraints imposed (described below), and are NP-HARD problems, so a local optimized result is desired.
Design an implement the fleet behavior using data returned by the pgRouting Cost Matrix category.
Choose only one from the following:
- VRP with Multiple Trips: 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.
- VRP Truck & Trailer routing problem: 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.
- VRP Capacitated location routing problem: 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.
- VRP Support for multiple capacities: 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.
- VRP Museum visitor routing problem: 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.
-
Test driven code improvement on current VRP functions: The focus will be to improve
vrp_pgr_pickDeliverfunction, with a different name & parameters names & types using VROOM terminology. A first stage is to create the pgtap tests that will drive the SQL code functionality, and the fixes on the existing base code that will make the tests pass. Consider date/time types as part of your design. To make your pgtap tests use a 5 pick & deliver set of orders from the li & lim benchmark tests.
In your proposal:
- Provide the design of the algorithm chosen and a plan of the implementation
- Research about existing implementations, research papers, etc. and document it.
- The details of the idea will be in the form of Proposed User’s Documentation.
- Be clear of the limits of the proposal.
Consider that at the expected products at the end of GSoC are:
- Self Documented Code (SQL, C, C++)
- Simple pgTAP tests
- User's Documentation
- Comments on code when needed
Languages needed for this idea: C/C++/SQL
