Spaces:
Sleeping
Sleeping
Download shift_optimizer.py from naheedakhtar/top2: direct link, hf CLI and curl.
- Browser
- Download file 11.5 kB
-
https://huggingface.co/spaces/naheedakhtar/top2/resolve/main/shift_optimizer.py
- Command line
-
hf download hf://spaces/naheedakhtar/top2/shift_optimizer.py
-
curl -L -o shift_optimizer.py https://huggingface.co/spaces/naheedakhtar/top2/resolve/main/shift_optimizer.py
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 | |