NullPointerException in NearbyDistanceMatrix.getDestination()

[Aleksandrs Saveljevs]

Dear Geoffrey and OptaPlanner,

We have OptaPlanner crashing with the following stacktrace:

Exception in thread "main" java.lang.NullPointerException
        at org.optaplanner.core.impl.heuristic.selector.common.nearby.NearbyDistanceMatrix.getDestination(NearbyDistanceMatrix.java:72)
        at org.optaplanner.core.impl.heuristic.selector.value.nearby.NearEntityNearbyValueSelector$RandomEntityNearbyValueIterator.next(NearEntityNearbyValueSelector.java:210)
        at org.optaplanner.core.impl.heuristic.selector.common.iterator.AbstractRandomChangeIterator.createUpcomingSelection(AbstractRandomChangeIterator.java:70)
        at org.optaplanner.core.impl.heuristic.selector.common.iterator.AbstractRandomChangeIterator.createUpcomingSelection(AbstractRandomChangeIterator.java:25)
        at org.optaplanner.core.impl.heuristic.selector.common.iterator.UpcomingSelectionIterator.hasNext(UpcomingSelectionIterator.java:42)
        at org.optaplanner.core.impl.heuristic.selector.move.decorator.FilteringMoveSelector$JustInTimeFilteringMoveIterator.createUpcomingSelection(FilteringMoveSelector.java:96)
        at org.optaplanner.core.impl.heuristic.selector.move.decorator.FilteringMoveSelector$JustInTimeFilteringMoveIterator.createUpcomingSelection(FilteringMoveSelector.java:81)
        at org.optaplanner.core.impl.heuristic.selector.common.iterator.UpcomingSelectionIterator.hasNext(UpcomingSelectionIterator.java:42)
        at org.optaplanner.core.impl.heuristic.selector.move.composite.UnionMoveSelector$RandomUnionMoveIterator.refreshMoveIteratorMap(UnionMoveSelector.java:190)
        at org.optaplanner.core.impl.heuristic.selector.move.composite.UnionMoveSelector$RandomUnionMoveIterator.hasNext(UnionMoveSelector.java:164)
        at org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider.decideNextStep(LocalSearchDecider.java:108)
        at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:70)
        at org.optaplanner.core.impl.solver.AbstractSolver.runPhases(AbstractSolver.java:88)
        at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:191)
        at com.example.ProblemSolver.solve(ProblemSolver.java:44)
        at com.example.ConsoleRunner.main(ConsoleRunner.java:24)

This means that the NearbyDistanceMatrix does not have an entry for the entity and this is due to the following move configuration:

<changeMoveSelector>
    <entitySelector id="entitySelector1">
        <entityClass>com.example.Task</entityClass>
        <filterClass>com.example.TaskChangeFilter</filterClass>
    </entitySelector>
    <valueSelector>
        <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector1"/>
            <nearbyDistanceMeterClass>com.example.TaskDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
        </nearbySelection>
    </valueSelector>
    <filterClass>com.example.TaskChangeMoveFilter</filterClass>
</changeMoveSelector>

The problem seems to be in <filterClass>com.example.TaskChangeFilter</filterClass> part. We have noticed that when TaskDistanceMeter is called in the beginning of local search, it is not called for entities which are filtered out by TaskChangeFilter. Therefore, those entities are absent in NearbyDistanceMatrix and hence the crash.

However, we are a bit confused here - is TaskChangeFilter meant to be called at every step? Experiments show that it is called at every step. But then why is it used to filter out entities from NearbyDistanceMatrix in the very beginning? An entity that may not be suitable for a move in the beginning, may become suitable for a move later on. Therefore, if TaskChangeFilter is meant to be called at every step and filter out entities based on the current situation, it seems incorrect to use it for the purposes of constructing NearbyDistanceMatrix in the beginning.

Is it a bug or some misunderstanding on our part?

Best regards,

Aleksandrs

[Aleksandrs Saveljevs]

Dear Geoffrey and OptaPlanner,

Today I would like to revisit this thread about NullPointerException in NearbyDistanceMatrix.getDestination() and, first of all, I would like to apologize for not including a simple way to practically reproduce the crash in my previous email.

This time, I have prepared a way to reproduce the crash - please see https://github.com/asaveljevs/optaplanner/tree/custom/nearby-distance-crash . It builds upon OptaPlanner 7.49.0 and in commit https://github.com/asaveljevs/optaplanner/commit/7bf86b18ed08e613d28433720faf964c76e12fa9 adds a customer change filter and some logging to see what is going on.

In the filter, for simplicity, only those customers that are not directly attached to a vehicle are accepted. This is artificial, but it allows to show the problem with minimal changes to the code. In our real life scenario, we had work orders that were composed of a short sequence of pickups followed by a short sequence of deliveries and we used the filter, for instance, to not accept single deliveries for consideration, as they cannot be moved by themselves if they have an associated pickup, and this is how we discovered the crash in June last year.

In order to reproduce the crash, just run the examples, select vehicle routing, open "cvrp-32customers" and start solving, after which it should soon crash. A log with the crash is attached for convenience. There we can see that the crash happened after CustomerChangeFilter.accept() on "Customer-22" returned "true" and we can see towards the top of the log that, when NearbyDistanceMatrix was constructed, CustomerChangeFilter.accept() on "Customer-22" returned "false". We can also observe there that CustomerNearbyDistanceMeter.getNearbyDistance() was not called for entities for which CustomerChangeFilter.accept() returned "false".

So having this practical example, I would like to kindly ask you to consider the question in my previous email:

However, we are a bit confused here - is CustomerChangeFilter meant to be called at every step? Experiments show that it is called at every step. But then why is it used to filter out entities from NearbyDistanceMatrix in the very beginning? An entity that may not be suitable for a move in the beginning, may become suitable for a move later on. Therefore, if CustomerChangeFilter is meant to be called at every step and filter out entities based on the current situation, it seems incorrect to use it for the purposes of constructing NearbyDistanceMatrix in the beginning.

If it is a bug and not a misunderstanding on my part, I would be happy to report it on the issue tracker.

Best regards,

Aleksandrs

[Radovan Synek]

Hello Aleksandrs,

what you are describing looks like a valid bug. Would you mind reporting it in the Jira https://issues.redhat.com/projects/PLANNER/summary ?

Thanks,

Radek

[Aleksandrs Saveljevs]

Hello Radek,

Thank you for a prompt response! Upon your request, I have reported the issue as https://issues.redhat.com/browse/PLANNER-2337 .

Kind regards,

Aleksandrs