Or-tools: VRP with Time Windows - More than 1 time window per location

[ilaif]

Hey guys,

Amazing library!

I have a situation where a location (or "customer") has two or more available time windows (let's say it's open in the morning, closed for siesta, and then open again until the evening).
The following SetRange line of code: time_dimension.CumulVar(order).SetRange(start, end) gives one such constraint, how can I add two with "OR" logic between them?

Thanks,
Ilai

[michaelarakel]

@ilaif I had the same problem and here is how I approached it:

• First construct 2 lists of starts and ends of ranges that the CumulVar cannot take
• Then use the NotMemberCt of constraint solver as follows (assuming routing is your RoutingModel:

solver = routing.solver()
solver.AddConstraint(
    solver.NotMemberCt(
        time_dimension.CumulVar(order), 
        forbidden_time_frame_starts, forbidden_time_frame_ends
    )
)

[ilaif]

Thanks @michaelarakel !

1. Just to make sure I understand: Your solution was to use De Morgan Rules: (A OR B) = NOT(NOT(A) AND NOT(B)) and chain a list of "AND" constraints on a variable?
2. The two lists (forbidden_time_frame_starts and ..._ends) are plain lists of numbers?
3. Also, when can I see simple documentation on the additional library api? like using the "NotMemberCt" and even "AddConstraint" methods.

[michaelarakel]

@ilaif

1. Yes you can think of it as using De Morgan's rule
2. Yes they are just lists of numbers. Let me give an example to make this clearer. Suppose forbidden_time_frame_starts = [0, 34000] and forbidden_time_frame_ends = [26999, 57000]. This means that the CumulVar will not be allowed to take values in ranges [0, 26999] and [34000, 57000]. One note though: you need to make sure that these "time frames" are non-intersecting and in sorted order
3. These 2 functions are not part of the routing, but belong to the constraint solver. I have been using the code as documentation :) You can have a look at the constraint_solver.h for other constraints (in c++). constraint_solver.i contains the python bindings

[furnon]

I confirm this is the proper way to model multiple time windows (and the
routing solver will take them into account actively in the local search).

On Mon, Aug 28, 2017 at 3:01 PM, michaelarakel [e-mail]
wrote:

@ilaif https://github.com/ilaif

1. Yes you can think of it as using De Morgan's rule
2. Yes they are just lists of numbers. Let me give an example to make
   this clearer. Suppose forbidden_time_frame_starts = [0, 34000] and forbidden_time_frame_starts
   = [26999, 57000]. This means that the CumulVar will not be allowed to
   take values in ranges [0, 26999] and [34000, 57000]
3. These 2 functions are not part of the routing, but belong to the
   constraint solver. I have been using the code as documentation :) You can
   have a look at the constraint_solver.h for other constraints (in c++).
   constraint_solver.i contains the python bindings

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/456#issuecomment-325346894,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUineD46iixYddKQPYFtM5i9nOt6Hks5scroygaJpZM4PDjqs
.

[ilaif]

Hey @michaelarakel, @furnon,

I think there might be a bug with this method.
I've used the instructions above to create forbidden time windows:

solver = routing.solver()
solver.AddConstraint(
    solver.NotMemberCt(
        time_dimension.CumulVar(order), 
        forbidden_time_frame_starts, forbidden_time_frame_ends
    )
)

In the test I have 6 locations:

• index: 0, forbidden time windows: None (Not inserted as a constraint)
• index: 1, forbidden time windows: None (Not inserted as a constraint)
• index: 2, forbidden time windows: [10801], [86400]
• index: 3, forbidden time windows: [10801], [86400]
• index: 4, forbidden time windows: [0, 46801], [20999, 86400]
• index: 5, forbidden time windows: [0, 46801], [20999, 86400]

Where 86400 is the horizon, index 0 is the start location and index 1 is the end location.

The assignment is the following order:

• index: 0, max_arrive_time: 0, min_arrive_time: 0
• index: 3, max_arrive_time: 6482, min_arrive_time: 672
• index: 4, max_arrive_time: 10800, min_arrive_time: 4990
• index: 5, max_arrive_time: 41831, min_arrive_time: 21000
• index: 2, max_arrive_time: 43317, min_arrive_time: 22486
• index: 1, max_arrive_time: 46800, min_arrive_time: 25969

As you can see node index 4 is arriving during the forbidden time window.

The full source code:
https://gist.github.com/ilaif/a79dfd8c41b2924d4d74758e342c88f5

Command I've called (with the relevant input parameters):

python vrpsolver.py --data {\"locations\":[{\"time_windows\":[],\"service_time\":0},{\"time_windows\":[],\"service_time\":0},{\"time_windows\":[[0,10800]],\"service_time\":900},{\"time_windows\":[[0,10800]],\"service_time\":900},{\"time_windows\":[[21000,46800]],\"service_time\":900},{\"time_windows\":[[18000,46800]],\"service_time\":900}],\"distance_matrix\":[[0,0,2553,672,3561,2372],[0,0,2553,672,3561,2372],[2583,2583,0,2288,2063,741],[812,812,2410,0,3418,2229],[3585,3585,1906,3290,0,1756],[2452,2452,586,2157,1732,0]],\"start_location_index\":0,\"end_location_index\":1}

Appreciate the effort,
Thanks, Ilai

[furnon]

The issue with your code is that node and variable are mixed. In particular
when you set the time windows, it should be:
solver.Add(
solver.NotMemberCt(
time_dimension.CumulVar(routing.NodeToIndex(order)), <--
note the conversion here
[tw[0] for tw in closed_time_windows], [tw[1] for tw in
closed_time_windows]
)
)

Also note that there's probably a typo in the forbidden time windows you
displayed; it's actually:
index: 4, forbidden time windows: [0, 20999], [46801, 86400]
index: 5, forbidden time windows: [0, 17999], [46801, 86400]
(at least from the command line you specified).

On Sat, Sep 23, 2017 at 8:14 PM, Ilai Fallach [e-mail]
wrote:

Hey, guys,

I think there might be a bug with this method.
I've used the instructions above to create forbidden time windows:

solver = routing.solver()
solver.AddConstraint(
solver.NotMemberCt(
time_dimension.CumulVar(order),
forbidden_time_frame_starts, forbidden_time_frame_ends
)
)

In the test I have 6 locations:

• index: 0, forbidden time windows: None (Not inserted as a constraint)
• index: 1, forbidden time windows: None (Not inserted as a constraint)
• index: 2, forbidden time windows: [10801], [86400]
• index: 3, forbidden time windows: [10801], [86400]
• index: 4, forbidden time windows: [0, 46801], [20999, 86400]
• index: 5, forbidden time windows: [0, 46801], [20999, 86400]

Where 86400 is the horizon, index 0 is the start location and index 1 is
the end location.

The assignment is the following order:

• index: 0, max_arrive_time: 0, min_arrive_time: 0
• index: 3, max_arrive_time: 6482, min_arrive_time: 672
• index: 4, max_arrive_time: 10800, min_arrive_time: 4990
• index: 5, max_arrive_time: 41831, min_arrive_time: 21000
• index: 2, max_arrive_time: 43317, min_arrive_time: 22486
• index: 1, max_arrive_time: 46800, min_arrive_time: 25969

As you can see node index 4 is arriving during the forbidden time window.

The full source code:
https://gist.github.com/ilaif/a79dfd8c41b2924d4d74758e342c88f5

Command I've called (with the relevant input parameters):

python vrpsolver.py --data {\"locations\":[{\"time_windows\":[],\"service_time\":0},{\"time_windows\":[],\"service_time\":0},{\"time_windows\":[[0,10800]],\"service_time\":900},{\"time_windows\":[[0,10800]],\"service_time\":900},{\"time_windows\":[[21000,46800]],\"service_time\":900},{\"time_windows\":[[18000,46800]],\"service_time\":900}],\"distance_matrix\":[[0,0,2553,672,3561,2372],[0,0,2553,672,3561,2372],[2583,2583,0,2288,2063,741],[812,812,2410,0,3418,2229],[3585,3585,1906,3290,0,1756],[2452,2452,586,2157,1732,0]],\"start_location_index\":0,\"end_location_index\":1}

Appreciate the effort,
Thanks, Ilai

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/456#issuecomment-331660275,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUgD8yWPp5YigYJeHiAYBdD2vJzcPks5slUqNgaJpZM4PDjqs
.

[ilaif]

@furnon thanks a lot! It solved the problem. The forbidden time windows are indeed a type :)

[JacobenVosloo]

In this post - https://groups.google.com/forum/#!topic/or-tools-discuss/MBq1TcqSQTI they suggest a different approach.
Instead of using the 'solver.NotMemberCt()' function they simply remove the forbidden intervals using

' time_dimension.CumulVar(index).RemoveInterval(time_window_end, next_time_window_start)'

Here is a link to another implementation https://stackoverflow.com/questions/61456895/multiple-time-windows-vrp-or-tools

which approach is better or more correct?
The latter definitely looks easier...