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.

Abstract

The end of the winter season marks the beginning of the spring street sweeping operations, during which thousands of kilometers of roads must be cleaned to remove winter residues such as abrasives and sand. These operations are essential to ensure the safety and cleanliness of road infrastructure. Carried out in a very short space of time, they represent a major logistical challenge for the managers in charge of planning them. This raises a crucial question: how can street sweeping be efficiently organized using a fleet of vehicles and multiple depots, while minimizing costs and empty trips? This problem, known as the Vehicle Routing Problem for Spring Street Sweeping, aims to design routes that cover the entire road network within a minimal total duration, while satisfying a set of constraints, such as the maximum duration of work shifts and the continuity between shifts. Two modeling formulations have been proposed in the literature: arc-based formulations, which are detailed but computationally expensive even on small instances, and node-based formulations, which are more compact but suffer from weak continuous relaxations. This study seeks to improve the relaxation to obtain high-quality solutions within reasonable computation times. To this end, a path-based mathematical formulation was developed, where each variable represents a route.