Initial routes

[Trollgeir]

Is there - or are there any plans - for the possibility to pass initial routes to vroom which it can continue to optimize?

We have some really big datasets which could be handy to cluster, divide, solve, merge, and then let vroom continue to optimize along the seams.

[jcoupey]

This is not something that would be very hard to implement: we'd have to parse the initial routes and bypass the current heuristic process (replaced by setting up initial routes), then simply move on to the current local search phase. Note that this last step might significantly change the initial routes though. The only technical question would be on how to handle initial routes that are not valid with regard to constraints.

But before diving more into this, could you provide a bit of context on what you're trying to achieve? How would the solution obtained with such a workflow be better/more interesting than the ones you'd get when solving from scratch?

[Trollgeir]

I think it's okay for any first take on such an implementation to have a requirement that the initial routes has to be valid. If I have two sub-problems that I have solved and want to merge them, I am also guaranteed that the merged solution is valid.

Our hypothesis is that splitting the dataset up (per depot/custom clustering, etc.) would make us optimize better and faster (can run them in parallel) and could yield better result. One of our big datasets requires 50mins to solve with vroom (64 threads, but we could get more), and I'd like to not have to degrade our exploration factor as the performance of solutions is vital for us.

[jcoupey]

I think it's okay for any first take on such an implementation to have a requirement that the initial routes has to be valid

Agreed. Also we could have a simple process that:

1. Checks the whole route for validity, then creates it if valid.
2. If the whole route is not valid, try to append jobs one at a time, simply discarding the ones that invalidate the route in construction.

We already have all building blocks in place to do this (function members for RawRoute and TWRoute).

[jcoupey]

One thing to keep in mind is that the current approach spawns several parallel heuristic processes, number depending on exploration level. Then the whole local search phase runs with one thread per search process.

Now if we "seed" the local search with an initial solution, we're down to a single local search phase. I think it still does make sense if the various merged solutions are already good and obtained through the "classical" approach. But then it may be a good opportunity to dig into parallelizing the local search itself. I've had this in mind for a while but not ticketed it yet, will do if we go ahead with this idea.

[jcoupey]

2. If the whole route is not valid, try to append jobs one at a time, simply discarding the ones that invalidate the route in construction.

Turns out this is not so simple, due to shipments: it's not possible to decide whether a pickup (or delivery) is valid in itself in isolation and they can be separated by other tasks in the route.

So the current implementation in #606 checks whether the route is valid as a whole, and issues an error if not.