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 still empty, so unassigned. It is a planning variable.

      • The other fields, such as capacity, homeLocation and departureTime, 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 still null for a fresh solution. They are planning shadow variables.

      • The other fields, such as name, location and demand, are filled in. These fields are problem properties.

However, this class is also the output of the solution:

  • The vehicles field for which each Vehicle instance has non-null visits 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)
        }
    }
}