Génération de colonnes pour le balayage printanier des rues

La fin de la saison hivernale marque le lancement du grand ménage printanier, durant lequel des milliers de kilomètres de routes doivent être nettoyées pour éliminer les résidus laissés par l’hiver, notamment les abrasifs et le sable. Ces opérations sont essentielles pour garantir la sécurité et la propreté des infrastructures routières. Réalisées dans un laps de temps très court, elles représentent un défi logistique important pour les gestionnaires chargés de leur planification. Face à ce défi, se pose un problème crucial : comment organiser le balayage des rues à l’aide d’une flotte de véhicules et de plusieurs dépôts, tout en minimisant les coûts et les déplacements à vide ? Ce problème, connu sous le nom de problème de tournée de véhicules pour le balayage printanier, vise à planifier des itinéraires permettant de couvrir l’ensemble du réseau routier dans un temps total minimal, en respectant un ensemble de contraintes : la durée maximale des quarts de travail et la continuité entre les quarts. Deux modélisations ont été proposées dans la littérature : celle par arcs, détaillée mais très coûteuse même sur de petites instances, et celle par nœuds, plus compacte, mais avec une relaxation continue de faible qualité. Cette étude cherche à améliorer cette relaxation pour obtenir de bonnes solutions en un temps raisonnable. Pour cela, une formulation mathématique basée sur les chemins a été développée, où chaque variable représente une route.