Prevent triggering unnecessary shadow variable updates in chained planning

Question

We have modelled our vehicle routing problem with pickup and delivery as a chained planning problem. On top of that we have a custom move implementation which unlinks a pickup-delivery pair from the fleet and inserts it somewhere else.

Our chain is updated in a similar fashion as the ArrivalTimeUpdatingVariableListener from the optaplanner examples, starting from the changed planning entities and then proceeding incrementally up until the end of the chain.

We're facing the problem that the chain is being updated unnecessarily often. Since we announce 4 planning variable changes to the scoreDirector for each move, the variable listener performs a full chain update starting from each of these 4 planning entities. Often times all four entities are located in the same chain and one update starting from the first changed entity would be sufficient.

We already implemented an early exit: In case a specific shadow variable is not updated during the chain update we skip the remainder of the chain. However, this only works if by chance we first process the chain from the first entity.

How can we ensure that we only update the chain once per Move, starting from the first changed entity?

Fabian Braun Fabian Braun · Accepted Answer · 2020-11-16T22:48:31

Through debugging and iteratively changing the order in which we announce variable changes to the score director we managed to get rid of the superfluous chain updates.

TL;DR: It seems that Optaplanner triggers chain updates in the order in which planning-variable updates are announced to the score director.

Consider an insertion move which inserts a pickup-delivery pair into an existing chain of Visits (applying terminology from Optaplanner examples):

v1 <- v2 <- v3 <- v4
// insert p between v1&v2, d between v2&v3. Result:
v1 <- p <- v2 <- d <- v3 <- v4

This operation leads to 4 planning variable changes:

p.previousStandstill = v1
v2.previousStandstill = p
d.previousStandstill = v2
v3.previousStandstill = d

Each of these planning variables changes is announced to the score director (scoreDirector.beforeVariableChanged(...), scoreDirector.afterVariableChanged(...)) and without further tweaking Optaplanner will invoke a full chain update from each of the changed entities. This is not necessary, because a single chain update starting from p is sufficient to update all relevant shadow variables.

For preventing Optaplanner to carry out the superfluous chain updates, we need to ensure that:

The planning-variable update of p (the earliest touched entity in the chain) needs to be announced to the scoreDirector before all other planning-variable updates
The iterative chain update is stopped at soon as a shadow variable remains unchanged throughout the process

In our case implementing these steps correctly reduced the CPU-time we spend updating chains by more than 50%.

Prevent triggering unnecessary shadow variable updates in chained planning

1 Answers