Description
What version of OR-Tools and what language are you using?
Version: 9.12.4544
Language: Python
Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver
What operating system (Linux, Windows, ...) and version?
Windows
What did you do?
Im not sure this is a bug or feature request...
Im trying to solve a VRP problem with ~3000 nodes.
I've implemented breaks in the following way:
# Break logic
node_visit_transit = [0] * routing.Size()
for index in range(routing.Size()):
node = manager.IndexToNode(index)
if node == data["depot"]:
node_visit_transit[index] = data.get("loading_time", 0)
else:
node_visit_transit[index] = data["delivery_times"][node] if node < len(data["delivery_times"]) else 0
for v in range(data['num_vehicles']):
start_var = time_dimension.CumulVar(routing.Start(v))
break_start = routing.solver().Sum([routing.solver().IntVar(360, 420), start_var])
break_intervals = [
routing.solver().FixedDurationIntervalVar(
break_start, 30, 'Break for vehicle {}'.format(v))
]
time_dimension.SetBreakIntervalsOfVehicle(break_intervals, v, node_visit_transit)This seems to create a lot of not needed slack in the beginning of the routes (between depot, and first stop).
The start time of the routes needs to be very free and any start time between 1 and 1440 is allowed.
Further, because I also have a limit on the number of loading docks being able to be used at the same time, slack at the beginning of the route must be allowed. Thus I cant simply limit the the amount of allowed slack (I tried that, and unnecessary slack is still created, just less of it).
Code for the loading docks logic:
solver = routing.solver()
load_intervals = []
for vehicle_id in range(data["num_vehicles"]):
start_var = time_dimension.CumulVar(routing.Start(vehicle_id))
load_interval = solver.FixedDurationIntervalVar(
start_var,
loading_time,
f"depot_load_interval_{vehicle_id}"
)
load_intervals.append(load_interval)
gate_usage = [1] * len(load_intervals)
solver.Add(
solver.Cumulative(
load_intervals,
gate_usage,
data["number_of_gates"],
"depot_gates"
)
)The span cost, does make the solver reduce the slack in the beginning, however this is only feasible with upto around ~1000 nodes. After which the local search is so slow, the slack is not reduced within reasonable time (2 hours). Adding the break logic slows the local search from around 1300 solutions in 90 seconds, to merely 20 solutions in 90 seconds. (The loading dock logic is not causing this issue, commenting it out only barely makes the local search faster 20 -> 25 solutions)
Further the break logic 10x the memory consumption (2 GB -> 20 GB)
((Further I tried using "setbreakdistancedurationofvehicle", however this seems to not work, and works more like SetSpanUpperBoundForVehicle.))
((I tried many things to make this work))
((Adding AddVariableMaximizedByFinalizer and AddVariableMinimizedByFinalizer to the start/end times didnt make a difference))
What did you expect to see
A better break implementation. Breaks are important for real world use cases.
I hope breaks gets an upgrade in an upcoming version, with improved performance, options and usability.