Vehicle routing in Java

This page plans a real week of deliveries with the Java client quicopt-java. The rules are constraint streams over a planning list variable, and the search runs on the Quicopt planner service. The data are real and anonymised.

The delivery week

Every weekday, 13 or 14 trucks leave one depot and serve 88 to 105 customers. A plan says which truck serves which customers, and in which order. It has to keep five rules:

• Capacity. No trip carries more than its truck holds.
• Time windows. Some customers have a latest start of service.
• Duty day. A driver's day, from leaving the depot to returning, lasts at most 8 h 45: 9 h 30 of working time less a 45-minute break, deducted every day. Waiting for a window counts.
• Trailer access. Some trucks pull a trailer today. They carry about twice as much, but most customers' yards are too small for them.
• Reloads. A truck may return to the depot up to four times to load again. Each return starts a new trip with an empty truck.

Of the plans that keep all five rules, the best one drives the fewest hours in total.

Each day is a JSON file with the customers, the trucks and two tables of drive times. A truck with a trailer takes other roads than a truck alone, so each kind has its own table. Names, places and weekdays are gone, and times and demands are perturbed.

The model

A truck's route is a list of stops, and the solver decides the list:

@PlanningEntity
public class Vehicle {
    // …
    @PlanningListVariable(allowsUnassignedValues = true)
    private List<Stop> stops = new ArrayList<>();

A stop is a customer or a reload. A reload sits at the depot and splits the route into trips. The number of reloads a truck needs is part of the answer, so the plan holds a pool of them, as many as all trucks together may use. The solver puts some into routes and leaves the rest out, which is why the list variable allows unassigned values:

int reloads = day.vehicles().stream().mapToInt(Day.Truck::maxReloads).sum();
for (int r = 0; r < reloads; r++) {   // loop over the reload pool
    stops.add(Stop.reload("reload " + (r + 1), depot));
}   // end loop over the reload pool

A reload left out costs nothing. A customer left out breaks a rule of its own, on the score's medium level, so the solver first serves everyone and then shortens the drive.

The rules

RoutingConstraints lists the seven rules. Five are hard and have the same shape: for each truck, penalize by how much its route breaks the rule.

public class RoutingConstraints implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory factory) {
        return new Constraint[] {
                capacity(factory),
                timeWindow(factory),
                dutyDay(factory),
                trailerAccess(factory),
                reloadLimit(factory),
                everyCustomerServed(factory),
                drive(factory)
        };
    }

    /** No trip carries more than the truck holds. */
    Constraint capacity(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .penalize(HardMediumSoftScore.ONE_HARD, Vehicle::excessLoad)
                .asConstraint("capacity");
    }

A route that keeps the rule penalizes 0, so no filter stands in front of penalize. A filter would call the same measure again and walk the route a second time.

The other two rules are the medium level and the objective:

    /** Every customer is on some route. Reloads may stay unused. */
    Constraint everyCustomerServed(ConstraintFactory factory) {
        return factory.forEachIncludingUnassigned(Stop.class)
                .filter(stop -> !stop.isReload() && stop.getVehicle() == null)
                .penalize(HardMediumSoftScore.ONE_MEDIUM)
                .asConstraint("customer served");
    }

    /** The objective: as little driving as possible. */
    Constraint drive(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .penalize(HardMediumSoftScore.ONE_SOFT, Vehicle::driveSeconds)
                .asConstraint("drive");
    }

Route measures

Each measure is a method on Vehicle that walks the route. Capacity holds per trip, so the load starts again at every reload:

    /** @return load beyond the truck's capacity, summed over its trips */
    public long excessLoad() {
        long load = 0;
        long excess = 0;
        for (Stop stop : stops) {
            if (stop.isReload()) {
                excess += Math.max(0, load - capacity);
                load = 0;
            } else {
                load += stop.demand();
            }
        }
        return excess + Math.max(0, load - capacity);
    }

The duty day takes more care. A truck that arrives before a window opens waits, and the waiting counts as working time. It could also leave the depot later and wait less, as long as every stop still starts in time. The walk starts the truck at 0 and keeps two sums: the waiting so far, and how much later the truck could have left and still made every latest start. The day is shorter by the smaller of the two:

    public long durationSeconds() {
        long clock = 0;
        long waitSoFar = 0;                     // waiting before the current stop, all stops so far
        long canLeaveLater = Long.MAX_VALUE;    // how much later the truck could leave and be on time
        Location at = depot;
        for (Stop stop : stops) {
            long arrival = clock + travel.drive(at, stop.location());
            long serviceStart = Math.max(arrival, stop.earliestStart());
            waitSoFar += serviceStart - arrival;
            if (stop.latestStart() != Stop.OPEN) {
                canLeaveLater = Math.min(canLeaveLater, waitSoFar + stop.latestStart() - serviceStart);
            }
            clock = serviceStart + stop.serviceSeconds();
            at = stop.location();
        }
        long end = clock + travel.drive(at, depot);
        return end - Math.max(0, Math.min(waitSoFar, canLeaveLater));
    }

Code the service can run

The search runs on the service, not in your JVM. The client reads the rule methods, and every method they call, and sends them with the plan. Version 0.1.0-beta.1 can't send three things, and the model is written around them:

• Array reads. A rule reads a drive time through a method, never from long[][] directly. The client calls the method for every pair of locations before the solve and sends the results as a table.
• New objects. A record holding drive, duration and load from one walk would be the natural design. Instead, each measure is a method of its own and walks the route itself.
• switch. A rule that depends on a kind of truck or day uses if.

The drive times show the first point. TravelTimes holds one table, and every vehicle of one kind shares one object:

public record TravelTimes(long[][] seconds) {

    /**
     * @param from where the drive starts
     * @param to where the drive ends
     * @return the drive in seconds
     */
    public long drive(Location from, Location to) {
        return seconds[from.index()][to.index()];
    }
}

A model that breaks one of these is refused before the solve starts. The message names the method and the line.

The solve

The configuration names the classes and a time limit:

        SolverConfig config = new SolverConfig()
                .withSolutionClass(RoutePlan.class)
                .withEntityClasses(Vehicle.class, Stop.class)
                .withConstraintProviderClass(RoutingConstraints.class)
                .withTerminationSpentLimit(perDay);
        Solver<RoutePlan> solver = SolverFactory.<RoutePlan> create(config).buildSolver();

One solver plans the days one after another:

            Day day = JSON.readValue(new File(args[a]), Day.class);
            RoutePlan plan = solver.solve(new RoutePlan(day));

With 20 seconds per day, the run printed:

Day 1  0hard/0medium/-117365soft  drive 32.60 h  12 trucks, 13 trips
Day 2  0hard/0medium/-127969soft  drive 35.55 h  11 trucks, 14 trips
Day 3  0hard/0medium/-99320soft   drive 27.59 h  10 trucks, 12 trips
Day 4  0hard/0medium/-121173soft  drive 33.66 h  11 trucks, 13 trips
Day 5  0hard/0medium/-126215soft  drive 35.06 h  12 trucks, 14 trips
Week drive 164.46 h

Every day scores 0 hard and 0 medium: the plan breaks no rule and serves every customer. The soft score is minus the drive in seconds. Each trip beyond the number of trucks is a reload: on day 2, trucks come back to load again three times.

Running it

The whole project, data included, is the example examples/vehicle-routing in the client's repository. The client isn't on Maven Central yet, so install the version the example uses first:

git clone https://github.com/Quicopt/quicopt-java.git
cd quicopt-java
git checkout v0.1.0-beta.1
mvn -q install -DskipTests
git checkout main

The example depends on it:

    <dependency>
      <groupId>com.quicopt</groupId>
      <artifactId>quicopt-planner</artifactId>
      <version>0.1.0-beta.1</version>
    </dependency>

The service needs an API key. Register to receive one by email, and put it into the environment variable QUICOPT_API_KEY. Then build with JDK 21 or later and run:

cd examples/vehicle-routing
mvn -q package
java -jar target/routing.jar 20 data/day-1.json data/day-2.json data/day-3.json data/day-4.json data/day-5.json

Each day's routes are written to plans/day-<n>.json.

Your own model

The Java client is in beta. Questions about it, or a planning model you want to run on Quicopt? Just ask: