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.
-
a) Title: Adding Google OR-Tools functionality to pgRouting
b) Organisation: pgRouting under OSGeo -
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
-
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.
-
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.
- 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.
- 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
- 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