OptaPlanner ignoring constraint

Question

I created a timeToIdealDate constraint in VehicleRoutingConstraintProvider.

• The goal of this constraint is to group visits to vehicles with the visit's idealDate being closest to the vehicle's start date.

• The issue I'm having it doesn't matter which dates are assigned to start and idealDate. It seems like the visits are randomly assigned to vehicles, ignoring the soft constraint.

• What I'm expecting is for the solver to switch visits from one vehicle to the next until the score becomes lower and lower due to start date being closer to the sum of all idealDate` for the vehicle.

Any ideas?

Example

Given we have "Vehicle A" with start date of 2022-01-05 and "Vehicle B" with start date of 2022-10-05. A visit with idealDate 2022-11-23 should be assigned to "Vehicle B".

Sample Dataset

• 5 vehicles (start date spread out throughout a single year)
• 30 visits (idealDate randomly spread throughout a single year)

Main Data

PlanningVisit has idealDate:

• The ideal target date for when a vehicle would visit the location
• Format: unix timestamp in seconds

PlanningVehicle has start:

• The date the vehicle would leave the depot
• Format: unix timestamp in seconds

Code Snippets

vehiclerouting/plugin/planner/VehicleRoutingConstraintProvider.java:

package org.optaweb.vehiclerouting.plugin.planner;

import static org.optaplanner.core.api.score.stream.ConstraintCollectors.sumLong;

import org.optaplanner.core.api.score.buildin.hardmediumsoftlong.HardMediumSoftLongScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
import org.optaplanner.core.api.score.stream.ConstraintProvider;
import org.optaweb.vehiclerouting.plugin.planner.domain.PlanningVisit;

public class VehicleRoutingConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                vehicleCapacity(constraintFactory),
                timeToIdealDate(constraintFactory)
        };
    }

    Constraint vehicleCapacity(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(PlanningVisit.class)
                .groupBy(PlanningVisit::getVehicle, sum(PlanningVisit::getDemand))
                .filter((vehicle, demand) -> demand > vehicle.getCapacity())
                .penalizeLong(
                        "vehicle capacity",
                        HardMediumSoftLongScore.ONE_HARD,
                        (vehicle, demand) -> demand - vehicle.getCapacity());
    }

    Constraint timeToIdealDate(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(PlanningVisit.class)
                .penalizeLong(
                        "time to ideal date",
                        HardMediumSoftLongScore.ONE_SOFT,
                        PlanningVisit::absoluteDistanceToIdealDate);
    }
}

vehiclerouting/plugin/planner/domain/PlanningVisit.java:

package org.optaweb.vehiclerouting.plugin.planner.domain;

import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.lookup.PlanningId;
import org.optaplanner.core.api.domain.variable.AnchorShadowVariable;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
import org.optaplanner.core.api.domain.variable.PlanningVariableGraphType;
import org.optaweb.vehiclerouting.plugin.planner.weight.DepotAngleVisitDifficultyWeightFactory;

@PlanningEntity(difficultyWeightFactoryClass = DepotAngleVisitDifficultyWeightFactory.class)
public class PlanningVisit implements Standstill {

    @PlanningId
    private long id;
    private PlanningLocation location;
    private int idealDate;

    // Planning variable: changes during planning, between score calculations.
    @PlanningVariable(valueRangeProviderRefs = { "vehicleRange", "visitRange" },
            graphType = PlanningVariableGraphType.CHAINED)
    private Standstill previousStandstill;

    // Shadow variables
    private PlanningVisit nextVisit;
    @AnchorShadowVariable(sourceVariableName = "previousStandstill")
    private PlanningVehicle vehicle;

    PlanningVisit() {
        // Hide public constructor in favor of the factory.
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    @Override
    public PlanningLocation getLocation() {
        return location;
    }

    public void setLocation(PlanningLocation location) {
        this.location = location;
    }

    public int getIdealDate() {
        return idealDate;
    }

    public void setIdealDate(int idealDate) {
        this.idealDate = idealDate;
    }

    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    public void setPreviousStandstill(Standstill previousStandstill) {
        this.previousStandstill = previousStandstill;
    }

    @Override
    public PlanningVisit getNextVisit() {
        return nextVisit;
    }

    @Override
    public void setNextVisit(PlanningVisit nextVisit) {
        this.nextVisit = nextVisit;
    }

    public PlanningVehicle getVehicle() {
        return vehicle;
    }

    public void setVehicle(PlanningVehicle vehicle) {
        this.vehicle = vehicle;
    }

    // ************************************************************************
    // Complex methods
    // ************************************************************************

    /**
     * Distance from the previous standstill to this visit. This is used to calculate the travel cost of a chain
     * beginning with a vehicle (at a depot) and ending with the {@link #isLast() last} visit.
     * The chain ends with a visit, not a depot so the cost of returning from the last visit back to the depot
     * has to be added in a separate step using {@link #distanceToDepot()}.
     *
     * @return distance from previous standstill to this visit
     */
    public long distanceFromPreviousStandstill() {
        if (previousStandstill == null) {
            throw new IllegalStateException(
                    "This method must not be called when the previousStandstill (null) is not initialized yet.");
        }
        return previousStandstill.getLocation().distanceTo(location);
    }

    /**
     * Distance from this visit back to the depot.
     *
     * @return distance from this visit back its vehicle's depot
     */
    public long distanceToDepot() {
        return location.distanceTo(vehicle.getLocation());
    }

    public long absoluteDistanceToIdealDate() {
        long vehicleStart = vehicle.getStart();
        if (idealDate > 0 && vehicleStart > 0) {
            return Math.abs(idealDate - vehicleStart);
        }

        return 0;
    }

    /**
     * Whether this visit is the last in a chain.
     *
     * @return true, if this visit has no {@link #getNextVisit() next} visit
     */
    public boolean isLast() {
        return nextVisit == null;
    }

    @Override
    public String toString() {
        return "PlanningVisit{" +
                (location == null ? "" : "location=" + location.getId()) +
                ",demand=" + demand +
                ",idealDate=" + idealDate +
                (previousStandstill == null ? "" : ",previousStandstill='" + previousStandstill.getLocation().getId()) +
                (nextVisit == null ? "" : ",nextVisit=" + nextVisit.getId()) +
                (vehicle == null ? "" : ",vehicle=" + vehicle.getId()) +
                ",id=" + id +
                '}';
    }
}

vehiclerouting/plugin/planner/domain/PlanningVehicle.java:

package org.optaweb.vehiclerouting.plugin.planner.domain;

import java.util.Iterator;
import java.util.NoSuchElementException;

import org.optaplanner.core.api.domain.lookup.PlanningId;

public class PlanningVehicle implements Standstill {

    @PlanningId
    private long id;
    private int capacity;
    private int start;
    private PlanningDepot depot;

    // Shadow variables
    private PlanningVisit nextVisit;

    PlanningVehicle() {
        // Hide public constructor in favor of the factory.
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

   public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public int getStart() {
        return start;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public PlanningDepot getDepot() {
        return depot;
    }

    public void setDepot(PlanningDepot depot) {
        this.depot = depot;
    }

    @Override
    public PlanningVisit getNextVisit() {
        return nextVisit;
    }

    @Override
    public void setNextVisit(PlanningVisit nextVisit) {
        this.nextVisit = nextVisit;
    }

    public Iterable<PlanningVisit> getFutureVisits() {
        return () -> new Iterator<PlanningVisit>() {
            PlanningVisit nextVisit = getNextVisit();

            @Override
            public boolean hasNext() {
                return nextVisit != null;
            }

            @Override
            public PlanningVisit next() {
                if (nextVisit == null) {
                    throw new NoSuchElementException();
                }
                PlanningVisit out = nextVisit;
                nextVisit = nextVisit.getNextVisit();
                return out;
            }
        };
    }

    @Override
    public PlanningLocation getLocation() {
        return depot.getLocation();
    }

    @Override
    public String toString() {
        return "PlanningVehicle{" +
                "start=" + start +
                "capacity=" + capacity +
                (depot == null ? "" : ",depot=" + depot.getId()) +
                (nextVisit == null ? "" : ",nextVisit=" + nextVisit.getId()) +
                ",id=" + id +
                '}';
    }
}

Answer 1

The timeToIdealDate constraint looks right, even though it can be simplified by removing the groupBy() and passing the PlanningVisit::absoluteDistanceToIdealDate directly to the penalizeLong():

Constraint timeToIdealDate(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(PlanningVisit.class)
                .penalizeLong(
                        "time to ideal date",
                        HardMediumSoftLongScore.ONE_SOFT,
                        PlanningVisit::absoluteDistanceToIdealDate);
    }
}

As far as debugging constraints is concerned, the following steps could help:

• create a small dataset that can be visually checked by a human being
• implement a ConstraintProviderTest
• temporarily disable other constraints