Tasks with multiple required vehicles

jsprit
1

Hi!

We currently use jSprit to solve several problems, and have extended it with support for many different and more complex scenarios than a “simple CVRPTW” . Sadly, we have reached a point where we do not know how we could implement a certain feature, nor if it is possible without major changes.

We would like to allow a task to have a required number of vehicles and, therefore, multiple vehicles per task. In short: a task could now have several vehicles instead of a single one.

When we looked at the problem, we thought about doing the following:

  1. Create multiple tasks for each required vehicle. If a task requires 3 vehicles, we create 3 tasks.
  2. Force tasks to be “atomic”: they are all either done or not done
  3. Force tasks to be assigned to different vehicles
  4. Force tasks to be assigned at startTime

1., 2. and 3. are easy. We already have a solution to 2 and 3 in our project.

However, when we looked at ways of solving 4, we quickly realized how nightmarish it is. We cannot change the startTime dynamically when the algorithm runs (is this correct?), not even with a listener, and therefore have no way of forcing vehicles to start the tasks at the same time. We have pondered about overriding the time travel calculation while the algorithm is running, so that we can change the travel time to make vehicles synchronize their arrival and departure at the task location. We are aware that we would have other issues, such as the need to modify the routes of the user after we update the startTime (e.g. we may have made the following activity unavailable), but we believe that we already know how to do this. Our issue really is: how can we change the start/endTime of an activity while the algorithm is running?

Do you have any proposals to solve this issue? Perhaps our logic is flawed (are we overthinking this?), and 4. really is not feasible, and perhaps there is a better way to achieve what we want. We are accepting any proposal for solution, even if it involves heavily modifying the core logic of jSprit.

Thank you very much for your time