Optaplanner:如何在仓库等待匹配当天晚些时候访问的时间窗口?

Question

我已经遵循了optaplanners源代码树中CVRPTW的示例，它工作得很好。 :)

但是我有一个与我挣扎的用例有关的事情。

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

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

在访问到达时间，我已经注册了一个侦听器以更新到达时间。

@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;
}
}
}

我在想，在更新到达时间时，我以某种方式需要检测是否是第一次访问正在更新，然后向后计算一天以找到合适的出发时间，同时考虑到时间窗口中的所有准备时间。

但这必须是一个普遍问题。有没有更好的解决方案？

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);可以计算出从仓库出发可以延迟多少分钟，以最大限度地减少每个客户的等待时间，但又不会推翻时间窗口。