Define the constraints and calculate the score

A score represents the quality of a specific solution. The higher the better. Timefold Solver looks for the best solution, which is the solution with the highest score found in the available time. It might be the optimal solution.

Because this use case has hard and soft constraints, use the HardSoftScore class to represent the score:

Hard constraints must not be broken. For example: The vehicle capacity must not be exceeded.
Soft constraints should not be broken. For example: The sum total of travel time.

Hard constraints are weighted against other hard constraints. Soft constraints are weighted too, against other soft constraints. Hard constraints always outweigh soft constraints, regardless of their respective weights.

To calculate the score, you could implement an EasyScoreCalculator class:

Java
Kotlin

package org.acme.vehiclerouting.solver;

import java.util.List;

import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore;
import ai.timefold.solver.core.api.score.calculator.EasyScoreCalculator;

import org.acme.vehiclerouting.domain.Vehicle;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
import org.acme.vehiclerouting.domain.Visit;

public class VehicleRoutingEasyScoreCalculator implements EasyScoreCalculator<VehicleRoutePlan, HardSoftLongScore> {
    @Override
    public HardSoftLongScore calculateScore(VehicleRoutePlan vehicleRoutePlan) {

        List<Vehicle> vehicleList = vehicleRoutePlan.getVehicles();

        int hardScore = 0;
        int softScore = 0;
        for (Vehicle vehicle : vehicleList) {

            // The demand exceeds the capacity
            if (vehicle.getVisits() != null && vehicle.getTotalDemand() > vehicle.getCapacity()) {
                hardScore -= vehicle.getTotalDemand() - vehicle.getCapacity();
            }

            // Max end-time not met
            if (vehicle.getVisits() != null) {
                for (Visit visit: vehicle.getVisits()) {
                    if (visit.isServiceFinishedAfterMaxEndTime()) {
                        hardScore -= visit.getServiceFinishedDelayInMinutes();
                    }
                }
            }

            softScore -= (int) vehicle.getTotalDrivingTimeSeconds();
        }

        return HardSoftLongScore.of(hardScore, softScore);
    }
}

package org.acme.vehiclerouting.solver;

import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore
import ai.timefold.solver.core.api.score.calculator.EasyScoreCalculator

import org.acme.vehiclerouting.domain.Vehicle
import org.acme.vehiclerouting.domain.VehicleRoutePlan

class VehicleRoutingEasyScoreCalculator :
    EasyScoreCalculator<VehicleRoutePlan, HardSoftLongScore> {
    override fun calculateScore(vehicleRoutePlan: VehicleRoutePlan): HardSoftLongScore {
        val vehicleList: List<Vehicle> = vehicleRoutePlan.vehicles!!

        var hardScore = 0
        var softScore = 0
        for (vehicle in vehicleList) {
            // The demand exceeds the capacity

            if (vehicle.visits != null && vehicle.totalDemand > vehicle.capacity) {
                hardScore -= (vehicle.totalDemand - vehicle.capacity).toInt()
            }

            // Max end-time not met
            if (vehicle.visits != null) {
                for (visit in vehicle.visits!!) {
                    if (visit.isServiceFinishedAfterMaxEndTime) {
                        hardScore -= visit.serviceFinishedDelayInMinutes.toInt()
                    }
                }
            }

            softScore -= vehicle.totalDrivingTimeSeconds.toInt()
        }

        return HardSoftLongScore.of(hardScore.toLong(), softScore.toLong())
    }
}

Unfortunately that does not scale well, because it is non-incremental: every time a visit is scheduled to a different vehicle, all visits are re-evaluated to calculate the new score.

Instead, create a VehicleRoutingConstraintProvider class to perform incremental score calculation. It uses Timefold Solver’s Constraint Streams API which is inspired by Java Streams and SQL:

Java
Kotlin

Create a src/main/java/org/acme/vehiclerouting/solver/VehicleRoutingConstraintProvider.java class:

package org.acme.vehiclerouting.solver;

import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore;
import ai.timefold.solver.core.api.score.stream.Constraint;
import ai.timefold.solver.core.api.score.stream.ConstraintFactory;
import ai.timefold.solver.core.api.score.stream.ConstraintProvider;

import org.acme.vehiclerouting.domain.Visit;
import org.acme.vehiclerouting.domain.Vehicle;
import org.acme.vehiclerouting.solver.justifications.MinimizeTravelTimeJustification;
import org.acme.vehiclerouting.solver.justifications.ServiceFinishedAfterMaxEndTimeJustification;
import org.acme.vehiclerouting.solver.justifications.VehicleCapacityJustification;

public class VehicleRoutingConstraintProvider implements ConstraintProvider {

    public static final String VEHICLE_CAPACITY = "vehicleCapacity";
    public static final String SERVICE_FINISHED_AFTER_MAX_END_TIME = "serviceFinishedAfterMaxEndTime";
    public static final String MINIMIZE_TRAVEL_TIME = "minimizeTravelTime";

    @Override
    public Constraint[] defineConstraints(ConstraintFactory factory) {
        return new Constraint[] {
                vehicleCapacity(factory),
                serviceFinishedAfterMaxEndTime(factory),
                minimizeTravelTime(factory)
        };
    }

    protected Constraint vehicleCapacity(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .filter(vehicle -> vehicle.getTotalDemand() > vehicle.getCapacity())
                .penalizeLong(HardSoftLongScore.ONE_HARD,
                        vehicle -> vehicle.getTotalDemand() - vehicle.getCapacity())
                .justifyWith((vehicle, score) -> new VehicleCapacityJustification(vehicle.getId(), vehicle.getTotalDemand(),
                        vehicle.getCapacity()))
                .asConstraint(VEHICLE_CAPACITY);
    }

    protected Constraint serviceFinishedAfterMaxEndTime(ConstraintFactory factory) {
        return factory.forEach(Visit.class)
                .filter(Visit::isServiceFinishedAfterMaxEndTime)
                .penalizeLong(HardSoftLongScore.ONE_HARD,
                        Visit::getServiceFinishedDelayInMinutes)
                .justifyWith((visit, score) -> new ServiceFinishedAfterMaxEndTimeJustification(visit.getId(),
                        visit.getServiceFinishedDelayInMinutes()))
                .asConstraint(SERVICE_FINISHED_AFTER_MAX_END_TIME);
    }

    protected Constraint minimizeTravelTime(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .penalizeLong(HardSoftLongScore.ONE_SOFT,
                        Vehicle::getTotalDrivingTimeSeconds)
                .justifyWith((vehicle, score) -> new MinimizeTravelTimeJustification(vehicle.getId(),
                        vehicle.getTotalDrivingTimeSeconds()))
                .asConstraint(MINIMIZE_TRAVEL_TIME);
    }
}

Create a src/main/kotlin/org/acme/vehiclerouting/solver/VehicleRoutingConstraintProvider.kt class:

package org.acme.vehiclerouting.solver

import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore
import ai.timefold.solver.core.api.score.stream.Constraint
import ai.timefold.solver.core.api.score.stream.ConstraintFactory
import ai.timefold.solver.core.api.score.stream.ConstraintProvider

import org.acme.vehiclerouting.domain.Visit
import org.acme.vehiclerouting.domain.Vehicle
import org.acme.vehiclerouting.solver.justifications.MinimizeTravelTimeJustification
import org.acme.vehiclerouting.solver.justifications.ServiceFinishedAfterMaxEndTimeJustification
import org.acme.vehiclerouting.solver.justifications.VehicleCapacityJustification

class VehicleRoutingConstraintProvider : ConstraintProvider {
    override fun defineConstraints(factory: ConstraintFactory): Array<Constraint> {
        return arrayOf(
            vehicleCapacity(factory),
            serviceFinishedAfterMaxEndTime(factory),
            minimizeTravelTime(factory)
        )
    }

    protected fun vehicleCapacity(factory: ConstraintFactory): Constraint {
        return factory.forEach(Vehicle::class.java)
            .filter({ vehicle: Vehicle -> vehicle.totalDemand > vehicle.capacity })
            .penalizeLong(
                HardSoftLongScore.ONE_HARD
            ) { vehicle: Vehicle -> vehicle.totalDemand - vehicle.capacity }
            .justifyWith({ vehicle: Vehicle, score: HardSoftLongScore? ->
                VehicleCapacityJustification(
                    vehicle.id, vehicle.totalDemand.toInt(),
                    vehicle.capacity
                )
            })
            .asConstraint(VEHICLE_CAPACITY)
    }

    protected fun serviceFinishedAfterMaxEndTime(factory: ConstraintFactory): Constraint {
        return factory.forEach(Visit::class.java)
            .filter({ obj: Visit -> obj.isServiceFinishedAfterMaxEndTime })
            .penalizeLong(HardSoftLongScore.ONE_HARD,
                { obj: Visit -> obj.serviceFinishedDelayInMinutes })
            .justifyWith({ visit: Visit, score: HardSoftLongScore? ->
                ServiceFinishedAfterMaxEndTimeJustification(
                    visit.id,
                    visit.serviceFinishedDelayInMinutes
                )
            })
            .asConstraint(SERVICE_FINISHED_AFTER_MAX_END_TIME)
    }

    protected fun minimizeTravelTime(factory: ConstraintFactory): Constraint {
        return factory.forEach(Vehicle::class.java)
            .penalizeLong(HardSoftLongScore.ONE_SOFT,
                { obj: Vehicle -> obj.totalDrivingTimeSeconds })
            .justifyWith({ vehicle: Vehicle, score: HardSoftLongScore? ->
                MinimizeTravelTimeJustification(
                    vehicle.id,
                    vehicle.totalDrivingTimeSeconds
                )
            })
            .asConstraint(MINIMIZE_TRAVEL_TIME)
    }

    companion object {
        const val VEHICLE_CAPACITY: String = "vehicleCapacity"
        const val SERVICE_FINISHED_AFTER_MAX_END_TIME: String = "serviceFinishedAfterMaxEndTime"
        const val MINIMIZE_TRAVEL_TIME: String = "minimizeTravelTime"
    }
}

The ConstraintProvider scales much better than the EasyScoreCalculator: typically O(n) instead of O(n²).