Difficulty in Adding an Exact Time Break in Vehicle Routing Problem

[ibiscp]

Hello all,

I'm trying to solve a routing problem where the routing starts at 9:00 and finishes at 17:00. I need to add a break from 12:00 to 13:00, but the break must start exactly at 12:00. For instance, if the previous visit ends at 11:30 and it's not feasible to make another visit before the break, I want the driver to wait until 12:00 to start the break, or move to the next location and wait for the break there.

Here is the closest solution I have come up with:

# Start time of the routes
for vehicle_id in range(manager.GetNumberOfVehicles()):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetValue(self.shift_hours[0][0])

# Add breaks
if len(self.shift_hours) > 1:
    node_visit_transit = [0] * routing.Size()
    for index in range(routing.Size()):
        node = manager.IndexToNode(index)
        node_visit_transit[index] = service_times[node]

    break_start_time = self.shift_hours[0][1]
    break_end_time = self.shift_hours[1][0]
    break_duration = break_end_time - break_start_time

    for v in range(manager.GetNumberOfVehicles()):
        # Create a fixed duration interval for the break
        interval = routing.solver().FixedDurationIntervalVar(
            break_start_time, break_start_time, break_duration, False, "Break"
        )

        # Introduce an auxiliary variable to ensure the break starts at exactly the specified time
        break_start_var = routing.solver().IntVar(break_start_time, break_start_time, f'BreakStart_{v}')
        
        # Add constraints to enforce the break start time
        routing.solver().Add(time_dimension.CumulVar(routing.End(v)) >= break_start_var)

        # Optional: Add slack before the break if the previous task ends early
        slack_var = routing.solver().IntVar(0, break_start_time, f'Slack_{v}')
        routing.solver().Add(time_dimension.CumulVar(routing.Start(v)) + slack_var >= break_start_time)

        time_dimension.SetBreakIntervalsOfVehicle([interval], v, service_times)

Problems with this solution:

• The break starts one hour earlier than expected
• The arrival time at the depot is showing one hour before, so the driver is losing one hour of work

Any help or suggestions to solve this issue would be greatly appreciated!

[sschnug]

As the break-interval is just an interval-variable (which is a set of integer-variables), why don't you just fix (e.g. with that) it's start (and end) variables and let the solver figure out the rest?

I don't see any need for aux-vars or constraints here as this sounds like the most trivial / simple case of vehicle-breaks (fixed position on time-dimension).