CODEWITHSUNDEEP
droolsoptaplanner
Piyush Kumar
Piyush Kumar

Reputation: 3

Optaplanner: Generating a partial solution to VRP where trucks and/or stops may remain unassigned based on Time windows

I am solving a variation on vehicle routing problem. The model worked until I implemented a change where certain vehicles and/or stops may remain unassigned because the construction filter does not allow the move due to time window considerations (late arrival not allowed).

The problem size is 2 trucks/3 stops. truck_1 has 2 stops (Stop_1 and Stop_2) assigned to it, and consequently 1 truck and 1 stop remain unassigned since truck_2 will arrive late to Stop_3.

I have the following error:

INFO  o.o.c.i.c.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: step total (2), time spent (141), best score (-164hard/19387soft).

java.lang.IllegalStateException: Local Search phase started with an uninitialized Solution. First initialize the Solution. For example, run a Construction Heuristic phase first.
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.phaseStarted(DefaultLocalSearchPhase.java:119)
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:60)
    at org.optaplanner.core.impl.solver.DefaultSolver.runPhases(DefaultSolver.java:213)
    at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:176)

I tried to set the planning variable to null (nullable = true) but it seems it is not allowed in case of chained variables. I am using Optaplanner 6.2.

Please help, Thank you, Piyush

Upvotes: 0

Views: 579

Answers (1)

rinde
rinde

Reputation: 1263

Your construction filter may be too restrictive, it could prevent the construction heuristic from creating an initialized solution. You should remove the time window constraint from the construction filter and add it as a hard score constraint in your score calculator instead.

From the Optaplanner docs:

Instead of implementing a hard constraint, it can sometimes be built in. For example: If Lecture A should never be assigned to Room X, but it uses ValueRangeProvider on Solution, so the Solver will often try to assign it to Room X too (only to find out that it breaks a hard constraint). Use a ValueRangeProvider on the planning entity or filtered selection to define that Course A should only be assigned a Room different than X.

This can give a good performance gain in some use cases, not just because the score calculation is faster, but mainly because most optimization algorithms will spend less time evaluating unfeasible solutions. However, usually this not a good idea because there is a real risk of trading short term benefits for long term harm:

  • Many optimization algorithms rely on the freedom to break hard constraints when changing planning entities, to get out of local optima.
  • Both implementation approaches have limitations (feature compatiblity, disabling automatic performance optimizations, ...), as explained in their documentation.

Upvotes: 1

Related Questions