使用Optaplanner解决VRPTWPD

我是optaplanner的新手，我希望用它来解决拾取和交付的VRPTW问题（VRPTWPD）。

我首先从示例repo中获取VRPTW代码 。 我想添加它来解决我的问题。 但是，我无法返回一个符合优先级/车辆限制的解决方案（必须在交付之前完成拾取，并且两者都必须由同一车辆完成）。

我一直在返回一个解决方案，其中硬分数是我期望的这样一个解决方案（即我可以在一个小样本问题中加上所有违规，并看到硬分数与我为这些违规分配的处罚相匹配）。

我尝试的第一种方法是遵循Geoffrey De Smet在此处概述的步骤 – https://stackoverflow.com/a/19087210/351400

每个Customer都有一个变量customerType ，描述它是皮卡（PU）还是交付（DO）。 它还有一个名为parcelId的变量，用于指示正​​在拾取或交付的包裹。

我向名为parcelIdsOnboard的Customer添加了一个shadow变量。 这是一个HashSet，它包含驱动程序在访问给定Customer时所拥有的所有parcelId。

保持parcelIdsOnboard更新的我的VariableListener如下所示：

 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 parcelIdsOnboard = (previousStandstill instanceof TimeWindowedCustomer) ? new HashSet(((TimeWindowedCustomer) previousStandstill).getParcelIdsOnboard()) : new HashSet(); 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 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 } } 

然后我添加了以下流口水规则：

 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，一辆车完成所有交付。

我使用的第二种方法是给每个Customer一个对应Customer对象的参考（例如，包裹1的PICKUP Customer对包裹1的交付Customer有参考，反之亦然）。

然后我实施了以下规则来强制包裹在同一车辆中（注意：没有完全实现优先约束）。

 rule "pudoInSameVehicle" when TimeWindowedCustomer(vehicle != null && counterpartCustomer.getVehicle() != null && (vehicle != counterpartCustomer.getVehicle())); then scoreHolder.addHardConstraintMatch(kcontext, -1000); end 

对于相同的样本问题，这始终给出-3000的分数和与上述分数相同的解决方案。

我试过在FULL_ASSERT模式下运行这两个规则。 使用parcelIdsOnboard的规则不会触发任何exception。 但是，规则"pudoInSameVehicle"会触发以下exception（在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 和对应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分钟。

我了解了滤波器选择 。 我的理解是你可以运行一个函数来检查你要进行的移动是否会导致破坏内置的硬约束，如果可以，则跳过此移动。

这意味着您不必重新运行分数计算或探索您知道不会富有成效的分支。 例如，在我的问题中，我不希望您能够将Customer移动到Vehicle除非其对应方被分配给该车辆或根本没有分配车辆。

这是我为检查它而实现的filter。 它只适用于ChangeMoves，但我怀疑我需要这个来为SwapMoves实现类似的function。

 public class PrecedenceFilterChangeMove implements SelectionFilter { @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; } } 

添加此filter会立即导致分数下降。 这让我觉得我已经错误地实现了这个function，虽然我不清楚为什么它不正确。

更新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; }