GSoC 2021 VRP functionality with VROOM on the database - pgRouting/pgrouting GitHub Wiki

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
#11 Updated documentation for develop Aug 13th, 2021 Merged
#10 [GSoC-2021] Experimental VROOM Category functions - vrp_vroom, vrp_vroomJobs, vrp_vroomShipments Aug 11th, 2021 Merged
#189 GSoC-2021 Week 9: vrp_vroom Aug 8th, 2021 Merged
#185 GSoC-2021 Week 8: vrp_vroom July 31st, 2021 Merged
#183 GSoC-2021 Week 7: vrp_vroom July 24th, 2021 Merged
#180 GSoC-2021 Week 6: vrp_vroom July 18th, 2021 Merged
#178 GSoC-2021 Week 5: vrp_vroom July 10rd, 2021 Merged
#177 GSoC-2021 Week 4: vrp_vroom July 3rd, 2021 Merged
#174 GSoC-2021 Week 3: vrp_vroom June 26th, 2021 Merged
#170 GSoC-2021 Week 2: vrp_vroom June 19th, 2021 Merged
#167 GSoC-2021 Week 1: vrp_vroom June 12th, 2021 Merged
#165 GSoC-2021 Bonding Period: vrp_vroom June 5th, 2021 Merged
#141 GSoC Task 2: Adding name in contributor list February 9th, 2021 GSoC Task Pull Request - Not to Merge

Slides

https://docs.google.com/presentation/d/1hQeRd-BpQfaz2cMViOenhpQun6Mvi28dnislwvbG73M/edit?usp=sharing

Final Report

(The below report was sent to the two mailing lists of OSGeo - SoC and pgrouting-dev)

Hello everyone,

With the GSoC period coming to an end, I hereby present the final report of my work, which I did over the past 10 weeks. It has been a great experience working twice during GSoC with the pgRouting community and the mentors. This report is in accordance with the guidelines set by Google [1] and OSGeo GSoC Admins [2].

  1. (a) Title: VRP functionality with VROOM on the database for pgRouting
    (b) Organization: pgRouting under OSGeo.

  2. Abstract:

The GSoC project dealt with the implementation of the VROOM category functions in the vrpRouting repository of pgRouting.

VROOM is an open-source optimization engine that aims at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time. It can solve several well-known types of vehicle routing problems (VRP):

  • TSP (travelling salesman problem)
  • CVRP (capacitated VRP)
  • VRPTW (VRP with time windows)
  • MDHVRPTW (multi-depot heterogeneous vehicle VRPTW)
  • PDPTW (pickup-and-delivery problem with TW)
  • VROOM can also solve any mix of the above problem types.

The project dealt with implementing the VROOM functionality as a PostgreSQL function so that it can be used directly in the database. It involved creating the three functions in vrpRouting - vrp_vroom, vrp_vroomJobs, and vrp_vroomShipments.

  1. The state of the project before GSoC:

The vrpRouting repository was created a few months before the starting of the GSoC program, by extracting the code of the pgrouting repository involving the VRP functions. It initially contained 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 was not implemented in vrprouting. The three functions that I created under the VROOM category did not exist before GSoC.

  1. The addition that my project brought to pgRouting:

My project added the code, documentation (with the docqueries), and the pgTAP tests of these three functions:

  • vrp_vroom - Vehicle Routing Problem with VROOM, involving both jobs and shipments.
  • vrp_vroomJobs - Vehicle Routing Problem with VROOM, involving only jobs.
  • vrp_vroomShipments - Vehicle Routing Problem with VROOM, involving only shipments.

We wanted some standard external library for solving the VRP problems (similar to how the other pgRouting functions used Boost for adding the graph algorithms), and that was made available through these functions that I created during GSoC.

  1. Potential Future Work:

The implementation of these functions is complete. We can create more similar functions having different signatures based on the use-case, such as replacing the time with timestamps. The VROOM functionality can be tested by creating performance tests. Also, the build can be made compatible with other OS, such as macOS and Windows, as the build perhaps fails on macOS. Different applications of the functions can be studied, and specific functions can be made based on that.

  1. Links:

(i) Users Documentation:

(ii) Tag:

(iii) Pull Requests:

(iv) Wiki Page:

  1. Image:

  2. Media:

I'm glad to participate in the GSoC program twice as a student developer. I would be happy if my code proves beneficial to the community. Thanks to everyone for the support!

Thank you,
Ashish Kumar.

[1]. https://developers.google.com/open-source/gsoc/help/work-product
[2]. https://lists.osgeo.org/pipermail/soc/2021-August/004804.html

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)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2021-July/004781.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2021-July/002222.html)

  • What did I get done this week?

    • Fixed code checker script.
    • Created functions for min_version and min_lib_version
    • Added and updated the documentation/docqueries.
    • Updated existing pgTAP tests.
    • Added vroomJobs-vroom and vroomShipments-vroom equivalence test
    • Added edge cases test.
    • Made a pull request with all these changes (#185).

  • What do I plan on doing next week?

    • Modify the signature of the functions and make corresponding changes everywhere, so that an SQL query is not stored inside the database.
    • If possible, fix the macOS build, and add more pgTAP tests.

  • Am I blocked on anything?

    • No blocking issues, but need to fix the macOS GitHub Actions Build.

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)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2021-July/004744.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2021-July/002215.html)

  • What did I get done this week?

    • Added VROOM matrix input in base matrix class, and removed my custom added matrix.
    • Changed C++14 to C++17 [‘std::optional’ is only available from C++17 onwards]
    • Added style-lint test and linted the C/C++ code.
    • Changed vehicle load from BIGINT to BIGINT[].
    • Adjusted vroom helper functions, and added some functions to get the result.
    • Completed the basic implementation of vrp_vroom, but may need to do several improvements.
    • Added one sample docquery for vroom.
    • Made a pull request with all these changes (#178).

  • What do I plan on doing next week?

    • Add more docqueries to the vrp_vroom function.
    • Do a manual testing of the function, fix the todos, warnings or bugs.

  • Am I blocked on anything?

    • No blocking issues.

Week 4 (June 28th - July 4th)

Week 3 (June 21st - June 27th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2021-June/004715.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2021-June/002210.html)

  • What did I get done this week?

    • Added function to get positive int array input.
    • Updated all the GitHub actions build for building VROOM with vrprouting: Ubuntu Clang, Boost versions, Check queries, Documentation, Releases. Could not get the macOS build working.
    • Added functions to get columns data input - Index, MatrixIndex, Duration, Priority, Distance.
    • Made a pull request with all these changes (#174).

  • What do I plan on doing next week?

    • I will be adding various functions to connect VROOM with vrprouting.

  • Am I blocked on anything?

    • No blocking issues. Could not get the macOS build working, but this can be fixed later on.

  • Meetings attended in this week

    • June 25th: Discussion on PR#1933 regarding update scripts, and actions to check coding style.

Week 2 (June 14th - June 20th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2021-June/004704.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2021-June/002205.html)

  • What did I get done this week?

    • Added functions to get the postgres datatypes and convert them to vroom C types.
      • Breaks input
      • Steps input
      • Time Windows input
      • Jobs input
      • Shipments input
      • Vehicles input
    • Created basic skeleton to take the inputs in vroom.c and pass them to the vroom driver function.
    • Updated CMakeLists to build and compile vrprouting with vroom.
    • Updated GitHub actions scripts for Ubuntu to build VROOM.
    • Made a pull request with all these changes (#170).

  • What do I plan on doing next week?

    • Update GitHub actions scripts for macOS and other jobs.
    • Add matrix cell input function for vroom
    • Add or update the functions in array input, and columns input file for taking vroom inputs.

  • Am I blocked on anything?

    • No blocking issues.

Week 1 (June 7th - June 13th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2021-June/004690.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2021-June/002202.html)

  • What did I get done this week?

    • Started coding the vrp_vroom function.
    • Added vrp_vroom SQL functions:
    • Added vroom.c file to convert postgres datatypes to C.
    • Added vroom driver file and corresponding header file.
    • Added sample boilerplate for pgTAP test.
    • Updated typedefs and added vroom types structures.
    • Updated CMakeLists temporarily so that tests don't fail on warnings.
    • Updated configuration file, for compilation to include sql and src files of vroom.
    • Made a pull request with all these changes (#167).

  • What do I plan on doing next week?

    • Add functions to get the postgres datatypes and convert them to vroom C types.
    • Pass the data after conversion to the vroom driver function.
    • Add GitHub actions scripts and update CMakeLists to build and compile vrprouting with vroom.

  • Am I blocked on anything?

    • No blocking issues.

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