Optaplanner: Как ждать в депо, чтобы соответствовать временному окну для посещения позже в тот же день?

Question

Я следовал примеру CVRPTW в дереве исходных текстов optaplanners, и он прекрасно работает.:)

Но у меня есть кое-что, связанное с моим вариантом использования, с которым я борюсь.

Допустим, у транспортного средства есть только 2 посещения в течение дня, и посещение А доступно в течение всего дня, в то время как посещение Б имеет узкое временное окно во второй половине дня. В настоящее время моим лучшим решением было бы, чтобы транспортное средство рано отправлялось на сервисное посещение А, а прибытие слишком рано на посещение Б - и ожидало, пока не начнется временное окно.

Вместо этого я бы хотел, чтобы Автомобиль ждал в депо, чтобы ему меньше приходилось ждать в поле.

При посещении времени прибытия я зарегистрировал слушателя, чтобы обновить время прибытия.

@CustomShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class,
            sources = {
                @CustomShadowVariable.Source(variableName = "previousLocation")})
    public int getArrivalTime() {
        return arrivalTime;
    }

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

Мой слушатель в настоящее время выглядит так:

public class ArrivalTimeUpdatingVariableListener implements VariableListener<Visit> {

    @Override
    public void beforeEntityAdded(ScoreDirector scoreDirector, Visit entity) {
        // Do nothing
    }

    @Override
    public void afterEntityAdded(ScoreDirector scoreDirector, Visit visit) {
        updateArrivalTime(scoreDirector, visit);
    }

    @Override
    public void beforeVariableChanged(ScoreDirector scoreDirector, Visit entity) {
        // Do nothing
    }

    @Override
    public void afterVariableChanged(ScoreDirector scoreDirector, Visit visit) {
        updateArrivalTime(scoreDirector, visit);
    }

    @Override
    public void beforeEntityRemoved(ScoreDirector scoreDirector, Visit entity) {
        // Do nothing
    }

    @Override
    public void afterEntityRemoved(ScoreDirector scoreDirector, Visit entity) {
        // Do nothing
    }

    protected void updateArrivalTime(ScoreDirector scoreDirector, Visit sourceVisit) {
        WorkPlanSolution solution = (WorkPlanSolution) scoreDirector.getWorkingSolution();
        Location previousLocation = sourceVisit.getPreviousLocation();
        Integer departureTime = null;
        if(previousLocation != null) {
            departureTime = previousLocation.getDepartureTime();
        }
        Visit shadowVisit = sourceVisit;

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

    private Integer calculateArrivalTime(WorkPlanSolution solution, Visit visit, Integer previousDepartureTime) {
        if (visit == null || visit.getLocation()== null) {
            return 0;
        }

        int distanceToPreviousInSeconds = 0;

        if(visit.getPreviousLocation() != null) {
            distanceToPreviousInSeconds = solution.getDistanceMatrix().getDistanceBetween(visit.getPreviousLocation().getLocation(), 
                    visit.getLocation());
        } else if(visit.getWorkPlan() != null) {
            distanceToPreviousInSeconds = solution.getDistanceMatrix().getDistanceBetween(visit.getWorkPlan().getLocation(), visit.getLocation());
        }

        int distanceToPreviousInMinutes = distanceToPreviousInSeconds / 60;  

        if (previousDepartureTime == null) {
            // PreviousStandstill is the Vehicle, so we leave from the Depot at the best suitable time

            return Math.max(visit.getReadyTime(), distanceToPreviousInMinutes);
        } else {
            return previousDepartureTime + distanceToPreviousInMinutes;
        }
    }
}

Я думаю, что при обновлении ArrivalTime мне нужно как-то определить, обновляется ли это первое посещение, а затем рассчитать день в обратном направлении, чтобы найти подходящее время отправления, принимая во внимание все время готовности из временных окон.

Но это должно быть общим вопросом. Есть ли лучшее решение?

Answer 1

Итак, мне наконец удалось решить эту проблему, хотя мне все еще нужно оптимизировать производительность.

В полупсевдо-терминах это то, что я сделал в моем методе updateArrivalTime:

protected void updateArrivalTime(ScoreDirector scoreDirector, Visit sourceVisit) {
        WorkPlanSolution solution = (WorkPlanSolution) scoreDirector.getWorkingSolution();
    Location previousLocation = sourceVisit.getPreviousLocation();
    WorkPlan plan = getWorkPlan(sourceVisit);
    Integer prevDepartureTime = null;

    if (previousLocation != null) {
        prevDepartureTime = previousLocation.getDepartureTime();
    }


    if(plan == null) {
        // No plan found. Just update from this element and downwards
        Visit firstLink = sourceVisit;
        Integer arrivalTime = calculateArrivalTime(solution, plan, firstLink, prevDepartureTime);
        updateChainedArrival(scoreDirector, solution, arrivalTime, plan, firstLink);
    } else {
        // Plan found. Recalculate from the beginning of the workplan.
        plan.resetDepartureTime();
        Visit firstLink = plan.getNextVisit();
        Integer arrivalTime = calculateArrivalTime(solution, plan, firstLink, plan.getDepartureTime());
        updateChainedArrival(scoreDirector, solution, arrivalTime, plan, firstLink);

        // Update wait time if needed 
        int trimableTime = WorkPlanHelper.calculateTrimableWaitTime(plan);
        if(trimableTime > 0) {
            // Update all arrival times of the workplan again
            firstLink = plan.getNextVisit();
            plan.setDepartureTime(plan.getDepartureTime() + trimableTime);
            arrivalTime = calculateArrivalTime(solution, plan, firstLink, plan.getDepartureTime());
            updateChainedArrival(scoreDirector, solution, arrivalTime, plan, firstLink);
        }
    }

}

Как это работает? WorkPlanHelper.calculateTrimableWaitTime(plan); Можно определить, на сколько минут можно отложить отправку со склада, чтобы минимизировать время ожидания у каждого клиента, но без учета временных интервалов.

Answer 2

Если визит является первым клиентом (так if previousStandstill instanceof Vehicle) то время прибытия действительно должно быть max(readyTime, previousStandstillWhichIsVehicle.getDepotOpenTime() + drivingTime),

Все остальное, как в примере: при изменении времени посещения для посещения (и, следовательно, также и времени вылета), слушатель выполняет итерации по остальной части цепочки, чтобы соответствующим образом обновить эти посещения (см. Также изображение в документации).