Logiciel de recherche
du plus court chemin

Présentation du projet

🎯 Objectifs du projet

Dans le cadre de la SAE 201-202-205, nous devions concevoir une application Java capable de résoudre le problème du voyageur de commerce (TSP). Ce projet de groupe de 3 personnes avait pour but de nous faire découvrir les algorithmes d'optimisation et de nous initier au développement d'interfaces graphiques avancées.

L'objectif principal était de créer un système capable d'optimiser des parcours en utilisant différents algorithmes, tout en proposant une interface graphique interactive permettant de visualiser les résultats en temps réel. L'application devait gérer à la fois des coordonnées euclidiennes pour des problèmes mathématiques abstraits, et des coordonnées géographiques pour des applications concrètes comme l'optimisation de tournées de livraison.

Ma contribution personnelle au projet

Dans cette équipe de 3 développeurs, j'ai pris en charge les aspects les plus techniques du projet :

• Gestion des distances : Implémentation complète du gestionnaire de distances avec matrice d'adjacence et calculs géographiques (formule de Haversine)
• Algorithmes d'optimisation : Développement des algorithmes 2-opt, 3-opt et de la recherche locale itérée (ILS)
• Algorithme de recherche du meilleur chemin : Conception de la méta-heuristique combinant tous les algorithmes pour trouver la solution optimale
• Interface utilisateur avancée : Développement des composants graphiques personnalisés et de l'interaction temps réel
• Tests et validation : Création de la suite de tests unitaires JUnit pour valider tous les algorithmes

Mes coéquipières Leia et Emy ont respectivement travaillé sur les algorithmes de construction de base (Insertion, Glouton) et la gestion d'erreurs, tandis que j'ai concentré mes efforts sur les optimisations avancées et l'architecture technique.

Le programme peut importer des fichiers au format TSPLIB standard ou générer des points aléatoirement pour les tests. Il intègre également un système de validation robuste qui guide l'utilisateur et évite les erreurs d'utilisation courantes.

Vue d'ensemble du logiciel montrant les fonctionnalités principales

Technologies et architecture technique

Architecture modulaire du projet

Nous avons structuré le projet selon le pattern MVC (Modèle-Vue-Contrôleur) avec une séparation claire des responsabilités. Cette approche nous a permis de travailler en parallèle sans conflits et de maintenir un code propre et évolutif.

L'architecture comprend cinq modules principaux :

• Model : Entités métier (PointCoordonnee, Arete, Fichier) gérant les données de base
• Algo : Algorithmes TSP et gestionnaire de distances avec toutes les optimisations
• Core : Logique métier centrale, lecture de fichiers TSPLIB et coordination générale
• Vue : Interface utilisateur Swing avec composants personnalisés et interactions
• Test : Tests unitaires JUnit pour validation de tous les composants

Technologies utilisées

Java 11 : Le projet utilise Java 11 avec les fonctionnalités avancées de programmation orientée objet. Nous avons exploité les collections Java, les streams pour le traitement des données, et les patterns de conception comme Strategy pour l'interchangeabilité des algorithmes.

Swing et AWT : Pour l'interface graphique, nous avons développé des composants Swing personnalisés avec des interactions avancées. L'interface inclut des panneaux de configuration, des zones de visualisation interactives, et des menus contextuels pour une expérience utilisateur optimale.

JXMapViewer2 : Cette bibliothèque nous a permis d'intégrer des cartes géographiques interactives pour la visualisation des coordonnées géographiques. Elle supporte le zoom, le déplacement, et l'affichage de marqueurs personnalisés pour représenter les points du parcours.

JUnit : Framework de tests utilisé pour valider le bon fonctionnement de nos algorithmes. Les tests couvrent les cas nominaux, les cas limites, et vérifient les propriétés mathématiques des optimisations.

Optimisations de performance

Nous avons implémenté plusieurs optimisations pour améliorer les performances de l'application :

• Matrice de distances pré-calculée : Évite les recalculs répétitifs lors des optimisations
• Structures de données optimisées : Utilisation d'ArrayList pour les parcours et de HashMap pour les caches
• Algorithmes efficaces : Implémentations optimisées du 2-opt et 3-opt avec arrêt anticipé
• Gestion mémoire : Réutilisation d'objets et nettoyage automatique pour les gros jeux de données

Interface et sélection d'algorithmes

L'application propose un menu intuitif pour choisir parmi plusieurs algorithmes de construction de parcours. Chaque algorithme peut être combiné avec des optimisations locales pour améliorer la qualité de la solution finale. Cette approche modulaire permet à l'utilisateur de tester différentes stratégies selon ses besoins spécifiques.

Interface de sélection permettant de combiner algorithmes de construction et optimisations locales

Algorithmes de construction disponibles

L'application implémente plusieurs approches pour construire un parcours initial :

• Algorithme glouton : Construction séquentielle en choisissant toujours la ville la plus proche non visitée
• Algorithme d'insertion : Insertion progressive des villes à la position qui minimise l'augmentation du coût total
• Algorithme de Christofides simplifié : Approche basée sur l'arbre couvrant minimal avec amélioration heuristique
• Génération aléatoire : Création de parcours aléatoires pour servir de base aux optimisations

Interaction temps réel avec la carte

Une des fonctionnalités les plus innovantes que j'ai développées est la possibilité d'ajouter des points directement en cliquant sur la carte. Cette interaction nécessitait de gérer les événements souris, de recalculer automatiquement les distances et de mettre à jour l'affichage en temps réel.

Le système détecte automatiquement le type de coordonnées (euclidiennes ou géographiques) et applique les formules de calcul appropriées. Pour les coordonnées géographiques, j'ai implémenté la formule de Haversine qui tient compte de la courbure terrestre.

Mon algorithme de recherche du meilleur chemin

Principe général de la méta-heuristique

J'ai conçu un algorithme intelligent appelé MettreAJourMeilleurParcours() qui combine tous les algorithmes disponibles pour garantir la meilleure solution possible. Cette méta-heuristique exécute systématiquement tous les algorithmes de construction puis les compare pour sélectionner le parcours optimal.

L'algorithme fonctionne en trois phases distinctes : exécution de tous les algorithmes de base, application de l'optimisation avancée sur le meilleur résultat, puis sélection finale du parcours ayant la distance totale minimale.

Phase 1 : Exécution exhaustive des algorithmes

L'algorithme commence par réexécuter tous les algorithmes de construction disponibles, même s'ils ont déjà été utilisés précédemment. Cette approche garantit que l'ajout de nouveaux points ou la modification des données est prise en compte :

// Réexécution systématique de tous les algorithmes
Algorithmes.ExecuterAlgorithme("Aleatoire");
Algorithmes.ExecuterAlgorithme("Christofides");
Algorithmes.ExecuterAlgorithme("Glouton");
Algorithmes.ExecuterAlgorithme("Insertion");
Algorithmes.ExecuterAlgorithme("OptiAlterneEtRechercheLocale");

Chaque algorithme génère un parcours complet qui est stocké dans la classe SolutionGlobale pour comparaison ultérieure.

Phase 2 : Algorithme d'optimisation alternée avancée

L'algorithme OptiAlterneEtRechercheLocale() que j'ai développé représente la partie la plus sophistiquée du système. Il commence par identifier le meilleur parcours parmi ceux générés par les algorithmes de construction :

// Évaluation comparative des parcours de base
ArrayList<PointCoordonnee> meilleur = parcoursAleatoire;
double meilleurScore = GestionnaireDistances.CalculDistanceTotale(meilleur);

// Comparaison avec tous les autres parcours
if (scoreGlouton < meilleurScore) {
    meilleur = parcoursGlouton;
    meilleurScore = scoreGlouton;
}

Une fois le meilleur parcours initial identifié, l'algorithme applique une optimisation en deux étapes :

Étape 1 : Optimisation alternée 2-opt/3-opt

Ma méthode optimisationAlternee() applique de manière intelligente les algorithmes 2-opt et 3-opt avec une stratégie d'alternance :

while (amelioration && (System.currentTimeMillis() - tempsDepart < LIMITE_TEMPS)) {
    ancienCout = GestionnaireDistances.CalculDistanceTotale(parcours);
    Algorithmes.twoOpt(parcours);
    nouveauCout = GestionnaireDistances.CalculDistanceTotale(parcours);
    
    if (ancienCout <= nouveauCout) {
        Algorithmes.threeOpt(parcours);
        nouveauCout = GestionnaireDistances.CalculDistanceTotale(parcours);
        if (ancienCout <= nouveauCout) {
            amelioration = false;
        }
    }
}

L'algorithme commence toujours par un 2-opt (plus rapide). Si aucune amélioration n'est détectée, il tente un 3-opt (plus coûteux mais plus puissant). Cette stratégie optimise le rapport qualité/temps de calcul.

Étape 2 : Recherche locale itérée (ILS)

Pour éviter les optimums locaux, j'ai implémenté une recherche locale itérée avec perturbation Double Bridge :

while (nbTentatives < maxTentatives) {
    ArrayList<PointCoordonnee> candidat = new ArrayList<>(meilleur);
    doubleBridge(candidat);  // Perturbation
    twoOpt(candidat);        // Optimisation locale
    
    if (coutCandidat < coutMeilleur) {
        meilleur = candidat;
        nbTentatives = 0; // Réinitialisation si amélioration
    } else {
        nbTentatives++;
    }
}

La perturbation Double Bridge que j'ai programmée découpe le parcours en 5 segments et les recombine selon un schéma spécifique (1→4→3→2→5) pour explorer de nouvelles régions de l'espace de solutions.

Phase 3 : Sélection finale du meilleur parcours

La dernière phase compare tous les parcours générés et optimisés pour retourner celui ayant la distance totale minimale :

for (ArrayList<PointCoordonnee> parcours : tousLesParcours) {
    if (parcours != null && !parcours.isEmpty()) {
        double distance = GestionnaireDistances.CalculDistanceTotale(parcours);
        if (distance < meilleureDistance) {
            meilleureDistance = distance;
            meilleur = parcours;
        }
    }
}

Optimisations de performance implémentées

J'ai intégré plusieurs optimisations pour garantir des performances acceptables :

• Limite de temps : Les optimisations 2-opt et 3-opt sont limitées à 60 et 20 secondes respectivement
• Limite d'itérations : Le 2-opt s'arrête après 100 000 itérations pour éviter les boucles infinies
• Matrice de distances pré-calculée : Tous les calculs utilisent une matrice en cache pour éviter les recalculs
• Arrêt anticipé : Les algorithmes s'arrêtent dès qu'aucune amélioration n'est détectée

Cette approche multicouche garantit d'obtenir une solution de très bonne qualité en combinant la robustesse des algorithmes de construction avec la puissance des optimisations locales et la capacité d'exploration de la recherche itérée.

Visualisation des données

Analyse des distances

Une fois l'itinéraire calculé, l'application génère une visualisation complète de la matrice des distances, permettant d'analyser en détail les relations spatiales entre tous les points du parcours.

Exemple concret : Parcours R1

Voici un exemple d'un parcours R1 avec sa matrice des distances :

Tests et validation

J'ai développé une suite de tests unitaires JUnit pour valider le bon fonctionnement de tous nos algorithmes. Nous avons testé nos implémentations sur plusieurs instances de référence de la TSPLIB pour s'assurer de la validité de nos résultats.

Chaque algorithme est testé avec différents jeux de données, et nous vérifions que les parcours générés sont valides (chaque point visité exactement une fois).

Gestion d'erreurs et robustesse

Système de validation des données

Nous avons accordé une attention particulière à la robustesse du programme en développant un système complet de validation qui guide l'utilisateur et évite les erreurs d'utilisation courantes. Le système détecte automatiquement les problèmes les plus fréquents et affiche des messages d'erreur clairs pour aider l'utilisateur à corriger ses actions.

La validation s'applique à plusieurs niveaux : vérification de la validité des fichiers importés, contrôle de la cohérence des coordonnées, validation des sélections d'algorithmes, et détection des configurations impossibles. Cette approche préventive améliore considérablement l'expérience utilisateur.

Validation des points et données

Détection automatique des problèmes de données avec message explicite

Assistance à la sélection d'algorithmes

Avertissements intelligents pour guider l'utilisateur dans ses choix

Résultats et performances obtenus

Qualité des solutions générées

L'application démontre d'excellentes performances sur diverses instances TSP. L'algorithme de Christofides combiné avec les optimisations locales (2-opt et 3-opt) produit des résultats proches de l'optimum sur les petites instances et des approximations très satisfaisantes sur les plus grandes.

Performances et validation

L'évaluation sur plusieurs instances de référence TSPLIB a validé l'efficacité de notre approche. Mon algorithme de recherche du plus court chemin s'est distingué en se classant dans le top 3 des plus performants de la promotion d'étudiants :

• Amélioration moyenne : 10-20% par rapport aux solutions gloutonnes initiales
• Temps de calcul : Moins de 2 secondes pour 100 points
• Scalabilité : Performances optimales jusqu'à 200 points, dégradation progressive au-delà
• Stabilité : Résultats reproductibles et cohérents

Bilan personnel

Ce projet m'a permis de maîtriser les algorithmes d'optimisation combinatoire et de développer une interface graphique avancée en Java. L'approche rigoureuse avec tests unitaires et validation sur instances de référence m'a initié aux bonnes pratiques de développement scientifique.