4 présentations

• 
  15h30 - 15h55

  Génération de colonnes pour la planification du balayage printanier

  • Fairouz Mansouri, prés., Polytechnique Montréal

  À la fin de l’hiver, les municipalités doivent organiser le balayage de l’ensemble du réseau routier afin d’éliminer les résidus abrasifs et d’assurer la sécurité routière. Ce besoin opérationnel, à réaliser dans un délai restreint et avec des ressources limitées, peut être modélisé comme un problème de tournée de véhicules pour le balayage printanier, qui vise à planifier les itinéraires d’une flotte partant de plusieurs dépôts, tout en minimisant les coûts et en respectant les contraintes opérationnelles, notamment la durée maximale des quarts de travail et leur continuité. Dans la littérature, deux modélisations ont été proposées : par arcs (détaillée mais coûteuse) et par nœuds (plus compacte mais offrant des relaxations de faible qualité). Nous proposons une approche alternative basée sur une modélisation par chemins. Le problème est résolu par la méthode Branch-and-Price, avec génération de routes initiales via une heuristique inspirée de GRASP. Les expérimentations menées sur plusieurs instances, incluant un cas réel à Victoriaville, Québec, ont démontré des gains importants, avec une borne inférieure en moyenne 20 fois meilleure que celle de CPLEX, et un temps de calcul réduit de 3600 à 406 secondes.

• 
  15h55 - 16h20

  An Event-Based Approach to the Recycling Skips Pick-Up and Delivery Problem

  • Hani Zbib, prés., ESG - UQAM

  The recycling skips pickup and delivery problem arises in the context of transporting large metal containers (known as skips) used for collecting various types of recyclable materials at recycling centers (e.g., textiles, tires, iron). Each transport request involves picking up a full skip from a recycling center, transporting it to its assigned treatment facility for emptying, and subsequently delivering the empty skip back to its original location. The tractors performing the transportation can carry up to two skips at a time, in any sequence, and must complete their routes within a specified workday duration limit. The objective of the problem is to determine a set of least-cost routes that satisfy all transport requests while minimizing total tractor usage and travel costs, subject to vehicle capacity and route duration constraints. While this problem has been studied previously, we propose an alternative event-based formulation, in which each key operation (pickup, emptying, and delivery) is represented as a discrete event that updates the state of each vehicle (current load and location). This approach provides a structured and flexible way to capture the sequencing of operations performed by each tractor while implicitly ensuring that constraints related to vehicle capacity and route duration are respected.

• 
  16h20 - 16h45

  Solving the Mixed Capacitated Arc Routing Problem with Intermediate Facilities and Stochastic Demands

  • Juan Sebastian Riveros Perez, prés., HEC Montréal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Jorge Mendoza, HEC Montréal

  Municipal waste collection in urban areas presents complex logistical challenges due to fluctuating demand, operational constraints, and mixed street network structures. This study introduces and addresses the Mixed Capacitated Arc Routing Problem with Intermediate Facilities and Stochastic Demands (MCARP-IF-SD)—a generalization of the classical CARP that integrates three critical real-world features: stochastic service demands, mandatory visits to intermediate facilities (e.g., dump sites), and the use of mixed graphs. Motivated by a real-world case study in Longueuil, Canada, this work proposes a two-index mixed-integer programming formulation for the deterministic version of the problem and extends it into a two-stage stochastic programming model with analytically defined recourse costs. These theoretical developments are complemented by a data-driven instance generation procedure based on operational GPS and dump-site records. The resulting framework bridges key gaps in the arc routing literature and lays the groundwork for scalable, practical decision-support tools in sustainable urban waste logistics.

• 
  16h45 - 17h10

  Optimization of snow removal operations on sidewalks

  • Chahid Ahabchane, prés., Polytechnique Montréal

  Winter maintenance is essential for safe urban mobility, but represents a significant budgetary expense, especially in snow-prone regions. This research addresses the optimization of sidewalk snow removal, a task often overlooked compared to road plowing. We conduct a comparative analysis with traditional road snow removal. We propose an Arc Routing Problem model with multiple passes and priorities constraints. To address the computational complexity of this optimization problem, we implement metaheuristic algorithms. These algorithms are applied to a real-world case study, utilizing data from the City of Rouyn-Noranda, with the primary objectives of minimizing operational costs and significantly enhancing service quality. By providing a data-driven approach to sidewalk snow removal, this research aims to offer municipalities a practical and efficient tool for improving winter mobility.