I have an implementation that is supposed to set multiple time windows for a shipment:
def _set_allowed_time_window(time_dimension, index, time_windows: list):
""" Sets the appropriate time windows for a node. """
# ortools lacks a function to set a list of time windows
# workaround is to set the min and max of a list of sorted time windows as the allowed range
# and then to restrict the times in between the allowed time windows
# see https://github.com/google/or-tools/issues/456 and
# https://groups.google.com/forum/#!topic/or-tools-discuss/MBq1TcqSQTI
earliest_start = int(time_windows[0][0])
latest_end = int(time_windows[len(time_windows)-1][1])
time_dimension.CumulVar(index).SetRange(earliest_start, latest_end)
for tw_index, time_window in enumerate(time_windows):
if tw_index == len(time_windows)-1:
break
time_window_end = int(time_window[1])
next_time_window_start = int(time_windows[tw_index+1][0])
time_dimension.CumulVar(index).RemoveInterval(time_window_end, next_time_window_start)
There seems to be nothing wrong logically, yet or-tools is unable to return a solution unless I remove the line time_dimension.CumulVar(index).RemoveInterval(time_window_end, next_time_window_start). Any ideas what am I doing wrong here ?
Here time_windows is a lis, e.g: [[100, 200], [300, 400]] and index is the index retrieved from NodeToIndex.
The problem seems indeed to be in the FirstSolutionStrategy as mentioned in the comments. When everything comes out unassigned or-tools is simply unable to build a first solution. Unfortunately this is not very clear from the logs. I have had success with the FirstSolutionStrategys ALL_UNEPRFORMED and PATH_MOST_CONSTRAINED_ARC.
Unfortunately in my case ALL_UNPERFORMED was unable to solve trivial cases, but PATH_MOST_COSNTRAINED_ARC worked well. I just wish that the algorithms has more in-depth descriptions so it is easier to select the proper algorithm.