CVRPTW with Precedences amd vehicle failure in OptaPlanner

Question

I have a problem and it is really hard for me to manage it. I want to use OptaPlanner to solve a CVRPTW with Precedences and vehicle failures. What I have done so far is to get the standard example and solve it in the GUI, and then save the results. Than I modified the .xml file in python, to manually delete a vehicle and free the customers. I know the right way is to make a ProblemFact, but I don't have a clue how to do this. I saw some answers, but I would need more help or an example of how it is done.

The second thing is, how I could model precedences. So customer 'A' has to come before customer 'B'. (The only example is within another problem called Project Job Scheduling)

Thank you very much!

score 3 · Accepted Answer · answered Aug 27 '18 at 22:47

Question A is super easy.

Question B not so.

As for A, you need to be at a position where you can access the object graph (say, after deserializing a solution). Then, you get the first customer of that vehicle, setting its previousStandstill to null:

 Customer nextCustomer = vehicle.getNextCustomer();
 if (nextCustomer != null){
     scoreDirector.beforeVariableChanged(nextCustomer, "previousStandstill");
     nextCustomer.setPreviousStandstill(null);
     scoreDirector.afterVariableChanged(nextCustomer, "previousStandstill");
     scoreDirector.triggerVariableListeners();
 }

I believe that Question B warrants more attention. The default way of doing this is to implement an OrderListener which triggers on previousStandstill of the customer, the listener updating all the customers in a vehicle's chain whenever a previousStandstill is changed on any customer:

@CustomShadowVariable(variableListenerClass = OrderListener.class,
        sources = {@PlanningVariableReference(variableName = "previousStandstill")})
public Integer getPositionInVehicleChain() {
    return position;
}

and then in the OrderListener's afterVariableChanged method to have something like this:

while (nextCustomer != null) {
        if (position == nextTe.getPositionInVehicleChain()) break;
        scoreDirector.beforeVariableChanged(nextCustomer, "position");
        nextCustomer.setPositionInStapelabschnitt(pos);
        scoreDirector.afterVariableChanged(nextCustomer, "position");
        pos++;
        nextCustomer = nextCustomer.getNextCustomer();  
    }

Then you implement an isBeforeCustomer(Customer otherCustomer) in your Customer class, where you compare the two positions.

However, this is certainly not the most elegant method, as its time complexity is O(n), where n is the total number of planning entities. The nice way of doing this is to implement a so called Order Maintenance data structure on the customers per vehicle. This data structure supports the operations

Insert (x, y): This is inserting a new customer in an existing chain
Delete (x): This is removing a customer in an existing chain, see question A.
Order (x, y): Determine whether x precedes y in the chain order - this is what you're after.

The state of the art algorithms (see, e.g., "Bender M.A., Cole R., Demaine E.D., Farach-Colton M., Zito J. (2002) Two Simplified Algorithms for Maintaining Order in a List. In: Möhring R., Raman R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg") support O(1) amortized insertion/deletion time and O(1) worst-case query time, much better than the system proposed above (but a lot more work). Have a look around for transitivity utils if you're interested in an implementation. I would be very interested if such a data structure were included as shadow variables out of the box in optaplanner - the question of whether an entity is before another in a chain is ubiquitous.

I've thinking of adding such an out of the box `@OrderShadowVariable` (name will change) so you get the order number without having to write the `VariableListener`, similar to how there's out of the box `@AnchorShadowVariable`. — Geoffrey De Smet, Aug 28 '18 at 07:00

CVRPTW with Precedences amd vehicle failure in OptaPlanner

1 Answers1