GSoC 2022 Add Google OR Tools functionality in vrpRouting - pgRouting/pgrouting GitHub Wiki

Table of Contents

Proposal

Brief Description

Vrprouting is a subsection of pgrouting that deals with vehicle routing problems for now. In the long run Vrprouting aims to become the one-stop for all kinds of optimization functions. In this project google OR-tools needs to be integrated with vrprouting.

Google OR is an open-source software suite that can solve optimization problems such as these. The aim of this project is to use Google OR functions and wrap it up with Vrprouting functions to solve the above-mentioned problem

State of the Project Before GSoC

Currently, in Vrprouting, Vehicle routing optimization functions with various constraints have been implemented and are in the experimental stage. No functions related to scheduling, linear optimization and bin packing have been implemented.

Benefits to the Community

Adding google-or tools functionalities have multiple benefits:

  • Bin packing algorithm can be used to find the optimum way to fill items into various trucks/vehicles
  • Knapsack problem can be used to find optimum ways of organising your items
  • Schedule employees in multiple shifts, subject to a complex set of constraints and staffing requirements.
  • In the future, one can extend existing implemented google or-tools functions to more functions and libraries and improve Vrprouting.

Deliverables

  • Implementation of OR-Tools Bin Packing functions: vrp_knapsack, vrp_multiple_knapsack and vrp_bin_packing
  • SQL Queries to run the implemented function with self-documentation
  • Users' Documentation of the function
  • pgTap test cases
  • Wiki page of the function

If time permits

  • Extending the or-tools scheduling library to other algorithms like the “Job shop problem” function signature would be vrp_or_job_shop_scheduler.
  • Additional pgTAP tests and unit tests.

Detailed Proposal

Detailed Proposal in Google Doc

Participants

Title GitHub Handle Name
1st Mentor @krashish8 Ashish Kumar
2nd Mentor @cvvergara Celia Virginia Vergara Castillo
Student Developer @Manas23601 Manas Sivakumar

Timeline

Community Bonding Period (May 20th - June 12th)

  • Get to know my mentors and other members of Pgrouting.
  • Understand the coding principles and application development process of the Pgrouting community.
  • Understand the existing code and available implementation to find suitable measures to improve them.
  • Explore the Google OR functionalities to a greater depth
  • Set up a local development environment for myself.
  • Learn more about PostGIS and Postgresql.
  • Learn how to write a PgTAP.

Introduction Mail : GSoC22 Introduction
Community Bonding Report : Community Bonding Report

First Coding Period (June 13th - July 24th)

Week 1 (June 13th - June 19th)

  • Create a basic skeleton for vrp_or_employee_scheduler
  • Set up a blog for weekly reports

Week 1 report

Week 2 (June 20th - June 26th)

  • Create a basic skeleton for user’s documentation, pgtaps, SQL code
  • Understanding Google Or tools terminology

Week 2 Report:

  • Report Mail : SoC(https://lists.osgeo.org/pipermail/soc/2022-June/004883.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-July/002269.html)

  • What did I get done this week?

    • Deviated from Proposal's Timeline by first implementing the Bin Packing Functions. Will implement Employee Scheduler type if time permits
    • Discussion on function naming convention. Snake-style? Camel Style ?
    • Created a SQL function for knapsack_0_1.
    • Configured CMake to process OR-Tools
    • Created empty placeholders for doc, docqueries, and src files for knapsack
    • Looked at Google OR-tools terminology
    • Learned about pgTAPs
    • Made a Pull Request with the following changes. (Pull Request)

  • What do I plan on doing next week?

    • Figure out how to add the google OR-Tools library to vrpRouting

  • Am I blocked on anything?

    • Didn't have a clear understanding of vrprouting's file structure.
    • Wasted a lot of time reading how postgresSQL works internally.

Week 3 (June 27th - July 03rd)

  • Modularizing the or-tools optimization code into functions(constraints, variable).
  • Building and running the functions in Vrprouting

Week 3 Report:

Week 4 (July 04th - July 10th)

  • Create the necessary class wrappers for the functions.

Week 4 Report:

  • Report Mail : SoC(https://lists.osgeo.org/pipermail/soc/2022-July/004905.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-July/002275.html)

  • What did I get done this week?

    • Updated knapsack driver file with new signature.
    • Working on Knapsack driver implementation with necessary structs.
    • Compiled OR-tools with vrpRouting CMake.
    • Experimented with add_subdirectory() method in CMake.
    • Fixed Lint Errors on my code due to trailing white spaces and indentation mistakes.
    • Updated various developer tool scripts and adjusted them according to my local setup.
    • Made a Pull Request with the following changes. (Pull Request)

  • Hindrance working with OR-Tools CMake:

    • I was able to compile OR-Tools with add_subdirectory and find_package methods, the Issue occurs when I try to use the OR-Tools Library as part of a vrpRouting function.
    • find_package: the location of the root .config file is required. It seems like the ortools.config file is unable to identify all the sub-dependencies .configs inside OR-Tools package and hence fails to work.
      • The target .configs were located in an another folder.
      • Attempted to manually add all the .configs by looping over the project repo. Failed to do so as I couldn't find any discernible pattern to exploit.
    • add_subdirectory: In this Method we compile the two projects separately and link them. This is similar to the approach followed in VROOM addition.
      • Although they were linked, the driver files inside OR-Tools wasn't unlike VROOM.

  • What do I plan on doing next week?

    • Considering I have put two weeks of effort into compiling OR-Tools in vrpRouting with no fruitful results, I have decided to keep it aside for now, finish other works and circle back to it later.
    • Make knapsack function work without using ortools in knapsack driver

  • Am I blocked on anything?

    • None

Week 5 (July 11th - July 17th)

  • Transforming the solution computed to suitable containers for PostgreSQL

Week 5 Report:

Week 6 (July 18th - July 24th)

  • Testing the function using sample pgtap’s. Preparation of first coding period report

Week 6 Report:

  • Report Mail : Soc(https://lists.osgeo.org/pipermail/soc/2022-July/004919.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-July/002283.html)

  • What have I done this week?*

    • After contacting the official community of OR-Tools in Discord. I realised the root cause of the error to be how the abseil-cpp dependency is compiled. apparently there seems to some C++ version discrepancy from my end when I compile.
    • By default, I compile with C++14 where as abseil-cpp at least requires C++17 and above.
    • Due to multiple C++ dialect requirements, absl and all it sub-dependencies failed for me.

  • Huge Roadblock

    • Compiling OR-tools with CMake has proved to be a deadend for me. Considering I'm already half way done, I have decided to forsake all my efforts on compiling OR-Tools C++ and redirect my efforts to an alternate solution that is PL/Python.
    • Switching to python from C++ for knapsack implementation.
    • Made a Pull Request with the following changes. (Pull Request).

  • What do I plan to do next week?*

    • Convert knapsack c++ to python
    • figure out how to add python ortools to pgrouting requirements

  • Am I blocked on anything?*

    • None

Second Coding Period (July 25th - September 04th)

Week 7 (July 25th - July 31st)

  • Create a basic skeleton for vrp_or_knapsack_0_1
  • Create a basic skeleton for vrp_or_mulitple_knapsack_0_1
  • Create a basic skeleton for vrp_or_bin_packing
  • Create a basic skeleton for user’s documentation, pgtaps, SQL code.

Week 7 Report:

  • Report Mail : SoC(https://lists.osgeo.org/pipermail/soc/2022-July/004924.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-July/002288.html)

  • What have I done this week?*

    • Added plpython3u extension to vrpRouting wherever necessary except in Github Actions.
    • Learned how to use PL/Python. Made Sample functions demonstrating basic coding principles.
    • Implemented multiple_knapsack in PL/Python.
    • Implemented bin_packing in PL/Python
    • Converted knapsack from c++ to PL/Python.
    • Updated CMake. i.e no more src requirement for OR-Tools.
    • Made a Pull Request with the following changes. (Pull Request)

  • What do I plan to do next week?*

    • figure out how to compile ortools library in vrpRouting.
    • update Ubuntu Github action to build PL/Python extension.

  • Am I blocked on anything?*

    • None

Week 8 (August 01st - August 07th)

  • Building and running the code in Vrprouting

Week 8 Report:

Week 9 (August 08th - August 14th)

  • wrappers the implemented functions using SQL commands.

Week 9 Report:

Report Mail : SoC(https://lists.osgeo.org/pipermail/soc/2022-August/004941.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-August/002302.html)

  • What have I done this week?*

    • partially implemented no_crash_test and inner_query pgTAP.

  • What do I plan to do next week?*

    • pgTAPs
    • Make necessary changes to tool scripts

  • Am I blocked on anything?*

    • I was occupied with an urgent family issue.

Week 10 (August 15th - August 21st)

  • Transforming the solution computed to suitable containers for PostgreSQL

Week 10 Report:

Report Mail : SoC(https://lists.osgeo.org/pipermail/soc/2022-August/004944.html), pgRouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-August/002303.html)

  • What have I done this week?*

    • pgTAP for ortools
      • no_crash_test
      • types_check
      • inner_query
    • Built Google OR-Tools in Github Actions.
    • Completed docqueries for knapsack, bin_packing and multiple_knapsack.
    • Partially completed Documentation.
    • Added a file in tool scripts to create and insert data into ortools tables.
    • Made a Pull Request with the following changes. (Pull Request)

  • What do I plan to do next week?*

    • Enhancements/bugs if any
    • Update Results and Inner Queries Tables in User's Documentation.
    • Create Final Pull Request

  • Am I blocked on anything?*

    • None

Week 11 (August 22nd - August 28th)

  • Testing the functions using sample pgtap’s.
  • Proof-checking the blog

Week 11 Report:

Week 12 (August 29th - September 04th)

  • Preparation of the final report

Week 12 Report:

Log of Pull Requests

Pull Request Description Date Status
#40 [GSoC-2022] Experimental OR-Tools Category Bin Packing functions - vrp_knapsack, vrp_multiple_knapsack, vrp_bin_packing September 5th, 2022 Merged
#257 GSoC-2022: Manas Sivakumar Week 11 August 28th, 2022 Merged
#252 GSoC-2022: Manas Sivakumar Week 10 August 21st, 2022 Merged
#247 GSoC-2022: Manas Sivakumar Week 8 August 7th, 2022 Merged
#241 GSoC-2022: Manas Sivakumar Week 7 July 31st, 2022 Merged
#236 GSoC-2022: Manas Sivakumar Week 6 July 26th, 2022 Merged
#229 GSoC-2022: Manas Sivakumar Week 5 July 18th, 2022 Merged
#227 GSoC-2022: Manas Sivakumar Week 4 July 11th, 2022 Merged
#225 GSoC-2022: Manas Sivakumar Week 3 July 3rd, 2022 Merged
#219 GSoC-2022: Manas Sivakumar Week 2 June 26th, 2022 Merged
#215 GSoC-2022: Manas Sivakumar Week 1 June 18th, 2022 Merged
#197 Task 2: Experience with GitHub & Git February 11th, 2022 GSoC Task Pull Request - Not to Merge

FOSS4G 2022 Presentation Slides

GSoC_2022_ pgRouting_Presentation_Manas_Sivakumar

Final Report

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

Hello Everyone,

With the Google Summer of Code 2022 coming to an end, I hereby present the final report of my work, which I have done over the course of this summer. Everything that has a beginning must have an end, it has been my pleasure working with the pgRouting community and mentors and becoming a part of OSGeo.

This report is in accordance with the guidelines set by Google and OSGeo GSoC Admins.

    • Title: Adding Google OR-Tools functionality to pgRouting
    • Organisation: pgRouting under OSGeo

  2. Abstract: The GSoC project dealt with the implementation of the OR-Tools Bin Packing category functions in the vrpRouting repository of pgRouting.

Google OR-Tools is an open-source software suite that can solve optimization problems such as:

  • Vehicle Routing
  • Flows
  • Integer and Linear Programming
  • Constraint Programming
  • Bin Packing

The project dealt with implementing the OR-Tools Bin packing functionality as a PostgreSQL function so that it can be used directly in the database. It involved creating three functions in vrpRouting

  • vrp_knapsack
  • vrp_multiple_knapsack
  • vrp_bin_packing

  1. State of the Project Before GSoC: Currently, in vrpRouting, Vehicle routing optimization functions with various constraints have been implemented and are in the experimental stage. No functions related to scheduling, linear optimization and bin packing have been implemented.

  2. 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_knapsack
  • vrp_multiple_knapsack
  • vrp_bin_packing

These functions can now provide solutions to Bin Packing problems in vrpRouting.

  1. Potential Future Work: The library can be extended to solve other optimization problems like:
  • Vehicle Routing
  • Scheduling
  • Network Flows

and also special functions (different signature but similar code) for different applications.

  1. Links:
  1. Blog: Work in Progress : https://manaspilot.blogspot.com/2022/08/google-summer-of-code.html

I'm forever grateful for this opportunity. It has been a strange yet satisfying learning for me. I would be delighted if my code is useful to the community. Finally, thanks to my mentors Vicky and Ashish and all of you for your encouragement. Looking forward to contributing more and growing with the community.

Thanks and regards,
Manas Sivakumar

Community Bonding Period (May 20th - June 12th)

Tasks

  • Request writing access to the OSGeo wiki, for editing all info related to my project.
  • Set up the development environment.
  • Interact 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.
  • Add a wiki link to OSGeo's accepted student's wiki page.
  • Studied GSoC students guide and the OSGeo recommendations for students.
  • Introduce myself and my project on OSGeo's SOC and pgrouting-dev mailing list.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Learn to create unit tests using pgTAP.
  • Created a public repository GSoC-pgRouting where all my works are reflected in the GSoC period.
  • Learned how and where to create Pull Request, merge and how to commit, etc.
  • Created a new branch named [to be made] in the GSoC-pgRouting repository, where I will be merging all the Pull Requests.

Meeting Discussions

  1. June 3rd

    • Introduction meeting with the mentors.
    • Basic Repository preparation of vrpRouting.
    • Understood the files and structures of functions.

  2. June 22nd

    • Learned about code structures.
    • Learned about the work of different directories like src, sql, doc, docqueries, drivers and pgtaps.

  3. July 1st

    • Review of the PR.
    • Learned how to add google OR-tools to CMakeLists.txt.
    • Learned how to make docqueries.

  4. July 6th

    • Learned how to add example code in pgRouting.
    • Learned various developer techniques.

Pre-Bonding Period (March 07th - April 19th)

References