This page is always a work in progress because we admit new ideas!

• pgRouting's GSoC Mentors:
• Introduction
  • Important
• Summary of Ideas
  • Completed in prior years
  • How to get started
• pgRouting application requirements
• Details of Ideas

Our mentors can mentor any project (unless otherwise stated).

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.
• We would advise you to choose a different idea that is not chosen by some other student. If the idea is same, the exact algorithm should differ (e.g. choosing two different Boost Graph algorithms). So, please mention in the Gitter channel any idea that you are working upon, to make sure that some other student is not simultaneously working on the same idea.

The projects are of multiple sizes, classified as medium (~175 hours) or large (~350 hours). Choose accordingly, based on your availability. Some projects can be classified in either of the categories, depending on the depth of implementation, so please mention in your proposal the timeline and the total hours.

Apart from the ideas mentioned below, you can choose any interesting ideas from the current issues (such as Functionality Request or Discussion), but please comment on the issue to know its current status and its relevance as a GSoC Idea. Not to mention, "small" bug fixes or feature addition don't comply with a complete GSoC project, but they can be worked upon anytime before the GSoC coding period to become more familiar with the pgRouting's codebase.

To give you an idea about possible pgRouting GSoC ideas that can be worked upon:

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
• Details of idea 16

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 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 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 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 the 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 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 the 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 functional 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 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

Multimodal 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 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

The 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 a function of time and other parameters. Unlike static scenarios, 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 the 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 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 making 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 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 functional 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 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 metres, turn left on foo street, go 300 metres, turn right on bar street, the destination is in 20 metres

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 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 the 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 a 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 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 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 TSP

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 an NP-HARD problem so 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 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 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 implementation

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 and 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 takes a lot of weight, and the vehicle has volume and weight limitations. 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_pickDeliver function, with different name & parameters names & types using VROOM terminology. The 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.

OGC compliant output from pgRouting

The Open Geospacial Consortium OGC is currently working on the OGC Route Exchange Model and the OGC API - Routes - Part 1: Core The aim of this idea is to generate OGC conformant output functionality from pgRouting. A route in the Route Exchange Model (REM) is represented as a GeoJSON Feature Collection.

The idea should be implemented on a postgres extension "pgRouting2rem" (currently is a suggested name) Part of the work should cover:

• Determine the requisites of the extension
• Use the following data as an example: https://download.osgeo.org/pgrouting/workshops/mumbai.osm.bz2
• Create a function that based on a json format will give the result in REM format
• First focus: Make the function work on pgr_dijkstra in the following variation: one to one.
• The result as complete as possible in terms of attributes.
• Second focus: Make the function work on pgr_dijkstra in the rest of the variation: one to many, many to one, many to many, combinations

In your proposal:

• Research about existing implementations of input and output (VROOM, OSRM).
• Deep explanation of your understanding of the current drafts from OGC.
• Be clear of the limits of the proposal.

NOTE: if you are interested in this project let (@cvvergara) know in order to create a suitable repository for the work on this idea.

Consider that 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