如何在Google或Tools中限制路由持续时间？

Question

我正在研究路由优化问题，我发现自己陷入了一些僵局。我正在使用或工具作为解算器。净核心。

问题如下：当我处理时间窗口约束时，可能需要等待一些时间来适应某个位置时间窗口。这很好。解算器倾向于使用时间窗口约束位置作为第一个节点。这也很好。但这样的话，我们可能想把车辆的出发日期推迟一些。因此，当我将路线持续时间限制设置为8小时，并且我们在开始时有2小时的等待时间，结果我们以6小时的工作时间结束，这不是最优的。我不知道如何通知解算器第一个节点的等待时间正在增加总持续时间。

这里是文档链接：https://developers.google.com/optimization/routing/vrp

//这是我的时间维度

        _routingModel.AddDimension(
            evaluator_index: _absoluteTimeCallbackIndex,
            slack_max: (long)TimeSpan.FromDays(1).TotalSeconds,
            capacity: (long)TimeSpan.FromDays(1).TotalSeconds,
            fix_start_cumul_to_zero: true,
            name: PlannerConstants.TIME_DIMENSION_NAME);

//这段代码设置了时间窗口和持续时间约束

        var timeDimension = _routingModel.GetDimensionOrDie(PlannerConstants.TIME_DIMENSION_NAME);

        for (int locationNodeIndex = 0; locationNodeIndex < _targets.Count; locationNodeIndex++)
        {
            var location = _targets[locationNodeIndex].Location;
            var index = _manager.NodeToIndex(locationNodeIndex);

            var timeWindowMatch = new TimeWindowMatcher(_departureDate, location.TimeSlots.ToList())
                .GetTimeWindowsWithGaps();

            var start = (long)timeWindowMatch.WideTimeRange.From.TotalSeconds;
            var end = (long)timeWindowMatch.WideTimeRange.To.TotalSeconds;

            timeDimension
                .CumulVar(index)
                .SetRange(start, end);

            timeWindowMatch.TimeGaps.ForEach(gap =>
            {
                timeDimension
                    .CumulVar(index)
                    .RemoveInterval((long)gap.From.TotalSeconds, (long)gap.To.TotalSeconds);
            });
        }


        for (int vehicleNodeIndex = 0; vehicleNodeIndex < _vehicles.Count; vehicleNodeIndex++)
        {
            _routingModel
                .solver()
                .Add(RelativeDuration.DoesNotExeedLimit(_settings.MaximumRouteDuration, _routingModel, vehicleNodeIndex, _vehicles[vehicleNodeIndex]));
        }

public class RelativeDuration
    {
        public static Constraint DoesNotExeedLimit(TimeSpan limit, RoutingModel routing, int vehicleIndex, RoutingVehicle vehicle)
        {
            var timeDimension = routing.GetDimensionOrDie(PlannerConstants.TIME_DIMENSION_NAME);

            var startSerconds = timeDimension.CumulVar(routing.Start(vehicleIndex));
            var endSeconds = timeDimension.CumulVar(routing.End(vehicleIndex));

            if (vehicle.Type == VehicleType.Virual)
                return endSeconds < (long) PlannerConstants.INFINITIVE_WORKDAY_SECONDS;

            return endSeconds <= (long) limit.TotalSeconds + startSerconds;
        }
    }

我还尝试为工期限制添加单独的维度，设置地平线到目标的限制，但导致了相同的问题。

魔法应该发生在DoesnoteedLimit方法中。Imho我应该将startSeconds设置为SlackVar，但这会导致访问内存异常。可能GC正在以某种方式删除这些变量。

你们有什么想法吗？很抱歉发了这么长的帖子，但问题很复杂：）

Answer 1

好吧经过一周的搜索，终于在这里找到了解决方案：OR-TOOLS RL VRPTW问题中的移位长度约束？

谢谢@ihadanny！

我所需要的只是在时间维度上使用SetSpanUpperBoundForVehicle方法，将StartCumulZero设置为false。