Introduce route optimization

[alexsegura]

After looking around, it looks like VROOM is the best candidate for this, because it plays nicely with our existing stack (it uses OSRM under the hood)

Here are some guidelines to implement it.

Related issues:

• 217

• 887

• 4

---

Add vroom-docker to docker-compose.yml

VROOM is a command-line program, but it's simpler for us to use its API flavour, vroom-express There is a Docker image running vroom-express, vroomvrp/vroom-docker. There is an example docker-compose.yml configuration in the repository. Of courser, VROOM_ROUTER should be osrm

Create a custom Symfony Normalizer to convert a Task to a Job

The VROOM API expects a problem JSON payload, and returns a solution. The JSON payload of the problem is described in the usage section of vroom-express, and also on the API docs of VROOM.

The problem payload contains a jobs key, which correspond to an array of Task objects in our system.

We have our own serialization format, but the VROOM format is different. We use Symfony Normalizer component, and so we need to create a custom Normalizer

⚠️ It's not clear in the docs what is the difference between jobs and shipments, it needs more investigation on how to map data.

We want to solve the following Vehicle Routing Problems

• Vehicle Routing Problem with Pickup and Delivery (VRPPD)
• Vehicle Routing Problem with Time Windows (VRPTW)

In our system, a Task has a type, than can be either pickup or dropoff

Create a RouteOptimizer class

Basically, what we want in the end, is a class that takes an array of Task objects, and returns it optimized. A trivial interface would be:

/**
 * @param Task[] $tasks
 * @return Task[]
 */
public function optimize(array $tasks): array;

The implementation loops over the Tasks, converts them to a VROOM problem payload, decodes the VROOM solution, and returns the list sorted.

It will need some dependencies, like a HTTP client to interact with the VROOM API. We can create a HTTP client using CsaGuzzleBundle, and inject it to the constructor of RouteOptimizer

[andrewcunnin]

looks like a shipment is a series of jobs that share a pickup point. i know that this is a useful distinction for situations like the Compost Collective's routing. however, i think the job object is a more direct translation of task for now.

i'm also not even certain that it's a super useful distinction programmatically and the jobs seem to be just a more flexible version of shipment- i guess the shipment just keeps your json smaller