在 Jsprit 中使用 HardActivityConstraint 强加顺序

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。如果问题非常小，则要删除的作业份额可能不够。这将在下一个版本中发生变化，您可以在该版本中使用开箱即用的算法，该算法定义了需要删除的作业的绝对最小值。暂时，修改算法配置.xml中的共享。