Optaplanner：如何在站点等待当天晚些时候的匹配时间 window？

Question

我遵循了 optaplanners 源代码树中的 CVRPTW 示例，它运行良好。 :)

但是我遇到了一个与我的用例相关的问题，我对此很纠结。

假设一辆车一天只有 2 次访问，并且访问 A 全天可用，而访问 B 在下午的时间很短 window。目前，我最好的解决方案是让车辆提前离开以服务访问 A，而在访问 B 过早到达 - 等到时间 window 开始。

相反，我希望车辆在站点等候，这样他就不需要在现场等待。

在 Visit arrivalTime 我注册了一个监听器以更新 arrivalTime。

@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 时，我需要以某种方式检测它是否是正在更新的第一次访问，然后向后计算日期以找到合适的出发时间，从时间 windows考虑在内。

但这一定是一个普遍的问题。有更好的解决方案吗？

Answer 1

如果访问的是第一个客户（所以if previousStandstill instanceof Vehicle）那么到达时间确实应该是max(readyTime, previousStandstillWhichIsVehicle.getDepotOpenTime() + drivingTime)。

其余部分与示例中的一样：当访问的到达时间发生变化时（因此它也是离开时间），侦听器遍历链的其余部分以相应地更新这些访问（另请参见文档中的图片） .

Answer 2

好的，所以我终于设法解决了它，尽管我仍然需要优化性能。

用半伪术语来说，这就是我在 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); 可以计算出从站点出发可以延迟多少分钟，以最大限度地减少每个客户的等待时间，但不会否决时间 windows。

Optaplanner：如何在站点等待当天晚些时候的匹配时间 window？

Optaplanner: How to wait at depot to match time window for visit later in the day?

optaplanner