OptaPlanner 中具有优先级和车辆故障的 CVRPTW

Question

我有一个问题，我真的很难处理它。我想使用 OptaPlanner 来解决具有优先顺序和车辆故障的 CVRPTW。到目前为止我所做的是获取标准示例并在 GUI 中解决它，然后保存结果。比起我修改 python 中的 .xml 文件来手动删除车辆并释放客户。我知道正确的方法是制作 ProblemFact，但我不知道如何做。我看到了一些答案，但我需要更多帮助或如何完成的示例。

第二件事是，我如何为优先级建模。所以顾客 'A' 必须在顾客 'B' 之前来。（唯一的例子是在另一个名为 Project Job Scheduling 的问题中）

非常感谢！

Answer 1

A题超级简单。

B题不是这样。

至于 A，您需要位于可以访问对象图的位置（例如，在反序列化解决方案之后）。然后，您获得该车辆的第一个客户，将其 previousStandstill 设置为 null:

 Customer nextCustomer = vehicle.getNextCustomer();
 if (nextCustomer != null){
     scoreDirector.beforeVariableChanged(nextCustomer, "previousStandstill");
     nextCustomer.setPreviousStandstill(null);
     scoreDirector.afterVariableChanged(nextCustomer, "previousStandstill");
     scoreDirector.triggerVariableListeners();
 }

我认为问题 B 值得更多关注。这样做的默认方法是实现一个 OrderListener，它会在客户的 previousStandstill 上触发，每当任何客户的 previousStandstill 发生变化时，侦听器都会更新车辆链中的所有客户：

@CustomShadowVariable(variableListenerClass = OrderListener.class,
        sources = {@PlanningVariableReference(variableName = "previousStandstill")})
public Integer getPositionInVehicleChain() {
    return position;
}

然后在 OrderListener 的 afterVariableChanged 方法中有这样的东西：

while (nextCustomer != null) {
        if (position == nextTe.getPositionInVehicleChain()) break;
        scoreDirector.beforeVariableChanged(nextCustomer, "position");
        nextCustomer.setPositionInStapelabschnitt(pos);
        scoreDirector.afterVariableChanged(nextCustomer, "position");
        pos++;
        nextCustomer = nextCustomer.getNextCustomer();  
    }

然后在 Customer class 中实现 isBeforeCustomer(Customer otherCustomer)，比较两个 position。

然而，这肯定不是最优雅的方法，因为它的时间复杂度是O(n)，其中n是规划实体的总数。 nice 这样做的方法是对每辆车的客户实施所谓的订单维护数据结构。此数据结构支持操作

Insert (x, y)：这是在现有链中插入一个新客户
删除 (x)：这是删除现有链中的客户，请参阅问题 A。
顺序 (x, y)：确定 x 是否在链顺序中先于 y - 这就是您所追求的。

最先进的算法（参见 "Bender M.A., Cole R., Demaine E.D., Farach-Colton M., Zito J. (2002) Two Simplified Algorithms for Maintaining Order in a List. In: Möhring R., Raman R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg"）支持 O(1) 分摊 insertion/deletion 时间和 O(1) 最坏情况查询时间，比上面提出的系统（但还有很多工作）。如果您对实现感兴趣，请查看 transitivity utils。如果这样的数据结构作为开箱即用的影子变量包含在 optaplanner 中，我会非常感兴趣——一个实体是否在链中的另一个实体之前的问题无处不在。

OptaPlanner 中具有优先级和车辆故障的 CVRPTW

CVRPTW with Precedences amd vehicle failure in OptaPlanner

java

optimization

traveling-salesman

optaplanner