使用Optaplanner解决VRPTWPD

问：

我是 optaplanner 的新手，希望用它来解决提货和送货 （VRPTWPD） 的 VRPTW 问题。

我首先从示例存储库中获取 VRPTW 代码。我正在尝试添加它以解决我的问题。但是，我无法返回符合优先级/车辆限制的解决方案（提货必须在交付前完成，并且两者都必须由同一辆车完成）。

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

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

每个变量都有一个变量，用于描述它是取件 （PU） 还是交货 （DO）。它还有一个变量，用于指示正在取货或交付哪个包裹。CustomercustomerTypeparcelId

我在命名的 .这是一个 HashSet，它保存了驱动程序在访问给定时随身携带的所有 parcelId。CustomerparcelIdsOnboardCustomer

我的保持更新看起来像这样：VariableListenerparcelIdsOnboard

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

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

rule "pickupBeforeDropoff"
    when
        TimeWindowedCustomer((customerType == Customer.DELIVERY) && !(parcelIdsOnboard.contains(parcelId)));
    then
        System.out.println("precedence violated");
        scoreHolder.addHardConstraintMatch(kcontext, -1000);
end

对于我的示例问题，我总共创建了 6 个对象（3 个 PICKUPS 和 3 个 DELIVERIES）。我的车队规模是 12 辆车。Customer

当我运行它时，我始终得到 -3000 的硬分数，这与我看到使用两辆车的输出相匹配。一辆车负责所有的皮卡，一辆车负责所有的送货。

我使用的第二种方法是为每个对象提供对其对应对象的引用（例如，包裹 1 的 PICKUP 引用了包裹 1 的 DELIVERY，反之亦然）。CustomerCustomerCustomerCustomer

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

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

对于相同的示例问题，这始终给出 -3000 的分数，并且解决方案与上述问题相同。

我尝试在模式下运行这两个规则。使用的规则不会触发任何异常。但是，该规则会触发以下异常（在模式下不会触发）。FULL_ASSERTparcelIdsOnboard"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 的依赖性上。也就是说，如果您采取的措施消除了对 DELIVERY 的硬性处罚，您还必须取消与 PICKUP 相关的处罚。为了保持这些同步，我更新了我的和我的，以在两个对象上触发分数计算回调。这是更新它后的方法，以在刚刚移动的和对应物上触发分数计算。CustomerCustomerCustomerVehicleUpdatingVariableListenerArrivalTimeUpdatingVariableListenerCustomerupdateVehicleCustomerCustomer

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 分钟内运行它。

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

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

这是我为检查这一点而实施的过滤器。它只为 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 社区中的某个人关于我的方法，以及他们是否认为有更好的方法来模拟这个问题！

优先级FilterChangeMove

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

优先级筛选器交换移动

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