Reducing downtime (idle time) when arriving early for a visit

Viewed 31

Optaplanner is being used to plan the routes of a fleet of vehicles and I am optimizing the route times.

I have a scenario where I have one visit with time windows in the morning and the second visit with time window in the afternoon. However the vehicle leaves when the time window opens, makes the first delivery and heads to the second visit. Since the second visit has a time window in the afternoon, the vehicle has to wait for the time window of this visit to open, which introduces downtime. This downtime (idle time) can be reduced by leaving the depot later. So I would like to ask if: Is there any rule to q backtrack to the depot or to the previous visit, wait longer to continue, and thereby reduce the downtime or waiting time on the second visit?

I have tried different variants:

1- I implemented a constraint to penalize if early to a visit and penalize with customer -> customer.getReadyTime() - customer.getArrivalTime(). This may optimize but it does not roll back the arrivalTime.

2- Modify my listener (ArrivalTimeUpdatingVariableListener, updateArrivalTime method).When calculating the arrival time, if there is idle time, I go to the previous visit and subtract the idle time. However, in some cases it does not recursively update all previous visits correctly, and in other cases it gives me a "VariableListener corruption". I have had no success for this variant either.

Is there any rule to wait or roll back and update all visits again?

I attach my constraint and listener for better context.

ArrivalTimeUpdatingVariableListener.class:

   protected void updateArrivalTime(ScoreDirector scoreDirector, TimeWindowedVisit sourceCustomer) {
        Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
        Long departureTime = previousStandstill == null ? null
                : (previousStandstill instanceof TimeWindowedVisit)
                ? ((TimeWindowedVisit) previousStandstill).getArrivalTime() + ((TimeWindowedVisit) previousStandstill).getServiceDuration()
                : ((PlanningVehicle) previousStandstill).getDepot() != null
                ? ((TimeWindowedDepot) ((PlanningVehicle) previousStandstill).getDepot()).getReadyTime()
                : 0;
        TimeWindowedVisit shadowCustomer = sourceCustomer;
        Long arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);

        while (shadowCustomer != null && !Objects.equals(shadowCustomer.getArrivalTime(), arrivalTime)) {
            scoreDirector.beforeVariableChanged(shadowCustomer, "arrivalTime");
            shadowCustomer.setArrivalTime(arrivalTime);
            scoreDirector.afterVariableChanged(shadowCustomer, "arrivalTime");
            departureTime = shadowCustomer.getDepartureTime();
            shadowCustomer = shadowCustomer.getNextVisit();
            arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
        }
    }

    private Long calculateArrivalTime(TimeWindowedVisit customer, Long previousDepartureTime) {
        long arrivalTime = 0;
        if (customer == null || customer.getPreviousStandstill() == null) {
            return null;
        }
        if (customer.getPreviousStandstill() instanceof PlanningVehicle) {
             arrivalTime = Math.max(customer.getReadyTime(),
                    previousDepartureTime + customer.distanceFromPreviousStandstill());
        } else {
            arrivalTime = previousDepartureTime + customer.distanceFromPreviousStandstill();
            
             // to reach backwards and (attempt to) shift the previous arrival time.
            Standstill previousStandstill = customer.getPreviousStandstill();
            long idle = customer.getReadyTime() - arrivalTime;
            if (previousStandstill != null && idle > 0) {
                arrivalTime += idle;

                if (previousStandstill instanceof TimeWindowedVisit) {
                    long previousArrival = ((TimeWindowedVisit) previousStandstill).getArrivalTime() + idle;
                    if (previousArrival >  ((TimeWindowedVisit) previousStandstill).getDueTime()){
                        System.out.println("Arrival es mayor que el duetime");
                        previousArrival = ((TimeWindowedVisit) previousStandstill).getDueTime() - ((TimeWindowedVisit) previousStandstill).getServiceDuration();
                    }
                   ((TimeWindowedVisit) previousStandstill).setArrivalTime(previousArrival);
                }
            }
        }
         
        // breaks

        return arrivalTime;
    }

ConstraintProvider.class:

    private Constraint arrivalEarly(ConstraintFactory constraintFactory) {
        return constraintFactory.from(TimeWindowedVisit.class)
                .filter((customer) -> !customer.getVehicle().isGhost() && customer.getArrivalTime() < customer.getReadyTime())
                .penalizeConfigurableLong(
                        VehicleRoutingConstraintConfiguration.MINIMIZE_IDLE_TIME,
                        customer -> customer.getReadyTime() - customer.getArrivalTime());

    }
0 Answers
Related