Optaplanner: extending the vrp example to tackle multi trip case

Question

At my company we are currently using optaplanner to solve a vehicle routing problem with great results, we built a web app to manage vehicles, clientes, locations, depots and to show a graphic representation of the solution (including showing the locations in a map). We wrapped the solver in a spring java app with a rest interface to receive request and solve the problem. We are using Google maps to get distance-time data. Now we need to implement multirip....

To tackle the multitrip part I am following this approach:

1.- I added readyTime, endOfTrip and dueTime members to Vehicle class

2.- I created a rule to prevent arrivals at customers after vehicle->dueTime

3.- I modified the ArrivalTimeUpdateListener to consider the vehicle->readyTime when calculating the departureTime from a vehicle (using Math.max(depot->readyTime, vehicle->readyTime)

4.- At this point I started using the vehicle class as if it were a vehicle trip instead of a vehicle (I still don´t change the name but that is the idea )

5.- I created a member nextVehicle in vehicle to represent the next trip

6.- For testing purposes I manually link two vehicles (or vehicle trips) before sending it to solver->solve

7.- In the ArrivalTimeUpdatingVariableListener class I extended the method that updates the arrival times to consider updating the nextVehicle->readyTime and by consequence the arrival times of the customers that belong to the next trip (and so on when there are more than two trips)

I am sure this is not the most elegant solution, but I tried other approaches (using custom shadow variable on Vehicle for instance) but it couldn´t make it work. The problem I am facing right now is that I don´t get to understand the state of the model when ArrivalTimeUpdatingVariableListener is called, maybe someone faced similar problem and can help me. What i found (after try and error) is:

• the customer.getVehice() method not always returns a value (distinct from null value), it seems to get updated some time after the previousStandstill change triggers the listener "updateArrivalTime" method.
  • In construction fase when a customer get assign to a vehicle the customer.getVehice() method returns null (it came from "not assigned")
  • In construction fase when a customer "is freed" the customer.getVehice() method returns the "previous vehicle"
  • In local search fase when a customer get assign to a vehicle the customer.getVehice() method returns the "previous vehicle" (original vehicle)
  • In local search fase when a customer go back to the original vehicle the customer.getVehice() method returns the "previous assign vehicle"

Any thoughts on this? Am I making right assumptions? (because originally I considered customer.getVehicle() as the "actual" vehicle and the solutions were completely wrong...)

• The order of triggering the previousStandstill change it´s kind of difficult to understand (for me). I mean when moving customers or swapping them between vehicles...any thoughts or hints on were to find info?

• Can I access some variables from the "previous state of the model" when the solver makes a move?, because I am thinking I will need that if I continue with this approach (to update the vehicle->endOfTrip that is the nextVehicle->readyTime when the customer is the last one on the chain for instance)

and finally...am i doing something completely wrong conceptually ?

Any comments will be greatly appreciated (and sorry my grammar, I am native spanish speaker)

Answer 1

The chaotic triggering of shadow vars that you describe should not happen any more in optaplanner 6.3.0.Final or higher because it now gives the guarantee shown below.

But older versions (optaplanner 6.2 and earlier) suffer from that chaotic trigger behaviour (as fixed by PLANNER-252 - yes I know that issue number by heart - and yes, I am not the only one) could drive a developer (who's working on a complex model with multiple shadow variable(s)) insane and provide a one way ticket to the asylum.

Fortunately it has been fixed a few months ago, so upgrade to 6.3.0.Final or later and keep your sanity.