2

在重新解决以前解决的问题的场景中（当然，使用一些新数据），通常不可能重新分配车辆的第一个任务。驱动程序已经在路上，任何新的解决方案都必须考虑到：

  • 工作必须是他的（不能分配给另一辆车）
  • 最初分配给他的活动在未来的解决方案中必须保持不变

为简单起见，我使用的是单个车辆场景，并且只尝试强加第二个项目符号（即确保某个活动将成为解决方案中的第一个）。

这就是我定义约束的方式：

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 辆车）。

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

谢谢扎克

4

1 回答 1

0

首先，您可以使用初始路线确保从一开始就需要将某些工作分配给特定车辆（参见示例）。

其次，为了确保在开始和您的初始工作（位置）之间不会插入任何活动（例如，您的示例中的“C1”），您需要按照您定义 HardActConstraint 的方式禁止它，只需修改它以便 newAct 永远不会介于 prevAct=Start 和 nextAct=act(C1) 之间。

第三，关于您的更新，请记住算法的本质是破坏部分解决方案（删除一些作业）并再次重新创建解决方案（插入未分配的作业）。目前，schrimpf 算法破坏了相对于工作总数的一些工作，即 noJobs = 0.5 * totalNoJobs 用于随机破坏和 0.3 * totalNoJobs 用于径向破坏。如果您的问题非常小，则要删除的工作份额可能不够。这将在下一个版本中改变，您可以使用开箱即用的算法来定义需要删除的作业的绝对最小值。暂时，修改您的 algorithmConfig.xml 中的共享。

于 2015-03-10T08:31:55.833 回答