Or-tools: [Question] Driver Schedules and Locking Locations to Certain Drivers

[calatian]

Hello,

I am working on a Vehicle Routing problem and have the basic VRP running, but I need some direction on how to add the following constraints next:

• Certain locations can only be serviced by a specific driver.

• Schedules: Each driver has a workday start/end time, as well as available slts throughout the day. The services should only be scheduled within those slots, and of course within their workday. Service times and travel time should also be considered, so that they are able to arrive it to the end depot before their workday ends.

Any help to get me started with these constraints would be very helpful. I am working in Python.
Thanks!

[Mizux]

1) Please take a look at https://github.com/google/or-tools/issues/334#issuecomment-484781754

index = manager.NodeToIndex(location_index)
# use vehicle 2, 3, or 4 (-1 is sentinel for unactive node since solver add node to route little by little)
routing.VehicleVar(index).SetValues([-1, 2,3,4])

2) Time Windows constraint on vehicle start/end node ?
also take a look at https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/doc/VRP.md#time-window-constraints

Transit_time can be service_time + travel_time in your callback
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/samples/cvrptw.py#L138-L171

[calatian]

Thank you for the answer, @Mizux. As far as #2 goes, I don't only need route start/end time constraints; each vehicle would have several time windows in which they are available. For example:

Vehicle 1:
Workday: 8AM to 5PM
Available: 8AM to 9AM, 10AM to 12PM, 2PM to 3PM, 4PM to 5PM.

And a similar situation for the rest of the vehicles.

Do you know if this is doable? Thanks again.

[Mizux]

Actually, do you want three breaks ? [9AM, 10AM], [12PM, 2PM] and [3PM, 4PM] ?
i.e. vehicle can't travel during this period

or vehicle can only deliver customer during this time windows ?

[calatian]

Ideally, the vehicle can only deliver during these time windows (but it can be any customer, not a specific location).

Otherwise, I could try "negating" the available times and using breaks instead.

Thanks again!

[Mizux]

you can remove some interval in time windows...

[calatian]

Could you give me some more details on how to do this? Thanks again!

[Mizux]

suppose you must have
https://github.com/google/or-tools/blob/5b5116df81be20f8fe4c93470778864ed74dd405/ortools/constraint_solver/samples/vrp_time_windows.py#L147-L148
and you want to remove [A,B], then simply add

 time_dimension.CumulVar(index).RemoveInterval(A, B) 

src:
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/constraint_solver.h#L3980-L3988

note: note tested however

[calatian]

When you say you remove an interval, the interval would be each break (times when a driver is not available); is that correct?

[Mizux]

yup, but in this case it means this location must not be served during the driver "break" but the solver can still use this range to make the vehicle travel during this time i.e. it's a break for the delivery, not for the driver ;)

[calatian]

However, this would be linked to the location itself (from what you are explaining), which wouldn't work for my situation. In my situation, it is the driver that cannot have any assignments during certain times (breaks). Does that make sense?

[Mizux]

so you want vehicle break interval like in
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/samples/cvrptw_break.py#L308-L317

[calatian]

That's correct, but can you set specific times in which those breaks should be taken for each vehicle?

[Mizux]

comes from:
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/constraint_solver.h#L1757-L1763
(rename in python in FixedDurationIntervalVar) so i would say for the break 9AM-10AM

# suppose uor time are in minute and you start at 0AM
start_min = 9 *60
start_max = start_min
duration = 60 # 1 Hours from 9AM to 10AM
is_optional = false
routing.solver().FixedDurationIntervalVar(start_min, start_max, duration, is_optional, "lorem ipsum...")

[calatian]

Thank you so much, Mixuz! I will look into this.

[calatian]

Hi @Mizux, thanks again for your help. I have been implementing the breaks and I don't think I have understood how to set the break intervals correctly; I keep getting an error.

I have hard-coded an example where vehicle 1 is getting a break from 11am-2pm and another one from 4-5pm, vehicle 2 gets a break from 12pm-3pm:

driver_breaks = [
    [1, [[11 * 60, 14 * 60], [16 * 60, 17 * 60]]],
    [2, [[12 * 60, 15 * 60]]]
]

    for driver in driver_breaks:
        driver_id = driver[0]
        intervals = []
        for br in driver[1]:
            start_min = br[0]
            start_max = start_min
            duration = br[1] - br[0]
            is_optional = False
            intervals.append(routing.solver().FixedDurationIntervalVar(
            start_min,
            start_max,
            duration,
            is_optional,
            "break"))
        time_dimension.SetBreakIntervalsOfVehicle(intervals, driver_id, transit_callback_index)`

I keep getting the following error:

in SetBreakIntervalsOfVehicle return _pywrapcp.RoutingDimension_SetBreakIntervalsOfVehicle(self, breaks, vehicle, node_visit_transits) TypeError: 'int' object is not iterable

I have tried to follow your example but I am not sure what I am doing wrong. Could you advise?
Thanks in advance.

[Mizux]

AFAIK break API take an array of service time (of locations size)
https://github.com/google/or-tools/blob/f3fd201e68cf75b7720ff5c3cadc599a1d02b54b/ortools/constraint_solver/routing.h#L2031-L2042

i.e. breaks don't overlap with service time of each nodes so you must provide the service time info since a dimension transit callback is:
```
transit_time(A, B) == service_time(A) + travel_time(A, B)
````

[calatian]

Thank you, that really helped! It works now.

[abduakhatov]

@Mizux in cvrptw_break.py#L310 example, if more than one vehicle break is added, it stucks. Whats wrong?

    # for v in xrange(data['num_vehicles']): # stucks
    for v in [0]: # works fast 

[abduakhatov]

@calatian Is it working with multiple vehicles?

[routemegood]

@abduakhatov @Mizux You can get it to work with multiple vehicles if change the way it solves. You need to add a disjunction for every node (make them optional) and then change the first_solution_strategy parameter to "ALL_UNPERFORMED". It then inserts the node visits one by one around the break, and usually returns a feasible solution with all nodes visited.

The problem is it doesn't scale too well. With lots more vehicles and nodes (10 vehicles and 320 nodes) it really struggles. After 10 minutes it had only found about 35 solutions, where without breaks it would be in the tens of thousands.

I think the problem with the example "as is" is that the default first solution strategy (or all except the one I recommended) doesn't find a feasible solution that includes breaks, or gets stuck trying to find one, even when all nodes are optional.

[sreyas7]

Thank you, that really helped! It works now.

I am trying to create a similar CVRPTW where I am allowing the vehicle to travel for multiple days and one of the constraints is that the vehicle can only travel for a duration of 'max working hours' for each day.
I am trying to implement the same approach that @Mizux had suggested but somehow I am still unable to get it.
I did the following change to overcome the exact same error that you had encountered but something seems to be wrong which leads to an infeasible solution.

I am giving it a service time of 10 minutes for each location.

Can you show what changed did you have to make?

Thanks.