jsprit should allow multiple tours of same vehicle

[kainagel]

Idea:

• All vehicles get empty tour at end of current tour(s).
• They can be used for ruin and recreate insertions the same way as other tours. Without fixed costs if possible.

[oblonski]

Tilman called me with regard to this. This is already possible when using shipments. It then works as described here: https://www.graphhopper.com/blog/2016/07/21/how-to-model-multiple-delivery-routes-with-a-single-vehicle/ However, solving the underlying problem with shipments takes much longer. Here I have been working on a solution that improves this. I can let you know once you can use it.

[kt86]

Using jsprit "shipments" is an option, but then the algo can no longer do multidepot search. The reason presumably is how the algorithm internally works:

• With "services", we have a number of points (services), which are all inside a tour which are all connected to some depot. One can now take a service and more it from one tour to another. If that other tour starts at a different depot, then the service is automatically assigned to a different depot.
• With "shipments", then we have a number of shipments that need to be moved from one location to another (pick up and delivery problem). So one can move shipments from one tour to another. This is much more expensive, since in the other tour one needs to test multiple insertions for the pickup and multiple insertions for the delivery, while making sure that there is enough space in the vehicle. Now it is clear that this can model multiple visits at the same pickup location, i.e. can one model multiple visits at the depot.
  Clearly, one option is to assign the depots first, and then use shipments. Still, this feels more heavyweight than necessary.

KMT suggests allowing additional tours without fixed costs, and departure times after the arrival from the previous tour. @oblonski , via telephone, instead has the intuition to rather try it as the same tour.

@kt86 and @kainagel will look into the jsprit code, @oblonski will comment.

[JWJoubert]

@kt86 English please.

[oblonski]

https://github.com/graphhopper/jsprit/issues/435

[kainagel]

As a fix are currently doing the following:

1. run multi-depot version with services to assign depot to each service
2. afterwards convert services to shipments, and run single-depot version with shipments. Slow with more than approx. 200 shipments per carrier (multiple days runtime).