用HardActivityConstraint在Jsprit中强制命令

Question

在重新解决以前解决的问题的场景中(当然，有一些新的数据)，通常不可能在给出车辆的第一次任务时重新分配。司机已经在路上了，任何新的解决办法都必须考虑到：

• 这项工作必须是他的(不能分配给另一辆车)
• 作为第一位分配给他的活动，必须在未来的解决方案中保持不变。

为了简单起见，我使用的是一个单一的车辆场景，并且只尝试强制执行第二个项目(即确保某个特定的活动将是解决方案中的第一个)。

我是这样定义约束的：

new HardActivityConstraint()
{
    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct,
                                       double prevActDepTime)
    {
        String locationId = newAct.getLocation().getId();

        //  we want to make sure that any solution will have "C1" as its first activity
        boolean activityShouldBeFirst = locationId.equals("C1");

        boolean attemptingToInsertFirst = (prevAct instanceof Start);

        if (activityShouldBeFirst && !attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED_BREAK;

        if (!activityShouldBeFirst && attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED;

        return ConstraintsStatus.FULFILLED;
    }
}

我就是这样构建算法的：

VehicleRoutingAlgorithmBuilder vraBuilder;
vraBuilder = new VehicleRoutingAlgorithmBuilder(vrpProblem, "schrimpf.xml"); 
vraBuilder.addCoreConstraints();
vraBuilder.addDefaultCostCalculators();

StateManager stateManager = new StateManager(vrpProblem);
ConstraintManager constraintManager = new ConstraintManager(vrpProblem, stateManager);
constraintManager.addConstraint(new HardActivityConstraint() { ... }, Priority.HIGH);
vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);

VehicleRoutingAlgorithm algorithm = vraBuilder.build();

结果不是很好。我只得到一个任务分配的解决方案(一个具有所需的活动)。在调试中，很明显，作业插入迭代考虑了许多可行的选项，这些选项似乎完全解决了问题，但从根本上说，算法返回的最佳解决方案不包括其他作业。

更新：更令人惊讶的是，当我在5辆以上车辆的场景中使用约束时，它工作得很好(最糟糕的结果是1辆车)。

如果需要的话，我很乐意附上更多的信息。

谢谢扎克

Answer 1

首先，您可以使用初始路径来确保从一开始就需要将某些任务分配给特定的车辆(请参阅示例)。

第二，确保在开始和初始工作(地点)之间不会插入任何活动。"C1“(在您的示例中)，您需要按照定义HardActConstraint的方式禁止它，只需修改它，使newAct永远不会介于prevAct=Start和nextAct=act(C1)之间。

第三，关于您的更新，请记住，算法的本质是破坏解决方案的一部分(删除多个作业)并再次重新创建解决方案(插入未分配的作业)。目前，schrimpf算法相对于总作业数破坏了许多作业，即随机破产的noJobs = 0.5 * totalNoJobs和径向破产的0.3 * totalNoJobs。如果你的问题很小，那么要删除的工作的比例可能还不够。随着下一个版本的发布，这种情况将发生变化，您可以使用一个开箱即用的算法，该算法定义了需要删除的作业的绝对最小值。暂时，修改您的algorithmConfig.xml中的份额。