Or-tools: VRPTWs - Solver fails if timeWindows is too high when setting range in dimension

[Platou]

OR Tools Version

Google.OrTools v7.1.6720 (.Net)

Snippet

from https://developers.google.com/optimization/routing/vrptw#program

RoutingDimension timeDimension = routing.GetMutableDimension("Time");
  // Add time window constraints for each location except depot.
  for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) {
    long index = manager.NodeToIndex(i);
    timeDimension.CumulVar(index).SetRange(
        data.TimeWindows[i, 0],
        data.TimeWindows[i, 1]);
  }

Expected Behavior

The range should be set for value in Int64 since SetRange() takes two long param.

Actual Behavior

System.ApplicationException: fail at timeDimension.CumulVar(index).SetRange() when data.TimeWindows[i, 0] is equal to 25396 from my testing and doesn't crash when equal to 15396.

Additionnal Informations

My duration matrix (distance matrix) is in second so I suppose the TimeWidows should be in second to.

// fix_start_cumul_to_zero = false
// slack_max = 20000

long[,] TimeMatrix = {
  {0, 3448, 5211, 5211},
  {3457, 0, 1763, 1763},
  {5240, 1783, 0, 0},
  {5240, 1783, 0, 0}
};

long[,] TimeWindows = {
  {0, 0},
  {0, 0},
  {4396, 6396},
  {14396, 16396} // Works
};

long[,] TimeWindows = {
  {0, 0},
  {0, 0},
  {4396, 6396},
  {24396, 26396} // Crashes
};

In this case, I have 2 different vehicles and 2 destinations that are in fact the same. I need the 2 vehicles to visit the destination at 2 different time in the day. I'm trying to do so by delaying the second visit by the second vehicle with a higher time window.

[jmarca]

Without posting all of your code it is difficult to check the "usual suspects" that cause my code to crash in similar ways.

My guess is that there is a disconnect between the dimension and the time windows.

Can provide information on how you set up the underlying dimensions that use these time windows? If I recall correctly, the horizon of the solver must be greater than the max time window in the nodes.

For example, something like:

     # Add a dimension for time and a limit on the total time_horizon
    routing.AddDimension(
        tot_time_fn,    # total time function callback
        time_slack,     # allowed time slack at a node
        time_horizon, # the maximum value for time
        True,              # set time to zero at start (or false if that doesn't make sense)
        'Time')

In one project there were some requests that were outside of the vehicle operating hours, (I was using vehicle operating hours to set the start and end time of the time dimension) and so the model crashed, as it could not serve the demands outside of the operating hours. Once I made sure the two synced up, all was good.

So perhaps in the failing case, you have not set the maximum allowed value of the time dimension to "26396"?

[Platou]

the horizon of the solver must be greater than the max time window in the nodes.

@jmarca Indeed my horizon was less than the max time window in the node. I increased it and it solved my issue.

[jmarca]

Cool! Glad that helped.

James

On Jul 16, 2019, at 06:13, Platou [e-mail] wrote:

Closed #1419.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.

[JacobenVosloo]

@jmarca
I had the same problem in my setup but fixing it by setting the 'time_horizon' to the max of the time windows has me confused.

I thought that parameter is for setting the vehicle capacities as per the guides on OR-Tools
https://developers.google.com/optimization/routing/dimensions

routing.AddDimension( callback_index, slack_max, capacity, fix_start_cumul_to_zero, dimension_name)

where
capacity: Maximum for the total quantity accumulated along each route. Use capacity to create constraints like those in the CVRP. If your problem doesn't have such a constraint, you can set capacity to a value that is sufficiently large to impose no restrictions on the routes—for example, the sum of all entries of the matrix or array used to define the callback.

I see you refer to this parameter as time_horizon

My understanding was that if a vehicle is only allowed to travel 8 hours a day and a location needs to be visit 10 hours from now you can set the capacity to 8 hours and then set the time window start to 10 hours, but this gives the exception as described above.

[jmarca]

Not sure if this is a good explanation, AND I haven't been using OR
Tools lately so I'm rusty, but... A dimension is an accumulator. Just
because you call it time doesn't mean the solver understands that...it
just sees a value that is greater than or equal to zero. So when you
create the dimension, the "capacity" is really the maximum value that
you are going to allow for that dimension.

In your example, if you want to visit a location 10 hours from now,
then the maximum value of the accumulator in that dimension must be at
least 10. If it is 8, the solver will fail.

If you are willing to play games with time, then you can make it
work...like starting time with an offset or something. But if the
value of the dimension inside the solver exceeds the capacity, then it
will fail.

The solver also won't magically drop appointments that are impossible.
If you set the time dimension based on vehicle operating hours (say
from noon to 8pm, so capacity is 20hours and vehicle cannot leave
depot before 12hours), and you start your clock at midnight (0 hours),
and all the appointments are between 12 hours (noon) and 20 hours
(8pm), then things will probably work out (as long as you can get back
to depot before the maximum time). But if you have appointments
outside of the range (say 21 hours), then the solver will fail. You
have to prune those "impossible" nodes by hand prior to running the
solver.

On Tue, Jun 16, 2020 at 05:35:46AM +0000, Jaco-Ben Vosloo wrote:

@jmarca
I had the same problem in my setup but fixing it by setting the 'time_horizon' to the max of the time windows has me confused.

I thought that parameter is for setting the vehicle capacities as per the guides on OR-Tools
https://developers.google.com/optimization/routing/dimensions

routing.AddDimension( callback_index, slack_max, capacity, fix_start_cumul_to_zero, dimension_name)

where
capacity: Maximum for the total quantity accumulated along each route. Use capacity to create constraints like those in the CVRP. If your problem doesn't have such a constraint, you can set capacity to a value that is sufficiently large to impose no restrictions on the routes—for example, the sum of all entries of the matrix or array used to define the callback.

I see you refer to this parameter as time_horizon

My understanding was that if a vehicle is only allowed to travel 8 hours a day and a location needs to be visit 10 hours from now you can set the capacity to 8 hours and then set the time window start to 10 hours, but this gives the exception as described above.

--
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub:
https://github.com/google/or-tools/issues/1419#issuecomment-644540348

--

James E. Marca
Activimetrics LLC