Multi Day Vehicle Routing - Use Vehicle With Smaller Day Index

Question

I try to build a multi day vehicle routing based on optaplanner vehicle routing examples. I create VehicleDay class to model a vehicle for a single day trip. The VehicleDay class was a join of Vehicle object and Day object. Here is the classes:

public class Day extends AbstractPersistable {
    protected int dayIndex;
    protected int dayInt;
    protected String day;

    // getter and setter methods
    ...
}

public class Vehicle extends AbstractPersistable {
    protected int capacity;
    protected Depot depot;

    // getter and setter methods
    ...
}

public class VehicleDay extends AbstractPersistable implements Standstill {
    protected Vehicle vehicle;
    protected Day day;

    // Shadow variables
    protected Customer nextCustomer;

    // getter and setter methods
    ...
}

I moved the planning entity from Vehicle to VehicleDay. Then I tried to create a sample dataset (cvrp-72customers-edited.xml) which consist of 8 vehicle days and 71 customers. I take this sample dataset from cvrp-72customers and modify the vehicle capacity to only 3/4 (22000) of the original data. 8 vehicle days are consist of :

1. Vehicle id 1 with Day 1 (MONDAY)
2. Vehicle id 1 with Day 2 (TUESDAY)
3. Vehicle id 2 with Day 1 (MONDAY)
4. Vehicle id 2 with Day 2 (TUESDAY)
5. Vehicle id 3 with Day 1 (MONDAY)
6. Vehicle id 3 with Day 2 (TUESDAY)
7. Vehicle id 4 with Day 1 (MONDAY)
8. Vehicle id 4 with Day 2 (TUESDAY)

But when I tried to run it, the result is some vehicle from Day 1 are not used, and instead planner use some vehicle from Day 2 (cvrp-72customers-edited-solved.xml). What I try to achieve is, the planner use the vehicle with Day 1 first, after all vehicle with Day 1 used, then planner start to use the vehicle on Day 2. I tried to use Comparator and created StandstillDifficultyComparator class :

public class StandstillDifficultyComparator implements Comparator<Standstill>, Serializable {

    @Override
    public int compare(Standstill a, Standstill b) {
        if (a instanceof Customer) {
            return new CompareToBuilder()
                    .append(((Customer)a).getId(), ((Customer)b).getId())
                    .toComparison();    
        } else {
            return new CompareToBuilder()
                    .append(((VehicleDay)a).getDay().getDayIndex(), ((VehicleDay)b).getDay().getDayIndex())
                    .append(((VehicleDay)a).getId(), ((VehicleDay)b).getId())
                    .toComparison();    
        }        
    }

}

Then at the unionMoveSelector configuration, I add my comparator class like this:

<unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterComparatorClass>org.optaplanner.examples.vehiclerouting.domain.solver.StandstillDifficultyComparator</sorterComparatorClass>
            <sorterOrder>ASCENDING</sorterOrder>
        </entitySelector>
      </changeMoveSelector>
      <swapMoveSelector>
        <entitySelector>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterComparatorClass>org.optaplanner.examples.vehiclerouting.domain.solver.StandstillDifficultyComparator</sorterComparatorClass>
            <sorterOrder>ASCENDING</sorterOrder>
        </entitySelector>
      </swapMoveSelector>
      <tailChainSwapMoveSelector>
        <entitySelector>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterComparatorClass>org.optaplanner.examples.vehiclerouting.domain.solver.StandstillDifficultyComparator</sorterComparatorClass>
            <sorterOrder>ASCENDING</sorterOrder>
        </entitySelector>      
      </tailChainSwapMoveSelector>
      <subChainChangeMoveSelector>
        <selectReversingMoveToo>true</selectReversingMoveToo>
        <entitySelector>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterComparatorClass>org.optaplanner.examples.vehiclerouting.domain.solver.StandstillDifficultyComparator</sorterComparatorClass>
            <sorterOrder>ASCENDING</sorterOrder>
        </entitySelector>
      </subChainChangeMoveSelector>
      <subChainSwapMoveSelector>
        <selectReversingMoveToo>true</selectReversingMoveToo>
        <entitySelector>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterComparatorClass>org.optaplanner.examples.vehiclerouting.domain.solver.StandstillDifficultyComparator</sorterComparatorClass>
            <sorterOrder>ASCENDING</sorterOrder>
        </entitySelector>
      </subChainSwapMoveSelector>
    </unionMoveSelector>

When I run it, an exception was throw like this:

Exception in thread "main" java.lang.IllegalArgumentException: Unmarshalling of solverConfigResource (org/optaplanner/examples/vehiclerouting/solver/vehicleRoutingSolverConfig.xml) fails on line number (53).
    at org.optaplanner.core.impl.solver.XStreamXmlSolverFactory.configure(XStreamXmlSolverFactory.java:123)
    at org.optaplanner.core.api.solver.SolverFactory.createFromXmlResource(SolverFactory.java:90)
    at org.optaplanner.examples.common.app.CommonApp.createSolver(CommonApp.java:102)
    at org.optaplanner.examples.common.app.CommonApp.createSolutionBusiness(CommonApp.java:97)
    at org.optaplanner.examples.common.app.CommonApp.init(CommonApp.java:84)
    at org.optaplanner.examples.common.app.CommonApp.init(CommonApp.java:80)
    at org.optaplanner.examples.vehiclerouting.app.VehicleRoutingApp.main(VehicleRoutingApp.java:34)
Caused by: " com.thoughtworks.xstream.converters.reflection.AbstractReflectionConverter$UnknownFieldException: No such field org.optaplanner.core.config.heuristic.selector.move.generic.chained.SubChainChangeMoveSelectorConfig.entitySelector
---- Debugging information ----
message             : No such field org.optaplanner.core.config.heuristic.selector.move.generic.chained.SubChainChangeMoveSelectorConfig.entitySelector
field               : entitySelector
class               : org.optaplanner.core.config.heuristic.selector.move.generic.chained.SubChainChangeMoveSelectorConfig
required-type       : org.optaplanner.core.config.heuristic.selector.move.generic.chained.SubChainChangeMoveSelectorConfig
converter-type      : com.thoughtworks.xstream.converters.reflection.ReflectionConverter
line number         : 53
class[1]            : org.optaplanner.core.config.heuristic.selector.move.composite.UnionMoveSelectorConfig
class[2]            : org.optaplanner.core.config.localsearch.LocalSearchPhaseConfig
class[3]            : org.optaplanner.core.config.solver.SolverConfig
version             : 1.4.10
-------------------------------
    at org.optaplanner.core.impl.solver.XStreamXmlSolverFactory.configure(XStreamXmlSolverFactory.java:123)
    at org.optaplanner.core.api.solver.SolverFactory.createFromXmlResource(SolverFactory.java:90)
    at org.optaplanner.examples.common.app.CommonApp.createSolver(CommonApp.java:102)
    at org.optaplanner.examples.common.app.CommonApp.createSolutionBusiness(CommonApp.java:97)
    at org.optaplanner.examples.common.app.CommonApp.init(CommonApp.java:84)
    at org.optaplanner.examples.common.app.CommonApp.init(CommonApp.java:80)
    at org.optaplanner.examples.vehiclerouting.app.VehicleRoutingApp.main(VehicleRoutingApp.java:34)

How can I make planner use all the vehicle on day 1 first, and then after that use vehicle on day 2?

Answer 1

I think you need to create a scoring rule that rewards OptaPlanner for scheduling the days in order. So in the rule you could say that for every vehicle scheduled on day X deduct one point if Day X-1 is not yet full.