CODEWITHSUNDEEP
optaplannervehicle-routingtimefoldoptaweb-vehicle-routing
Edmanan Khandelwal
Edmanan Khandelwal

Reputation: 53

Timefold is returning a solution with hard score in Vehicle Routing Problem Time windowed

I am using timefold for my vehicle routing problem time windowed use case :

  1. There are nurses/clinicians and there are visits.
  2. nurses/clinicians will perform visits starting from home location and travel from visit to visit.
  3. Visits will have time windows.
  4. Requirement is to find optimized route for nurses/clinicians.

Planning Entity 1:

@PlanningEntity
@Data
public class Visits {
    @PlanningId
    private String id;

    private Double matrixVisitId;
    private Long clientId;
    private VisitMsa msa;
    private Date[] slotPreferences;
    private String[] products;
    private VisitsMember member;
    private String slotType;
    private boolean pinned;
    private TimeWindow timeWindow;

    private ClinicianSlot assignedSlot;

    private Providers assignedClinician;
    private Visits previousVisit;

    @CascadingUpdateShadowVariable(targetMethodName = "updateArrivalTime")
    private LocalDateTime arrivalTime;

    @ValueRangeProvider(id = "timeBlockRangeForVisit")
    public List<ClinicianSlot> generatePossibleTimeBlocks() {
        if (this.timeWindow == null) {
            return Collections.emptyList();
        }
        List<ClinicianSlot> possibleTimeBlocks = new ArrayList<>();
        LocalDateTime start = timeWindow.getStart();
        while (!start.plusHours(1).isAfter(timeWindow.getEnd())) {
            possibleTimeBlocks.add(new ClinicianSlot(start, start.plusHours(1)));
            start = start.plusHours(1);
        }
        return possibleTimeBlocks;
    }

    @PlanningPin
    public boolean isPinned() {
        return pinned;
    }

    @PreviousElementShadowVariable(sourceVariableName = "visits")
    public Visits getPreviousVisit() {
        return previousVisit;
    }

    public void setPreviousVisit(Visits previousVisit) {
        this.previousVisit = previousVisit;
    }

    @InverseRelationShadowVariable(sourceVariableName = "visits")
    public Providers getAssignedClinician() {
        return assignedClinician;
    }

    public LocalDateTime getArrivalTime() {
        return arrivalTime;
    }

    public void setArrivalTime(LocalDateTime arrivalTime) {
        this.arrivalTime = arrivalTime;
    }

    @SuppressWarnings("unused")
    private void updateArrivalTime() {
        if (previousVisit == null && assignedClinician == null) {
            arrivalTime = null;
            return;
        }
        LocalDateTime departureTime = previousVisit == null ? assignedClinician.getDepartureTime() : previousVisit.getDepartureTime();
        arrivalTime = departureTime != null ? departureTime.plusMinutes(getDrivingTimeSecondsFromPreviousStandstill()) : null;
    }

    @JsonProperty(access = JsonProperty.Access.READ_ONLY)
    public LocalDateTime getDepartureTime() {
        if (arrivalTime == null) {
            return null;
        }
        return getStartServiceTime().plusMinutes(55);
    }

    @JsonProperty(access = JsonProperty.Access.READ_ONLY)
    public LocalDateTime getStartServiceTime() {
        if (arrivalTime == null) {
            return null;
        }
        return arrivalTime;
    }

    @JsonIgnore
    public long getDrivingTimeSecondsFromPreviousStandstill() {
        if (assignedClinician == null) {
            throw new IllegalStateException(
                    "This method must not be called when the shadow variables are not initialized yet.");
        }
        if (previousVisit == null) {
            return Constants.getDrivingTime(assignedClinician.getLocation().getCoordinates(), member.getMemberLocation().getCoordinates());
        }
        return Constants.getDrivingTime(previousVisit.getMember().getMemberLocation().getCoordinates(), member.getMemberLocation().getCoordinates());
    }

    @Override
    public String toString() {
        return id;
    }
}

Planning entity 2:

@Data
@PlanningEntity
@AllArgsConstructor
@NoArgsConstructor
public class Providers {

    @PlanningId
    private String id;

    private Integer staffResourceId;
    private String providerId;
    private ProviderMsa[] msa;
    private Client[] clients;
    private String[] products;
    private List<ClinicianSlot> availableSlots;

    @PlanningListVariable(valueRangeProviderRefs = "visitRange",allowsUnassignedValues = true)
    private List<Visits> visits = new ArrayList<>();

    @GeoSpatialIndexed(type = GeoSpatialIndexType.GEO_2DSPHERE)
    private Location location;

    private LocalDateTime departureTime;

    @JsonProperty(access = JsonProperty.Access.READ_ONLY)
    public int getTotalDrivingTimeSeconds() {
        if (visits.isEmpty()) {
            return 0;
        }

        int totalDrivingTime = 0;
        Location previousLocation = location;

        for (Visits visit : visits) {
            totalDrivingTime += Constants.getDrivingTime(previousLocation.getCoordinates(), visit.getMember().getMemberLocation().getCoordinates());
            previousLocation = visit.getMember().getMemberLocation();
        }
        totalDrivingTime += Constants.getDrivingTime(previousLocation.getCoordinates(), location.getCoordinates());

        return totalDrivingTime;
    }

    @JsonProperty(access = JsonProperty.Access.READ_ONLY)
    public LocalDateTime arrivalTime() {
        if (visits.isEmpty()) {
            return departureTime;
        }

        Visits lastVisit = visits.get(visits.size() - 1);
        return lastVisit.getDepartureTime().plusMinutes(Constants.getDrivingTime(lastVisit.getMember().getMemberLocation().getCoordinates(), location.getCoordinates()));
    }

    @Override
    public String toString() {
        return id;
    }
}

Solution Class :

@PlanningSolution
@Data
public class ProviderRouteSolution {

    private List<Visits> visitList;

    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "visitRange")
    public List<Visits> getVisitList() {
        return visitList;
    }

    private List<Providers> clinicianList;
    
    @PlanningScore
    private HardSoftScore score;

    @ValueRangeProvider(id = "clinicianRange")
    @PlanningEntityCollectionProperty
    public List<Providers> getClinicianList() {
        return clinicianList;
    }
}

Service Method :

public List<String> getProviderRouteForTheDay(int staffResourceId, double radiusInMiles, String visitDateString) throws ParseException {
        Providers provider = providersRepository.findByStaffResourceId(staffResourceId);
        Double longitude = provider.getLocation().getCoordinates()[0];
        Double latitude = provider.getLocation().getCoordinates()[1];
        double radiusInMeters = radiusInMiles * 1609.34;
        Location location = new Location(latitude, longitude);
        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
        dateFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
        Date visitDate = dateFormat.parse(visitDateString);
        // Set start of the day (UTC)
        Calendar startCal = Calendar.getInstance(TimeZone.getTimeZone("UTC"));
        startCal.setTime(visitDate);
        startCal.set(Calendar.HOUR_OF_DAY, 0);
        startCal.set(Calendar.MINUTE, 0);
        startCal.set(Calendar.SECOND, 0);
        startCal.set(Calendar.MILLISECOND, 0);
        Date startOfDay = startCal.getTime();
        // Set end of the day (UTC)
        Calendar endCal = Calendar.getInstance(TimeZone.getTimeZone("UTC"));
        endCal.setTime(visitDate);
        endCal.set(Calendar.HOUR_OF_DAY, 23);
        endCal.set(Calendar.MINUTE, 59);
        endCal.set(Calendar.SECOND, 59);
        endCal.set(Calendar.MILLISECOND, 999);
        Date endOfDay = endCal.getTime();
        System.out.println("Start of Day: " + startOfDay);
        System.out.println("End of Day: " + endOfDay);
        List<ProviderSlots> providerSlots = providerSlotsRepository.findSlotsByProviderAndDateRangeAndStatus(provider.getStaffResourceId(), startOfDay, endOfDay, "available");
        List<ClinicianSlot> clinicianSlots = new ArrayList<>();
        for (ProviderSlots slot : providerSlots) {
            clinicianSlots.addAll(generate1HourSlots(convertToLocalDateTime(slot.getSlotTime()), convertToLocalDateTime(slot.getSlotEndTime())));
        }
        provider.setAvailableSlots(clinicianSlots);
        provider.setDepartureTime(LocalDateTime.of(
                LocalDateTime.now(ZoneOffset.UTC).getYear(),
                LocalDateTime.now(ZoneOffset.UTC).getMonth(),
                26,
                12, 0
        ));
        List<Visits> visitsList = visitsRepository.findUnclaimedVisitsNear(location.getLongitude(), location.getLatitude(), radiusInMeters, startOfDay, endOfDay);
        assignVisitTimeWindows(visitsList);
        ProviderRouteSolution unsolvedSolution = new ProviderRouteSolution();
        ProviderRouteSolution solvedSolution = new ProviderRouteSolution();
        unsolvedSolution.setVisitList(visitsList);
        unsolvedSolution.setClinicianList(Collections.singletonList(provider));
        initializeDrivingTimeMatrix(provider, visitsList);
        try {
            solvedSolution = solver.solve(unsolvedSolution);
        } catch(Exception ex) {
            ex.printStackTrace();
        }
        System.out.println(solvedSolution);
        return null;
    }

Constraint Class :

@Service
public class ProviderSchedulingConstraintProvider implements ConstraintProvider {

    public ProviderSchedulingConstraintProvider() {
    }

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
                enforceAllHardConstraints(constraintFactory),
                assignVisitToValidSlotAndClinician(constraintFactory),
                minimizeChainedTravelDistance(constraintFactory),
                penalizeUnassignedVisits(constraintFactory)
        };
    }
    
    private Constraint penalizeUnassignedVisits(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachIncludingUnassigned(Visits.class)
                .filter(visit -> visit.getAssignedClinician() == null)
    .penalize(HardMediumSoftScore.ONE_MEDIUM).asConstraint("Unassigned Visit");
    }

    private Constraint enforceAllHardConstraints(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Visits.class)
                .filter(visit -> visit.getAssignedClinician() != null) // Ensure clinician is assigned
                .penalize(HardSoftScore.ONE_HARD, visit -> {
                    Providers clinician = visit.getAssignedClinician();
                    boolean msaMatches = (clinician.getMsa() != null && visit.getMsa() != null) &&
                            Arrays.stream(clinician.getMsa())
                                    .anyMatch(msa -> Objects.equals(msa.getState(), visit.getMsa().getName()));
                    boolean clientMatches = (clinician.getClients() != null && visit.getClientId() != null) &&
                            Arrays.stream(clinician.getClients())
                                    .anyMatch(client -> Objects.equals(client.getClientId().longValue(), visit.getClientId()));
                    boolean productMatches = (clinician.getProducts() != null && visit.getProducts() != null) &&
                            Arrays.asList(clinician.getProducts()).contains("CHA") &&
                            Arrays.asList(visit.getProducts()).contains("CHA");
                    return (msaMatches && clientMatches && productMatches) ? 0 : 1;
                }).asConstraint("Enforce All Hard Constraints");
    }

    protected Constraint minimizeChainedTravelDistance(ConstraintFactory factory) {
        return factory.forEach(Providers.class)
                .penalize(HardSoftScore.ONE_SOFT,
                        Providers::getTotalDrivingTimeSeconds)
                .asConstraint("minimizeTravelTime");
    }

    private Constraint assignVisitToValidSlotAndClinician(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Visits.class)
                .filter(visit -> visit.getAssignedClinician() != null)
                .penalize(HardSoftScore.ONE_HARD, visit -> {
                    Providers assignedClinician = visit.getAssignedClinician();
                    boolean fitsVisitWindow = isVisitWithinMemberTimeWindow(assignedClinician, visit);
                    return (!fitsVisitWindow) ? 10000 : 0;
                }).asConstraint("Assign Visit to Valid Slot and Clinician");
    }


    private boolean isVisitWithinMemberTimeWindow(Providers clinician, Visits visit) {
        LocalDateTime visitWindowStart = visit.getTimeWindow().getStart();
        LocalDateTime visitWindowEnd = visit.getTimeWindow().getEnd();
        boolean isArrivalAfterWindowStart = visit.getArrivalTime().isAfter(visitWindowStart);
        boolean isDepartureBeforeWindowEnd = visit.getArrivalTime().plusMinutes(55).isBefore(visitWindowEnd);
        return isArrivalAfterWindowStart && isDepartureBeforeWindowEnd;
    }
}

vehicleRoutingSolverConfig.xml :

<?xml version="1.0" encoding="UTF-8"?>

<!--<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"-->
<!--        xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">-->
<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
            xsi:schemaLocation="https://timefold.ai/xsd/solver">

    <solutionClass>com.optaplanner.dto.ProviderRouteSolution</solutionClass>
    <entityClass>com.optaplanner.model.Visits</entityClass>
    <entityClass>com.optaplanner.model.Providers</entityClass>

    <scoreDirectorFactory>
        <constraintProviderClass>com.optaplanner.service.impl.ProviderSchedulingConstraintProvider
        </constraintProviderClass>
        <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
    </scoreDirectorFactory>

    <termination>
        <minutesSpentLimit>5</minutesSpentLimit>
    </termination>
    <constructionHeuristic>
    </constructionHeuristic>
    <localSearch>
        <acceptor>
            <lateAcceptanceSize>200</lateAcceptanceSize>
        </acceptor>
        <forager>
            <acceptedCountLimit>1</acceptedCountLimit>
        </forager>
    </localSearch>
</solver>

Now there are 4 visits each with same timeWindow : 12:00-16:00 and visit duration of each visit is 55 mins After running the solvedSolution i get has below arrival time :

Visit 1: arrivalTime : 2024-10-26T12:47 Visit 1 completion time(55 mins) : 2024-10-26T13:42

Visit 1 -> Visit 2 driving time : 55mins

Visit 2: arrivalTime : 2024-10-26T14:37 Visit 2 completion time(55 mins) : 2024-10-26T14:32

Visit 2 -> Visit 3 driving time : 49mins

Visit 3: arrivalTime : 2024-10-26T17:21 Visit 3 completion time(55 mins) : 2024-10-26T16:16

Visit 3 -> Visit 4 driving time : 90mins

Visit 4: arrivalTime : 2024-10-26T19:46 Visit 4 completion time(55 mins) : 2024-10-26T13:42

Now clearly visit 3 and visit 4 violate the timeWindow constraint (check method assignVisitToValidSlotAndClinician()) and also constraints score of the solvedSolution is 40000Hard/-381Soft, still inside solved solution, inside clinicianList[0].visits i am getting all 4 visits with above arrival time.

Question 1 : why is Hard score 40000, it means that all 4 visits violated hard constraint of assignVisitToValidSlotAndClinician(), but visit 1 and visit 2 are well within the rules. Question 2 : why are visit 3 and visit 4 included in solved solution even when they violate hard constraint of assignVisitToValidSlotAndClinician() as they are outside visit time window based on arrival time.

NOTE : all the arrvial time calculation and driving time matrix is working fine calculation wise, constraints are not working as expected. Just visit 1 and visit 2 should be assigned to the clinician in above example. Also above is a simple case still it is taking 5 mins for timefold in my local. Note that termination is set to 5 mins in vehicleRoutingSolverConfig.xml.

After looking more i think issue is that timefold is returning a solution even when it has a hard score, i want solutions with no hard score. Also, not all the visits need to be assigned to clinician in my case, optimal solution only has visits assigned to clinician where no hard constraint was violated. Hope this helps to further debug the problem and find what i have missed.

Output :

id : 784b2591-21f1-4286-a41c-e012ba4d03d3
arrivalTime : 2024-09-26T12:47
visitWindowStart : 2024-09-26T12:00
visitWindowEnd : 2024-09-26T16:00
isVisitWithinMemberTimeWindow : true

id : f4a73f50-2a36-45d8-995e-19332e41c53b
arrivalTime : 2024-09-26T14:37
visitWindowStart : 2024-09-26T12:00
visitWindowEnd : 2024-09-26T16:00
isVisitWithinMemberTimeWindow : true

id : 01672414-c2c4-4ae9-85e9-612e84e948e3
arrivalTime : 2024-09-26T17:21
visitWindowStart : 2024-09-26T12:00
visitWindowEnd : 2024-09-26T16:00
isVisitWithinMemberTimeWindow : false

id : 035b5e2f-53e3-4af2-8b44-2691d4a964f5
arrivalTime : 2024-09-26T19:46
visitWindowStart : 2024-09-26T12:00
visitWindowEnd : 2024-09-26T16:00
isVisitWithinMemberTimeWindow : false

Upvotes: 0

Views: 161

Answers (0)

Related Questions