GSoC Ideas: 2019 - pgRouting/pgrouting GitHub Wiki

pgRouting's GSoC Ideas for 2019

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

Table of Contents

Introduction

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

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)

Summary of Ideas

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.

pgRouting's GSoC Mentors:

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

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 & and building the project

  • Fork the GSoC-pgRouting repository
  • Clone the GSoC-pgRouting repository
  • In your clone, add as upstream the pgRouting main repository

Create Task Issues on your fork

issue: Build locally pgRouting

Content of Issue:

- [ ] Install requirements
- [ ] build locally pgRouting v2.6
- [ ] build locally pgRouting v3.0-dev

issue: Get familiar with C++

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

issue: Get familiar with pgRoutingLayer

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

issue: Get familiar with python 3

For pgRoutingLayer ideas Content of Issue: TBD

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
  - [ ] 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 Ideas

Details of idea 1

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

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

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 5

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 6

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 7

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 8

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 9

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 10

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 11

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 12

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