Exemple d'Application du Problème du Voyageur de Commerce (TSP) avec OpenStreetMap

Objectif

Créer une application web pour résoudre le problème du voyageur de commerce (TSP) en utilisant une heuristique du plus proche voisin. L'application utilisera OpenStreetMap pour afficher les itinéraires.

Étapes de l'implémentation

  1. Initialiser une application web avec une carte OpenStreetMap.
  2. Ajouter des points sur la carte représentant les villes.
  3. Implémenter l'algorithme du plus proche voisin pour résoudre le TSP.
  4. Afficher l'itinéraire optimal sur la carte.

Prérequis

  • Connaissance de base de JavaScript, HTML et CSS.
  • Utilisation de la bibliothèque Leaflet.js pour OpenStreetMap.
  • Utilisation de la bibliothèque leaflet-routing-machine pour le calcul des itinéraires.

Code Complet

1. Structure HTML
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Traveling Salesman Problem with OpenStreetMap</title>
    <link rel="stylesheet" href="https://unpkg.com/leaflet/dist/leaflet.css" />
    <style>
        #map {
            height: 100vh;
        }
    </style>
</head>
<body>
    <div id="map"></div>

    <script src="https://unpkg.com/leaflet/dist/leaflet.js"></script>
    <script src="https://unpkg.com/leaflet-routing-machine/dist/leaflet-routing-machine.js"></script>
    <script src="script.js"></script>
</body>
</html>
2. Script JavaScript

Créez un fichier script.js et ajoutez le code suivant :

const map = L.map('map').setView([48.8566, 2.3522], 6); // Centré sur Paris, France

L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
    attribution: '© OpenStreetMap contributors'
}).addTo(map);

const cities = [
    { name: "Paris", coords: [48.8566, 2.3522] },
    { name: "Lyon", coords: [45.7640, 4.8357] },
    { name: "Marseille", coords: [43.2965, 5.3698] },
    { name: "Nice", coords: [43.7102, 7.2620] },
    { name: "Toulouse", coords: [43.6047, 1.4442] }
];

const markers = cities.map(city => L.marker(city.coords).addTo(map).bindPopup(city.name));

const tspNearestNeighbor = (points) => {
    const n = points.length;
    const visited = new Array(n).fill(false);
    const path = [];
    let current = 0;
    let totalDistance = 0;

    visited[current] = true;
    path.push(current);

    for (let i = 1; i < n; i++) {
        let nearest = -1;
        let minDist = Infinity;

        for (let j = 0; j < n; j++) {
            if (!visited[j]) {
                const dist = map.distance(points[current].coords, points[j].coords);
                if (dist < minDist) {
                    minDist = dist;
                    nearest = j;
                }
            }
        }

        visited[nearest] = true;
        path.push(nearest);
        current = nearest;
        totalDistance += minDist;
    }

    // Retour à la ville de départ
    totalDistance += map.distance(points[current].coords, points[0].coords);
    path.push(0);

    return { path, totalDistance };
};

const { path } = tspNearestNeighbor(cities);

const routePoints = path.map(index => cities[index].coords);

L.Routing.control({
    waypoints: routePoints.map(coords => L.latLng(coords)),
    createMarker: function() { return null; },
    lineOptions: { styles: [{ color: 'blue', weight: 4 }] }
}).addTo(map);

Explication du Code

  1. Initialisation de la Carte : La carte est centrée sur Paris, France, avec les coordonnées [48.8566, 2.3522].

  2. Ajout des Villes : Un tableau cities contient les noms et coordonnées des villes. Les villes sont ajoutées à la carte avec des marqueurs.

  3. Implémentation de l'Algorithme du Plus Proche Voisin : La fonction tspNearestNeighbor implémente l'heuristique du plus proche voisin pour trouver un chemin approximatif pour le TSP. Elle calcule les distances entre les villes en utilisant map.distance de Leaflet.

  4. Calcul de l'Itinéraire Optimal : Le chemin trouvé par l'algorithme est utilisé pour créer un itinéraire. La bibliothèque leaflet-routing-machine est utilisée pour afficher cet itinéraire sur la carte.

  5. Affichage de l'Itinéraire : Les points de l'itinéraire sont passés à L.Routing.control pour dessiner l'itinéraire sur la carte.

Conclusion

Cette application web utilise Leaflet.js pour afficher une carte OpenStreetMap et résout le problème du voyageur de commerce en utilisant une heuristique du plus proche voisin. L'algorithme approximatif permet de trouver un chemin proche de l'optimal en temps raisonnable, illustrant comment les algorithmes probabilistes peuvent être appliqués à des problèmes réels comme l'optimisation des itinéraires de livraison et la planification des circuits touristiques.

Modifié le: vendredi 7 juin 2024, 07:48