Projet de spécialité - Optimisation des tournées de ramassage des déchets ménagers

De Ensiwiki
Aller à : navigation, rechercher

Projet de spécialité 2018-2019 suivi par Wojciech.Bienia@grenoble-inp.fr

Contexte

Étant 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 carburant 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.

Méthodes

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.

Objectifs

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.

Contact

Avant d’accepter les candidat(e)s (plusieurs groupes sont envisageables), l’entretien préalable avec l’encadrant est nécessaire.

Wojciech Bienia