Chapitre 4 Flashcards
Que veux-dire “TSP” ?
Traveling Salesman Problem
Quels sont les caractéristiques du TSP ?
Il y a un seul véhicule, on a n noeuds avec un dépôt et n-1 clients. Une tournée doit visiter les clients une seule fois. Le véhicule part du dépôt et y revient.
PTV ?
Problèmes de tournées de véhicules
Est-ce que les PTV sont réservés à la logistique ?
Non, ils ne sont pas limités par la logistique : ils ont de nombreuses applictions dans des domaines très variés.
Donner un exemple de PTV
- Les microprocesseurs, fabriqués avec un laser qui grave des transistor microscopiques sur une puce de silicium 1x1cm. Les sites à visiter sont les transistors et le véhicule est l’extremumu du faisceau laser.
- Photographier les villes par satellite : le satellite ne visite pas directement les villes mais doit les survoler dans un certain ordre et pointer ses caméras dessus pour prendre des clichés.
- etc.
Combien y’a-t-il de grands groupes de PTV ?
2
Quels sont les grands groupes de PTV ?
- Problème de tournée sur noeuds
- Problème de tournée sur arc
Quel groupe de PTV est le plus fréquent ?
Le groupe des problèmes de tournée sur noeuds.
Donner un exemple de problème de tournée sur arc
- Collecte de déchets urbains
- Salage des routes
- Inspection de réseaux (conduits d’eau, ligne à haute tension).
En terme de complexité des problèmes d’optimisation combinatoire, que peut on en dire ?
Ce sont des problèmes NP-difficiles
Que signifie NP-Difficile ?
C’est lorsqu’il y a un nombre important de solutions, et on ne connait aucun algorithme de complexité polynomiale.
Vrai ou Faux, pour le TSP (académique) on considère un graphe orienté ?
Faux, dans le cas académique, on considère un graphe non orienté pour le Traveling Salesman Problem.
Pour le TSP, combien y-a t-il de tournées possibles ?
(n-1)!/2
Admettons un TSP avec 17 noeuds. Combien admet-il de tournées possibles dans ce cas de figure ?
(17-1)!/2 = 16!/2 = 1.0461395e+
Donner un benchmark du TSP
TSPLIB de Reinelt
Donner les étapes de l’algorithme de Little
L’algorithme de Little peut être décrit par les étapes suivantes :
-
Initialisation :
- Définir une matrice des coûts initiaux pour les trajets entre les villes à visiter.
- Calculer la borne inférieure initiale (BI) basée sur les coûts des arcs disponibles.
-
Calcul des Coûts :
- Calculer les coûts initiaux pour chaque trajet possible entre les villes.
-
Sélection de l’Arc :
- Choisir un arc avec un coût nul dans la matrice des coûts.
-
Calcul du Regret :
- Calculer le regret pour chaque arc avec un coût nul en comparant les coûts des autres arcs connectés.
-
Sélection de l’Arc avec le Regret Maximum :
- Choisir l’arc avec le plus grand regret par rapport à la borne inférieure.
-
Mise à Jour de la Solution :
- Mettre à jour la solution en ajoutant l’arc sélectionné à la tournée en cours de construction.
-
Répéter les Étapes :
- Répéter les étapes précédentes jusqu’à ce que tous les arcs aient un coût non nul.
-
Finalisation de la Tournée :
- Finaliser la tournée en revenant à la ville de départ pour former un cycle.
-
Évaluation de la Solution :
- Évaluer la qualité de la solution obtenue en fonction du coût total de la tournée.
-
Optimisation basée sur la BI :
- Utiliser la borne inférieure pour élaguer les branches de l’arbre de recherche qui ne peuvent pas conduire à une solution meilleure que la meilleure solution actuelle.
-
Optimisation Locale :
- Appliquer des techniques d’optimisation locale pour améliorer la solution en respectant la borne inférieure.
En intégrant la notion de borne inférieure, l’algorithme de Little devient plus efficace en guidant la recherche vers des solutions potentiellement plus optimales tout en réduisant l’espace de recherche exploré.
