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 ***@***.***> 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 <#456 (comment)>, 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 ***@***.***> 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 <#456 (comment)>, 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...