Vehicle Routing Quick Start Guide

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);
    }
}

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"
    }
}

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;
    }
}

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
    }
}

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;
    }
}

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
    }
}

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());
    }
}

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"
    }
}

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)));
    }
}

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]
        }
    }
}

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) {

    }
}

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)
        }
    }
}