Add VRP functionality through libvroom

[dkastl]

Is your feature request related to a problem? Please describe.
pgRouting has a few VRP functions already, but it would be better to collaborate on the algorithm part with other projects.

Describe the solution you'd like
Vroom has made it's VRP functionality available as a library, so it could be implemented similar to how pgRouting makes use of Boost for example: https://github.com/VROOM-Project/vroom/blob/master/libvroom_examples/libvroom.cpp

Additional context
We could sponsor this development with funds we have at the moment on CommunityBridge.

[dkastl]

We may use the Vroom terminology to avoid different naming and confusion: https://github.com/VROOM-Project/vroom/blob/master/docs/API.md

• jobs
• shipments
• vehicles
• matrix

According to the Readme VROOM can solve several well-known types of vehicle routing problems (VRP).

• TSP (travelling salesman problem)
• CVRP (capacitated VRP)
• VRPTW (VRP with time windows)
• MDHVRPTW (multi-depot heterogeneous vehicle VRPTW)
• PDPTW (pickup-and-delivery problem with TW)

VROOM can also solve any mix of the above problem types.

[cvvergara]

what with the names that are not on VROOM?
Vehicle Routing Problem with Profits (VRPP)
Team Orienteering Problem (TOP) which is the most studied variant of the VRPP
The Capacitated Team Orienteering Problem (CTOP),
The TOP with Time Windows (TOPTW).
Vehicle Routing Problem with Pickup and Delivery (VRPPD):
Vehicle Routing Problem with LIFO: Similar to the VRPPD, except an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at delivery locations because there is no need to temporarily unload items other than the ones that should be dropped off.
Capacitated Vehicle Routing Problem: CVRP or CVRPTW.
Vehicle Routing Problem with Multiple Trips (VRPMT)
Open Vehicle Routing Problem (OVRP)
Inventory Routing Problem (IRP)

[cvvergara]

Comment about TSP:
https://docs.pgrouting.org/3.1/en/flow-family.html
just like there are many different algorithms to get the flow of a network, we can have many algorithms to solve TSP
The user would just need to choose which one.

[dkastl]

There are the following cases:

1. Solver available in Vroom and not in pgRouting
2. Solver available in pgRouting and not in Vroom
3. Solver available in pgRouting and also in Vroom but somehow different
4. Solver not available anywhere

Case (1) is solved by creating pgr_vroom.
Case (4) might be solved best by adding the function to libvroom and through that to pgRouting
Case (2) is probably OK if we do not look at it at the beginning, but using common terminology might be a good idea
Case (3) is a headache and needss discussion

Since we have lots of shortest path functions for example, that basically do the same but slightly different, I think it's also OK to have multiple implementations of TSP ... just as an example. I just think maintaining less makes it easier, but we don't need to remove functionality.

[cvvergara]

I dont see libvroom as a package on ununtu:
https://packages.ubuntu.com/search?suite=focal&section=all&arch=any&keywords=libvroom&searchon=names

I dont know what are the implications of not using a non package as requirement

[dkastl]

Not sure what Libvroom depends on, but if there are no license implications, could it be just packaged with pgRouting maybe? We wouldn't need all the JSON parser, etc..

[krashish8]

The Vroom-category functions have been added in vrpRouting: pgRouting/vrprouting#10
Documentation: VROOM - Category (Experimental)