GustavoArzola
GustavoArzola

Reputation: 21

Optaplanner: extending the vrp example to tackle multi trip case

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:

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...)

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

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

Upvotes: 2

Views: 789

Answers (1)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27357

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.

enter image description here

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.

Upvotes: 1

Related Questions