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 {
@PlanningEntityCollectionProperty
private List<Vehicle> vehicles;
@PlanningEntityCollectionProperty
@ValueRangeProvider
private List<Visit> visits;
@PlanningScore
private HardSoftLongScore score;
// Fields and constructors used for visualization excluded
public VehicleRoutePlan() {
}
public VehicleRoutePlan(String name,
List<Vehicle> vehicles,
List<Visit> visits) {
this.name = name;
this.vehicles = vehicles;
this.visits = visits;
// Enhance locations with a pre-calculated driving time map
List<Location> locations = Stream.concat(
vehicles.stream().map(Vehicle::getHomeLocation),
visits.stream().map(Visit::getLocation)).toList();
DrivingTimeCalculator drivingTimeCalculator = HaversineDrivingTimeCalculator.getInstance();
drivingTimeCalculator.initDrivingTimeMaps(locations);
}
// Getters and Setters excluded
}
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
@PlanningEntityCollectionProperty
var vehicles: List<Vehicle>? = null
private set
@PlanningEntityCollectionProperty
@ValueRangeProvider
var visits: List<Visit>? = null
private set
@PlanningScore
var score: HardSoftLongScore? = null
// Fields and constructors used for visualization excluded
constructor()
constructor(
name: String,
vehicles: List<Vehicle>,
visits: List<Visit>
) {
this.name = name
this.vehicles = vehicles
this.visits = visits
// Enhance locations with a pre-calculated driving time map
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)
}
}
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
.
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.
Distance calculation
A matrix of distances between each location is typically calculated before starting the solver. 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)
}
}
}