Chapitre 4

Question 1

Que veux-dire “TSP” ?

Answer 1

Traveling Salesman Problem

Question 2

Quels sont les caractéristiques du TSP ?

Answer 2

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.

Question 3

PTV ?

Answer 3

Problèmes de tournées de véhicules

Question 4

Est-ce que les PTV sont réservés à la logistique ?

Answer 4

Non, ils ne sont pas limités par la logistique : ils ont de nombreuses applictions dans des domaines très variés.

Question 5

Donner un exemple de PTV

Answer 5

• 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.

Question 6

Combien y’a-t-il de grands groupes de PTV ?

Answer 6

2

Question 7

Quels sont les grands groupes de PTV ?

Answer 7

• Problème de tournée sur noeuds
• Problème de tournée sur arc

Question 8

Quel groupe de PTV est le plus fréquent ?

Answer 8

Le groupe des problèmes de tournée sur noeuds.

Question 9

Donner un exemple de problème de tournée sur arc

Answer 9

• Collecte de déchets urbains
• Salage des routes
• Inspection de réseaux (conduits d’eau, ligne à haute tension).

Question 10

En terme de complexité des problèmes d’optimisation combinatoire, que peut on en dire ?

Answer 10

Ce sont des problèmes NP-difficiles

Question 11

Que signifie NP-Difficile ?

Answer 11

C’est lorsqu’il y a un nombre important de solutions, et on ne connait aucun algorithme de complexité polynomiale.

Question 12

Vrai ou Faux, pour le TSP (académique) on considère un graphe orienté ?

Answer 12

Faux, dans le cas académique, on considère un graphe non orienté pour le Traveling Salesman Problem.

Question 13

Pour le TSP, combien y-a t-il de tournées possibles ?

Answer 13

(n-1)!/2

Question 14

Admettons un TSP avec 17 noeuds. Combien admet-il de tournées possibles dans ce cas de figure ?

Answer 14

(17-1)!/2 = 16!/2 = 1.0461395e+

Question 15

Donner un benchmark du TSP

Answer 15

TSPLIB de Reinelt

Question 16

Donner les étapes de l’algorithme de Little

Answer 16

L’algorithme de Little peut être décrit par les étapes suivantes :

1. 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.
2. Calcul des Coûts :
   
   • Calculer les coûts initiaux pour chaque trajet possible entre les villes.
3. Sélection de l’Arc :
   
   • Choisir un arc avec un coût nul dans la matrice des coûts.
4. Calcul du Regret :
   
   • Calculer le regret pour chaque arc avec un coût nul en comparant les coûts des autres arcs connectés.
5. Sélection de l’Arc avec le Regret Maximum :
   
   • Choisir l’arc avec le plus grand regret par rapport à la borne inférieure.
6. Mise à Jour de la Solution :
   
   • Mettre à jour la solution en ajoutant l’arc sélectionné à la tournée en cours de construction.
7. 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.
8. Finalisation de la Tournée :
   
   • Finaliser la tournée en revenant à la ville de départ pour former un cycle.
9. Évaluation de la Solution :
   
   • Évaluer la qualité de la solution obtenue en fonction du coût total de la tournée.
10. 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.
11. 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é.