I am new to optaplanner and hope to use it to solve VRPTW problems with pickups and supplies (VRPTWPD).
I started by using the VRPTW code from the sample repos. I am trying to add to it a solution to my problem. However, I cannot return a solution that meets the priority / vehicle restrictions (pickups must be performed before deliveries, and both must be performed by the same vehicle).
I constantly return a decision where a tough score is what I would expect for such a solution (i.e. I can compensate for all the violations in a small problem with the samples and see that the tough score corresponds to the fines I assigned for these violations) .
First approach . I tried to follow the steps described by Jeffrey De Smeth here: https://stackoverflow.com/a/416829/
Each Customer has a customerType variable that describes whether it is a pickup (PU) or a delivery (DO). It also has a variable called parcelId that indicates which package is either picked up or delivered.
I added a shadow variable to Customer named parcelIdsOnboard . This is a HashSet that contains all the parcelIds that the driver has with it when it visits a given Customer .
My VariableListener , which supports parcelIdsOnboard , looks like this:
public void afterEntityAdded(ScoreDirector scoreDirector, Customer customer) { if (customer instanceof TimeWindowedCustomer) { updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer); } } public void afterVariableChanged(ScoreDirector scoreDirector, Customer customer) { if (customer instanceof TimeWindowedCustomer) { updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer); } } protected void updateParcelsOnboard(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) { Standstill previousStandstill = sourceCustomer.getPreviousStandstill(); Set<Integer> parcelIdsOnboard = (previousStandstill instanceof TimeWindowedCustomer) ? new HashSet<Integer>(((TimeWindowedCustomer) previousStandstill).getParcelIdsOnboard()) : new HashSet<Integer>(); TimeWindowedCustomer shadowCustomer = sourceCustomer; while (shadowCustomer != null) { updateParcelIdsOnboard(parcelIdsOnboard, shadowCustomer); scoreDirector.beforeVariableChanged(shadowCustomer, "parcelIdsOnboard"); shadowCustomer.setParcelIdsOnboard(parcelIdsOnboard); scoreDirector.afterVariableChanged(shadowCustomer, "parcelIdsOnboard"); shadowCustomer = shadowCustomer.getNextCustomer(); } } private void updateParcelIdsOnboard(Set<Integer> parcelIdsOnboard, TimeWindowedCustomer customer) { if (customer.getCustomerType() == Customer.PICKUP) { parcelIdsOnboard.add(customer.getParcelId()); } else if (customer.getCustomerType() == Customer.DELIVERY) { parcelIdsOnboard.remove(customer.getParcelId()); } else {
Then I added the following drool rule:
rule "pickupBeforeDropoff" when TimeWindowedCustomer((customerType == Customer.DELIVERY) && !(parcelIdsOnboard.contains(parcelId))); then System.out.println("precedence violated"); scoreHolder.addHardConstraintMatch(kcontext, -1000); end
For my sample task, I create a total of 6 Customer objects (3 PICKUPS and 3 DELIVERY). The size of my fleet is 12 cars.
When I run this, I constantly get a heavy result of -3000, which matches my result, where I see two cars. One car makes all the pickups and one vehicle makes all the deliveries.
I used the second approach to give each Customer link to its instance of the Customer object (for example, PICKUP Customer for parcel 1 has a reference to DELIVERY Customer for parcel 1 and vice versa).
Then I applied the following rule to ensure that the packages were in the same vehicle (note: does not fully implement the priority restriction).
rule "pudoInSameVehicle" when TimeWindowedCustomer(vehicle != null && counterpartCustomer.getVehicle() != null && (vehicle != counterpartCustomer.getVehicle())); then scoreHolder.addHardConstraintMatch(kcontext, -1000); end
For the same sample issue, this consistently yields a -3000 score and an identical solution above.
I tried to run both rules in FULL_ASSERT mode. A rule using parcelIdsOnboard does not raise any exceptions. However "pudoInSameVehicle" rule raises the following exception (which does not FAST_ASSERT in FAST_ASSERT mode).
The corrupted scoreDirector has no ConstraintMatch(s) which are in excess. The corrupted scoreDirector has 1 ConstraintMatch(s) which are missing:
I am not sure why this is spoiled, any suggestions would be highly appreciated.
Interestingly, both of these methodologies produce the same (wrong) solution. I hope that someone will have suggestions on what to do next. Thanks!
UPDATE:
After immersing myself in claims that started in FULL_ASSERT mode, I realized that the problem was related to the dependent nature of PICKUP and DELIVERY Customer s. That is, if you take a step that removes the tough penalty on DELIVERY Customer , you must also remove the penalty associated with PICKUP Customer . To synchronize them, I updated my VehicleUpdatingVariableListener and my ArrivalTimeUpdatingVariableListener to call result calculation callbacks for both Customer objects. Here's the updateVehicle method updateVehicle after updating it, to invoke the invoice calculation for both Customer who just moved, and to match the Customer .
protected void updateVehicle(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) { Standstill previousStandstill = sourceCustomer.getPreviousStandstill(); Integer departureTime = (previousStandstill instanceof TimeWindowedCustomer) ? ((TimeWindowedCustomer) previousStandstill).getDepartureTime() : null; TimeWindowedCustomer shadowCustomer = sourceCustomer; Integer arrivalTime = calculateArrivalTime(shadowCustomer, departureTime); while (shadowCustomer != null && ObjectUtils.notEqual(shadowCustomer.getArrivalTime(), arrivalTime)) { scoreDirector.beforeVariableChanged(shadowCustomer, "arrivalTime"); scoreDirector.beforeVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime"); shadowCustomer.setArrivalTime(arrivalTime); scoreDirector.afterVariableChanged(shadowCustomer, "arrivalTime"); scoreDirector.afterVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime"); departureTime = shadowCustomer.getDepartureTime(); shadowCustomer = shadowCustomer.getNextCustomer(); arrivalTime = calculateArrivalTime(shadowCustomer, departureTime); } }
This solved the account corruption problem that I had with my second approach, and for a small problem with the samples, I released a solution that satisfies all the strict limits (i.e. the solution had a strict score of 0).
Then I tried to run a big problem (~ 380 clients), but the solutions returned very bad hard points. I tried to find a solution in 1 minute, 5 minutes and 15 minutes. It is believed that the score improves linearly with the lead time. But at 15 minutes the solution is still so bad that it seems that he will need to work at least an hour to create a viable solution. I need it to work after a maximum of 5-10 minutes.
I found out about Filter Selection . My understanding is that you can run the function to check if the movement you are going to do will violate the built-in hard limit, and if that happens, this step will be skipped.
This means that you do not need to re-run account calculations or explore branches that, as you know, will not be fruitful. For example, in my problem, I don’t want you to ever be able to move Customer to Vehicle if his colleague is not assigned to this Vehicle or the Vehicle is not assigned at all.
Here is a filter that I performed to test this. It only works for ChangeMoves, but I suspect that I need this to implement a similar function for SwapMoves.
public class PrecedenceFilterChangeMove implements SelectionFilter<ChangeMove> { @Override public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) { TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity(); if (customer.getCustomerType() == Customer.DELIVERY) { if (customer.getCounterpartCustomer().getVehicle() == null) { return true; } return customer.getVehicle() == customer.getCounterpartCustomer().getVehicle(); } return true; } }
Adding this filter immediately led to worse results. This makes me think that I did this function incorrectly, although it is not clear to me why this is not true.
Update 2:
An employee pointed out a problem with my PrecedenceFilterChangeMove. The following is the correct version. I also included the implementation of PrecedenceFilterSwapMove. Together, they allowed me to find a solution to the problem where strict restrictions are not violated after ~ 10 minutes. There are several other optimizations that I think I can do to reduce this even further.
I will post another update if these changes are fruitful. I would still like to hear from someone in the optaplanner community about my approach and whether they think there are better ways to model this problem!
PrecedenceFilterChangeMove
@Override public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) { TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity(); if (customer.getCustomerType() == Customer.DELIVERY) { if (customer.getCounterpartCustomer().getVehicle() == null) { return true; } return selection.getToPlanningValue() == customer.getCounterpartCustomer().getVehicle(); } return true; }
PrecedenceFilterSwapMove
@Override public boolean accept(ScoreDirector scoreDirector, SwapMove selection) { TimeWindowedCustomer leftCustomer = (TimeWindowedCustomer)selection.getLeftEntity(); TimeWindowedCustomer rightCustomer = (TimeWindowedCustomer)selection.getRightEntity(); if (rightCustomer.getCustomerType() == Customer.DELIVERY || leftCustomer.getCustomerType() == Customer.DELIVERY) { return rightCustomer.getVehicle() == leftCustomer.getCounterpartCustomer().getVehicle() || leftCustomer.getVehicle() == rightCustomer.getCounterpartCustomer().getVehicle(); } return true; }