Ce mémoire présente la conception et l'implémentation d'un logiciel d'aide à la décision (Mythos), ayant comme but l'optimisation d'un problème de ramassage scolaire où chaque étudiant est soumis à des contraintes horaires. La conception de ce logiciel repose sur une réduction du problème initial en une généralisation du problème de coloration des nœuds d'un graphe non-orienté à l'aide d'un algorithme de calcul du plus court chemin dans un graphe orienté. Le problème de coloration des nœuds d'un graphe étant de nature NP-Complet, l'utilisation d'une heuristique pour sa résolution nous a permis d'obtenir des résultats assez étonnants pour des problèmes de taille. L'heuristique utilisée repose sur un hybride du recuit simulé. Cette heuristique produit des résultats meilleurs que ceux qui ont été précédemment présentés dans la littérature concernant les problèmes de collecte, en général. Le logiciel a été implémenté en utilisant le langage basé sur objets "Visual Basic 3.0 pour MS-Windows".
- recuit simulé
- heuristique
- optimisation combinatoire
- problèmes de transport
- NP-Complet
- coloration d'un graphe
- plus court chemin dans un graphe
Développement d'un SIAD sous Windows basé sur la méthode du Recuit Simulé pour l'optimisation d'un problème de transport
Christodoulidis, C. (Auteur), Delhaye, M. (Auteur). 1994
Student thesis: Master types › Master en sciences informatiques