I'm trying to create a scheduler which assigns a set of shifts to a set of drivers for each day of the week, enforcing a minimum of 1 Day off per week. For the following input data, I'm getting an infeasible solution. Any help?
Input data:
dow driver hub
0 Sunday 1 S
1 Sunday 2 S
2 Sunday 3 S
3 Monday 1 S
4 Monday 2 S
5 Monday 3 S
6 Tuesday 2 S
7 Tuesday 3 S
8 Wednesday 1 S
9 Wednesday 3 S
10 Thursday 1 S
11 Thursday 2 S
12 Thursday 3 S
13 Friday 1 S
14 Friday 2 S
15 Saturday 1 S
16 Saturday 2 S
17 Saturday 3 S
Code
from ortools.sat.python import cp_model
import pandas as pd
def create_shift_schedule(drivers,
shifts,
week_days,
hubs,
min_shift_drivers,
max_shift_drivers,
driver_hubs_relationships):
model = cp_model.CpModel()
# Create shift variables
schedule = {}
for e in drivers:
for d in week_days:
for s in shifts:
for r in hubs:
schedule[(e, d, s, r)] = model.NewBoolVar(f'schedule_{e}_{d}_{s}_{r}')
# Each driver works exactly one shift per day (including "Off" shift) at a specific hub
for e in drivers:
for d in week_days:
model.Add(sum(schedule[(e, d, s, r)] for s in shifts for r in hubs) == 1)
# Respect the minimum and maximum number of drivers per shift per hub per day
for d in week_days:
for s in shifts:
for r in hubs:
min_drivers = min_shift_drivers.get((d, s, r), 0)
max_drivers = max_shift_drivers.get((d, s, r), len(drivers))
model.Add(sum(schedule[(e, d, s, r)] for e in drivers) >= min_drivers)
model.Add(sum(schedule[(e, d, s, r)] for e in drivers) <= max_drivers)
# Ensure each driver has at least one "Off" shift per week and max 3 "off" shifts per week
for e in drivers:
model.Add(sum(schedule[(e, d, "Off", r)] for d in week_days for r in hubs) >= 1)
for e in drivers:
model.Add(sum(schedule[(e, d, "Off", r)] for d in week_days for r in hubs) <= 3)
# Assign each driver to their specific hub
for e in drivers:
for r in hubs:
if r not in driver_hubs_relationships[e]:
for d in week_days:
for s in shifts:
model.Add(schedule[(e, d, s, r)] == 0)
# Minimize the total number of working shifts assigned to drivers (excluding "Off" shift)
# model.Minimize(sum(
# schedule[(e, d, s, r)] for e in drivers for d in week_days for s in shifts if
# s != "Off" for r in hubs))
# Create auxiliary variables
same_shift_aux = {}
for e1 in drivers:
for e2 in drivers:
if e1 != e2:
for d in week_days:
for s in shifts:
if s != "Off":
for r in hubs:
same_shift_aux[(e1, e2, d, s, r)] = model.NewBoolVar(
f'same_shift_aux_{e1}_{e2}_{d}_{s}_{r}')
# Add constraints to link auxiliary variables with schedule variables
for e1 in drivers:
for e2 in drivers:
if e1 != e2:
for d in week_days:
for s in shifts:
if s != "Off":
for r in hubs:
model.AddImplication(schedule[(e1, d, s, r)],
same_shift_aux[(e1, e2, d, s, r)])
model.AddImplication(schedule[(e2, d, s, r)],
same_shift_aux[(e1, e2, d, s, r)])
# Modify the objective function
penalty_for_same_shift = 1 # Adjust this value to control the penalty for assigning the same
# shift to multiple drivers
model.Minimize(
sum(schedule[(e, d, s, r)] for e in drivers for d in week_days for s in shifts if
s != "Off" for r in hubs)
+ penalty_for_same_shift * sum(
same_shift_aux[(e1, e2, d, s, r)] for e1 in drivers for e2 in drivers if
e1 != e2 for d in week_days for s in shifts if s != "Off" for r in hubs))
# Solve the scheduling problem
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 300.0
solver.parameters.log_search_progress = True
status = solver.Solve(model)
print(f"status code {status}")
if status == cp_model.OPTIMAL:
solution = {}
for e in drivers:
solution[e] = {}
for d in week_days:
for s in shifts:
for r in hubs:
if solver.Value(schedule[(e, d, s, r)]) == 1:
solution[e][d] = (s, r)
return solution
else:
return None
file = pd.Dataframe(input_data) # i'm loading them from a file
file['driver'] = file['driver'].apply(lambda x: str(x))
drivers = file['driver'].unique().tolist()
num_shifts = 2 # Including "Off" shift
# Create shift assignment variables
shifts = ["Off"] + [f"Shift_{d}" for d in range(1, num_shifts)]
week_days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
hubs = file['hub'].unique().tolist()
# how many drivers are needed per dow and per hub
hub_counts = \
pd.DataFrame(file.groupby(['dow', 'hub'],
as_index=False)['driver'].count())
fixed_shift_drivers_per_day_hub = {
day: {
hub: driver_count
for hub, driver_count in zip(hub_counts[hub_counts['dow'] == day]['hub'],
hub_counts[hub_counts['dow'] == day]['driver'])
}
for day in week_days
}
min_shift_drivers = {
(day, shift, hub): 1
for day in week_days
for shift in shifts
for hub in hubs
}
max_shift_drivers = {
(day, shift, hub): fixed_shift_drivers_per_day_hub[day][hub] if shift != "Off" else 0
for day in week_days
for shift in shifts
for hub in hubs
}
driver_hubs_relationships = \
pd.DataFrame(file.groupby('driver')['hub'].apply(list)).reset_index()
driver_hubs_relationships = \
{key: value for key, value in zip(driver_hubs_relationships['driver'],
driver_hubs_relationships['hub'])}
solution = create_shift_schedule(drivers, shifts, week_days, hubs, min_shift_drivers,
max_shift_drivers, driver_hubs_relationships)
if solution:
for e in drivers:
print(f"{e}:")
for d in week_days:
print(f" {d}: {solution[e][d]}")
else:
print("No solution found.")
This constraint seems to be causing the issue. min_drivers can't be more than max_drivers.
# Respect the minimum and maximum number of drivers per shift per hub per day
for d in week_days:
for s in shifts:
for r in hubs:
min_drivers = min_shift_drivers.get((d, s, r), 0)
max_drivers = max_shift_drivers.get((d, s, r), len(drivers))
if min_drivers > max_drivers: # Added this check.
continue
expr = sum(schedule[(e, d, s, r)] for e in drivers)
model.AddLinearConstraint(expr, min_drivers, max_drivers) # L Perron's suggestion.