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