多次windows vrp [或-工具]

Question

我有一个应该为发货设置多个时间 windows 的实现：

    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)

逻辑上似乎没有错，但 or-tools 无法 return 解决方案，除非我删除行 time_dimension.CumulVar(index).RemoveInterval(time_window_end, next_time_window_start)。知道我在这里做错了什么吗？

这里time_windows是一个lis，例如：[[100, 200], [300, 400]]和index是从NodeToIndex中检索到的索引。

Answer 1

问题似乎确实出在评论中提到的 FirstSolutionStrategy 中。当一切都未分配或工具出来时，根本无法构建第一个解决方案。不幸的是，这从日志中不是很清楚。我在 FirstSolutionStrategys ALL_UNEPRFORMED 和 PATH_MOST_CONSTRAINED_ARC.

方面取得了成功

不幸的是，在我的案例中 ALL_UNPERFORMED 无法解决琐碎的案例，但 PATH_MOST_COSNTRAINED_ARC 效果很好。我只希望算法有更深入的描述，这样更容易 select 正确的算法。

多次windows vrp [或-工具]

Multiple time windows vrp [or-tools]

or-tools

vehicle-routing