How to limit route duration in Google Or-Tools?

Question

I m working on routes optimization problem, and I found myself in some deadlock. I m using or-tools as a solver with .Net core.

The problem is as follow: when I m dealing with time window constraint, it might happen that some waiting is needed in order to fit some location time window. And this is fine. Solver tends to use time window constrained location as first node. This is fine too. But this way we might want to put departure date of vehicle with some perfect delay. So when I m setting route duration limit to 8h, and we have 2h of waiting at start, we end with 6 hours of work as result and this is not optimal. I can not figure out how to inform solver that first node waiting time is increasing total duration.

here is docs link: https://developers.google.com/optimization/routing/vrp

// here is my time dimension

        _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);

// and this piece of code is setting up time window and duration constraints

        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;
        }
    }

I also tried to add separate dimension for duration limit constraint setting up horizon to target limit but causing the same issue.

The magic should happen in DoesNotExeedLimit method. Imho I should set startSeconds as a SlackVar, but this is causing accessing memory exception. Probably GC is somehow removing this vars.

Do U guys have any ideas? Sorry for long post, but problem is quite complicated :)

Answer 1

Alright! After a week of searching finally found solution posted here: shift length constraint in OR-TOOLS RL VRPTW problem?

thanks @ihadanny !

All I needed was use SetSpanUpperBoundForVehicle method on time dimension with StartCumulZero to false.