4 Presentations

• 
  10:30 AM - 10:55 AM

  Resource Allocation Optimization in Crowdsensed Parking Availability Data Collection

  • Elham Heydarigharaei, presenter,
  • Mehdi Nourinejad,

  Efficient parking occupancy detection is crucial for reducing congestion and optimizing mobility. Traditional methods, such as in-ground sensors and stationary cameras, are often expensive and difficult to scale.
  In contrast, mobile sensing devices, such as dashcams and ultrasonic sensors mounted on vehicles, offer a
  more flexible and cost-effective alternative. However, achieving comprehensive and efficient data collection
  requires the strategic deployment of these mobile sensors to balance accuracy, coverage, and operational costs. This paper presents an optimization framework for crowdsensed parking data collection that determines the optimal number of mobile sensing units and their routes. Unlike previous studies, which typically focus on either sensor allocation or path planning in isolation, our approach integrates both components while incorporating minimum and maximum revisitation thresholds to ensure data accuracy without excessive redundancy. The model represents the city as a graph of nodes and minimizes the total travel time of sensing units while maintaining the required data collection frequency. We develop a heuristic algorithm that efficiently approximates the optimal solution. The algorithm first applies K-Means clustering to partition the city into routes. Within each route, the Nearest Neighbor Algorithm determines the optimal sequence of visits, minimizing total travel distance. A linear resource allocation model then assigns the optimal number of sensing units per route, subject to headway constraints and the total number of available sensing units. To further refine the heuristic solution, we incorporate Lagrangian-inspired swapping heuristics that iteratively adjust node assignments within and between routes to improve efficiency. Numerical experiments demonstrate that our heuristic algorithm produces high-quality solutions with significantly reduced computational costs compared to the exact model. Our framework efficiently scales with city size, supports different sensing technologies, and enhances real-time parking monitoring for smart mobility solutions.

• 
  10:55 AM - 11:20 AM

  Optimisation de la confection des horaires des résidents par modélisation mathématique

  • Amine Bouzid, presenter, CIRRELT-FSA-ULaval
  • Rekik Monia, Université Laval

  Cette recherche propose une méthode d’optimisation pour la confection des horaires des résidents en médecine dans les Groupes de Médecine de Famille (GMF). L’objectif est d’automatiser le processus de planification en remplaçant les procédures manuelles par des modèles de Programmation Linéaire en Nombres Entiers Mixtes (MILP). Le problème est décomposé en plusieurs périodes et blocs, tenant compte de la typologie des résidents selon leur année et leur affectation. Chaque résident doit réaliser un nombre précis d’occurrences pour diverses tâches tout en respectant des contraintes temporelles et de qualification. Les modèles MILP, résolus avec des solveurs tels que CoinBC et CPLEX, garantissent une répartition équitable et équilibrée des tâches. Des tests sur des cas réels, issus d’un partenariat avec la Clinique Maizerets – GMF universitaire, confirment l’efficacité de la solution proposée. Cette approche permet ainsi de réduire la charge administrative et d’améliorer la qualité des horaires, ouvrant la voie à une intégration plus large dans la gestion des effectifs en santé.

• 
  11:20 AM - 11:45 AM

  Nurse Scheduling with built-in Flexibility

  • Flore Caye, presenter, Polytechnique Montréal
  • Antoine Legrain, GERAD - Polytechnique Montréal

  The nurse scheduling problem (NSP) involves assigning nurses to shifts while balancing institutional staffing requirements and individual preferences. Traditional approaches often produce rigid schedules that do not account for unforeseen last-minute constraints faced by nurses. To address this, we introduce novel flexibility mechanisms: shift flips and nurse swaps.

  A shift flip allows a nurse to interchange a working day with a day off, provided that the new schedule remains feasible. A nurse swap extends this concept by allowing two nurses to exchange assignments, ensuring mutual benefit without compromising staffing needs.

  We first solve the NSP without flexibility using a Column Generation algorithm to generate individual rosters. Because flips and swaps have to be mutually beneficial, their pricing cannot be embedded in the Column Generation framework.

  Then, a preprocessing step lists for each roster all the feasible flips and swaps. We formulate a mixed-integer programming (MIP) model, composed of the column generation restricted master problem to which is added a set of flexibility constraints. The model ensures a minimum level of swap opportunities while optimizing overall scheduling costs and respecting demand constraints.

  We propose different swap pricing strategies and analyse the balance between flexibility and operational costs. Experimental results demonstrate the possibility of incorporating flexibility without being detrimental to operating costs.

  By embedding these concepts into scheduling frameworks, we provide a practical solution for hospitals and healthcare institutions seeking to improve both efficiency and staff well-being.

• 
  11:45 AM - 12:10 PM

  The resource utilization cost problem

  • Fayez Boctor, presenter, Université Laval

  This talk introduces a new project scheduling problem called the resource utilization cost problem (RUCP), proposes a mixed-integer linear formulation and develops a biased genetic solution algorithm to solve it. A computational experiment is reported to assess the efficiency of the proposed genetic algorithm.