Vehicle Routing Quick Start Guide
1. What you will build
You will build a REST application that optimizes a Vehicle Route Problem (VRP):
Your service will assign Vist
instances to Vehicle
instances automatically
by using AI to adhere to hard and soft scheduling constraints, such as the following examples:
-
The demand for a vehicle cannot exceed its capacity.
-
The deliveries have specific deadlines that must be met.
-
The less total travel time, the better.
Mathematically speaking, VRP is an NP-hard problem. This means it is difficult to scale. Simply brute force iterating through all possible combinations takes millions of years for a non-trivial dataset, even on a supercomputer. Luckily, AI constraint solvers such as Timefold Solver have advanced algorithms that deliver a near-optimal solution in a reasonable amount of time.
2. Solution source code
Follow the instructions in the next sections to create the application step by step (recommended).
Alternatively, you can also skip right to the completed example:
-
Clone the Git repository:
$ git clone https://github.com/TimefoldAI/timefold-quickstarts
or download an archive.
-
Find the solution in the
java
directory and run it (see its README file).
3. Prerequisites
To complete this guide, you need:
-
JDK 17+ with
JAVA_HOME
configured appropriately. For example with Sdkman:$ curl -s "https://get.sdkman.io" | bash $ sdk install java
-
Apache Maven 3.9.2+
-
An IDE, such as IntelliJ IDEA, VSCode or Eclipse
4. The build file and the dependencies
Use code.quarkus.io to generate an application with the following extensions, for Maven or Gradle:
-
RESTEasy JAX-RS (
quarkus-resteasy
) -
RESTEasy Jackson (
quarkus-resteasy-jackson
) -
Timefold Solver (
timefold-solver-quarkus
) -
Timefold Solver Jackson (
timefold-solver-quarkus-jackson
)
Your pom.xml
file has the following content:
-
Java
-
Kotlin
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.acme</groupId>
<artifactId>vehicle-routing</artifactId>
<version>1.0-SNAPSHOT</version>
<properties>
<maven.compiler.release>11</maven.compiler.release>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<version.io.quarkus>3.14.4</version.io.quarkus>
<version.ai.timefold.solver>1.14.0</version.ai.timefold.solver>
</properties>
<dependencyManagement>
<dependencies>
<dependency>
<groupId>io.quarkus</groupId>
<!-- Alternatively, use <artifactId>quarkus-universe-bom</artifactId>
which includes both quarkus-bom and timefold-solver-bom. -->
<artifactId>quarkus-bom</artifactId>
<version>${version.io.quarkus}</version>
<type>pom</type>
<scope>import</scope>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-bom</artifactId>
<version>${version.ai.timefold.solver}</version>
<type>pom</type>
<scope>import</scope>
</dependency>
</dependencies>
</dependencyManagement>
<dependencies>
<dependency>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-resteasy</artifactId>
</dependency>
<dependency>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-resteasy-jackson</artifactId>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-quarkus</artifactId>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-quarkus-jackson</artifactId>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>${version.compiler.plugin}</version>
</plugin>
<plugin>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-maven-plugin</artifactId>
<version>${version.io.quarkus}</version>
<executions>
<execution>
<goals>
<goal>build</goal>
</goals>
</execution>
</executions>
</plugin>
<plugin>
<artifactId>maven-surefire-plugin</artifactId>
<configuration>
<systemPropertyVariables>
<java.util.logging.manager>org.jboss.logmanager.LogManager</java.util.logging.manager>
</systemPropertyVariables>
</configuration>
</plugin>
</plugins>
</build>
</project>
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.acme</groupId>
<artifactId>vehicle-routing</artifactId>
<version>1.0-SNAPSHOT</version>
<properties>
<maven.compiler.release>11</maven.compiler.release>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<version.io.quarkus>3.14.4</version.io.quarkus>
<version.ai.timefold.solver>1.14.0</version.ai.timefold.solver>
</properties>
<dependencyManagement>
<dependencies>
<dependency>
<groupId>io.quarkus</groupId>
<!-- Alternatively, use <artifactId>quarkus-universe-bom</artifactId>
which includes both quarkus-bom and timefold-solver-bom. -->
<artifactId>quarkus-bom</artifactId>
<version>${version.io.quarkus}</version>
<type>pom</type>
<scope>import</scope>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-bom</artifactId>
<version>${version.ai.timefold.solver}</version>
<type>pom</type>
<scope>import</scope>
</dependency>
</dependencies>
</dependencyManagement>
<dependencies>
<dependency>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-resteasy</artifactId>
</dependency>
<dependency>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-resteasy-jackson</artifactId>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-quarkus</artifactId>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-quarkus-jackson</artifactId>
</dependency>
<dependency>
<groupId>org.jetbrains.kotlin</groupId>
<artifactId>kotlin-stdlib</artifactId>
<version>1.9.22</version>
</dependency>
</dependencies>
<build>
<sourceDirectory>src/main/kotlin</sourceDirectory>
<testSourceDirectory>src/test/kotlin</testSourceDirectory>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>${version.compiler.plugin}</version>
</plugin>
<plugin>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-maven-plugin</artifactId>
<version>${version.io.quarkus}</version>
<executions>
<execution>
<goals>
<goal>build</goal>
</goals>
</execution>
</executions>
</plugin>
<plugin>
<artifactId>maven-surefire-plugin</artifactId>
<configuration>
<systemPropertyVariables>
<java.util.logging.manager>org.jboss.logmanager.LogManager</java.util.logging.manager>
</systemPropertyVariables>
</configuration>
</plugin>
<plugin>
<groupId>org.jetbrains.kotlin</groupId>
<artifactId>kotlin-maven-plugin</artifactId>
<version>${version.kotlin}</version>
<executions>
<execution>
<id>compile</id>
<goals>
<goal>compile</goal>
</goals>
</execution>
<execution>
<id>test-compile</id>
<goals>
<goal>test-compile</goal>
</goals>
</execution>
</executions>
<dependencies>
<dependency>
<groupId>org.jetbrains.kotlin</groupId>
<artifactId>kotlin-maven-allopen</artifactId>
<version>${version.kotlin}</version>
</dependency>
</dependencies>
<configuration>
<javaParameters>true</javaParameters>
<jvmTarget>17</jvmTarget>
<compilerPlugins>
<plugin>all-open</plugin>
</compilerPlugins>
<pluginOptions>
<option>all-open:annotation=jakarta.ws.rs.Path</option>
<option>all-open:annotation=jakarta.enterprise.context.ApplicationScoped</option>
<option>all-open:annotation=io.quarkus.test.junit.QuarkusTest</option>
</pluginOptions>
</configuration>
</plugin>
</plugins>
</build>
</project>
5. Model the domain objects
Your goal is to assign each visit to a vehicle. You will create these classes:
5.1. Location
The Location
class is used to represent the destination for deliveries or the home location for vehicles.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/Location.java
class:
package org.acme.vehiclerouting.domain;
import java.util.Map;
public class Location {
private double latitude;
private double longitude;
private Map<Location, Long> drivingTimeSeconds;
public Location(double latitude, double longitude) {
this.latitude = latitude;
this.longitude = longitude;
}
public double getLatitude() {
return latitude;
}
public double getLongitude() {
return longitude;
}
public Map<Location, Long> getDrivingTimeSeconds() {
return drivingTimeSeconds;
}
public void setDrivingTimeSeconds(Map<Location, Long> drivingTimeSeconds) {
this.drivingTimeSeconds = drivingTimeSeconds;
}
public long getDrivingTimeTo(Location location) {
return drivingTimeSeconds.get(location);
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/Location.kt
class:
package org.acme.vehiclerouting.domain
class Location @JsonCreator constructor(val latitude: Double, val longitude: Double) {
var drivingTimeSeconds: Map<Location, Long>? = null
fun getDrivingTimeTo(location: Location): Long {
if (drivingTimeSeconds == null) {
return 0
}
return drivingTimeSeconds!![location]!!
}
override fun toString(): String {
return "$latitude,$longitude"
}
}
5.2. Vehicle
Vehicle
has a defined route plan with scheduled visits to make.
Each vehicle has a specific departure time and starting location.
It returns to its home location after completing the route and has a maximum capacity that must not be exceeded.
During solving, Timefold Solver updates the visits
field of the Vehicle
class to assign a list of visits.
Because Timefold Solver changes this field, Vehicle
is a planning entity:
Based on the diagram, the visits
field is a genuine variable that changes during the solving process.
To ensure that Timefold Solver recognizes it as a sequence of connected variables,
the field must have an @PlanningListVariable
annotation indicating that the solver can distribute a subset of the
available visits to it.
The objective is to create an ordered scheduled visit plan for each vehicle.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/Vehicle.java
class:
package org.acme.vehiclerouting.domain;
import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.List;
import ai.timefold.solver.core.api.domain.entity.PlanningEntity;
import ai.timefold.solver.core.api.domain.lookup.PlanningId;
import ai.timefold.solver.core.api.domain.variable.PlanningListVariable;
@PlanningEntity
public class Vehicle {
@PlanningId
private String id;
private int capacity;
private Location homeLocation;
private LocalDateTime departureTime;
@PlanningListVariable
private List<Visit> visits;
public Vehicle() {
}
public Vehicle(String id, int capacity, Location homeLocation, LocalDateTime departureTime) {
this.id = id;
this.capacity = capacity;
this.homeLocation = homeLocation;
this.departureTime = departureTime;
this.visits = new ArrayList<>();
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public int getCapacity() {
return capacity;
}
public void setCapacity(int capacity) {
this.capacity = capacity;
}
public Location getHomeLocation() {
return homeLocation;
}
public void setHomeLocation(Location homeLocation) {
this.homeLocation = homeLocation;
}
public LocalDateTime getDepartureTime() {
return departureTime;
}
public List<Visit> getVisits() {
return visits;
}
public void setVisits(List<Visit> visits) {
this.visits = visits;
}
public int getTotalDemand() {
int totalDemand = 0;
for (Visit visit : visits) {
totalDemand += visit.getDemand();
}
return totalDemand;
}
public long getTotalDrivingTimeSeconds() {
if (visits.isEmpty()) {
return 0;
}
long totalDrivingTime = 0;
Location previousLocation = homeLocation;
for (Visit visit : visits) {
totalDrivingTime += previousLocation.getDrivingTimeTo(visit.getLocation());
previousLocation = visit.getLocation();
}
totalDrivingTime += previousLocation.getDrivingTimeTo(homeLocation);
return totalDrivingTime;
}
@Override
public String toString() {
return id;
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/Vehicle.kt
class:
package org.acme.vehiclerouting.domain
import java.time.LocalDateTime
import java.util.ArrayList
import ai.timefold.solver.core.api.domain.entity.PlanningEntity
import ai.timefold.solver.core.api.domain.lookup.PlanningId
import ai.timefold.solver.core.api.domain.variable.PlanningListVariable
@PlanningEntity
class Vehicle {
@PlanningId
lateinit var id: String
var capacity: Int = 0
lateinit var homeLocation: Location
lateinit var departureTime: LocalDateTime
@PlanningListVariable
var visits: List<Visit>? = null
constructor()
constructor(id: String, capacity: Int, homeLocation: Location, departureTime: LocalDateTime) {
this.id = id
this.capacity = capacity
this.homeLocation = homeLocation
this.departureTime = departureTime
this.visits = ArrayList()
}
val totalDemand: Long
get() {
var totalDemand = 0L
for (visit in visits!!) {
totalDemand += visit.demand
}
return totalDemand
}
val totalDrivingTimeSeconds: Long
get() {
if (visits!!.isEmpty()) {
return 0
}
var totalDrivingTime: Long = 0
var previousLocation = homeLocation
for (visit in visits!!) {
totalDrivingTime += previousLocation.getDrivingTimeTo(visit.location!!)
previousLocation = visit.location!!
}
totalDrivingTime += previousLocation.getDrivingTimeTo(homeLocation)
return totalDrivingTime
}
override fun toString(): String {
return id
}
}
The Vehicle
class has an @PlanningEntity
annotation,
so Timefold Solver knows that this class changes during solving because it contains one or more planning variables.
Notice the toString()
method keeps the output short,
so it is easier to read Timefold Solver’s DEBUG
or TRACE
log, as shown later.
Determining the |
5.3. Visit
The Visit
class represents a delivery that needs to be made by vehicles.
A visit includes a destination location, a delivery time window represented by [minStartTime, maxEndTime]
,
a demand that needs to be fulfilled by the vehicle, and a service duration time.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/Visit.java
class:
package org.acme.vehiclerouting.domain;
import java.time.Duration;
import java.time.LocalDateTime;
import ai.timefold.solver.core.api.domain.entity.PlanningEntity;
import ai.timefold.solver.core.api.domain.lookup.PlanningId;
import ai.timefold.solver.core.api.domain.variable.InverseRelationShadowVariable;
import ai.timefold.solver.core.api.domain.variable.NextElementShadowVariable;
import ai.timefold.solver.core.api.domain.variable.PreviousElementShadowVariable;
import ai.timefold.solver.core.api.domain.variable.ShadowVariable;
import org.acme.vehiclerouting.solver.ArrivalTimeUpdatingVariableListener;
@PlanningEntity
public class Visit {
@PlanningId
private String id;
private String name;
private Location location;
private int demand;
private LocalDateTime minStartTime;
private LocalDateTime maxEndTime;
private Duration serviceDuration;
private Vehicle vehicle;
private Visit previousVisit;
private Visit nextVisit;
private LocalDateTime arrivalTime;
public Visit() {
}
public Visit(String id, String name, Location location, int demand,
LocalDateTime minStartTime, LocalDateTime maxEndTime, Duration serviceDuration) {
this.id = id;
this.name = name;
this.location = location;
this.demand = demand;
this.minStartTime = minStartTime;
this.maxEndTime = maxEndTime;
this.serviceDuration = serviceDuration;
}
public String getId() {
return id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Location getLocation() {
return location;
}
public void setLocation(Location location) {
this.location = location;
}
public int getDemand() {
return demand;
}
public void setDemand(int demand) {
this.demand = demand;
}
public LocalDateTime getMinStartTime() {
return minStartTime;
}
public LocalDateTime getMaxEndTime() {
return maxEndTime;
}
public Duration getServiceDuration() {
return serviceDuration;
}
@InverseRelationShadowVariable(sourceVariableName = "visits")
public Vehicle getVehicle() {
return vehicle;
}
public void setVehicle(Vehicle vehicle) {
this.vehicle = vehicle;
}
@PreviousElementShadowVariable(sourceVariableName = "visits")
public Visit getPreviousVisit() {
return previousVisit;
}
public void setPreviousVisit(Visit previousVisit) {
this.previousVisit = previousVisit;
}
@NextElementShadowVariable(sourceVariableName = "visits")
public Visit getNextVisit() {
return nextVisit;
}
public void setNextVisit(Visit nextVisit) {
this.nextVisit = nextVisit;
}
@ShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sourceVariableName = "vehicle")
@ShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sourceVariableName = "previousVisit")
public LocalDateTime getArrivalTime() {
return arrivalTime;
}
public void setArrivalTime(LocalDateTime arrivalTime) {
this.arrivalTime = arrivalTime;
}
public LocalDateTime getDepartureTime() {
if (arrivalTime == null) {
return null;
}
return getStartServiceTime().plus(serviceDuration);
}
public LocalDateTime getStartServiceTime() {
if (arrivalTime == null) {
return null;
}
return arrivalTime.isBefore(minStartTime) ? minStartTime : arrivalTime;
}
public boolean isServiceFinishedAfterMaxEndTime() {
return arrivalTime != null
&& arrivalTime.plus(serviceDuration).isAfter(maxEndTime);
}
public long getServiceFinishedDelayInMinutes() {
if (arrivalTime == null) {
return 0;
}
return Duration.between(maxEndTime, arrivalTime.plus(serviceDuration)).toMinutes();
}
public long getDrivingTimeSecondsFromPreviousStandstill() {
if (vehicle == null) {
throw new IllegalStateException(
"This method must not be called when the shadow variables are not initialized yet.");
}
if (previousVisit == null) {
return vehicle.getHomeLocation().getDrivingTimeTo(location);
}
return previousVisit.getLocation().getDrivingTimeTo(location);
}
@Override
public String toString() {
return id;
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/Visit.kt
class:
package org.acme.vehiclerouting.domain
import java.time.Duration
import java.time.LocalDateTime
import ai.timefold.solver.core.api.domain.entity.PlanningEntity
import ai.timefold.solver.core.api.domain.lookup.PlanningId
import ai.timefold.solver.core.api.domain.variable.InverseRelationShadowVariable
import ai.timefold.solver.core.api.domain.variable.NextElementShadowVariable
import ai.timefold.solver.core.api.domain.variable.PreviousElementShadowVariable
import ai.timefold.solver.core.api.domain.variable.ShadowVariable
import org.acme.vehiclerouting.solver.ArrivalTimeUpdatingVariableListener
@PlanningEntity
class Visit {
@PlanningId
lateinit var id: String
lateinit var name: String
lateinit var location: Location
var demand: Int = 0
lateinit var minStartTime: LocalDateTime
lateinit var maxEndTime: LocalDateTime
lateinit var serviceDuration: Duration
private var vehicle: Vehicle? = null
@get:PreviousElementShadowVariable(sourceVariableName = "visits")
var previousVisit: Visit? = null
@get:NextElementShadowVariable(sourceVariableName = "visits")
var nextVisit: Visit? = null
@get:ShadowVariable(
variableListenerClass = ArrivalTimeUpdatingVariableListener::class,
sourceVariableName = "previousVisit"
)
@get:ShadowVariable(
variableListenerClass = ArrivalTimeUpdatingVariableListener::class,
sourceVariableName = "vehicle"
)
var arrivalTime: LocalDateTime? = null
constructor()
constructor(
id: String, name: String, location: Location, demand: Int,
minStartTime: LocalDateTime, maxEndTime: LocalDateTime, serviceDuration: Duration
) {
this.id = id
this.name = name
this.location = location
this.demand = demand
this.minStartTime = minStartTime
this.maxEndTime = maxEndTime
this.serviceDuration = serviceDuration
}
@InverseRelationShadowVariable(sourceVariableName = "visits")
fun getVehicle(): Vehicle? {
return vehicle
}
fun setVehicle(vehicle: Vehicle?) {
this.vehicle = vehicle
}
val departureTime: LocalDateTime?
get() {
if (arrivalTime == null) {
return null
}
return startServiceTime!!.plus(serviceDuration)
}
val startServiceTime: LocalDateTime?
get() {
if (arrivalTime == null) {
return null
}
return if (arrivalTime!!.isBefore(minStartTime)) minStartTime else arrivalTime
}
val isServiceFinishedAfterMaxEndTime: Boolean
get() = (arrivalTime != null
&& arrivalTime!!.plus(serviceDuration).isAfter(maxEndTime))
val serviceFinishedDelayInMinutes: Long
get() {
if (arrivalTime == null) {
return 0
}
return Duration.between(maxEndTime, arrivalTime!!.plus(serviceDuration)).toMinutes()
}
val drivingTimeSecondsFromPreviousStandstill: Long
get() {
if (vehicle == null) {
throw IllegalStateException(
"This method must not be called when the shadow variables are not initialized yet."
)
}
if (previousVisit == null) {
return vehicle!!.homeLocation.getDrivingTimeTo(location)
}
return previousVisit!!.location.getDrivingTimeTo((location))
}
override fun toString(): String {
return id
}
}
Some methods are annotated with @InverseRelationShadowVariable
, @PreviousElementShadowVariable
,
@NextElementShadowVariable
, and @ShadowVariable
.
They are called shadow variables,
and because Timefold Solver changes them,
Visit
is a planning entity:
The method getVehicle()
has an @InverseRelationShadowVariable
annotation,
creating a bi-directional relationship with the Vehicle
.
The function returns a reference to the Vehicle
where the visit is scheduled.
Let’s say the visit Ann
was scheduled to the vehicle V1
during the solving process.
The method returns a reference of V1
.
The methods getPreviousVisit()
and getNextVisit()
are annotated with @PreviousElementShadowVariable
and
@NextElementShadowVariable
, respectively.
The method returns a reference of the previous and next visit of the current visit instance.
Assuming that vehicle V1
is assigned the visits of Ann
, Beth
, and Carl
,
the getNextVisit()
method returns Carl
,
and the getPreviousVisit()
method returns Ann
for the visit of Beth
.
The method getArrivalTime()
has two @ShadowVariable
annotations,
one per each variable: vehicle
and previousVisit
.
The solver triggers ArrivalTimeUpdatingVariableListener
to update arrivalTime
field every time the fields vehicle
or previousVisit
get updated.
The Visit
class has an @PlanningEntity
annotation
but no genuine variables and is called shadow entity.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/solver/ArrivalTimeUpdatingVariableListener.java
class:
package org.acme.vehiclerouting.solver;
import java.time.LocalDateTime;
import java.util.Objects;
import ai.timefold.solver.core.api.domain.variable.VariableListener;
import ai.timefold.solver.core.api.score.director.ScoreDirector;
import org.acme.vehiclerouting.domain.Visit;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
public class ArrivalTimeUpdatingVariableListener implements VariableListener<VehicleRoutePlan, Visit> {
private static final String ARRIVAL_TIME_FIELD = "arrivalTime";
@Override
public void beforeVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
}
@Override
public void afterVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
if (visit.getVehicle() == null) {
if (visit.getArrivalTime() != null) {
scoreDirector.beforeVariableChanged(visit, ARRIVAL_TIME_FIELD);
visit.setArrivalTime(null);
scoreDirector.afterVariableChanged(visit, ARRIVAL_TIME_FIELD);
}
return;
}
Visit previousVisit = visit.getPreviousVisit();
LocalDateTime departureTime =
previousVisit == null ? visit.getVehicle().getDepartureTime() : previousVisit.getDepartureTime();
Visit nextVisit = visit;
LocalDateTime arrivalTime = calculateArrivalTime(nextVisit, departureTime);
while (nextVisit != null && !Objects.equals(nextVisit.getArrivalTime(), arrivalTime)) {
scoreDirector.beforeVariableChanged(nextVisit, ARRIVAL_TIME_FIELD);
nextVisit.setArrivalTime(arrivalTime);
scoreDirector.afterVariableChanged(nextVisit, ARRIVAL_TIME_FIELD);
departureTime = nextVisit.getDepartureTime();
nextVisit = nextVisit.getNextVisit();
arrivalTime = calculateArrivalTime(nextVisit, departureTime);
}
}
@Override
public void beforeEntityAdded(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
}
@Override
public void afterEntityAdded(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
}
@Override
public void beforeEntityRemoved(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
}
@Override
public void afterEntityRemoved(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
}
private LocalDateTime calculateArrivalTime(Visit visit, LocalDateTime previousDepartureTime) {
if (visit == null || previousDepartureTime == null) {
return null;
}
return previousDepartureTime.plusSeconds(visit.getDrivingTimeSecondsFromPreviousStandstill());
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/solver/ArrivalTimeUpdatingVariableListener.kt
class:
package org.acme.vehiclerouting.solver
import java.time.LocalDateTime
import ai.timefold.solver.core.api.domain.variable.VariableListener
import ai.timefold.solver.core.api.score.director.ScoreDirector
import org.acme.vehiclerouting.domain.Visit
import org.acme.vehiclerouting.domain.VehicleRoutePlan
class ArrivalTimeUpdatingVariableListener : VariableListener<VehicleRoutePlan?, Visit> {
override fun beforeVariableChanged(scoreDirector: ScoreDirector<VehicleRoutePlan?>, visit: Visit) {
}
override fun afterVariableChanged(scoreDirector: ScoreDirector<VehicleRoutePlan?>, visit: Visit) {
if (visit.getVehicle() == null) {
if (visit.arrivalTime != null) {
scoreDirector.beforeVariableChanged(visit, ARRIVAL_TIME_FIELD)
visit.arrivalTime = null
scoreDirector.afterVariableChanged(visit, ARRIVAL_TIME_FIELD)
}
return
}
val previousVisit: Visit? = visit.previousVisit
var departureTime: LocalDateTime? =
if (previousVisit == null) visit.getVehicle()!!.departureTime else previousVisit.departureTime
var nextVisit: Visit? = visit
var arrivalTime = calculateArrivalTime(nextVisit, departureTime)
while (nextVisit != null && nextVisit.arrivalTime != arrivalTime) {
scoreDirector.beforeVariableChanged(nextVisit, ARRIVAL_TIME_FIELD)
nextVisit.arrivalTime = arrivalTime
scoreDirector.afterVariableChanged(nextVisit, ARRIVAL_TIME_FIELD)
departureTime = nextVisit.departureTime
nextVisit = nextVisit.nextVisit
arrivalTime = calculateArrivalTime(nextVisit, departureTime)
}
}
override fun beforeEntityAdded(scoreDirector: ScoreDirector<VehicleRoutePlan?>?, visit: Visit?) {
}
override fun afterEntityAdded(scoreDirector: ScoreDirector<VehicleRoutePlan?>?, visit: Visit?) {
}
override fun beforeEntityRemoved(scoreDirector: ScoreDirector<VehicleRoutePlan?>?, visit: Visit?) {
}
override fun afterEntityRemoved(scoreDirector: ScoreDirector<VehicleRoutePlan?>?, visit: Visit?) {
}
private fun calculateArrivalTime(visit: Visit?, previousDepartureTime: LocalDateTime?): LocalDateTime? {
if (visit == null || previousDepartureTime == null) {
return null
}
return previousDepartureTime.plusSeconds(visit.drivingTimeSecondsFromPreviousStandstill)
}
companion object {
private const val ARRIVAL_TIME_FIELD = "arrivalTime"
}
}
6. 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²).
7. Gather the domain objects in a planning solution
A VehicleRoutePlan
wraps all Vehicle
and Visit
instances of a single dataset.
Furthermore, because it contains all vehicles and visits, each with a specific planning variable state,
it is a planning solution
and it has a score:
-
If visits are still unassigned, then it is an uninitialized solution, for example, a solution with the score
-4init/0hard/0soft
. -
If it breaks hard constraints, then it is an infeasible solution, for example, a solution with the score
-2hard/-3soft
. -
If it adheres to all hard constraints, then it is a feasible solution, for example, a solution with the score
0hard/-7soft
.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/VehicleRoutePlan.java
class:
package org.acme.vehiclerouting.domain;
import java.time.LocalDateTime;
import java.util.List;
import java.util.stream.Stream;
import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty;
import ai.timefold.solver.core.api.domain.solution.PlanningScore;
import ai.timefold.solver.core.api.domain.solution.PlanningSolution;
import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider;
import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore;
import ai.timefold.solver.core.api.solver.SolverStatus;
import org.acme.vehiclerouting.domain.geo.DrivingTimeCalculator;
import org.acme.vehiclerouting.domain.geo.HaversineDrivingTimeCalculator;
@PlanningSolution
public class VehicleRoutePlan {
private String name;
private Location southWestCorner;
private Location northEastCorner;
private LocalDateTime startDateTime;
private LocalDateTime endDateTime;
@PlanningEntityCollectionProperty
private List<Vehicle> vehicles;
@PlanningEntityCollectionProperty
@ValueRangeProvider
private List<Visit> visits;
@PlanningScore
private HardSoftLongScore score;
private SolverStatus solverStatus;
private String scoreExplanation;
public VehicleRoutePlan() {
}
public VehicleRoutePlan(String name, HardSoftLongScore score, SolverStatus solverStatus) {
this.name = name;
this.score = score;
this.solverStatus = solverStatus;
}
public VehicleRoutePlan(String name,
Location southWestCorner,
Location northEastCorner,
LocalDateTime startDateTime,
LocalDateTime endDateTime,
List<Vehicle> vehicles,
List<Visit> visits) {
this.name = name;
this.southWestCorner = southWestCorner;
this.northEastCorner = northEastCorner;
this.startDateTime = startDateTime;
this.endDateTime = endDateTime;
this.vehicles = vehicles;
this.visits = visits;
List<Location> locations = Stream.concat(
vehicles.stream().map(Vehicle::getHomeLocation),
visits.stream().map(Visit::getLocation)).toList();
DrivingTimeCalculator drivingTimeCalculator = HaversineDrivingTimeCalculator.getInstance();
drivingTimeCalculator.initDrivingTimeMaps(locations);
}
public String getName() {
return name;
}
public Location getSouthWestCorner() {
return southWestCorner;
}
public Location getNorthEastCorner() {
return northEastCorner;
}
public LocalDateTime getStartDateTime() {
return startDateTime;
}
public LocalDateTime getEndDateTime() {
return endDateTime;
}
public List<Vehicle> getVehicles() {
return vehicles;
}
public List<Visit> getVisits() {
return visits;
}
public HardSoftLongScore getScore() {
return score;
}
public void setScore(HardSoftLongScore score) {
this.score = score;
}
public long getTotalDrivingTimeSeconds() {
return vehicles == null ? 0 : vehicles.stream().mapToLong(Vehicle::getTotalDrivingTimeSeconds).sum();
}
public SolverStatus getSolverStatus() {
return solverStatus;
}
public void setSolverStatus(SolverStatus solverStatus) {
this.solverStatus = solverStatus;
}
public String getScoreExplanation() {
return scoreExplanation;
}
public void setScoreExplanation(String scoreExplanation) {
this.scoreExplanation = scoreExplanation;
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/VehicleRoutePlan.kt
class:
package org.acme.vehiclerouting.domain;
import java.time.LocalDateTime
import java.util.stream.Stream
import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty
import ai.timefold.solver.core.api.domain.solution.PlanningScore
import ai.timefold.solver.core.api.domain.solution.PlanningSolution
import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider
import ai.timefold.solver.core.api.score.buildin.hardsoftlong.HardSoftLongScore
import ai.timefold.solver.core.api.solver.SolverStatus
import org.acme.vehiclerouting.domain.geo.DrivingTimeCalculator
import org.acme.vehiclerouting.domain.geo.HaversineDrivingTimeCalculator
@PlanningSolution
class VehicleRoutePlan {
lateinit var name: String
var southWestCorner: Location? = null
private set
var northEastCorner: Location? = null
private set
var startDateTime: LocalDateTime? = null
private set
var endDateTime: LocalDateTime? = null
private set
@PlanningEntityCollectionProperty
var vehicles: List<Vehicle>? = null
private set
@PlanningEntityCollectionProperty
@ValueRangeProvider
var visits: List<Visit>? = null
private set
@PlanningScore
var score: HardSoftLongScore? = null
var solverStatus: SolverStatus? = null
var scoreExplanation: String? = null
constructor()
constructor(name: String, score: HardSoftLongScore?, solverStatus: SolverStatus?) {
this.name = name
this.score = score
this.solverStatus = solverStatus
}
constructor(
name: String,
southWestCorner: Location?,
northEastCorner: Location?,
startDateTime: LocalDateTime?,
endDateTime: LocalDateTime?,
vehicles: List<Vehicle>,
visits: List<Visit>
) {
this.name = name
this.southWestCorner = southWestCorner
this.northEastCorner = northEastCorner
this.startDateTime = startDateTime
this.endDateTime = endDateTime
this.vehicles = vehicles
this.visits = visits
val locations = Stream.concat(
vehicles.stream().map({ obj: Vehicle -> obj.homeLocation }),
visits.stream().map({ obj: Visit -> obj.location })
).toList()
val drivingTimeCalculator: DrivingTimeCalculator = HaversineDrivingTimeCalculator.INSTANCE
drivingTimeCalculator.initDrivingTimeMaps(locations)
}
val totalDrivingTimeSeconds: Long
get() = if (vehicles == null) 0 else vehicles!!.stream()
.mapToLong({ obj: Vehicle -> obj.totalDrivingTimeSeconds }).sum()
}
The VehicleRoutePlan
class has an @PlanningSolution
annotation,
so Timefold Solver knows that this class contains all of the input and output data.
Specifically, these classes are the input of the problem:
-
The
vehicles
field with all vehicles-
This is a list of planning entities, because they change during solving.
-
For each
Vehicle
:-
The value of the
visits
is typically stillempty
, so unassigned. It is a planning variable. -
The other fields, such as
capacity
,homeLocation
anddepartureTime
, are filled in. These fields are problem properties.
-
-
-
The
visits
field with all visits-
This is a list of planning entities, because they change during solving.
-
For each
Visit
:-
The values of
vehicle
,previousVisit
,nextVisit
,arrivalTime
are typically stillnull
for a fresh solution. They are planning shadow variables. -
The other fields, such as
name
,location
anddemand
, are filled in. These fields are problem properties.
-
-
However, this class is also the output of the solution:
-
The
vehicles
field for which eachVehicle
instance has non-nullvisits
field after solving. -
The
score
field that represents the quality of the output solution, for example,0hard/-5soft
.
7.1. The value range providers
The visits
field is a value range provider.
It holds the Visit
instances which Timefold Solver can pick from to assign to the visits
field of Vehicle
instances.
The visits
field has an @ValueRangeProvider
annotation to connect the @PlanningListVariable
with the @ValueRangeProvider
,
by matching the type of the planning list variable with the type returned by the value range provider.
7.2. Distance calculation
The distance calculation method applies the Haversine approach, which measures distances in meters. First create a contract for driving time calculation:
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/geo/DrivingTimeCalculator.java
interface:
package org.acme.vehiclerouting.domain.geo;
import java.util.Collection;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import org.acme.vehiclerouting.domain.Location;
public interface DrivingTimeCalculator {
long calculateDrivingTime(Location from, Location to);
default Map<Location, Map<Location, Long>> calculateBulkDrivingTime(
Collection<Location> fromLocations,
Collection<Location> toLocations) {
return fromLocations.stream().collect(Collectors.toMap(
Function.identity(),
from -> toLocations.stream().collect(Collectors.toMap(
Function.identity(),
to -> calculateDrivingTime(from, to)))));
}
default void initDrivingTimeMaps(Collection<Location> locations) {
Map<Location, Map<Location, Long>> drivingTimeMatrix = calculateBulkDrivingTime(locations, locations);
locations.forEach(location -> location.setDrivingTimeSeconds(drivingTimeMatrix.get(location)));
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/geo/DrivingTimeCalculator.kt
interface:
package org.acme.vehiclerouting.domain.geo
import org.acme.vehiclerouting.domain.Location
import java.util.function.Function
import java.util.stream.Collectors
interface DrivingTimeCalculator {
fun calculateDrivingTime(from: Location, to: Location): Long
fun calculateBulkDrivingTime(
fromLocations: Collection<Location>,
toLocations: Collection<Location>
): Map<Location, Map<Location, Long>> {
return fromLocations.stream().collect(
Collectors.toMap(
Function.identity()
) { from: Location ->
toLocations.stream()
.collect(
Collectors.toMap(
Function.identity(),
{ to: Location ->
calculateDrivingTime(
from,
to
)
})
)
}
)
}
fun initDrivingTimeMaps(locations: Collection<Location>) {
val drivingTimeMatrix = calculateBulkDrivingTime(locations, locations)
locations.forEach { location: Location ->
location.drivingTimeSeconds = drivingTimeMatrix[location]
}
}
}
Then create an implementation using Haversine method:
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/domain/geo/HaversineDrivingTimeCalculator.java
class:
package org.acme.vehiclerouting.domain.geo;
import org.acme.vehiclerouting.domain.Location;
public final class HaversineDrivingTimeCalculator implements DrivingTimeCalculator {
private static final HaversineDrivingTimeCalculator INSTANCE = new HaversineDrivingTimeCalculator();
public static final int AVERAGE_SPEED_KMPH = 50;
private static final int EARTH_RADIUS_IN_M = 6371000;
private static final int TWICE_EARTH_RADIUS_IN_M = 2 * EARTH_RADIUS_IN_M;
static long metersToDrivingSeconds(long meters) {
return Math.round((double) meters / AVERAGE_SPEED_KMPH * 3.6);
}
public static synchronized HaversineDrivingTimeCalculator getInstance() {
return INSTANCE;
}
private HaversineDrivingTimeCalculator() {
}
@Override
public long calculateDrivingTime(Location from, Location to) {
if (from.equals(to)) {
return 0L;
}
CartesianCoordinate fromCartesian = locationToCartesian(from);
CartesianCoordinate toCartesian = locationToCartesian(to);
return metersToDrivingSeconds(calculateDistance(fromCartesian, toCartesian));
}
private long calculateDistance(CartesianCoordinate from, CartesianCoordinate to) {
if (from.equals(to)) {
return 0L;
}
double dX = from.x - to.x;
double dY = from.y - to.y;
double dZ = from.z - to.z;
double r = Math.sqrt((dX * dX) + (dY * dY) + (dZ * dZ));
return Math.round(TWICE_EARTH_RADIUS_IN_M * Math.asin(r));
}
private CartesianCoordinate locationToCartesian(Location location) {
double latitudeInRads = Math.toRadians(location.getLatitude());
double longitudeInRads = Math.toRadians(location.getLongitude());
// Cartesian coordinates, normalized for a sphere of diameter 1.0
double cartesianX = 0.5 * Math.cos(latitudeInRads) * Math.sin(longitudeInRads);
double cartesianY = 0.5 * Math.cos(latitudeInRads) * Math.cos(longitudeInRads);
double cartesianZ = 0.5 * Math.sin(latitudeInRads);
return new CartesianCoordinate(cartesianX, cartesianY, cartesianZ);
}
private record CartesianCoordinate(double x, double y, double z) {
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/domain/geo/HaversineDrivingTimeCalculator.kt
class:
package org.acme.vehiclerouting.domain.geo
import kotlin.math.asin
import kotlin.math.sqrt
import kotlin.math.cos
import kotlin.math.sin
import org.acme.vehiclerouting.domain.Location
class HaversineDrivingTimeCalculator private constructor() : DrivingTimeCalculator {
override fun calculateDrivingTime(from: Location, to: Location): Long {
if (from == to) {
return 0L
}
val fromCartesian = locationToCartesian(from)
val toCartesian = locationToCartesian(to)
return metersToDrivingSeconds(calculateDistance(fromCartesian, toCartesian))
}
private fun calculateDistance(from: CartesianCoordinate, to: CartesianCoordinate): Long {
if (from == to) {
return 0L
}
val dX = from.x - to.x
val dY = from.y - to.y
val dZ = from.z - to.z
val r: Double = sqrt((dX * dX) + (dY * dY) + (dZ * dZ))
return Math.round(TWICE_EARTH_RADIUS_IN_M * asin(r))
}
private fun locationToCartesian(location: Location): CartesianCoordinate {
val latitudeInRads = Math.toRadians(location.latitude)
val longitudeInRads = Math.toRadians(location.longitude)
// Cartesian coordinates, normalized for a sphere of diameter 1.0
val cartesianX: Double = 0.5 * cos(latitudeInRads) * sin(longitudeInRads)
val cartesianY: Double = 0.5 * cos(latitudeInRads) * cos(longitudeInRads)
val cartesianZ: Double = 0.5 * sin(latitudeInRads)
return CartesianCoordinate(cartesianX, cartesianY, cartesianZ)
}
private data class CartesianCoordinate(val x: Double, val y: Double, val z: Double)
companion object {
@JvmStatic
@get:Synchronized
val INSTANCE: HaversineDrivingTimeCalculator = HaversineDrivingTimeCalculator()
const val AVERAGE_SPEED_KMPH: Int = 50
private const val EARTH_RADIUS_IN_M = 6371000
private const val TWICE_EARTH_RADIUS_IN_M = 2 * EARTH_RADIUS_IN_M
fun metersToDrivingSeconds(meters: Long): Long {
return Math.round(meters.toDouble() / AVERAGE_SPEED_KMPH * 3.6)
}
}
}
8. Create the solver service
Now you are ready to put everything together and create a REST service.
But solving planning problems on REST threads causes HTTP timeout issues.
Therefore, the Quarkus extension injects a SolverManager
instance,
which runs solvers in a separate thread pool
and can solve multiple datasets in parallel.
-
Java
-
Kotlin
Create the src/main/java/org/acme/vehiclerouting/rest/VehicleRoutePlanResource.java
class:
package org.acme.vehiclerouting.rest;
import java.util.UUID;
import java.util.concurrent.ExecutionException;
import jakarta.inject.Inject;
import jakarta.ws.rs.Consumes;
import jakarta.ws.rs.POST;
import jakarta.ws.rs.Path;
import jakarta.ws.rs.Produces;
import jakarta.ws.rs.core.MediaType;
import ai.timefold.solver.core.api.solver.SolverJob;
import ai.timefold.solver.core.api.solver.SolverManager;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
@Path("route-plans")
public class VehicleRoutePlanResource {
private final SolverManager<VehicleRoutePlan, String> solverManager;
public VehicleRoutePlanResource() {
this.solverManager = null;
}
@Inject
public VehicleRoutePlanResource(SolverManager<VehicleRoutePlan, String> solverManager) {
this.solverManager = solverManager;
}
@POST
@Path("solve")
@Consumes({ MediaType.APPLICATION_JSON })
@Produces(MediaType.APPLICATION_JSON)
public VehicleRoutePlan solve(VehicleRoutePlan problem) {
String jobId = UUID.randomUUID().toString();
SolverJob<VehicleRoutePlan, String> solverJob = solverManager.solveBuilder()
.withProblemId(jobId)
.withProblem(problem)
.run();
VehicleRoutePlan solution;
try {
// Wait until the solving ends
solution = solverJob.getFinalBestSolution();
} catch (InterruptedException | ExecutionException e) {
throw new IllegalStateException("Solving failed.", e);
}
return solution;
}
}
Create the src/main/kotlin/org/acme/vehiclerouting/rest/VehicleRoutePlanResource.kt
class:
package org.acme.vehiclerouting.rest
import java.util.UUID
import java.util.concurrent.ExecutionException
import jakarta.inject.Inject
import jakarta.ws.rs.Consumes
import jakarta.ws.rs.POST
import jakarta.ws.rs.Path
import jakarta.ws.rs.Produces
import jakarta.ws.rs.core.MediaType
import ai.timefold.solver.core.api.solver.SolverManager
import org.acme.vehiclerouting.domain.VehicleRoutePlan
@Path("route-plans")
class VehicleRoutePlanResource {
private val solverManager: SolverManager<VehicleRoutePlan, String>?
constructor() {
this.solverManager = null
}
@Inject
constructor(solverManager: SolverManager<VehicleRoutePlan, String>?) {
this.solverManager = solverManager
}
@POST
@Path("solve")
@Consumes(MediaType.APPLICATION_JSON)
@Produces(MediaType.APPLICATION_JSON)
fun solve(problem: VehicleRoutePlan): VehicleRoutePlan {
val jobId = UUID.randomUUID().toString()
val solverJob = solverManager!!.solveBuilder()
.withProblemId(jobId)
.withProblem(problem)
.run()
val solution: VehicleRoutePlan
try {
// Wait until the solving ends
solution = solverJob.finalBestSolution
} catch (e: InterruptedException) {
throw IllegalStateException("Solving failed.", e)
} catch (e: ExecutionException) {
throw IllegalStateException("Solving failed.", e)
}
return solution
}
}
For simplicity’s sake, this initial implementation waits for the solver to finish, which can still cause an HTTP timeout. The complete implementation avoids HTTP timeouts much more elegantly.
9. Set the termination time
Without a termination setting or a terminationEarly()
event, the solver runs forever.
To avoid that, limit the solving time to five seconds.
That is short enough to avoid the HTTP timeout.
Create the src/main/resources/application.properties
file:
# The solver runs only for 5 seconds to avoid a HTTP timeout in this simple implementation.
# It's recommended to run for at least 5 minutes ("5m") otherwise.
quarkus.timefold.solver.termination.spent-limit=5s
Timefold Solver returns the best solution found in the available termination time. Due to the nature of NP-hard problems, the best solution might not be optimal, especially for larger datasets. Increase the termination time to potentially find a better solution.
10. Run the application
First start the application:
$ mvn compile quarkus:dev
10.1. Try the application
Now that the application is running, you can test the REST service.
You can use any REST client you wish.
The following example uses the Linux command curl
to send a POST request:
$ curl -i -X POST http://localhost:8080/route-plans/solve -H "Content-Type:application/json" -d '{"name":"demo","southWestCorner":[39.7656099067391,-76.83782328143754],"northEastCorner":[40.77636644354855,-74.9300739430771],"startDateTime":"2024-02-10T07:30:00","endDateTime":"2024-02-11T00:00:00","vehicles":[{"id":"1","capacity":15,"homeLocation":[40.605994321126936,-75.68106859680056],"departureTime":"2024-02-10T07:30:00","visits":[],"totalDrivingTimeSeconds":0,"totalDemand":0,"arrivalTime":"2024-02-10T07:30:00"},{"id":"2","capacity":25,"homeLocation":[40.32196770776356,-75.69785667307953],"departureTime":"2024-02-10T07:30:00","visits":[],"totalDrivingTimeSeconds":0,"totalDemand":0,"arrivalTime":"2024-02-10T07:30:00"}],"visits":[{"id":"1","name":"Dan Green","location":[40.76104493121754,-75.16056341466826],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":1200.000000000,"vehicle":null,"previousVisit":null,"nextVisit":null,"arrivalTime":null,"startServiceTime":null,"departureTime":null,"drivingTimeSecondsFromPreviousStandstill":null},{"id":"2","name":"Ivy King","location":[40.13754381024318,-75.492526629236],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":1200.000000000,"vehicle":null,"previousVisit":null,"nextVisit":null,"arrivalTime":null,"startServiceTime":null,"departureTime":null,"drivingTimeSecondsFromPreviousStandstill":null},{"id":"3","name":"Flo Li","location":[39.87122455090297,-75.64520072015769],"demand":2,"minStartTime":"2024-02-10T08:00:00","maxEndTime":"2024-02-10T12:00:00","serviceDuration":600.000000000,"vehicle":null,"previousVisit":null,"nextVisit":null,"arrivalTime":null,"startServiceTime":null,"departureTime":null,"drivingTimeSecondsFromPreviousStandstill":null},{"id":"4","name":"Flo Cole","location":[40.46124744193433,-75.18250987609025],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":2400.000000000,"vehicle":null,"previousVisit":null,"nextVisit":null,"arrivalTime":null,"startServiceTime":null,"departureTime":null,"drivingTimeSecondsFromPreviousStandstill":null},{"id":"5","name":"Carl Green","location":[40.61352381171549,-75.83301278355529],"demand":1,"minStartTime":"2024-02-10T08:00:00","maxEndTime":"2024-02-10T12:00:00","serviceDuration":1800.000000000,"vehicle":null,"previousVisit":null,"nextVisit":null,"arrivalTime":null,"startServiceTime":null,"departureTime":null,"drivingTimeSecondsFromPreviousStandstill":null}],"totalDrivingTimeSeconds":0}'
After about five seconds, according to the termination spent time defined in your application.properties
,
the service returns an output similar to the following example:
HTTP/1.1 200
Content-Type: application/json
...
{"name":"demo","southWestCorner":[39.7656099067391,-76.83782328143754],"northEastCorner":[40.77636644354855,-74.9300739430771],"startDateTime":"2024-02-10T07:30:00","endDateTime":"2024-02-11T00:00:00","vehicles":[{"id":"1","capacity":15,"homeLocation":[40.605994321126936,-75.68106859680056],"departureTime":"2024-02-10T07:30:00","visits":["5","1","4"],"arrivalTime":"2024-02-10T15:34:11","totalDemand":3,"totalDrivingTimeSeconds":10826},{"id":"2","capacity":25,"homeLocation":[40.32196770776356,-75.69785667307953],"departureTime":"2024-02-10T07:30:00","visits":["3","2"],"arrivalTime":"2024-02-10T13:52:18","totalDemand":3,"totalDrivingTimeSeconds":7890}],"visits":[{"id":"1","name":"Dan Green","location":[40.76104493121754,-75.16056341466826],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":1200.000000000,"vehicle":"1","previousVisit":"5","nextVisit":"4","arrivalTime":"2024-02-10T09:40:50","startServiceTime":"2024-02-10T13:00:00","departureTime":"2024-02-10T13:20:00","drivingTimeSecondsFromPreviousStandstill":4250},{"id":"2","name":"Ivy King","location":[40.13754381024318,-75.492526629236],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":1200.000000000,"vehicle":"2","previousVisit":"3","nextVisit":null,"arrivalTime":"2024-02-10T09:19:12","startServiceTime":"2024-02-10T13:00:00","departureTime":"2024-02-10T13:20:00","drivingTimeSecondsFromPreviousStandstill":2329},{"id":"3","name":"Flo Li","location":[39.87122455090297,-75.64520072015769],"demand":2,"minStartTime":"2024-02-10T08:00:00","maxEndTime":"2024-02-10T12:00:00","serviceDuration":600.000000000,"vehicle":"2","previousVisit":null,"nextVisit":"2","arrivalTime":"2024-02-10T08:30:23","startServiceTime":"2024-02-10T08:30:23","departureTime":"2024-02-10T08:40:23","drivingTimeSecondsFromPreviousStandstill":3623},{"id":"4","name":"Flo Cole","location":[40.46124744193433,-75.18250987609025],"demand":1,"minStartTime":"2024-02-10T13:00:00","maxEndTime":"2024-02-10T18:00:00","serviceDuration":2400.000000000,"vehicle":"1","previousVisit":"1","nextVisit":null,"arrivalTime":"2024-02-10T14:00:04","startServiceTime":"2024-02-10T14:00:04","departureTime":"2024-02-10T14:40:04","drivingTimeSecondsFromPreviousStandstill":2404},{"id":"5","name":"Carl Green","location":[40.61352381171549,-75.83301278355529],"demand":1,"minStartTime":"2024-02-10T08:00:00","maxEndTime":"2024-02-10T12:00:00","serviceDuration":1800.000000000,"vehicle":"1","previousVisit":null,"nextVisit":"1","arrivalTime":"2024-02-10T07:45:25","startServiceTime":"2024-02-10T08:00:00","departureTime":"2024-02-10T08:30:00","drivingTimeSecondsFromPreviousStandstill":925}],"score":"0hard/-18716soft","totalDrivingTimeSeconds":18716}
Notice that your application assigned all five visits to one of the two vehicles.
Also notice that it conforms to all hard constraints.
For example, visits 1
, 4
, and 5
were scheduled to the vehicle 1
.
On the server side, the info
log shows what Timefold Solver did in those five seconds:
... Solving started: time spent (17), best score (-5init/0hard/0soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).
... Construction Heuristic phase (0) ended: time spent (33), best score (0hard/-18755soft), score calculation speed (2222/sec), step total (5).
... Local Search phase (1) ended: time spent (5000), best score (0hard/-18716soft), score calculation speed (89685/sec), step total (40343).
... Solving ended: time spent (5000), best score (0hard/-18716soft), score calculation speed (89079/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).
10.2. Test the application
A good application includes test coverage.
10.2.1. Test the constraints
To test each constraint in isolation, use a ConstraintVerifier
in unit tests.
It tests each constraint’s corner cases in isolation from the other tests,
which lowers maintenance when adding a new constraint with proper test coverage.
First update your build tool configuration:
Add a timefold-solver-test
dependency in your pom.xml
:
<dependency>
<groupId>io.quarkus</groupId>
<artifactId>quarkus-junit5</artifactId>
<scope>test</scope>
</dependency>
<dependency>
<groupId>ai.timefold.solver</groupId>
<artifactId>timefold-solver-test</artifactId>
<scope>test</scope>
</dependency>
Then create the test itself:
-
Java
-
Kotlin
Create the src/test/java/org/acme/vehiclerouting/solver/VehicleRoutingConstraintProviderTest.java
class:
package org.acme.vehiclerouting.solver;
import java.time.Duration;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;
import java.util.Arrays;
import jakarta.inject.Inject;
import ai.timefold.solver.test.api.score.stream.ConstraintVerifier;
import org.acme.vehiclerouting.domain.Location;
import org.acme.vehiclerouting.domain.Vehicle;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
import org.acme.vehiclerouting.domain.Visit;
import org.acme.vehiclerouting.domain.geo.HaversineDrivingTimeCalculator;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;
import io.quarkus.test.junit.QuarkusTest;
@QuarkusTest
class VehicleRoutingConstraintProviderTest {
/*
* LOCATION_1 to LOCATION_2 is approx. 11713 m ~843 seconds of driving time
* LOCATION_2 to LOCATION_3 is approx. 8880 m ~639 seconds of driving time
* LOCATION_1 to LOCATION_3 is approx. 13075 m ~941 seconds of driving time
*/
private static final Location LOCATION_1 = new Location(49.288087, 16.562172);
private static final Location LOCATION_2 = new Location(49.190922, 16.624466);
private static final Location LOCATION_3 = new Location(49.1767533245638, 16.50422914190477);
private static final LocalDate TOMORROW = LocalDate.now().plusDays(1);
@Inject
ConstraintVerifier<VehicleRoutingConstraintProvider, VehicleRoutePlan> constraintVerifier;
@BeforeAll
static void initDrivingTimeMaps() {
HaversineDrivingTimeCalculator.getInstance().initDrivingTimeMaps(Arrays.asList(LOCATION_1, LOCATION_2, LOCATION_3));
}
@Test
void vehicleCapacityPenalized() {
LocalDateTime tomorrow_07_00 = LocalDateTime.of(TOMORROW, LocalTime.of(7, 0));
LocalDateTime tomorrow_08_00 = LocalDateTime.of(TOMORROW, LocalTime.of(8, 0));
LocalDateTime tomorrow_10_00 = LocalDateTime.of(TOMORROW, LocalTime.of(10, 0));
Vehicle vehicleA = new Vehicle("1", 100, LOCATION_1, tomorrow_07_00);
Visit visit1 = new Visit("2", "John", LOCATION_2, 80, tomorrow_08_00, tomorrow_10_00, Duration.ofMinutes(30L));
vehicleA.getVisits().add(visit1);
Visit visit2 = new Visit("3", "Paul", LOCATION_3, 40, tomorrow_08_00, tomorrow_10_00, Duration.ofMinutes(30L));
vehicleA.getVisits().add(visit2);
constraintVerifier.verifyThat(VehicleRoutingConstraintProvider::vehicleCapacity)
.given(vehicleA, visit1, visit2)
.penalizesBy(20);
}
}
Create the src/test/kotlin/org/acme/schooltimetabling/solver/TimetableConstraintProviderTest.kt
class:
package org.acme.vehiclerouting.solver;
import java.time.Duration
import java.time.LocalDate
import java.time.LocalDateTime
import java.time.LocalTime
import java.util.Arrays
import jakarta.inject.Inject
import ai.timefold.solver.test.api.score.stream.ConstraintVerifier
import ai.timefold.solver.core.api.score.stream.ConstraintFactory
import org.acme.vehiclerouting.domain.Location
import org.acme.vehiclerouting.domain.Vehicle
import org.acme.vehiclerouting.domain.VehicleRoutePlan
import org.acme.vehiclerouting.domain.Visit
import org.acme.vehiclerouting.domain.geo.HaversineDrivingTimeCalculator
import org.junit.jupiter.api.BeforeAll
import org.junit.jupiter.api.Test
import io.quarkus.test.junit.QuarkusTest
@QuarkusTest
internal class VehicleRoutingConstraintProviderTest {
@Inject
lateinit var constraintVerifier: ConstraintVerifier<VehicleRoutingConstraintProvider, VehicleRoutePlan>
@Test
fun vehicleCapacityPenalized() {
val tomorrow_07_00 = LocalDateTime.of(TOMORROW, LocalTime.of(7, 0))
val tomorrow_08_00 = LocalDateTime.of(TOMORROW, LocalTime.of(8, 0))
val tomorrow_10_00 = LocalDateTime.of(TOMORROW, LocalTime.of(10, 0))
val vehicleA = Vehicle("1", 100, LOCATION_1, tomorrow_07_00)
val visit1 = Visit("2", "John", LOCATION_2, 80, tomorrow_08_00, tomorrow_10_00, Duration.ofMinutes(30L))
vehicleA.visits!!.add(visit1)
val visit2 = Visit("3", "Paul", LOCATION_3, 40, tomorrow_08_00, tomorrow_10_00, Duration.ofMinutes(30L))
vehicleA.visits!!.add(visit2)
constraintVerifier!!.verifyThat { obj: VehicleRoutingConstraintProvider, factory: ConstraintFactory? ->
obj.vehicleCapacity(
factory!!
)
}
.given(vehicleA, visit1, visit2)
.penalizesBy(20)
}
companion object {
/*
* LOCATION_1 to LOCATION_2 is approx. 11713 m ~843 seconds of driving time
* LOCATION_2 to LOCATION_3 is approx. 8880 m ~639 seconds of driving time
* LOCATION_1 to LOCATION_3 is approx. 13075 m ~941 seconds of driving time
*/
private val LOCATION_1 = Location(49.288087, 16.562172)
private val LOCATION_2 = Location(49.190922, 16.624466)
private val LOCATION_3 = Location(49.1767533245638, 16.50422914190477)
private val TOMORROW: LocalDate = LocalDate.now().plusDays(1)
@JvmStatic
@BeforeAll
fun initDrivingTimeMaps() {
HaversineDrivingTimeCalculator.INSTANCE.initDrivingTimeMaps(
Arrays.asList(
LOCATION_1, LOCATION_2, LOCATION_3
)
)
}
}
}
This test verifies that the constraint VehicleRoutingConstraintProvider::vehicleCapacity
,
when given two visits assigned to the same vehicle, penalizes with a match weight of 20
(exceeded capacity).
So with a constraint weight of 20hard
it would reduce the score by -20hard
.
Notice how ConstraintVerifier
ignores the constraint weight during testing - even
if those constraint weights are hard coded in the ConstraintProvider
- because
constraints weights change regularly before going into production.
This way, constraint weight tweaking does not break the unit tests.
10.2.2. Test the solver
In a JUnit test, generate a test dataset and send it to the VehicleRoutePlanResource
to solve.
Add some dependencies in your pom.xml
:
<dependency>
<groupId>io.rest-assured</groupId>
<artifactId>rest-assured</artifactId>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.awaitility</groupId>
<artifactId>awaitility</artifactId>
<scope>test</scope>
</dependency>
Then create the test itself:
-
Java
-
Kotlin
Create the src/test/java/org/acme/vehiclerouting/rest/VehicleRoutePlanResourceTest.java
class:
package org.acme.vehiclerouting.rest;
import static io.restassured.RestAssured.get;
import static io.restassured.RestAssured.given;
import static org.awaitility.Awaitility.await;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.time.Duration;
import ai.timefold.solver.core.api.solver.SolverStatus;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
import org.junit.jupiter.api.Test;
import io.quarkus.test.junit.QuarkusTest;
import io.restassured.http.ContentType;
@QuarkusTest
public class VehicleRoutePlanResourceTest {
@Test
public void solveDemoDataUntilFeasible() {
VehicleRoutePlan vehicleRoutePlan = given()
.when().get("/demo-data/FIRENZE")
.then()
.statusCode(200)
.extract()
.as(VehicleRoutePlan.class);
String jobId = given()
.contentType(ContentType.JSON)
.body(vehicleRoutePlan)
.expect().contentType(ContentType.TEXT)
.when().post("/route-plans")
.then()
.statusCode(200)
.extract()
.asString();
await()
.atMost(Duration.ofMinutes(1))
.pollInterval(Duration.ofMillis(500L))
.until(() -> SolverStatus.NOT_SOLVING.name().equals(
get("/route-plans/" + jobId + "/status")
.jsonPath().get("solverStatus")));
VehicleRoutePlan solution = get("/route-plans/" + jobId).then().extract().as(VehicleRoutePlan.class);
assertEquals(solution.getSolverStatus(), SolverStatus.NOT_SOLVING);
assertNotNull(solution.getVehicles());
assertNotNull(solution.getVisits());
assertNotNull(solution.getVehicles().get(0).getVisits());
assertTrue(solution.getScore().isFeasible());
}
}
Create the src/test/kotlin/org/acme/vehiclerouting/rest/VehicleRoutePlanResourceTest.kt
class:
package org.acme.vehiclerouting.rest
import java.time.Duration
import ai.timefold.solver.core.api.solver.SolverStatus
import org.acme.vehiclerouting.domain.VehicleRoutePlan
import org.junit.jupiter.api.Test
import io.quarkus.test.junit.QuarkusTest
import io.restassured.RestAssured
import io.restassured.http.ContentType
import org.awaitility.Awaitility
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Assertions.assertNotNull
import org.junit.jupiter.api.Assertions.assertTrue
@QuarkusTest
class VehicleRoutePlanResourceTest {
@Test
fun solveDemoDataUntilFeasible() {
val vehicleRoutePlan = RestAssured.given()
.`when`()["/demo-data/FIRENZE"]
.then()
.statusCode(200)
.extract()
.`as`(VehicleRoutePlan::class.java)
val jobId = RestAssured.given()
.contentType(ContentType.JSON)
.body(vehicleRoutePlan)
.expect().contentType(ContentType.TEXT)
.`when`().post("/route-plans")
.then()
.statusCode(200)
.extract()
.asString()
Awaitility.await()
.atMost(Duration.ofMinutes(1))
.pollInterval(Duration.ofMillis(500L))
.until {
SolverStatus.NOT_SOLVING.name == RestAssured.get("/route-plans/$jobId/status")
.jsonPath().get("solverStatus")
}
val solution = RestAssured.get("/route-plans/$jobId").then().extract().`as`(
VehicleRoutePlan::class.java
)
assertEquals(solution.solverStatus, SolverStatus.NOT_SOLVING)
assertNotNull(solution.vehicles)
assertNotNull(solution.visits)
assertNotNull(solution.vehicles!!.get(0).visits)
assertTrue(solution.score!!.isFeasible())
}
}
This test verifies that after solving that it found a feasible solution (no hard constraints broken).
Add test properties to the src/main/resources/application.properties
file:
quarkus.timefold.solver.termination.spent-limit=5s
# Effectively disable spent-time termination in favor of the best-score-limit
%test.quarkus.timefold.solver.termination.spent-limit=1h
%test.quarkus.timefold.solver.termination.best-score-limit=0hard/*soft
Normally, the solver finds a feasible solution in less than 200 milliseconds.
Notice how the application.properties
overwrites the solver termination during tests
to terminate as soon as a feasible solution (0hard/*soft
) is found.
This avoids hard coding a solver time, because the unit test might run on arbitrary hardware.
This approach ensures that the test runs long enough to find a feasible solution, even on slow machines.
But it does not run a millisecond longer than it strictly must, even on fast machines.
10.3. Logging
When adding constraints in your ConstraintProvider
,
keep an eye on the score calculation speed in the info
log,
after solving for the same amount of time, to assess the performance impact:
... Solving ended: ..., score calculation speed (29455/sec), ...
To understand how Timefold Solver is solving your problem internally,
change the logging in the application.properties
file or with a -D
system property:
quarkus.log.category."ai.timefold.solver".level=debug
Use debug
logging to show every step:
... Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
... CH step (0), time spent (128), score (-18init/0hard/0soft), selected move count (15), picked move ([Math(101) {null -> Room A}, Math(101) {null -> MONDAY 08:30}]).
... CH step (1), time spent (145), score (-16init/0hard/0soft), selected move count (15), picked move ([Physics(102) {null -> Room A}, Physics(102) {null -> MONDAY 09:30}]).
...
Use trace
logging to show every step and every move per step.
11. Summary
Congratulations! You have just developed a Quarkus application with Timefold!
For a full implementation with a web UI and in-memory storage, check out the Quarkus quickstart source code.