使用Optaplanner解决VRPTWPD [英] Using Optaplanner to solve VRPTWPD

问题描述

我是optaplanner的新手，并希望将其用于解决取货和交货(VRPTWPD)的VRPTW问题.

I'm new to optaplanner, and am hoping to use it to solve the VRPTW problem with pickups and deliveries (VRPTWPD).

我首先以 VRPTW代码.我正在尝试添加它来解决我的问题.但是，我无法返回符合优先级/车辆约束的解决方案(提货必须在交付之前完成，并且都必须由同一辆车完成).

I started by taking the VRPTW code from the examples repo. I am trying to add to it to solve my problem. However, I'm unable to return a solution that honors the precedence/vehicle constraints (pickups must be done before deliveries, and both must be done by the same vehicle).

我一直在返回一个解决方案，其中硬分数是我希望获得的解决方案(即，我可以将所有违规行为加总到一个小样本问题中，然后看到硬分数与我为这些违规行为所分配的罚款相匹配) ).

I am consistently returning a solution where the hard score is what I would expect for such a solution (i.e. I can add up all the violations in a small sample problem and see that the hard score matches the penalties I assigned for these violations).

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

The first approach I tried was following the steps outlined by Geoffrey De Smet here - https://stackoverflow.com/a/19087210/351400

每个Customer都有一个变量customerType，该变量描述它是提货(PU)还是交货(DO).它还有一个名为parcelId的变量，该变量指示正在拾取或交付哪个包裹.

Each Customer has a variable customerType that describes whether it is a pickup (PU) or a delivery (DO). It also has a variable called parcelId that indicates which parcel is either being picked up or delivered.

我在名为parcelIdsOnboard的Customer中添加了一个阴影变量.这是一个HashSet，其中包含驾驶员访问给定Customer时驾驶员随身携带的所有parcelId.

I added a shadow variable to the Customer named parcelIdsOnboard. This is a HashSet that holds all the parcelIds that the driver has with him when he visits a given Customer.

我的保持更新parcelIdsOnboard的VariableListener看起来像这样:

My VariableListener that keeps parcelIdsOnboard updated looks like this:

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

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

I then added the following drool rule:

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辆车.

For my example problem I create a total of 6 Customer objects (3 PICKUPS and 3 DELIVERIES). My fleet size is 12 vehicles.

运行此命令时，我始终得到-3000的硬分，这与我看到的两辆车正在使用的输出相匹配.一辆车完成所有PICKUPS，一辆车完成所有交货.

When I run this I consistently get a hard score of -3000 which matches my output where I see two vehicles being used. One vehicle does all the PICKUPS and one vehicle does all the DELIVERIES.

我使用的第二种方法是给每个Customer引用其对应的Customer对象(例如，包裹1的PICKUP Customer引用了DELIVERY Customer对于包裹1，反之亦然).

The second approach I used was to give each Customer a reference to its counterpart Customer object (e.g. the PICKUP Customer for parcel 1 has a reference to the DELIVERY Customer for parcel 1 and vice versa).

然后我实施了以下规则，以强制将包裹置于同一车辆中(注意:没有完全实现优先约束).

I then implemented the following rule to enforce that the parcels be in the same vehicle (note: does not fully implement precedence constraint).

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

对于相同的样本问题，这始终给出-3000的分数，并且对上述问题给出相同的解决方案.

For the same sample problem this consistently gives a score of -3000 and an identical solution to the one above.

我尝试以FULL_ASSERT模式运行这两个规则.使用parcelIdsOnboard的规则不会触发任何异常.但是，规则"pudoInSameVehicle"确实会触发以下异常(在FAST_ASSERT模式下不会触发).

I've tried running both rules in FULL_ASSERT mode. The rule using parcelIdsOnboard does not trigger any exceptions. However, the rule "pudoInSameVehicle" does trigger the following exception (which is not triggered in FAST_ASSERT mode).

The corrupted scoreDirector has no ConstraintMatch(s) which are in excess.
The corrupted scoreDirector has 1 ConstraintMatch(s) which are missing:

我不确定为什么它会损坏，任何建议将不胜感激.

I'm not sure why this is corrupted, any suggestions would be much appreciated.

有趣的是，这两种方法都产生相同(不正确)的解决方案.我希望有人会对下一步尝试提出一些建议.谢谢！

It's interesting that both of these methodologies are producing the same (incorrect) solution. I'm hoping someone will have some suggestions on what to try next. Thanks!

更新:

深入研究以FULL_ASSERT模式触发的断言之后，我意识到问题出在PICKUP和DELIVERY Customer的依赖性质上.也就是说，如果您采取的行动消除了对DELIVERY Customer的硬性处罚，那么您还必须消除与PICKUP Customer相关的惩罚.为了使它们保持同步，我更新了VehicleUpdatingVariableListener和ArrivalTimeUpdatingVariableListener以触发两个Customer对象上的得分计算回调.这是更新后的updateVehicle方法，以触发刚刚移动的Customer和对应的Customer上的得分计算.

After diving into the asserts that were being triggered in FULL_ASSERT mode I realized that the problem was with the dependent nature of the PICKUP and DELIVERY Customers. That is, if you make a move that removes the hard penalty on a DELIVERY Customer you also have to remove the penalty associated with the PICKUP Customer. In order to keep these in sync I updated my VehicleUpdatingVariableListener and my ArrivalTimeUpdatingVariableListener to trigger score calculation callbacks on both Customer objects. Here's the updateVehicle method after updating it to trigger score calculation on both the Customer that was just moved and the counterpart 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).

This solved the score corruption issue I had with my second approach, and, on a small sample problem, produced a solution that satisfied all the hard constraints (i.e. the solution had a hard score of 0).

我接下来尝试运行一个更大的问题(〜380个客户)，但是解决方案返回的评分很差.我尝试搜索1分钟，5分钟和15分钟的解决方案.分数似乎随着运行时间线性增加.但是，在15分钟时，该解决方案仍然非常糟糕，以至于似乎需要至少运行一个小时才能生成可行的解决方案. 我需要最多在5-10分钟内运行.

I next tried to run a larger problem (~380 Customers), but the solutions are returning very poor hard scores. I tried searching for a solution for 1 min, 5 mins, and 15 mins. The score seems to improve linearly with runtime. But, at 15 minutes, the solution is still so bad that it seems like it would need to run for at least an hour to produce a viable solution. I need this to run in 5-10 minutes at the most.

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

I learned about Filter Selection. My understanding is that you can run a function to check whether the move you are about to make would result in breaking a built in hard constraint, and if it would, then this move is skipped.

这意味着您不必重新运行分数计算或探索您不会获得成果的分支.例如，在我的问题中，我不希望您永远不能将Customer移到Vehicle，除非将其对应对象分配给该车辆或根本没有分配车辆.

This means that you don't have to re-run score calculations or explore branches that you know will not be fruitful. For example, in my problem I don't want you to ever be able to move a Customer to a Vehicle unless its counterpart is assigned to that Vehicle or not assigned a Vehicle at all.

这是我实施检查的过滤器.它仅在ChangeMoves上运行，但是我怀疑我也需要这样做才能为SwapMoves实现类似的功能.

Here is the filter I implemented to check for that. It only runs for ChangeMoves, but I suspect I need this to implement a similar function for SwapMoves as well.

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

添加此过滤器会立即导致得分降低.这使我认为我没有正确实现该功能，尽管我不清楚为什么它不正确.

Adding this filter immediately led to worse scores. That makes me think I have implemented the function incorrectly, though it's not clear to me why it is incorrect.

更新2:

一位同事指出了我的PrecedenceFilterChangeMove问题.正确的版本如下.我还包括PrecedenceFilterSwapMove实现.在一起，这些使我能够找到解决问题的解决方案，在10分钟之内没有违反任何硬约束.我认为还有其他一些优化措施可以进一步减少这种情况.

A co-worker pointed out the problem with my PrecedenceFilterChangeMove. The correct version is below. I've also included PrecedenceFilterSwapMove implementation. Together, these have enabled me to find a solution to the problem where no hard constraints are violated in ~10 minutes. There are a couple of other optimizations I think I might be able to make to reduce this even further.

如果这些更改卓有成效，我将发布另一个更新.我仍然很乐意听到optaplanner社区中的某人关于我的方法以及他们是否认为有更好的方法来模拟此问题的方法！

I will post another update if those changes are fruitful. I'd still love to hear from someone in the optaplanner community about my approach and whether they think there are better ways to model this problem!

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

推荐答案

有混合的提货和发货这里的VRP实验代码有效.我们还没有一个开箱即用的例子，但是它是一个长期的路线图.

There's mixed pickup and delivery VRP experimental code here, which works. We don't have a polished out-of-the-box example yet, but we it's on long-term roadmap.

这篇关于使用Optaplanner解决VRPTWPD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！