Skip to content

GSoC 2021 VRP functionality with VROOM on the database

Jump to bottom Edit New page
Ashish Kumar edited this page Jun 5, 2021 · 34 revisions

Table of Contents

Proposal

Brief Description

The project aims at implementing the VRP functionality in the vrprouting repository of pgrouting, using VROOM as a library in C++.

VROOM is an open-source optimization engine, that aims at providing good solutions to well-known Vehicle Routing Problems (VRP), such as:

  • TSP (Travelling Salesman Problem)
  • CVRP (Capacitated VRP)
  • VRPTW (VRP with Time Windows)
  • MDHVRPTW (Multi-Depot Heterogeneous VRPTW)
  • PDPTW (Pickup-and-Delivery Problem with TW)

I propose to implement this functionality as an extension to PostGIS, the PostgreSQL geospatial database, by porting it to vrprouting, so that this functionality can be used in the PostgreSQL database

State of the Project Before GSoC

The vrprouting repository has been recently created by extracting the code of the pgrouting repository involving the VRP functions. It currently contains the functions to solve the Pickup-and-Delivery problem (vrp_pgr_pickDeliver and vrp_pgr_pickDeliverEuclidean) and the Single Depot VRP problem (vrp_oneDepot). However, the VROOM functionality is not yet implemented in vrprouting, which if implemented, can provide good solutions to these problems in an efficient way.

Benefits to the Community

Implementing the VROOM functionality as a postgreSQL extension will be very beneficial to those users who want to use the VROOM functionality in the database. VROOM provides a good solution to well-known vehicle routing problems within small computing times, and it can scale to handle very big instances. It is also customizable and supports user-defined cost matrices. Therefore the VROOM functionality in vrprouting can be of great use to the community, as the users can use it to solve real-world vehicle routing problems efficiently.

Deliverables

The deliverables at the end of GSoC period are:

  • Implementation of VROOM functionality for vrprouting, as a function in postgreSQL database, where the user will provide the JSON structure expected by VROOM, and get the solution of the problem instance in GeoJSON format.
  • Self-documented code in SQL, C, C++ with comments, wherever required.
  • User’s Documentation for the function.
  • Basic pgTAP tests to check the parameter types, parameter names, and connection with VROOM.
  • Experimentation on the C++20 Modules can be done in this project.

Only if time allows:

  • Additional pgTAP tests can be added, such as the server no crash tests and unit tests.
  • More specific functions can be made using VROOM, where the user can give the input in the form of SQL query (instead of JSON structure), and get the result as a set of rows (instead of the GeoJSON).

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @cvvergara Vicky Vergara
2nd Mentor @ashrafroni Ashraf Hossain
3rd Mentor @rahulworld Rahul Chauhan
Student Developer @krashish8 Ashish Kumar

Timeline

Community Bonding Period (May 17th - June 6th)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Get familiar with pgRouting’s development style and VROOM. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Set up the wiki page to keep track of weekly progress.
  • Develop a better understanding of PostgreSQL, PostGIS, PI/pgSQL, and how they interact with pgRouting.
  • Learn to create unit tests using pgTap.

First Coding Period (June 7th - July 11th)

Week 1 (June 7th - June 13th)

  • Developing vrp_vroom() starts.
  • Create a basic skeleton for C, C++, SQL code, users documentation and pgTAP tests.

Week 2 (June 14th - June 20th)

  • Read data from PostgreSQL.
  • Transform data to C++ containers suitable for calling the VROOM instance.

Week 3 (June 21st - June 27th)

  • Create the scripts for building the OSRM instance and running the OSRM server, on which VROOM runs.
  • Create the necessary class wrappers for making connections to VROOM.

Week 4 (June 28th - July 4th)

  • Make connections to the VROOM instance, and pass the parameters.
  • Transform the solution computed by VROOM to C containers suitable for passing to PostgreSQL.

Week 5 (July 5th - July 11th)

  • Basic testing of the function.
  • Preparation of the report for the First Coding Period.

Second Coding Period (July 12th - August 15th)

Week 6 (July 12th - July 18th)

  • Work on the feedback provided from the Phase 1 Evaluation.
  • Create the test script and the environment for running the OSRM server before executing the pgTAP tests of the function, and the GitHub Actions script for the same.
  • Create pgTAP tests to check the connection with the server.

Week 7 (July 19th - July 25th)

  • Create pgTAP tests for the function vrp_vroom() to check the parameter types, and parameter names.
  • Fix the bugs, if any, to ensure that the pgTAP tests pass.

Week 8 (July 26th - August 1st)

  • Prepare user’s documentation.
  • Create suitable queries using the examples of the VROOM API documentation.

Week 9 (August 2nd - August 8th)

  • Integration to the develop branch of the vrpRouting repository (the branch is not yet created)

Week 10 (August 9th - August 15th)

  • Preparation of the final report.

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository for GSoC 2021

Pull Request Description Date Status
#165 vrp_vroom GSoC-2021 Bonding Period June 5th, 2021 Merged
#141 GSoC Task 2: Adding name in contributor list February 9th, 2021 GSoC Task Pull Request - Not to Merge

Weekly Reports

Second Coding Period (July 12th - August 15th)

Week 10 (August 9th - August 15th)

Week 9 (August 2nd - August 8th)

Week 8 (July 26th - August 1st)

Week 7 (July 19th - July 25th)

Week 6 (July 12th - July 18th)

First Coding Period (June 7th - July 11th)

Week 5 (July 5th - July 11th)

Week 4 (June 28th - July 4th)

Week 3 (June 21st - June 27th)

Week 2 (June 14th - June 20th)

Week 1 (June 7th - June 13th)

Community Bonding Period (May 17th - June 6th)

Tasks

  • What did I get done during the Community Bonding period?

    • Set up the development environment.
    • Interacted with mentors, introduce myself to the community, and actively get involved in the discussion.
    • Set up a wiki page to keep track of weekly progress.
    • Studied Google's GSoC students guide and the OSGeo's specific instructions.
    • Added a wiki link to OSGeo's accepted student's wiki page.
    • Introduced myself and my project on OSGeo's SOC mailing list.
    • Got familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
    • Developed a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
    • Learned to create unit tests using pgTAP.
    • Got familiar with the VROOM and its codebase. Also, built VROOM locally, tested it using the sample queries, and tried to call the VROOM functions using C++ via libvroom.
    • Created a new branch named ashish-2021 in the GSoC-pgRouting repository, where I will be merging weekly pull requests.
    • Merged the first pull request in the Bonding Period, consisting of the proposed documentation of vrp_vroom.

  • What do I plan on doing next week?

    • Start coding my function vrp_vroom.
    • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.
    • Read the data from PostgreSQL and transform it to a suitable form, to create a basic skeleton for calling the VROOM functions.

  • Am I blocked on anything?

    • No, currently I don't have any blocking issue.

Meetings

  1. May 21st

    • Introductory meeting with the mentors for the future plans of the GSoC period.

  2. June 1st

    • Met with the core developer of VROOM - Julien Coupey, along with other pgRouting mentors - Daniel and Vicky, to introduce and discuss regarding the project, the VROOM, its terminologies, etc.

Pre-Bonding Period (March 10th - April 13th)

References

  1. Vehicle Routing Open-source Optimization Machine: VROOM-Project/vroom
  2. vrpRouting - Vehicle Routing problems on PostgreSQL: pgRouting/vrprouting
  3. Vehicle Routing Problems - Wikipedia
  4. VROOM API Documentation
  5. VROOM Documentation - Examples
  6. OpenStreetMap data for Ile-de-France: ile-de-france
  7. OpenStreetMap data extracts - Geofabrik
  8. Open Source Routing Machine (OSRM) - Backend: Project-OSRM/osrm-backend
  9. Vehicle Routing Functions - Category (Experimental) - vrpRouting documentation
  10. A sequential insertion heuristic for the initial solution to a constrained vehicle routing problem

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally