用Optaplanner求解VRPTWPD

Question

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

我从repo示例中的VRPTW代码开始。我正在努力增加它来解决我的问题。然而，我无法返回一个遵守优先/车辆约束的解决方案（必须在交付之前完成取货，并且两者必须由同一车辆完成）。

我总是返回一个解决方案，其中硬得分是我对这种解决方案的期望（即，我可以将一个小样本问题中的所有违规行为相加，并看到硬得分与我为这些违规行为分配的惩罚匹配）。

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

每个customer都有一个变量customertype来描述它是取货(PU)还是送货(DO)。它还有一个名为parcelid的变量，它指示正在取走或递送哪个包裹。

我向customer添加了一个名为parcelidsonboard的影子变量。这是一个哈希集，它保存了驱动程序访问给定的客户时随身携带的所有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<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

我使用的第二种方法是给每个客户一个对其对应的客户对象的引用（例如，包裹1的PICKUP客户有对包裹1的DELIVERY客户的引用，反之亦然）。

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

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模式下触发的断言之后，我意识到问题出在取货和送货客户的依赖性质上。也就是说，如果您移除了对送货客户的硬性惩罚，您还必须移除与提货客户相关联的惩罚。为了保持这些同步，我更新了我的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);
    }
}

我接下来尝试运行一个更大的问题（约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：

优先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;
}

优先FilterSwapMove

@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实验代码，它起作用了。我们还没有一个完善的现成的例子，但我们是在长期的路线图。