[SoC] GSoC 2021 - Final Report - VRP functionality with VROOM on the database for pgRouting

[Ashish Kumar]

Hello everyone,

With the GSoC period coming to an end, I hereby present the final report of
my work, which I did over the past 10 weeks. It has been a great experience
working twice during GSoC with the pgRouting community and the mentors.
This report is in accordance with the guidelines set by Google
[1] and OSGeo GSoC Admins [2].

1. (a) *Title*: VRP functionality with VROOM on the database for pgRouting
    (b) *Organization*: pgRouting under OSGeo.

2. *Abstract*:
The GSoC project dealt with the implementation of the VROOM category
functions in the vrpRouting repository of pgRouting.

VROOM is an open-source optimization engine that aims at providing good
solutions to various real-life vehicle routing problems (VRP) within a
small computing time. It 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.

The project dealt with implementing the VROOM functionality as a PostgreSQL
function so that it can be used directly in the database. It involved
creating the three functions in vrpRouting - vrp_vroom, vrp_vroomJobs, and
vrp_vroomShipments.

3. *The state of the project before GSoC*:
The vrpRouting repository was created a few months before the starting of
the GSoC program, by extracting the code of the pgrouting repository
involving the VRP functions. It initially contained the functions to solve
the Pickup-and-Delivery problem (vrp_pgr_pickDeliver and
vrp_pgr_pickDeliverEuclidean) and the Single Depot VRP problem
(vrp_oneDepot). However, the VROOM functionality was not implemented in
vrprouting. The three functions that I created under the VROOM category did
not exist before GSoC.

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:

   - vrp_vroom - Vehicle Routing Problem with VROOM, involving both jobs
   and shipments.
   - vrp_vroomJobs - Vehicle Routing Problem with VROOM, involving only
   jobs.
   - vrp_vroomShipments - Vehicle Routing Problem with VROOM, involving
   only shipments.

We wanted some standard external library for solving the VRP problems
(similar to how the other pgRouting functions used Boost for adding the
graph algorithms), and that was made available through these functions that
I created during GSoC.

5. *Potential Future Work*:
The implementation of these functions is complete. We can create more
similar functions having different signatures based on the use-case, such
as replacing the time with timestamps. The VROOM functionality can be
tested by creating performance tests. Also, the build can be made
compatible with other OS, such as macOS and Windows, as the build perhaps
fails on macOS. Different applications of the functions can be studied, and
specific functions can be made based on that.

6. *Links*:

(i) *Users Documentation*:

   - VROOM - Category (Experimental):
   https://vrp.pgrouting.org/dev/en/vroom-category.html
   - vrp_vroom - Experimental:
   https://vrp.pgrouting.org/dev/en/vrp_vroom.html
   - vrp_vroomJobs - Experimental:
   https://vrp.pgrouting.org/dev/en/vrp_vroomJobs.html
   - vrp_vroomShipments - Experimental:
   https://vrp.pgrouting.org/dev/en/vrp_vroomShipments.html
   - VROOM data section in Sample Data:
   https://vrp.pgrouting.org/dev/en/sampledata.html

(ii) *Tag*:

   - VROOM Category functions:
   https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2021-krashish8-vroom-category

(iii) *Pull Requests*:

   - Final Pull Request: Experimental VROOM Category functions - vrp_vroom,
   vrp_vroomJobs, vrp_vroomShipments -
   https://github.com/pgRouting/vrprouting/pull/10
   - Subsequent Pull Request for updating documentation: Added name in
   contributors list, updated release notes -
   https://github.com/pgRouting/vrprouting/pull/11
   - Intermediate weekly Pull Requests created in GSoC-pgRouting
   repository:
   https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Akrashish8+created%3A%3E2021-01-01

(iv) *Wiki Page*:

   - VRP functionality with VROOM on the database:
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2021-VRP-functionality-with-VROOM-on-the-database

7. *Image*:

   - Example of Garbage Collection with dummy data, solved using the
   VROOM-category functions:
   https://drive.google.com/file/d/1C1povjJG5OE1aHGpLcDyetVSXDrPntI6/view?usp=sharing

8. *Media*:

   - Slide Demonstration:
   https://docs.google.com/presentation/d/1hQeRd-BpQfaz2cMViOenhpQun6Mvi28dnislwvbG73M/edit?usp=sharing


I'm glad to participate in the GSoC program twice as a student developer. I
would be happy if my code proves beneficial to the community. Thanks to
everyone for the support!

Thank you,
Ashish Kumar.

[1]. https://developers.google.com/open-source/gsoc/help/work-product
[2]. https://lists.osgeo.org/pipermail/soc/2021-August/004804.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20210817/39020839/attachment.html>