Recherche Opérationnelle - Optimisation des tournées de ramassage des déchets ménagers

De Ensiwiki
Aller à : navigation, rechercher

Laboratoire : G-SCOP (http://www.g-scop.grenoble-inp.fr/) Equipe : Optimisation Combinatoire (http://www.g-scop.grenoble-inp.fr/optimisation-combinatoire/?RH=GSCOP_FR-OC) Encadrant : Wojciech.Bienia@grenoble-inp.fr

Etant donné un nombre important de points de collecte des déchets ménagers, il faut déterminer les tournées de ramassage qui minimisent les coûts sur une période donnée. Ces coûts sont liés aux temps de passage, le coût du carburent et l’emploi du personnel (les salaires, les heures supplémentaires etc). La difficulté du problème est due aux nombreuses contraintes. Un camion-benne a sa capacité limitée et ces limites sont exprimées pas seulement en poids maximum autorisé mais aussi en volume. Le temps de travail d’un chauffeur est strictement réglementé. Grâce aux capteurs électroniques, le taux de remplissage des bacs de collecte est connu. Les bacs complètement remplis doivent être vidé obligatoirement mais il est possible de vider un bac partiellement rempli pour optimiser la tournée ou pour retarder le moment de son remplissage total qui impliquerait son vidage obligatoire au moment inopportun. Le problème décrit peut être classifié comme une variante du Vehicle Routing Problem (VRP), appartenant aux problèmes Np-difficiles (à cause notamment des limitations de la benne). La résolution exacte des instances nécessite un temps exponentiel et devient vite non traitable dans la pratique. Il existe beaucoup de méthodes heuristiques et approximatives dont l'efficacité dépend largement des particularités des instances traitées. Le projet comporte plusieurs parties : 1° Modéliser et résoudre le problème sous forme d’un programme linéaire en nombres entiers (avec le logiciel CPLEX) pour déterminer les limites d’une telle démarche. 2° Utiliser des méthodes heuristiques connues et en inventer d’autres pour résoudre des problèmes de grande taille (les instances de test seront fournies). 3° Comparer les résultats des algorithmes heuristiques par rapport à la solution optimale obtenue dans la partie 1° ou, en cas des tailles non traitables par la programmation linéaire en nombres entiers, estimer les écarts d’approximation. Le travail doit être effectué en groupe mais les exigences seront proportionnelles au nombre de membres. Avant d’accepter les candidat(e)s (plusieurs groupes sont envisageables), l’entretien préalable avec l’encadrant est nécessaire.

Wojciech--Bienia 25 septembre 2016 à 16:30 (CEST)