我是OptaPlanner的新手，希望使用它来解决具有取货和配送（VRPTWPD）的VRPTW问题。
我从示例存储库中获取了VRPTW代码。 我正在尝试添加内容以解决我的问题。 但是，我无法返回符合先决条件/车辆约束的解决方案（必须在交付之前完成接货，并且两者都必须由同一辆车完成）。
我始终返回一个解决方案，其中硬分数与我预期的解决方案相同（即，我可以将小样本问题中的所有违规行为加起来，看到硬分数与我为这些违规行为分配的惩罚相匹配）。
我尝试的第一种方法是按照Geoffrey De Smet在此处概述的步骤进行操作 - https://dev59.com/kHfZa4cB1Zd3GeqPRGZJ#19087210
每个Customer都有一个变量customerType，用于描述它是取件（PU）还是送货（DO）。它还有一个名为parcelId的变量，指示正在取件或交付的包裹。我在
Customer中添加了一个名为parcelIdsOnboard的阴影变量。这是一个HashSet，保存司机在访问给定Customer时所带的所有包裹ID。我的
VariableListener会更新parcelIdsOnboard，代码如下：public void afterEntityAdded(ScoreDirector scoreDirector, Customer customer) {
if (customer instanceof TimeWindowedCustomer) {
updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer);
}
}
public void afterVariableChanged(ScoreDirector scoreDirector, Customer customer) {
if (customer instanceof TimeWindowedCustomer) {
updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer);
}
}
protected void updateParcelsOnboard(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) {
Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
Set<Integer> parcelIdsOnboard = (previousStandstill instanceof TimeWindowedCustomer)
? new HashSet<Integer>(((TimeWindowedCustomer) previousStandstill).getParcelIdsOnboard()) : new HashSet<Integer>();
TimeWindowedCustomer shadowCustomer = sourceCustomer;
while (shadowCustomer != null) {
updateParcelIdsOnboard(parcelIdsOnboard, shadowCustomer);
scoreDirector.beforeVariableChanged(shadowCustomer, "parcelIdsOnboard");
shadowCustomer.setParcelIdsOnboard(parcelIdsOnboard);
scoreDirector.afterVariableChanged(shadowCustomer, "parcelIdsOnboard");
shadowCustomer = shadowCustomer.getNextCustomer();
}
}
private void updateParcelIdsOnboard(Set<Integer> parcelIdsOnboard, TimeWindowedCustomer customer) {
if (customer.getCustomerType() == Customer.PICKUP) {
parcelIdsOnboard.add(customer.getParcelId());
} else if (customer.getCustomerType() == Customer.DELIVERY) {
parcelIdsOnboard.remove(customer.getParcelId());
} else {
// TODO: throw an assertion
}
}
我随后添加了以下的 drool 规则：
rule "pickupBeforeDropoff"
when
TimeWindowedCustomer((customerType == Customer.DELIVERY) && !(parcelIdsOnboard.contains(parcelId)));
then
System.out.println("precedence violated");
scoreHolder.addHardConstraintMatch(kcontext, -1000);
end
对于我的示例问题，我创建了总共6个
Customer对象（3个PICKUPS和3个DELIVERIES）。我的车队规模为12辆车。当我运行此代码时，我始终得到一个硬得分为-3000，与我的输出相匹配，其中我看到两辆车被使用。一辆车负责所有的PICKUPS，另一辆车负责所有的DELIVERIES。
我使用的第二种方法是给每个
Customer对象引用其对应的Customer对象（例如，包裹1的PICKUP Customer引用包裹1的DELIVERY Customer，反之亦然）。然后，我实现了以下规则来强制要求包裹在同一辆车上（注意：没有完全实现先决约束）。
rule "pudoInSameVehicle"
when
TimeWindowedCustomer(vehicle != null && counterpartCustomer.getVehicle() != null && (vehicle != counterpartCustomer.getVehicle()));
then
scoreHolder.addHardConstraintMatch(kcontext, -1000);
end
针对相同的示例问题，这个方法一直给出-3000的分数，并且与上面的解决方案完全相同。
我尝试在FULL_ASSERT模式下运行两个规则。使用parcelIdsOnboard的规则不会触发任何异常。然而，规则“pudoInSameVehicle”会触发以下异常（在FAST_ASSERT模式下不会触发）。
The corrupted scoreDirector has no ConstraintMatch(s) which are in excess.
The corrupted scoreDirector has 1 ConstraintMatch(s) which are missing:
我不确定为什么会出现损坏，希望能得到一些建议。
有趣的是，这两种方法都产生了相同（不正确）的解决方案。我希望有人能提出下一步该尝试什么的建议。谢谢！
更新：
在深入研究FULL_ASSERT模式下触发的断言之后，我意识到问题在于PICKUP和DELIVERY Customer的依赖性。也就是说，如果您进行移动以消除DELIVERY Customer上的硬惩罚，则还必须删除与PICKUP Customer相关联的惩罚。为了保持这些同步，我更新了我的VehicleUpdatingVariableListener和ArrivalTimeUpdatingVariableListener，在两个Customer对象上触发评分计算回调。这是更新后的updateVehicle方法，在移动刚刚移动的和对应的Customer时触发评分计算。
protected void updateVehicle(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) {
Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
Integer departureTime = (previousStandstill instanceof TimeWindowedCustomer)
? ((TimeWindowedCustomer) previousStandstill).getDepartureTime() : null;
TimeWindowedCustomer shadowCustomer = sourceCustomer;
Integer arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
while (shadowCustomer != null && ObjectUtils.notEqual(shadowCustomer.getArrivalTime(), arrivalTime)) {
scoreDirector.beforeVariableChanged(shadowCustomer, "arrivalTime");
scoreDirector.beforeVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime");
shadowCustomer.setArrivalTime(arrivalTime);
scoreDirector.afterVariableChanged(shadowCustomer, "arrivalTime");
scoreDirector.afterVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime");
departureTime = shadowCustomer.getDepartureTime();
shadowCustomer = shadowCustomer.getNextCustomer();
arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
}
}
这解决了我第二种方法中遇到的分数损坏问题，并且在一个小样本问题上，产生了满足所有硬约束条件的解决方案（即解决方案的硬分数为0）。
接下来，我尝试运行一个更大的问题（~380个客户），但是解决方案的硬分数非常低。我尝试搜索1分钟、5分钟和15分钟的解决方案，得分似乎随运行时间线性提高。但是，在15分钟内，解决方案仍然很差，看起来需要至少运行一个小时才能产生可行的解决方案。我需要最多在5-10分钟内运行。
我了解了Filter Selection。我的理解是，您可以运行一个函数来检查您即将进行的移动是否会导致打破内置的硬约束条件，如果会，则跳过此移动。
这意味着您无需重新运行得分计算或探索明显无效的分支。例如，在我的问题中，我不希望您能够将
客户移动到车辆，除非它的对应物已分配给该车辆或未分配给任何车辆。
以下是我实现的过滤器来检查此内容。它仅适用于ChangeMoves，但我怀疑我也需要实现类似的SwapMoves功能。
public class PrecedenceFilterChangeMove implements SelectionFilter<ChangeMove> {
@Override
public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) {
TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity();
if (customer.getCustomerType() == Customer.DELIVERY) {
if (customer.getCounterpartCustomer().getVehicle() == null) {
return true;
}
return customer.getVehicle() == customer.getCounterpartCustomer().getVehicle();
}
return true;
}
}
添加这个过滤器立即导致分数变差。这让我觉得我可能实现了函数不正确，尽管我不清楚为什么不正确。
更新2：
一位同事指出了我的PrecedenceFilterChangeMove的问题。正确版本如下。我还包括了PrecedenceFilterSwapMove的实现。这两者一起使我能够在约10分钟内找到一个没有违反任何硬性约束的解决方案。我认为我可能能做出其他优化，以进一步减少时间。
如果这些更改有成效，我将发布另一个更新。我仍然很想听听optaplanner社区中有关我的方法以及是否有更好的建模方法的意见！
PrecedenceFilterChangeMove
@Override
public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) {
TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity();
if (customer.getCustomerType() == Customer.DELIVERY) {
if (customer.getCounterpartCustomer().getVehicle() == null) {
return true;
}
return selection.getToPlanningValue() == customer.getCounterpartCustomer().getVehicle();
}
return true;
}
PrecedenceFilterSwapMove
@Override
public boolean accept(ScoreDirector scoreDirector, SwapMove selection) {
TimeWindowedCustomer leftCustomer = (TimeWindowedCustomer)selection.getLeftEntity();
TimeWindowedCustomer rightCustomer = (TimeWindowedCustomer)selection.getRightEntity();
if (rightCustomer.getCustomerType() == Customer.DELIVERY || leftCustomer.getCustomerType() == Customer.DELIVERY) {
return rightCustomer.getVehicle() == leftCustomer.getCounterpartCustomer().getVehicle() ||
leftCustomer.getVehicle() == rightCustomer.getCounterpartCustomer().getVehicle();
}
return true;
}