unimprovedStepCountLimit terminator does not terminate

[psion....@gmail.com]

I am using OptaPlanner to solve the Traveling Salesman Problem with Time Windows (TSPTW). My solution is based on the provided VRPTW example.

The problems I need to solve can range from 1 to 100 entities to visit. I initially configured an unimprovedMillisecondsSpentLimit termination on the solver set to 3 seconds. However, I found that larger problems would fail with the following error:

java.lang.IllegalStateException: Local Search phase (1) needs to start from an initialized solution, but the planning variable (Visit.previousRouteEvent) is uninitialized for the entity
  Initialize the solution by configuring a Construction Heuristic phase before this phase.
    at org.optaplanner.core.impl.phase.AbstractPhase.assertWorkingSolutionInitialized(AbstractPhase.java:141)
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.phaseStarted(DefaultLocalSearchPhase.java:124)
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:66)
    at org.optaplanner.core.impl.solver.DefaultSolver.runPhases(DefaultSolver.java:214)
    at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:176)

I believe this error occurs because the solver terminated before an answer was found. If I decrease the unimprovedMillisecondsSpentLimit then the smaller problems also produce this error. If I increase the limit enough, the error doesn't appear.

I currently have unimprovedMillisecondsSpentLimit at 30 seconds and have added an unimprovedStepCountLimit termination to the phase set to 100 steps.

This unimprovedStepCountLimit sometimes terminates; however, some simple problems don't terminate until the unimprovedMillisecondsSpentLimit is hit. The pattern seems to be:

• A problem with only one entity to visit will always take the full 30 seconds.
• A problem with more than one entity to visit will take the full 30 seconds if the allowed arrival times don't overlap.
• A problem whose entities have overlapping arrival times will terminate well before 30 seconds.

As a side note, I believe the author of this post was experiencing the same problem.

I debugged the code and the problem seems to be in LocalSearchDecider.decideNextStep:

for (Move move : moveSelector) {
    LocalSearchMoveScope moveScope = new LocalSearchMoveScope(stepScope);
    moveScope.setMoveIndex(moveIndex);
    moveIndex++;
    moveScope.setMove(move);
    // TODO use Selector filtering to filter out not doable moves
    if (!move.isMoveDoable(scoreDirector)) {
        logger.trace("        Move index ({}) not doable, ignoring move ({}).", moveScope.getMoveIndex(), move);
    } else {
        doMove(moveScope);
        if (forager.isQuitEarly()) {
            break;
        }
    }
    if (termination.isPhaseTerminated(stepScope.getPhaseScope())) {
        break;
    }
}

The problems that are taking the full 30 seconds are doing so because move.isMoveDoable always returns false, so no move is performed and the step count never increments. Because moveSelector is random, it never runs out of moves so I'm stuck in this loop.

Is there something I could configure (config pasted below) that would avoid this problem? As a longer term fix to the code, could the isMoveDoable check be performed within moveSelector so only doable moves are returned?

Here is my config:

<solver>
    <solutionClass>RouteSolution</solutionClass>
    <entityClass>AbstractRouteEvent</entityClass>
    <entityClass>Visit</entityClass>
   
    <scoreDirectorFactory>
        <scoreDefinitionType>HARD_SOFT_LONG</scoreDefinitionType>
        <scoreDrl>routeScoreRules.drl</scoreDrl>
        <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
    </scoreDirectorFactory>
   
    <termination>
        <unimprovedMillisecondsSpentLimit>30000</unimprovedMillisecondsSpentLimit>
    </termination>
    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
  <localSearch>
    <unionMoveSelector>
      <changeMoveSelector/>
      <swapMoveSelector/>
      <subChainChangeMoveSelector>
        <selectReversingMoveToo>true</selectReversingMoveToo>
      </subChainChangeMoveSelector>
      <subChainSwapMoveSelector>
          <selectReversingMoveToo>true</selectReversingMoveToo>
      </subChainSwapMoveSelector>
    </unionMoveSelector>
    <acceptor>
      <lateAcceptanceSize>200</lateAcceptanceSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
    <termination>
      <unimprovedStepCountLimit>100</unimprovedStepCountLimit>
    </termination>
  </localSearch>
</solver>

[psion....@gmail.com]

Correction: move.isMoveDoable doesn't always return false. The moveSelector, RandomUnionMoveSelector, never stops returning moves, so I'm stuck in the loop until the 30 second timeout.

[Paolo Predonzani]

I find this problem of the LocalSearchDecider getting in a infinite loop (which requires an unimprovedMillisecondsSpentLimit to break it) happens when:

- the move selector is infinite

- the number of entities or values is small

In this situation, the the forager never finds an accepted move while the selected move counter just increases indefinitely.

By default in Optaplanner move selectors are random, which also means they're infinite.

Try using SHUFFLED instead of RANDOM:

<unionMoveSelector>
    <cacheType>STEP</cacheType>
    <selectionOrder>SHUFFLED</selectionOrder>

    <changeMoveSelector/>
    <swapMoveSelector/>

    <!-- other selectors -->

</unionMoveSelector>

You may also try <cacheType>PHASE</cacheType>  for performance reasons if your problem allows it.

Reference:

http://docs.jboss.org/optaplanner/release/6.3.0.Final/optaplanner-docs/html_single/index.html#generalSelectorFeatures

Regards

Paolo

[psion....@gmail.com]

Thank you! This resolved my issue.