Adding Google OR Tools functionality to vrpRouting

- Manas Sivakumar

25th August 2022 in Firenze

Manas Sivakumar

• Student, B. Tech. in CSE
• IIITDMK Chennai, India
• Participated this year in GSoC
• pgRouting Developer
• Email: manas23601@gmail.com

Agenda

​

1. What is Google OR Tools
2. My Contributions
3. Usage & Applications
4. Future Scope
5. Conclusion

OR-Tools

OR-Tools

• Open Source optimization engine
• C++17, Python, Java, C#
• Great and quick solutions to :
• Vehicle Routing Problems
• Integer and linear programming Problems
• Constraint Programming Problems

My Contributions

My Contributions

• Added Google OR-Tools functionality to vrpRouting.
• Created 3 functions with pgTAP tests
• vrp_knapsack
• vrp_multiple_knapsack
• vrp_bin_packing

Benefits to the community

• Bin packing algorithms in vrpRouting
• PL/Python extension support
• Google OR-Tools support
• Applications in resource allocation problems

Usage & Applications

Terminologies

• Weight : The weight of an item
• Cost : The value gained by addition of the item to the knapsack or bin
• Capacity : Total capacity/capacities of the knapsacks or bins

Problem : Knapsack

Problem : Knapsack

CREATE TABLE knapsack_data(� weight INTEGER,� cost INTEGER);

​

Table Creation

INSERT INTO knapsack_data (weight, cost)�VALUES�(12, 4), (2, 2),�(1, 1), (4, 10), (1, 2);

Insert Data

SELECT * FROM vrp_knapsack('SELECT * FROM knapsack_data' , 15)

Query

vrp_knapsack(� Weights_Cost SQL,� Capacity,� max_rows)

​

Signature

Problem :Knapsack (Result)

Future Scope

What next?

Future Scope

• Library can be extended to solve other problems like:
• Routing (TSP, VRP)
• Network Flows
• Scheduling
• Special functions for different applications

�

​

https://github.com/pgRouting/pgrouting

More Information

pgRouting:

vrpRouting

Project:

Wiki Page:

OR-Tools

Manas Sivakumar: manas23601gmail.com

https://pgrouting.org/

https://github.com/pgRouting/vrprouting

https://summerofcode.withgoogle.com

github.com/pgRouting/pgrouting/wiki

Google OR-Tools

Thanks!