Détail du sujet

12/11/2018 Sujet 5 :  À l'aide, voleur ambulant !
Auteur : Arnaud Liefooghe  Ecrire Site
(Responsable Informatique : Bilel Derbel  Ecrire )
Sujet recherche

Un voleur ambulant a besoin de vous pour planifier sa prochaine série de cambriolages. Il a identifié un certain nombre de villes au sein desquelles il souhaite se rendre, ceci afin de sélectionner un certain nombre d'objets qui y sont disponibles, et ainsi remplir son sac à dos.

Étant données n villes dont les distances deux-à-deux sont connues, m objets ayant chacun un profit et un poids, et un sac à dos ayant une certaine capacité (poids maximum), il faut donc aider le voleur ambulant à identifier une tournée se rendant dans chacune des villes exactement une fois avant de retourner à la ville de départ, ainsi qu'un planning des objets à sélectionner dans chaque ville et à ranger dans le sac à dos, évidemment sans dépasser la capacité du sac. Il est important de noter que le temps que va mettre le voleur pour se rendre d'une ville A à une ville B dépend à la fois de la distance entre ses deux villes, et du poids de son sac à dos au moment du trajet. De même, la valeur des objets sélectionnés diminue au fur et à mesure du temps, c'est-à-dire que la valeur de l'objet au moment de la sélection n'est pas la même qu'à la fin du voyage. Le voleur a pour objectif de minimiser son temps total de déplacement tout en maximisant le profit total qu'il tire des objets sélectionnés.

Ainsi, la combinaison et l'inter-dépendance de deux problèmes classiques de l'optimisation (le problème du voyageur de commerce et le problème du sac à dos) donnent lieu à un problème d'optimisation combinatoire multi-objectif, qu'on vous propose de résoudre dans le cadre de ce projet.


Ainsi, le travail se déroulera suivant le plan détaillé ci-dessous :
0. Cerner les bases du domaine d’application visé (optimisation combinatoire multi-objectif) et se familiariser avec le problème du voleur ambulant (10% du projet)
1. Identifier et prendre en main les instances de la littérature pour le problème du voleur ambulant (10% du projet)
2. Analyser et caractériser les instances et leurs différences (10% du projet)
3. Concevoir et développer une méthode heuristique d'optimisation combinatoire multi-objectif pour le problème du voleur ambulant (20% du projet)
4. Expérimenter la solution algorithmique proposée et étudier son comportement et son efficacité en fonction des instances et de leurs caractéristiques (20% du projet)
5. En fonction des performances observées, revenir au point 3 afin d’affiner la conception (20% du projet)
6. Packaging des différents développements et documentation (10% du projet)


Le candidat idéal devra
- avoir un esprit critique, être motivé et intéressé par l'algorithmique en général et par la résolution de nouveaux problèmes
- maitriser un langage de programmation

Liens associés :
Sujet attribué
Affecté à : Marie Mons [M1-INFO]  Ecrire ,  Gatien Ryckebusch [M1-INFO]  Ecrire 
Soutenance : prévue le 27/05/2019 à 11h00     Salle : M5 A11