top2 / shift_optimizer.py
naheedakhtar's picture
Update shift_optimizer.py
2c50cb4 verified
Raw History Blame Contribute Delete
11.5 kB
from ortools.linear_solver import pywraplp
import numpy as np
import pandas as pd
# --- MIP Driver Shift Generator ---
def mip_generate_driver_shifts(hourly_demand, min_shift=8, max_shift=11):
solver = pywraplp.Solver.CreateSolver('SCIP')
shifts = []
possible_shifts = []
for start in range(24):
for length in range(min_shift, max_shift + 1):
end = (start + length - 1) % 24
if start <= end:
hours = list(range(start, end + 1))
else:
hours = list(range(start, 24)) + list(range(0, end + 1))
possible_shifts.append((start, end, hours))
x = {i: solver.IntVar(0, solver.infinity(), f'shift_{i}') for i, shift in enumerate(possible_shifts)}
over = {hour: solver.NumVar(0, solver.infinity(), f'over_{hour}') for hour in range(24)}
for hour in range(24):
solver.Add(
sum(x[i] for i, shift in enumerate(possible_shifts) if hour in shift[2]) == hourly_demand[hour] + over[hour]
)
penalty_weight = 0.001
solver.Minimize(
solver.Sum(x[i] for i in range(len(possible_shifts))) +
penalty_weight * solver.Sum(over[hour] for hour in range(24))
)
status = solver.Solve()
selected_shifts = []
if status == pywraplp.Solver.OPTIMAL:
for i, shift in enumerate(possible_shifts):
assigned_drivers = int(x[i].solution_value())
if assigned_drivers > 0:
selected_shifts.append((shift[0], shift[1], shift[2], assigned_drivers))
else:
raise Exception("No optimal solution found .")
return selected_shifts
# --- MIP Driver Shift Generator ---
def mip_generate_driver_shifts_limited_drivers(hourly_demand, max_drivers_available, min_hourly_taxis, min_shift=8, max_shift=11):
solver = pywraplp.Solver.CreateSolver('SCIP')
shifts = []
possible_shifts = []
for start in range(24):
for length in range(min_shift, max_shift + 1):
end = (start + length - 1) % 24
if start <= end:
hours = list(range(start, end + 1))
else:
hours = list(range(start, 24)) + list(range(0, end + 1))
possible_shifts.append((start, end, hours))
x = {i: solver.IntVar(0, solver.infinity(), f'shift_{i}') for i, shift in enumerate(possible_shifts)}
drivers_per_hour = {h: solver.Sum(x[i] for i, shift in enumerate(possible_shifts) if h in shift[2]) for h in range(24)}
# Constraints: Minimum hourly taxis
for hour in range(24):
solver.Add(drivers_per_hour[hour] >= min_hourly_taxis)
# Constraint: Total drivers used <= max_drivers_available
solver.Add(solver.Sum(x[i] for i in range(len(possible_shifts))) <= max_drivers_available)
# Priority weights (peak hours have higher priority)
max_demand = max(hourly_demand)
priority_weight = {h: hourly_demand[h] / max_demand for h in range(24)}
# Objective: maximize weighted sum of drivers assigned (more weight to peak demand hours)
solver.Maximize(
solver.Sum(priority_weight[h] * drivers_per_hour[h] for h in range(24))
)
status = solver.Solve()
selected_shifts = []
if status == pywraplp.Solver.OPTIMAL:
for i, shift in enumerate(possible_shifts):
assigned_drivers = int(x[i].solution_value())
if assigned_drivers > 0:
selected_shifts.append((shift[0], shift[1], shift[2], assigned_drivers))
else:
raise Exception("No optimal solution found with driver limits.")
return selected_shifts
def mip_generate_driver_shifts_limited_drivers_demand_proportional(hourly_demand, max_drivers_available, min_shift=8, max_shift=11):
"""
3-stage process:
1. Calculate drivers required as per given hourly demand.
2. If drivers required > max_drivers_available, reduce hourly demand by the same percent across all hours.
3. Adjust off-peak demand to make 0 extra drivers (fine-tune so total drivers assigned == max_drivers_available).
"""
solver = pywraplp.Solver.CreateSolver('SCIP')
solver.set_time_limit(90000)
# --- Stage 1: Calculate drivers required as per given hourly demand ---
# Use the original MIP to get the minimum drivers required for the demand
temp_shifts = mip_generate_driver_shifts(hourly_demand, min_shift, max_shift)
drivers_required = sum(shift[3] for shift in temp_shifts)
# --- Stage 2: If needed, reduce demand proportionally ---
if drivers_required > max_drivers_available:
reduction_percent = 1 - (max_drivers_available / drivers_required)
print(f"Reducing demand by {reduction_percent:.2%} to fit within driver limits.")
reduced_hourly_demand = (hourly_demand * (1 - reduction_percent)).round().astype(int)
else:
reduced_hourly_demand = hourly_demand.copy()
print(f"Reduced hourly demand: {reduced_hourly_demand}")
selected_shifts = mip_generate_driver_shifts(reduced_hourly_demand, min_shift, max_shift)
# selected_shifts = []
if selected_shifts != []:
return selected_shifts, reduced_hourly_demand
else:
raise Exception(f"Solver failed .")
def generate_taxi_utilization_matrix(final_shifts, num_taxis, required_gap=1):
"""
Generate a taxi utilization matrix that assigns one taxi to each driver shift,
ensuring no overlapping or consecutive shifts without required gaps.
Args:
final_shifts: List of shifts with [start_hour, end_hour, hours_list, drivers_assigned]
num_taxis: Maximum number of taxis available
required_gap: Minimum gap hours required between shifts for the same taxi (default: 1)
Returns:
utilization_df: DataFrame showing hourly taxi utilization for available taxis
utilization_df_revised: DataFrame showing hourly taxi utilization including additional taxis
summary_df: DataFrame summarizing taxi utilization hours
additional_taxis_needed: Number of additional taxis needed beyond what's available
"""
# Initialize taxi utilization tracking
utilization = np.zeros((num_taxis, 24), dtype=int)
# First, expand shifts to individual driver assignments
driver_shifts = []
for shift in final_shifts:
start_hour, end_hour, hours, drivers_assigned = shift
for _ in range(drivers_assigned):
driver_shifts.append((start_hour, end_hour, hours))
# Sort by shift length (descending) to place longer shifts first
driver_shifts.sort(key=lambda x: len(x[2]), reverse=True)
# Track taxi assignments and additional taxis needed
taxi_assignments = [] # List to store (taxi_id, shift_hours) tuples
additional_taxis_needed = 0
additional_taxi_utilization = []
# For each driver shift, find a suitable taxi
for shift_start, shift_end, shift_hours in driver_shifts:
# Convert shift hours to a set for quicker lookups
shift_hours_set = set(shift_hours)
# Try to find an available taxi
taxi_found = False
for taxi_id in range(num_taxis):
# Check if this taxi can accommodate this shift
can_use_taxi = True
# Check for overlap with existing assignments
for assigned_hours in [hours for tid, hours in taxi_assignments if tid == taxi_id]:
# Check direct overlap
if shift_hours_set.intersection(set(assigned_hours)):
can_use_taxi = False
break
# Check gap requirement
for h in shift_hours:
for gap in range(1, required_gap + 1):
if (h - gap) % 24 in assigned_hours or (h + gap) % 24 in assigned_hours:
can_use_taxi = False
break
if not can_use_taxi:
break
if not can_use_taxi:
break
if can_use_taxi:
taxi_assignments.append((taxi_id, shift_hours))
# Update utilization matrix
for h in shift_hours:
utilization[taxi_id, h] = 1
taxi_found = True
break
# If no suitable taxi found, need an additional taxi
if not taxi_found:
additional_taxis_needed += 1
# Track utilization for this additional taxi
taxi_hours = [0] * 24
for h in shift_hours:
taxi_hours[h] = 1
additional_taxi_utilization.append(taxi_hours)
# Create dataframe for detailed utilization of available taxis
taxi_names = [f"taxi_{i+1}" for i in range(num_taxis)]
hour_names = [str(h) for h in range(24)]
utilization_df = pd.DataFrame(utilization, index=taxi_names, columns=hour_names)
# Create revised utilization dataframe including additional taxis
utilization_revised = utilization.copy()
if additional_taxis_needed > 0:
# Create array for additional taxis
additional_array = np.array(additional_taxi_utilization)
# Combine with original utilization
utilization_revised = np.vstack([utilization, additional_array])
# Create revised dataframe with all taxis
revised_taxi_names = taxi_names + [f"additional_taxi_{i+1}" for i in range(additional_taxis_needed)]
utilization_df_revised = pd.DataFrame(utilization_revised, index=revised_taxi_names, columns=hour_names)
# Count total hours used per taxi
total_hours_per_taxi = pd.Series(utilization_revised.sum(axis=1))
# Summarize counts of taxis with same total hours
summary_series = total_hours_per_taxi.value_counts().sort_index()
summary_df = pd.DataFrame({
'Total Hours Utilized': summary_series.index,
'Number of Taxis': summary_series.values
})
# Add information about additional taxis needed
if additional_taxis_needed > 0:
summary_df = pd.concat([summary_df, pd.DataFrame({
'Total Hours Utilized': [f"Additional taxis needed"],
'Number of Taxis': [additional_taxis_needed]
})], ignore_index=True)
return utilization_df, utilization_df_revised, summary_df, additional_taxis_needed
def compute_taxi_utilization_summary(final_shifts, num_taxis):
utilization = np.zeros((num_taxis, 24), dtype=int)
taxi_pointer = 0 # Round-robin assignment
for shift in final_shifts:
start_hour, end_hour, hours, drivers_assigned = shift
for _ in range(drivers_assigned):
taxi_id = taxi_pointer % num_taxis
for h in hours:
utilization[taxi_id, h] = 1
taxi_pointer += 1
# Create dataframe for detailed utilization
taxi_names = [f"taxi_{i+1}" for i in range(num_taxis)]
hour_names = [str(h) for h in range(24)]
utilization_df = pd.DataFrame(utilization, index=taxi_names, columns=hour_names)
# Count total hours used per taxi
total_hours_per_taxi = pd.Series(utilization.sum(axis=1))
# Summarize counts of taxis with same total hours
summary_series = total_hours_per_taxi.value_counts().sort_index()
summary_df = pd.DataFrame({
'Total Hours Utilized': summary_series.index,
'Number of Taxis': summary_series.values
})
return utilization_df, summary_df