[pgrouting-dev] GSoC 2022 Final Report : Add Google OR-Tools functionality to pgRouting

[Manas Sivakumar]

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
<https://developers.google.com/open-source/gsoc/help/work-product> and OSGeo
GSoC Admins
<https://lists.osgeo.org/pipermail/soc/2022-September/004962.html>.

1) a) Title: Adding Google OR-Tools functionality to pgRouting
    b) *Organisation: *pgRouting under OSGeo

2) *Abstract: *The GSoC project dealt with the implementation of the OR-Tools
Bin Packing <https://developers.google.com/optimization/bin/bin>
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

   1. vrp_knapsack
   2. vrp_multiple_knapsack
   3. vrp_bin_packing

3) State of the Project Before GSoC: Currently, in vrpRouting
<https://vrp.pgrouting.org/v0/en/introduction.html>, 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.

4) *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:

   1. vrp_knapsack
   2. vrp_multiple_knapsack
   3. vrp_bin_packing

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

5) *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.

6) *Links:*

   - *Tags:*
      - OR-Tools Bin Packing (2022-manas23601-ortools)*: *
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-manas23601-ortools
   - *Pull Requests:*
      - *Final Pull Request: *Experimental OR-Tools Category Bin Packing
      functions: https://github.com/pgRouting/vrprouting/pull/40
      - *Intermediate Pull Request: *
      https://github.com/pgRouting/GSoC-pgRouting/pull/264
   - *Project Documentation:*
      - *Wiki Page: *GSoC 2022 Add Google OR Tools functionality in
      vrpRouting:
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Add-Google-OR-Tools-functionality-in-vrpRouting
      - *User's Documentation: *OR-Tools Category:
      https://manas23601.github.io/GSoC-pgRouting/dev/en/or_tools-category.html
      - *PL/Python What is it and How to use it?: *
      https://github.com/pgRouting/vrprouting/wiki/Pl-Python
   - *Example Image: *
   https://drive.google.com/file/d/1pNO3h-zs4EHkwRvBhDrsM1SJZGaN6Oe2/view?usp=sharing
   - *Media:*
      - *FOSS4G 2022 Presentation: *
      https://docs.google.com/presentation/d/1HbLVxSCwjrUiJE2cy3sdFihpyWihugJ02mJtr643B0Y/edit#slide=id.p1

7) *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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20220912/e7eb2fc6/attachment.htm>