用Optaplanner求解VRPTWPD

Question

我是新手，我希望用它来解决皮卡和送货的VRPTW问题(VRPTWPD)。

我首先从回购的例子中学习VRPTW码。我正在努力增加它来解决我的问题。但是，我无法返回符合优先级/车辆约束的解决方案(必须在交付之前完成拾取，并且必须由同一辆车完成)。

我一直在返回一个解决方案，其中硬分数是我对这样一个解决方案的期望(也就是说，我可以在一个小样本问题中将所有违规行为加在一起，并确保硬分数与我为这些违规行为规定的处罚相匹配)。

我尝试过的第一方法遵循Geoffrey这里- https://stackoverflow.com/a/19087210/351400概述的步骤。

每个Customer都有一个变量customerType，描述它是皮卡(PU)还是传递(DO)。它还有一个名为parcelId的变量，它指示正在捡起或交付哪个包裹。

我向Customer添加了一个名为parcelIdsOnboard的影子变量。这是一个HashSet，它保存了驱动程序在访问给定Customer时所携带的所有parcelIds。

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

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

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

对于我的示例问题，我总共创建了6个Customer对象(3个拾取和3个交付)。我的车队是12辆车。

当我运行这个，我一直得到一个困难的分数-3000，这与我的输出，我看到两辆车正在使用。一辆车负责所有的接送，一辆车负责所有的运送。

我使用的第二种方法是给每个Customer一个对应的Customer对象的引用(例如，第1包的拾取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的规则不会触发任何异常。但是，规则"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模式下触发的断言之后，我意识到问题在于皮卡和送货Customer的依赖性质。也就是说，如果您采取了移除交付Customer上的硬罚的动作，您还必须取消与拾取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，除非它的对应方被分配到该车辆，或者根本没有分配车辆。

下面是我实现的用于检查这一点的筛选器。它只运行于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;
}

Answer 1

这里有VRP混合收货实验代码，它可以工作。我们还没有现成的例子，但我们还在长远的路线图上。