Langage de développement et problème de voyageur de commerce bi-objectif

By 27 February 2014

Implementation et résultats experimentaux – Chapitre V :

I. INTRODUCTION :
II. LANGAGE DE DEVELOPPEMENT ET SYSTEME D’EXPLOITATION :
III. DESCRIPTION DE L’APPLICATION :
IV. CONCLUSION :
CONCLUSION GENERALE

I. Introduction :

Une fois que nous avons définis notre sujet et après avoir installé un environnement de développement, nous arrivons à l’étape de réalisation de notre application, la ou on à fait une description sur le fonctionnement de notre application.

II. Langage de développement et système d’exploitation :

Concernant l’outil de développement de notre application on a utilisé DELPHI comme langage de programmation et WINDOWS 7 comme système d’exploitation.

III. Description de l’application :

Premièrement :

On donne les poids pour les Y1 et Y2 puis On clic sur le bouton charger une configuration pour charger un fichier qui contienne les cordonnés des villes comme il est figuré ci-dessous.

Description de l’application

Par cette formule formule on calcule la distance euclidienne entre les villes, on aura comme résultat une matrice de distance.

Par cette formule formule on calcule le temps nécessaire pour aller de la ville i vers j, on aura comme résultat une matrice de Temps.

Par cette formule formule on calcule la matrice qu’on Apple matrice de décision. D’après cette matrice on peut déterminer le plus court chemin.

Une fois qu’on à déterminé le plus cour chemin on calcule le temps nécessaire pour ce cycle dans la matrice de temps, et la distance nécessaire dons la matrice de distance.

Deuxièmement :

On clic sur le Bouton Tester pour tester tout les chemins possible et enregistre le plus court comme il est montrer sur la figure ci-dessous.

Bouton Tester pour tester tout les chemins possible

Troisièmement :

On clic sur le Bouton Solution pour dessiner le cycle et afficher la distance et le temps pour se cycle comme il est montrer sur la figure ci-dessous.

afficher la distance et le temps

IV. Conclusion :

Nous avons présenté une approche basé sur le poids ou bien la probabilité de l’un des deux objectif (temps et distance) pour résoudre le problème du voyageur de commerce (TSP), l’algorithme ci-dessus est implémenté en Delphi et exécuté sur plusieurs instances symétriques de la bibliothèque TSPLIB de tailles variant.

Conclusion générale

Dans ce mémoire, nous avons constaté les capacités de l’optimisation par colonies de fourmis pour la résolution des problèmes d’optimisation combinatoire et multi-objectif qui consiste donc à optimiser simultanément plusieurs fonctions, en effet La notion de solution optimale unique dans l’optimisation uni-objectif disparait pour les problèmes d’optimisation multi-objectif.

Nous avons constaté que cette méta-heuristique (ACO) l’une des tâches principales est d’encoder notre problème à résoudre sous la forme d’un problème de recherche d’un chemin optimal dans un graphe complet, appelé graphe de construction, où la faisabilité est dénie en respectant un ensemble de contraintes.

L’approche proposée est basée sur une solution à l’aide de choix d’importance ou de poids initialisé par le décideur concernant les deux objectifs le temps et la distance.

Le PVC fournit un exemple d’étude d’un problème NP-complets dont les méthodes de résolution peuvent s’appliquer à d’autres problèmes de mathématiques discrète, il a aussi des applications qui sont nombreux notamment problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d’ordonnancement, même pour certains problèmes rencontrés dans l’industrie peuvent se modéliser sous la forme d’un problème de voyageur de commerce.

La Résolution du Problème de Voyageurs de Commerce Bi-Objectifs par La Métaheuristique d’Optimisation par Colonie de Fourmis Artificielles
Présenté pour l’obtention du diplôme de MASTER Option Réseaux et Multimédia
Département de Mathématique et d’Informatique