UNIVERSITÉ DE TECHNOLOGIE DE BELFORT-MONTBÉLIARD

AG41 Challenge 2011Soutenance de projet – P2011

Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit21 juin 2011

Úniversité de Technologie de Belfort-MontbéliardDépartement Informatique

www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Sommaire

1 Environnement de travail

2 Méthode utiliséeAlgorithme

CaractéristiquesFonctionnement général

Solutions initialesRecherche de voisinsDétection de cycles & liste tabou

3 Résultats obtenus

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 2/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Environnement de travail

• Netbeans• Subversion

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 3/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Caractéristiques

• Recherche tabou• Multi-threadé sur plusieurs solutions initiales• Détection de cycles• Durée tabou dynamique• Entièrement déterministe

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 4/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Fonctionnement général

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 5/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Solution initiale 1

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 6/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Solution initiale 2

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 7/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Solution initiale 3

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 8/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Solution initiale 4

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 9/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Recherche de voisins

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 10/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou

Détection de cycles & liste tabou

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 11/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Résultats obtenus

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 12/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Conclusion

L’algorithme fournit :• toujours au moins une solution valable ;• des solutions assez bonnes.

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 13/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Sources

• Études en recherche locale adaptative pour l’optimisationcombinatoire, Isabelle Devarenne ;

• Recherche tabou avec liste candidate adaptative, I.Devarenne,H. Mabed et A. Caminada.

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 14/15 – www.utbm.fr

Environnement de travailMéthode utilisée

Résultats obtenus

Remerciements

Avez-vous des questions ?

AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 15/15 – www.utbm.fr