Un modèle mathématique peut permettre de modéliser un problème complexe pour lequel les seuls algorithmes connus fournissant des solutions optimales sont de la nature "essayer-toutes-les-possibilités". Un tel problème célèbre est connu sous le nom de "problème du voyageur de commerce" [angl. travelling salesman problem; all. Problem des Handlungsreisenden].
Un voyageur de commerce doit rendre régulièrement visite aux clients de son département. Sa clientèle étant répartie dans N localités différentes de sa région, y compris son domicile, il constate un jour que ses frais de route sont relativement élevés et surtout qu'ils diffèrent considérablement d'une tournée à l'autre.
Il finit par s'adresser à un informaticien pour qu'il lui rédige un programme permettant de minimiser ses frais de route. Une première version de l'algorithme pourrait donc être :
(1) Minimiser les frais de route.
Cette première formulation trop vague ne permet guère de reconnaître le vrai problème à résoudre. Ainsi par exemple les données d'entrée (représentées ici par les causes des frais) ne sont pas mentionn 9‚es du tout. Une deuxième approche consiste donc à essayer de dégager des informations supplémentaires sur le champ de données en entrée. Finalement, cette deuxième étape fait savoir à l'informaticien que la totalité des frais de route se compose :
• des frais d'essence pour le trajet en voiture et,
• des frais de logement pour la nuit.
Ainsi, l'action
(1) Minimiser les frais de route.
peut être affinée en
(1.1) Minimiser les frais d'essence pour le trajet en voiture;
(1.2) Minimiser les frais de logement pour la nuit.
Si dans une troisième approche l'informaticien demande la raison des différences de frais, il apprend que l'ordre dans lequel les différentes localités sont visitées joue un rôle non négligeable.
Manifestement, chaque tournée entre deux localités successives occasionne des frais de route individuels et la totalité des frais d'essence s'obtient par addition des frais de route individuels.
Puis, la question est de savoir
- s'il y a des clients qu'il a visités plus souvent que d'autres,
- si tous les clients ou seulement une partie d'entre eux doivent être visités lors d'un même tour,
- s'il y a des clients qu'il a visités plusieurs fois lors d'un même tour?
Cette dernière approche consiste donc à essayer de simplifier le problème initial pour lui trouver une solution acceptable, à défaut d'être optimale.
C'est le représentant de commerce qui spécifie enfin qu'il rend visite exactement une fois par mois à chaque client de sa région, qu'une tournée de visites a une durée de cinq jours, et qu'il passe les nuits dans des hôtels à même prix.
Ainsi, les frais de logement pour la nuit étant fixes, l'informaticien peut en conclure que l'on peut les négliger lors de la résolution du problème de minimisation.
L'informaticien finit par formuler le problème du voyageur de commerce de la manière suivante :
Une fois par mois, à partir de son domicile, un représentant de commerce rend visite à sa clientèle qui est répartie sur N localités différentes (y compris son propre domicile) de sa région. Lors d'un même tour, il ne passe par chaque localité qu'une seule fois. C'est ainsi que son trajet se trouve divisé en exactement N parties différentes et que la totalité des frais de route s'obtient par addition des frais de route individuels , c.-à-d. des différentes parties. Chaque partie de route occasionnant des frais individuels différents, la totalité des frais varie selon l'ordre dans lequel le représentant fait sa tournée. Le problème consiste à déterminer le tour dont la somme des frais de route individuels est minimale. En réalité, la consommation d'essence pour une partie de route n'est évidemment pas proportionnelle à la distance parcourue, mais elle dépend des conditions particulières des routes (autoroute, route nationale, route droite - route sinueuse, route plane - route raide) et notamment du sens dans lequel la route est parcourue.
On peut supposer que le représentant de commerce a déterminé les consommations moyennes d'essence pour toutes les parties de routes possibles et qu'il les a mises à la disposition de l'informaticien sous forme d'un tableau à N lignes et à N colonnes.
La figure 2.3 représente le problème du représentant de commerce pour N = 5 localités. Nous y avons tracé deux trajets possibles A - B - C - D - E - A et A - E - C - B - D - A avec les frais de route individuels respectifs. Le premier trajet coûte 25, l'autre 28 unités.
Figure 2.3 Représentation du problème du représentant de commerce
Le problème du voyageur de commerce connaît un certain nombre d'applications pratiques. Ainsi par exemple, il a permis d'établir l'itinéraire des collecteurs d'argent pour les cabines de téléphone publics.
La conception d'un algorithme correspondant qui donne une solution optimale n'est pas du tout triviale si l'on songe qu'il y a (N - 1)! = (N 1).(N - 2).(N - 3) . . . 3.2.1 tours possibles pour N localités ce qui donne pour N = 20 exactement 1.2165 . 1017 tournées possibles, d'autant plus qu'un tel algorithme pourrait se révéler très coûteux en temps d'exécution.
Pourtant il existe des algorithmes qui donnent rapidement une bonne solution, bien que pas forcément optimale. Un tel algorithme s'appelle une méthode heuristique ou tout simplement une heuristique [angl. branch-and-bound].
Exercice:
a) Trouver sur la figure 2.3 le tour le moins coûteux.
b) Si vous avez suivi un schéma, alors décrivez-le.
Termes techniques
• Heuristique
© Aflo Informatique , 2003-2004