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²).