c# - 如何在 Google Or-Tools 中限制路线持续时间？

Question

我正在处理路由优化问题，但发现自己陷入了僵局。我正在使用 or-tools 作为 .Net 核心的求解器。

问题如下:当我处理时间窗口约束时，可能需要等待一些时间才能适应某个位置时间窗口。这很好。求解器倾向于使用时间窗约束位置作为第一个节点。这也很好。但是通过这种方式，我们可能希望将车辆的出发日期完全延迟。因此，当我将路线持续时间限制设置为 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;
        }
    }

我还尝试为持续时间限制约束添加单独的维度，将范围设置为目标限制，但导致了同样的问题。

魔术应该发生在 DoesNotExeedLimit 方法中。恕我直言，我应该将 startSeconds 设置为 SlackVar，但这会导致访问内存异常。可能 GC 以某种方式删除了这个变量。

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

Answer 1

好的!经过一周的搜索终于找到了这里发布的解决方案: shift length constraint in OR-TOOLS RL VRPTW problem?

谢谢@ihadanny!

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