Skip to content

GSoC 2022 Add Google OR Tools functionality in vrpRouting

Jump to bottom Edit New page
Manas Sivakumar edited this page Sep 11, 2022 · 30 revisions

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

  • Report Mail : https://lists.osgeo.org/pipermail/soc/2022-June/004876.html

  • What did I get done this week?

    • Created a branch manas-2022 in the GSoC-pgRouting repository.
    • Added My name as a contributor in vrpRouting-introduction.rst
    • Made a Pull Request with the following changes. (Pull Request)

  • What do I plan on doing next week?

    • Create a function skeleton for vrp_knapsack.
    • Create a basic skeleton for doc and docqueries.

  • Am I blocked on anything?

    • I was sick for the majority of last week so I couldn't focus on my week1 tasks. Now that I am fully recovered, I will finish my week1 tasks along with week 2.

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 : https://lists.osgeo.org/pipermail/soc/2022-June/004883.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:

  • Report Mail : https://lists.osgeo.org/pipermail/soc/2022-July/004897.html

  • What did I get done this week?

    • Created a driver file for vrp_knapsack_0_1.
    • Updated doc for vrp_knapsack_0_1.
    • Added OR-Tools C++ build Instructions for Ubuntu in Github Actions.
    • Experimented with different ways on adding OR-Tools to vrpRouting CMake such as.
    • Addressed Issues previously raised
    • Made a Pull Request with the following changes. (Pull Request)

  • What do I plan on doing next week?

    • Complete the driver functions for knapsack. Make necessary structs and SQL conversion functions.
    • Experiment with other CMake Modules to Integrate OR-Tools.
    • Use OR-tools library within vrpRouting.

  • Am I blocked on anything?

    • None

  • Resources:

Week 4 (July 04th - July 10th)

  • Create the necessary class wrappers for the functions.

Week 4 Report:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-July/004905.html

  • What did I get done this week?

    • Created driver files for knapsack
    • Compiled OR-tools with vrprouting OR-tools
    • Pull Request

  • What do I plan on doing next week?

    • 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:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-July/004913.html

  • What did I get done this week?

    • Changed Knapsack Function Signature
    • Created necessary structs and SQL conversion functions
    • Pull Request

  • What do I plan on doing next week?

    • Compile OR-tools with vrprouting OR-tools
    • Try to use ortools in knapsack driver

  • Am I blocked on anything?

    • None

Week 6 (July 18th - July 24th)

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

Week 6 Report:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-July/004919.html

  • What have I done this week?*

    • Compiling OR-tools with Cmake has proved to be a deadend for me.
    • Switching to python from C++ for knapsack implementation.
    • 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 : https://lists.osgeo.org/pipermail/soc/2022-August/004931.html

  • What have I done this week?*

    • Implemented multiple_knapsack in PL/Python
    • Implemented bin_packing in PL/Python
    • Converted knapsack from c++ to PL/Python
    • Pull Request

  • What do I plan to do next week?*

    • figure out how to add python ortools to pgrouting requirements

Am I blocked on anything?

  • None

Week 8 (August 01st - August 07th)

  • Building and running the code in Vrprouting

Week 8 Report:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-July/004924.html

  • What have I done this week?*

    • Error Handling in bin_packing, multiple_knapsack and knapsack
    • Cleaned code
    • added plpython3u to build worflow
    • Pull Request

  • What do I plan to do next week?*

    • pgtap tests
    • Make necessary changes to tool scripts

Am I blocked on anything?

  • None

Week 9 (August 08th - August 14th)

  • wrappers the implemented functions using SQL commands.

Week 9 Report:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-August/004941.html

  • What have I done this week?*

    • partially implemented no_crash_test an inner_query pgtap

  • What do I plan to do next week?*

    • pgtap tests
    • 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 : https://lists.osgeo.org/pipermail/soc/2022-August/004944.html

  • What have I done this week?*

    • no_crash_test, inner_query and types_check pgtaps for ortools
    • Built Google OR-tools in Github Actions
    • Created Docqueries for knapsack, bin_packing and multiple_knapsack.
    • Partially completed Documentation
    • Pull Request

  • What do I plan to do next week?*

    • Enhancements/bugs if any
    • Complete 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:

Report Mail : https://lists.osgeo.org/pipermail/soc/2022-August/004951.html

  • What have I done this week?*

    • Updated signature of all functions to print as SQL Table rows instead of terminal messages
    • Completed Documentation for all OR-Tools functions. Doc
    • Updated Docqueries, pgTAPs and SQL files
    • Pull Request

  • What do I plan to do next week?*

    • Final PR to vrpRouting repo
    • Final report

Am I blocked on anything?

  • None

Week 12 (August 29th - September 04th)

  • Preparation of the final report

Log of Pull Requests

Pull Request Description Date Status
#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

Slides

https://docs.google.com/presentation/d/1HbLVxSCwjrUiJE2cy3sdFihpyWihugJ02mJtr643B0Y/edit?usp=sharing

Final Report

To be added.

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.

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

References

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally