使用Optaplanner解决VRPTWPD

Question

我是optaplanner的新手,我希望用它来解决拾取和交付的VRPTW问题(VRPTWPD).

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

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

我尝试的第一种方法是遵循Geoffrey De Smet在此处概述的步骤 - /sf/answers/1336104731/

每个Customer都有一个变量customerType,描述它是一个皮卡(PU)还是一个交付(DO).它还有一个名为变量的变量parcelId,用于指示要拾取或交付的包裹.

我在Customer命名中添加了一个阴影变量parcelIdsOnboard.这是一个HashSet,它包含了驾驶员在访问给定时所拥有的所有parcelId Customer.

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个PICKUPS和3个DELIVERIES).我的车队规模是12辆.

当我运行这个时,我一直得到-3000的硬分,这与我的输出匹配,我看到两辆车正在使用.一辆车完成所有PICKUPS,一辆车完成所有交付.

我使用的第二种方法是给每个Customer对应Customer物体提供参考(例如Customer,地块1 的PICKUP 对地块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模式下触发的断言之后,我意识到问题在于PICKUP和DELIVERY Customer的依赖性.也就是说,如果您做出移动以消除交付上的硬罚款,Customer您还必须删除与PICKUP相关的惩罚Customer.为了保持这些同步,我更新了my VehicleUpdatingVariableListener和my 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到a,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 实验代码，可以运行。我们还没有一个完美的开箱即用的例子，但我们已经在长期路线图上。