VRP - Best practice for modifying vehicle routing quickstart to allow totalDemand to be reset in middle of the day.

[codyfletcher]

I am a huge fan of everything you've done with Timefold (and at OptaPlanner too)!

My question is how to best approach modify the vehicle routing quickstart to accomplish the following:

1. You have a Vehicle (trash truck) collecting trash
2. I want to create a constraint of some sort to allow the Vehicle to visit a Landfill. A landfill would have a location and duration.
3. What would be the recommended way to model this?

Thanks in advance for the help!

[ge0ffrey]

I would create a shadow variable on each visit to calculate the total amount of trash picked up so far.
If the pickupAmount exceeds the capacity of the truck, it automatically resets back to zero first, but changes the travel cost "from previous to this" into "from previous to landfill + from landfill to this"

[codyfletcher]

Thanks @ge0ffrey, making some progress and have a follow up...

There are multiple Landfills (each with a distinct duration and location). I'd like to let the solver choose the landfills when it needs them.

What I tried so far:

1. Landfill - I sub-classed Visit to create a Landfill object.

public class Landfill extends Visit {
    public Landfill() {}

    public Landfill(String id, String name, Location location,
                    LocalDateTime minStartTime, LocalDateTime maxEndTime, Duration serviceDuration) {
        super(id, name, location, 0, minStartTime, maxEndTime, serviceDuration);
    }
}

2. VehicleRoutePlan - I added a landfills property

public class VehicleRoutePlan {

...

    @PlanningEntityCollectionProperty
    private List<Landfill> landfills;

...

    @JsonCreator
    public VehicleRoutePlan(@JsonProperty("name") String name,
            @JsonProperty("southWestCorner") Location southWestCorner,
            @JsonProperty("northEastCorner") Location northEastCorner,
            @JsonProperty("startDateTime") LocalDateTime startDateTime,
            @JsonProperty("endDateTime") LocalDateTime endDateTime,
            @JsonProperty("vehicles") List<Vehicle> vehicles,
            @JsonProperty("visits") List<Visit> visits,
            @JsonProperty("landfills") List<Landfill> landfills) {

        // Added parameter and set it here
        this.landfills = landfills;
        ...
    }

...

    public List<Landfill> getLandfills() {
        return landfills;
    }

3. VehicleRouteDemoResource - I initialized the demo data with a list of landfills

public class VehicleRouteDemoResource {

...

    public enum DemoData { 
        ...
        ORANGE_COUNTY(3, 60, 6, LocalTime.of(7, 30),
                1, 2, 15, 25,
                new Location(33.3865199, -118.1180949),
                new Location(33.946237, -117.4149699));

    ....

    public VehicleRoutePlan buildOrangeCounty(DemoData demoData) {
        String name = "Orange County Demo";

        LocalDateTime vehicleDepartureTime = tomorrowAt(LocalTime.of(7, 0));
        LocalDateTime companyStartTime = tomorrowAt(LocalTime.of(6, 30));
        LocalDateTime companyEndTime = tomorrowAt(LocalTime.of(17, 0));

        List<Vehicle> vehicles = List.of(
                new Vehicle("1", 10, new Location(33.6499804,-117.7462975), vehicleDepartureTime)
        );

        List<Visit> visits = List.of(
                new Visit("1", "Golf Club", new Location(33.7400352, -117.7861598),
                        7, companyStartTime, companyEndTime, Duration.ofMinutes(10)),
                new Visit("2", "Zoo", new Location(33.7963676,-117.7601793),
                        8, companyStartTime, companyEndTime, Duration.ofMinutes(10))
        );

        List<Landfill> landfills = List.of(
                new Landfill("101", "Landfill #1", new Location(33.7185467, -117.7097546),
                        companyStartTime, companyEndTime, Duration.ofMinutes(30)),
                new Landfill("102", "Landfill #2", new Location(33.78793613, -117.7929696),
                        companyStartTime, companyEndTime, Duration.ofMinutes(30))
        );

        return new VehicleRoutePlan(name, demoData.southWestCorner, demoData.northEastCorner, tomorrowAt(demoData.vehicleStartTime), tomorrowAt(LocalTime.MIDNIGHT).plusDays(1L), vehicles, visits, landfills);
    }

4. Vehicle - Updated getTotalDemand() to reset to 0 if the Visit is a Landfill

public class Vehicle {

...

    public int getTotalDemand() {
        int totalDemand = 0;
        for (Visit visit : visits) {
            if (visit instanceof Landfill) {
                totalDemand = 0;
            }
            else {
                totalDemand += visit.getDemand();
            }
        }
        return totalDemand;
    }

...     

}

5. Visit - I created a shadow variable totalTrashPickedUp in an attempt to follow your suggestion

public class Visit {

    ...

    private Integer totalTrashPickedUp;

    ...

    @ShadowVariable(variableListenerClass = TotalTrashPickedUpUpdatingVariableListener.class, sourceVariableName = "vehicle")
    @ShadowVariable(variableListenerClass = TotalTrashPickedUpUpdatingVariableListener.class, sourceVariableName = "previousVisit")
    public Integer getTotalTrashPickedUp() {
        return totalTrashPickedUp;
    }

    public void setTotalTrashPickedUp(Integer totalTrashPickedUp) {
        this.totalTrashPickedUp = totalTrashPickedUp;
    }

6. TotalTrashPickedUpUpdatingVariableListener - I created a variable listener class

package org.acme.vehiclerouting.solver;

import ai.timefold.solver.core.api.domain.variable.VariableListener;
import ai.timefold.solver.core.api.score.director.ScoreDirector;
import org.acme.vehiclerouting.domain.VehicleRoutePlan;
import org.acme.vehiclerouting.domain.Visit;
import org.jboss.logging.Logger;

public class TotalTrashPickedUpUpdatingVariableListener implements VariableListener<VehicleRoutePlan, Visit> {
    private static final Logger LOGGER = Logger.getLogger(TotalTrashPickedUpUpdatingVariableListener.class);
    private static final String TOTAL_TRASH_PICKED_UP_FIELD = "totalTrashPickedUp";

    @Override
    public void beforeVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {}

    @Override
    public void afterVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
        if (visit.getVehicle() == null) {
            return; // Exit if no vehicle is assigned.
        }

        int totalTrashPickedUp = 0;
        Visit currentVisit = visit;

        while (currentVisit != null) {
            scoreDirector.beforeVariableChanged(currentVisit, TOTAL_TRASH_PICKED_UP_FIELD);

            LOGGER.info(" - currentVisit: %s (totalTrashPickedUp: %d, demand: %d)".formatted(currentVisit.getName(), totalTrashPickedUp, currentVisit.getDemand()));

            int vehicleCapacity = currentVisit.getVehicle().getCapacity();
            boolean capacityExceeded = totalTrashPickedUp + currentVisit.getDemand() > vehicleCapacity;
            if (capacityExceeded) {
                // A visit to the landfill is required to empty the vehicle.

                // TODO: Insert the landfill visit after the last successful visit.

                // TODO: Reset the totalTrashPickedUp to 0.
                // totalTrashPickedUp = 0;
            }
            else {
                totalTrashPickedUp += currentVisit.getDemand();
            }

            currentVisit.setTotalTrashPickedUp(totalTrashPickedUp);
            scoreDirector.afterVariableChanged(currentVisit, TOTAL_TRASH_PICKED_UP_FIELD);
            
            currentVisit = currentVisit.getNextVisit(); // Move to the next visit in the chain.
        }
    }

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

}

—

I'm not sure how to approach the actual insertion of Landfill stops into the list of visits for each vehicle.

Additional thought - I'm just a sole proprietor, but would be open to paying for some consultation on this.

Thank you!

Cody