# Une approche de l'ordonnancement des échanges selon le problème du commis-voyageur

Jean-François Challine

► To cite this version:

Jean-Francois Challine. Une approche de l'ordonnancement des échanges selon le problème du commis-voyageur. [Rapport de recherche] IRIA-RR-105, IRIA. 1975, pp.51. hal-04716097

HAL Id: hal-04716097

https://inria.hal.science/hal-04716097v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

Une approche de l'ordonnancement
des échanges selon le problème
du commis-voyageur

<figure><img src="image_2.png" /></figure>

J.F. Challine

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°105

Février 1975.
UNE APPROCHE DE L'ORDONNANCEMENT DES ÉCHANGES
SELON LE PROBLEME DU COMMIS-VOYAGEUR

J.F. Challine

(Presenté par M. Depeyrot)

## SOMMAIRE

Dans le cadre d'une politique d'ordonnancement pour un moniteur d'Entrée-Sortie, un heuristique est présenté pour la résolution séquentielle du problème du voyageur de commerce dans l'espace euclidien. La résolution consiste dans l'insertion pas à pas des points intérieurs dans l'enveloppe convexe. Un théorème démontré étaye la règle de l'heuristique quant au choix du point à insérer. Une évaluation de la limite de validité du critère est proposée.

## Mots clefs :

Voyageur de commerce, Entrées-sorties, ordonnancement, coût d'insertion, distance Euclidienne.

## ABSTRACT

Starting from considerations on an 1/0 monitor policy, we develop a heuristic method for sequential resolution of the travelling Salesman problem in a Euclidian Space.

Our solution consists in a stepwise modification of the convex outline : an inner point is chosen at each step and inserted in the subtour. We prove a theorem which results in the heuristic rule for choosing the next point to be inserted. A validity limit evaluation is then proposed for the criterion.

## Keywords and phrases :

Travelling Salesman, Input-output, Scheduling, insertion cost, Euclidian distance.
PLAN

Page

I. INTRODUCTION A ORDEX . 1

I. 1. Les algorithmes dynamiques et statiques. 3

I. 2. Le cadre de notre problème. 4

II. SOLUTIONS GEOMETRIQUES DANS ℓ² : 5

II. 1. Définitions. 5

II. 2. Abord du problème. 6

II. 3. Une évaluation de complexité de cette approche géométrique. 7

II. 4. Comment insérer deux points : possibilités d'obtenir l'optimal. 9

II. 5. Etude de la solution dans le cas K=2,N=3. 11

III. L'ALGORITHMEE VRP. 27

III. 1. Les critères. 30

III. 2. Analyse des résultats obtenus. 31

III. 3. Résultats et comparaison avec d'autres algorithmes. 38

IV. CRITERES ET CONFIGURATIONS DE POINTS. 41

IV. 1. Une évaluation de la limite de validité des critères. 41

IV. 2. Vers l'évaluation d'une borne à la solution. 48

BIBLIOGRAPHIE. 51
# I. INTRODUCTION A ORDEX

ORDEX (ORDonnancement des Echanges) est le moniteur d'entrées-sorties initialement défini pour le système temps réel SPECTRE [9,11].

Les données sont les suivantes : les utilisateurs construisent un ensemble de **programmes d'entrée-sortie** (PES), dont chacun est associé à une instruction de lancement d'entrée-sortie, à l'aide de **demandes d'échange** adressées au moniteur. Pour rendre compte de leurs contraintes, ils structurent les PES en les disposant en niveaux : **deux PS d'un même niveau** peuvent être exécutés en parallèle (ils sont commutatifs). Un PES d'un niveau (i) doit attendre que tous les PES des niveaux (0) à (i-1) dont il dépend soient terminés avant d'être lancé : ce sont les **contraintes de précédence** [5]. Les contraintes ainsi définies sont représentées de façon minimale pour un treillis que l'utilisateur construit et fournit à ORDEX (figure 2). Ces envois se produisent de façon aléatoire ; les PES requièrent des périphériques spécifiques. Le problème du moniteur est de répartir les **tâches** correspondant aux PES de façon à minimiser le temps d'exécution de l'ensemble existant à un instant donné.

<figure><img src="image_3.png" /></figure>

Ensemble de PES destinés au même périphérique

<caption>Figure 1. Arborescence des programmes d'E/T.</caption>
Pour manipuler ces treillis, il groupe les chaînes de PES (figure 1) d'un même niveau en paquets et fait exécuter séquentiellement ces paquets : cela revient à complexifier le treillis initial en ajoutant des relations de précédence. L'ensemble constitue un **Programme d'Exchange** (PEC).

<figure><img src="image_4.png" /><figcaption>Figure 2, Manipulation du treillis.</figcaption></figure>

Le problème revient maintenant à faire exécuter en parallèle les chaînes de PES dont chacune est associée à un même périphérique, de façon que le temps pris par la chaîne la plus longue soit minimal, ce qui minimise la durée d'exécution de l'ensemble des paquets.

On doit considérer le fait que les périphériques présentent un temps de positionnement entre deux exécutions de PES. Il s'agit de trouver la séquence qui minimise la somme de ces temps de positionnement. On est donc amené à un problème du type **Commis Voyageur**. ("Travelling Salesman").

Examinons le cas des unités à disques :

- Si l'on considère que le temps de rotation est négligeable par rapport au temps de sélection du cylindre (déplacement mécanique de la tête), la solution est triviale : il suffit de ranger les PES par ordre de cylindre croissant ou décroissant.

- Si l'on considère que le temps de sélection du cylindre est négligeable par rapport au temps de rotation (cas du disque à têtes fixes), une solution presqu'optimale consiste à classer les PES suivant les positions angulaires croissantes. On montre [8] que la différence entre la longueur optimale et la longueur obtenue n'excède pas une révolution du disque.
- Dans un troisième cas, on ne néglige rien. Dans le plan du disque, la tête décrit des arcs de spirale et des arcs de cercle entre 2 points. La distance d'un enregistrement A à un enregistrement B n'est pas la même que de B à A. Les coûts de transition entre 2 enregistrements ne sont pas linéaires en fonction des distances Euclidiennes.

Nous avons étudié le problème dans l'espace Euclidien ; il s'en dégage une méthode par recherche et identification d'agrégats qui pourra s'appliquer ultérieurement au cas non Euclidien.

# I. 1. Algorithmes dynamiques et statiques.

## Définition :

Un algorithme **statique** d'ordonnancement considère à l'avance un ensemble de tâches et donne un planning de répartition avant que la première tâche ne commence son exécution.

Il faut pour cela connaître au préalable les tâches qui vont arriver, leur durée et leur date de fin d'exécution au plus tard (ou échéance) s'il y a lieu. Dans le cas de processus activant périodiquement des tâches, ceci est possible. Un tel algorithme existe [4]. Si nous voulons prendre en compte les tâches d'entrées-sorties, nous devons savoir à quel moment les demandes arrivent, leur durée et la durée du reste de l'exécution de la tâche ayant fait la demande. On peut ainsi étendre l'algorithme [4] au cas de machines à temps de positionnement non nul.

## Définition :

Un algorithme **dynamique** prend en compte les demandes lorsqu'elles arrivent ; on l'emploie quand on ne connaît pas à l'avance les dates d'arrivée des demandes.

Parfois l'ordonnancement peut être hybride ; on dit que l'algorithme est **incrémental** ; il n'est activé que lorsqu'il a acquis un incrément suffisant de données, il travaille alors statiquement ; la taille de l'incrément est fixée
en fonction des impératifs du temps de réponse. C'est le cas de ORDEX qui
reçoit un programme structuré en paquets qui optimise chaque paquet et lance
son exécution.

Si un autre programme se présente, on peut faire les mêmes opérations et mettre les nouveaux paquets à la suite des autres ; on peut aussi bâtir une nouvelle structure en mélangeant les deux programmes, mais on n'est pas sûr que les demandes de deux paquets provenant de programmes différents soient commutatives.

La solution adoptée consiste à décomposer l'ensemble en éléments séquentiels : les programmes sont exécutés en séquence ; on n'essaye pas de les multiprogrammer entre eux. Cela évite de perdre la plupart du temps à bâtir des nouvelles structures de relations entre les demandes et à réoptimiser les paquets ainsi modifiés.

## I. 2. Le cadre de notre problème.

On a l'habitude de distinguer 3 types de ressources : la mémoire (M), l'unité centrale (P) et les organes de liaison (L) (entrée-sortie).

Des algorithmes d'ordonnancement ont été conçus pour chaque type ; dans le cas statique, souvent indépendamment les uns des autres. Seuls des algorithmes dynamiques, utilisant un modèle probabiliste de système, ont été étudiés du point de vue de leur action globale.

Il serait avantageux de prendre en compte tous les paramètres d'un ensemble de tâches connues à l'avance de façon à élaborer un algorithme statique global.

Si l'on peut connaître à l'avance les caractéristiques des tâches d'E/S, on peut faire une optimisation globale. On peut minimiser le temps total d'exécution de n tâches faisant des entrées-sorties.

L'optimisation locale du temps d'activité des canaux peut aller à l'encontre de l'optimisation du temps d'activité de l'unité centrale ; cette difficulté pourrait être levée.
Que l'on veuille étendre le cas de l'algorithme [4] au cas du temps de positionnement ou que l'on veuille optimiser les paquets d'échange, on est amené au problème suivant :

SOIT N TACHES ET UNE MACHINE, QUELLE SEQUENCE CHOISIR POUR OBTENIR UN TEMPS TOTAL D'EXECUTION MINIMAL ?

Le problème de N tâches et M machines équivalentes est étudié en [6].

## II. SOLUTIONS GEOMETRIQUES DANS L'ESPACE $\mathbb{R}^2$.

Nous avons étudié la réponse à ce problème dans l'espace de dimension 2. Nous l'étudions en **boucle fermée** de sorte que tout point puisse être choisi ultérieurement comme point de départ. Pour passer à la solution en **boucle ouverte**, dans laquelle le chemin s'arrête à la dernière ville sans retourner au point de départ, nous mettons en premier la tâche demandant un temps de positionnement $t_0$ par rapport à l'état initial de la machine ; soit $t_1$ le temps de positionnement le plus long pour une tâche voisine de la première. Nous recherchons sur l'ensemble des tâches le $t_0-t_1$ minimal ; la dernière tâche sera celle qui était séparée de la première par le coût $t_1$.

C'est une approximation de la solution en boucle ouverte.

### II. 1. Le problème du voyageur de commerce : définitions.

Soit un ensemble de points répartis dans l'espace et auxquels sont affectés des coûts (un à chaque paire de points). Le problème du "Travelling Salesman" consiste à trouver un chemin de coût minimal, passant par chaque point une fois et une seule, partant d'un point et y retournant à la fin.

Il existe un certain nombre de théorèmes [2] pour le cas où le coût est une distance Euclidienne.
### THEOREME I.

Dans le plan euclidien, le polygone convexe formant l'enveloppe extérieure des points est constitué par un sous ensemble de la solution optimale : l'ordre des sommets du polygone est conservé dans la solution optimale.

### THEOREME II.

Le chemin optimal ne se coupe pas.

## II. 2. Abord du problème.

Nous cherchons une méthode d'élaboration *séquentielle* de la solution :

- Nous partons de l'enveloppe convexe.

- A chaque étape nous choisissons un point à insérer dans la permutation constituée par l'enveloppe.

- Nous ne touchons pas l'ordre des points de l'enveloppe à cause du Théorème I.

Cette méthode a l'avantage de pouvoir utiliser un organe de décision extérieur : à chaque étape, un opérateur peut faire un choix en fonction de ce qui est présenté (sur une console graphique, par exemple) et faire revenir en arrière si la solution se construit mal.

Une première démarche consiste à insérer un point intérieur dans l'enveloppe quand il est seul.

**Définition :**

Soit N points extérieurs : $P_0, P_1, \dots, P_i, \dots, P_{N-1}$.

Soit un point intérieur K.

On appelle *coût d'insertion* de K entre $P_i$ et $P_{i-1}$ l'allongement du chemin initial lorsque K est inséré entre $P_i$ et $P_{i-1}$.

Le coût de l'enveloppe (ici sa longueur) est noté $C(P_0, P_1, \dots, P_{N-1}, P_0)$, où $N=0, \dots, N-1$, puisque c'est un circuit fermé.
On note $d(P_i P_{i+1})$ la distance entre $P_i$ et $P_{i+1}$.

Le coût d'insertion $\delta_i$ de K entre $P_i$ et $P_{i-1}$ (exprime de la façon suivante :

$$ \delta_i(K) = d(P_i K) + d(KP_{i-1}) - d(P_i P_{i-1}) . $$

En effet :

$$ C_O = C(P_i P_i) = \sum_{j=1}^{i-1} d(P_j P_{j+1}) = \sum_{j=1}^{i-2} d(P_j P_{j+1}) + d(P_i P_{i-1}) $$

Introduire K entre $P_i$ et $P_{i-1}$ revient à remplacer dans le coût du chemin $d(P_i P_{i-1})$ par $d(P_i K) + d(KP_{i-1})$

Si $C_1$ est le nouveau coût, les relations suivantes sont satisfaites :

$$ C_1 = \sum_{j=i}^{i-2} d(P_j P_{j+1}) + d(P_i K) + d(KP_{i-1}) \text{ et} $$

$$ \delta_i(K) = C_1 - C_O = d(P_i K) + d(KP_{i-1}) - d(P_i P_{i-1}) . $$

<figure><img src="image_5.png" /><figcaption>Figure 3. Eléments de définition du coût d'un chemin.</figcaption></figure>

**Définition :**

Pour insérer optimalement K, il suffit de calculer les $\delta_i$ pour tout i de 1 à N-1 et de prendre le minimum.

Si min est le segment correspondant à ce minimum, nous dirons que K appartient à min.

## II. 3. Une évaluation de complexité de cette approche géométrique.

Supposons qu'on ait deux points $K_1$ et $K_2$ à insérer et que l'on veuille obtenir le chemin optimal.
Il y a deux façons de procéder : introduire $K_1$ en premier ou $K_2$ en premier. Il n'est pas sur que le 1er point dans la solution optimale soit dans sa zone de coût d'insertion minimal. Mais si le premier point est bien inséré, alors le second le sera aussi.

Si l'on n'a pas de critère d'insertion, le problème conserve son aspect combinatoire : il y a N façons d'insérer le premier point, $N+1$ pour le second et ainsi de suite, soit

$$A_K^{N+K-1} = \frac{(N+K-1)!}{(N-1)!} \text{ solutions.}$$

Le problème envisagé sous forme de permutation de $N+K$ points comporte $\binom{N+K-1}{2}$ solutions dans le cas symétrique où $d(P_i P_j) = d(P_j P_i)$. Le rapport des solutions est $\binom{N-1}{2}!$. L'abord envisagé est d'autant plus rentable que le nombre de villes $N$ est grand.

Quand on dispose d'un critère d'insertion le nombre d'opérations est réduit et le problème se prête mieux à un traitement séquentiel voire conversationnel.

### THEOREME III.

Le nombre d'opérations pour trouver les zones d'appartenance des points intérieurs au cours de la résolution est $2K\left\lfloor N + \frac{K-1}{2} \right\rfloor$.

### Démonstration :

Pour insérer le premier point il faut $N$ additions, $N$ soustractions.

Pour insérer le ième point : $N+(i-1)$ additions, $N+(i-1)$ soustractions.

Il reste $K-i$ points à insérer.

Lorsque le dernier est inséré, on a fait :

$K$

$$\sum_{i=1}^{K} N+(i-1)=K\bar{N}-K+K\left(\frac{K+1}{2}\right) \text{ additions, soit en tout } 2K\left\lfloor N+\frac{K-1}{2} \right\rfloor \text{ opérations.}$$
## II. 4. Comment insérer deux points.

### Possibilités d'obtenir l'optimal.

Nous allons examiner les différents cas de figures pouvant se présenter dans la solution optimale avec 2 points intérieurs. Puisque le chemin optimal doit envelopper une surface connexe, il y en a 2.

<figure><img src="image_6.png" /></figure>

**Cas de Figure 4. a.** Les deux points sont insérés dans des segments différents.

### ASSERTION.

Avant leur insertion, $K_0$ et $K_L$ appartiennent respectivement à $P_1P_2$ et $P_iP_j$.

### Démonstration.

Si cela n'était pas, on aurait pu insérer $K$ et/ou $K_L$ ailleurs avec un coût moindre et le chemin de la figure 3 n'aurait pas été optimal. Par définition de l'appartenance, $\delta_1(K_0)$ et $\delta_i(K_L)$ étaient minimaux donc le chemin de la figure 3 est optimal.

<figure><img src="image_7.png" /></figure>

**Figure 4. b.** Les 2 points sont insérés dans le même segment.
Trois situations peuvent être à l'origine de ce chemin :

α) $K_1$ et $K_2$ appartiennent à $P_1P_2$,

β) un seul appartenait à $P_1P_2$,

γ) aucun n'appartenait à $P_1P_2$.

α) On a inséré $K_1$ ou $K_2$ entre $P_1$ et $P_2$.

Le coût d'insertion du 2ème point a été minimum entre le premier et un des $P_iP_j$ puisque la solution optimale a la forme indiquée. Dans ce cas, on trouve la solution optimale.

β) Un seul point appartenait à $P_1P_2$.

On choisit dans l'algorithme d'introduire en premier le point qui appartient au segment le plus long. Si $P_1P_2$ est le plus long, on obtient la solution optimale.

Si $P_1P_2$ n'est pas le plus long :
on introduit $K_1$ en $P_1P_2$ segment le plus long.

Puis $K_2$ en $P_1P_2$. Or, rien n'empêche, si $P_1P_2$ est suffisamment grand, que $K$ appartienne à $P_2P_3$ mais que si $K_2$ est introduit avant $K_1$, ce dernier ait un coût d'insertion moindre entre $K_2$ et $P_2$. (voir le problème des 42 villes).

Il conviendrait alors dans ce cas d'introduire d'abord $K_1$ dans sa zone puis $K_2$ dans la sienne et de voir le chemin le meilleur.

Ou bien, lors de l'introduction de $K_1$ en $P_1P_2$ voir directement si le chemin $P_1K_1K_2P_2P_3$ n'a pas une longueur inférieure à $P_1K_1P_2K_2P_3P_4$.

γ) Aucun des K n'appartenait au segment dans lequel il a été introduit.

Ce cas est possible.

Voir l'exemple suivant de 5 villes réparties en étoile sur un grand cercle et de 2 réparties sur un petit cercle concentrique (figure 5).
<figure><img src="image_8.png" /><figcaption>Figure 5. Un cas de figure délicat.</figcaption></figure>

Dans cet exemple $K_0$ appartient à $P_3P_4^3$
et $K_1$ appartient à $P_0P_1$.

Et le chemin optimal est obtenu en insérant $K_1$ et $K_0$ entre $P_0$ et $P_4$
Seule la méthode combinatoire envisageant tous les cas peut donner
le résultat.

$$
\text{On avait} \qquad \delta_{P_0 P_4^3} (K) > \delta_{P_3 P_4^3} (K),
$$

$$
\text{mais} \qquad \delta_{P_0 P_4} (K_0) + \delta_{P_0 K_0} (K_1) < \delta_{P_3 P_4} (K_0) + \delta_{P_0 P_1} (K_1),
$$

$$
\text{soit} \quad \delta_{P_0 P_4} (K_0) - \delta_{P_3 P_4} (K_0) < \delta_{P_0 P_1} (K_1) - \delta_{P_0 K_0} (\tau_1).
$$

Ce que l'on a perdu en mettant $K_0$ entre $P_0$ et $P_4$ est compensé
parce qu'on gagne en mettant $K_1$ entre $K_0, P_1$ au lieu de $P_0 P_1$.

II. 5. Etude de la solution optimale dans le cas K=2, n=3.

Nous allons voir dans quelles conditions nous pouvons obtenir la
solution optimale ; ceci nous permettra de faire le choix d'un critère d'insertion.

Le nombre de tours possibles est le suivant :

$$
c_{n-1}^2 \times (n-3) ! = \frac{(n-1) !}{2}
$$
On choisit une ville et on choisit ses deux voisines :

$$C_{n-1}^{2} = C_{K}^{2} = 6. \text{ (dans notre cas)},$$

puis on fait les permutations restantes permettant de joindre
les deux villes voisines : $(n-3)!(5-3)! = 2$.

$$\text{Il y a donc } 6 \times 2 = \binom{5-1}{2} = 12 \text{ .}$$

<figure><img src="image_9.png" /><figcaption>Figure 6. Illustration pour $K=2, n=3$.</figcaption></figure>

Les différents chemins sont :

<table><tr><td>1 2 3 5 4</td><td>(1) A B C E D</td><td rowspan="4">Nous représenterons les chemins soit par une succession de lettres, soit par le numéro décrélé qui leur est associé ci-contre.</td></tr><tr><td>1 2 3 4 5</td><td>(2) A B C D E</td></tr><tr><td>1 2 4 3 5</td><td>(3) A B D C E</td></tr><tr><td>1 2 5 3 4</td><td>(4) A B E C D</td></tr><tr><td>1 5 4 2 3</td><td>(5) A E D B C</td><td></td></tr><tr><td>1 4 5 2 3</td><td>(6) A D E B C</td><td></td></tr><tr><td>1 5 2 4 3</td><td>(7) A E B D C</td><td></td></tr><tr><td>1 4 2 5 3</td><td>(8) A D B E C</td><td></td></tr><tr><td>1 2 4 5 3</td><td>(9) A B D E C</td><td></td></tr><tr><td>1 2 5 4 3</td><td>(10) A B E D C</td><td></td></tr><tr><td>1 5 2 3 4</td><td>(11) A E B C D</td><td></td></tr><tr><td>1 4 2 3 5</td><td>(12) A D B C E</td><td></td></tr></table>
Nous allons voir comment sont réparties les zones dans lesquelles
un point a un coût d'insertion minimal pour un segment.

## THEOREME IV.

Soit un contour fermé de trois points.

$$ \text{Les branches d'hyperboles} \quad \left\{ \begin{array}{l} \text{KB} - \text{KA} = \text{CB} - \text{CA} , \\ \text{KC} - \text{KB} = \text{AC} - \text{AB} , \\ \text{KA} - \text{KC} = \text{BA} - \text{BC} , \end{array} \right. $$

congourent en un point I.

Leurs portions comprises entre I et le sommet qu'elles joignent
partagent la surface enfermée par le contour en 3 régions distinctes.

Un point situé dans une de ces régions, définie par un côté du triangle, appartient à ce côté au sens défini plus haut : son coût d'insertion est minimum pour le côté considéré.

## Démonstration.

$$ \left\{ \begin{array}{l} \delta_{AB}(K) = \text{KB} + \text{KA} - \text{AB} , \\ \delta_{BC} = \text{KB} + \text{KC} - \text{BC} , \\ \delta_{AC} = \text{KA} + \text{KC} - \text{AC} . \end{array} \right. $$

La zone $\{ K \text{ appartient à AC} \}$ est définie par :

$$ \left\{ \begin{array}{l} \delta_{AC} < \delta_{BC} \quad \text{soit} \quad \text{KC} - \text{AC} < \text{KB} - \text{AB} \quad \text{ou} \quad \boxed{\text{KC} - \text{KB} < \text{AC} - \text{AB}} , \\ \delta_{AC} < \delta_{AB} \quad \text{soit} \quad \text{KA} - \text{AC} < \text{KB} - \text{BC} \quad \text{ou} \quad \boxed{\text{KA} - \text{KB} < \text{CA} - \text{CB}} . \end{array} \right. $$

La branche d'hyperbole $\text{KC} - \text{KB} = \text{AC} - \text{AB}$ partage la portion de plan ABC en deux zones :

$$ \text{KC} - \text{KB} > \text{AC} - \text{AB} $$

et

$$ \text{KC} - \text{KB} < \text{AC} - \text{AB} . $$
<figure><img src="image_10.png" /><figcaption>**Figure 7.** Branches d'hyperbole du théorème 4.</figcaption></figure>

Les points C et B sont les foyers de l'hyperbole.

Si on dessine la famille d'hyperboles $XC - XB = m$, avec m croissant, on obtient un faisceau ; (nous ne représentons que les branches $XC - XB > 0$).

Le point d'intersection de ses éléments se rapproche de B quand $m$ croît. (figure 7).

La zone hachurée représente K appartient à AC. (figure 8).

<figure><img src="image_11.png" /><figcaption>**Figure 8.** Zone d'appartenance du segment AC.</figcaption></figure>

Il en va de même pour K appartient à AB et BC.
On obtient trois zones ( figure 9).

<figure><img src="image_12.png" /><figcaption>Figure 9. Les trois zones d'appartenance.</figcaption></figure>

$$
\left\{
\begin{array}{l}
\textcircled{1} : \text{K appartient à AB soit } \delta_{AB}^{(K \in \{1\})} \text{ minimum,} \\
\textcircled{3} : \text{K appartient à BC soit } \delta_{BC}^{(K \in \{3\})} \text{ minimum,} \\
\textcircled{2} : \text{K appartient à AC soit } \delta_{AC}^{(K \in \{2\})} \text{ minimum.}
\end{array}
\right.
$$

L'heuristique dont nous cherchons à localiser la validité,
consiste à choisir un point appartenant au segment le plus long, à l'y
insérer, puis à recommencer avec un autre point et ainsi de suite.

Cette méthode donne un nombre réduit de solutions ; nous allons
les comparer aux solutions non obtenues.

Les solutions diffèrent suivant la position des points
intérieurs D et E, c'est-à-dire suivant qu'ils sont situés dans telle
ou telle zone définie par les branches d'hyperboles.

Dans chaque cas de figure, nous chercherons la solution la
meilleure parmi celles que nous n'obtenons pas ; nous regarderons ensuite
si ou à quelles conditions les solutions de l'heuristique lui sont préférables
(du point de vue de la minimisation du coût).

Nous prenons un exemple où
$$
\begin{cases}
AC>AB, \\
AC>BC.
\end{cases}
$$
Les différents cas de figure sont :

1) D appartient à AB, E appartient à AC,

2) D appartient à AB, E appartient à BC,

3) D appartient à BC, E appartient à AC,

4) D et E appartiennent à AC,

5) D et E appartiennent à BC,

6) D et E appartiennent à AB.

Les situations 1 et 3 sont identiques du point de vue des conclusions : nous ne faisons pas de supposition sur les grandeurs relatives de AB et BC. Nous n'étudions que les situations 1 et 4 car les démonstrations sont semblables pour les autres ; elles apportent des résultats semblables, concernant les grandeurs relatives des segments auxquels appartiennent les points.

## II. 5. 1. Situation 1.

<figure><img src="image_13.png" /><figcaption>Figure 10. Situation 1.</figcaption></figure>

## THEOREME V.

Dans le cas de la figure 10, D appartient à AB, E appartient à AC, une des solutions de l'heuristique est la meilleure dans les cas suivants :

1) quand $\textcircled{5} < \textcircled{6}$ (cas amont).

2) quand $\textcircled{5} > \textcircled{6}$ et E dans la zone $\alpha$ et D dans la zone $\gamma$ (cas aval).
## Démonstration.

Nous commencerons par démontrer le lemme suivant.

### IEMME VI.

Dans le cas de la figure 10, D appartient à AB, E à AC.

Les chemins non trouvés par l'heuristique et candidats à l'optimalité sont :

$$ \begin{cases} \textcircled{5} \quad A \ E \ D \ B \ C \ , \\ \textcircled{6} \quad A \ D \ E \ B \ C \ , \\ \textcircled{9} \quad A \ B \ D \ E \ C \ , \\ \textcircled{10} \quad A \ B \ E \ D \ C \ . \end{cases} $$

Les branches d'hyperboles passant par C et A délimitent des zones numérotées (α), (β), (γ) et (δ) (voir figure 11).

Suivant l'appartenance de E et D à ces zones, nous avons la classification suivante :

* D situé au-dessus de l'hyperbole XA - XB = EA - EB soit (5) < (6)
Cas 2 (amont)

Si E est en (α) (9) est le meilleur.

Si E est en (β) (5) est le meilleur.

* D, en dessous
Cas 1 (aval)

E en (α) (9) ou (6) sont meilleurs.
E en (β) (6) est meilleur.
Les chemins que l'on peut trouver avec l'heuristique sont :

<figure><img src="image_14.png" /></figure>

Pour le critère du coût d'insertion minimal, (12) est meilleur que tous les chemins où D et E ne sont pas à la suite l'un de l'autre.

Restent donc :

<figure><img src="image_15.png" /></figure>

9 est meilleur que (10) si $BD + EC < BE + DC$,
soit $DB - DC < EB - EC$.

On a toujours
et
$DB - DC < AB - AC$,
$EB - EC > AB - AC$.

D'où (9) < (10) .

comparer (5) et (6) revient à comparer $DB - DA$ et $EB - EA$.

Pour D au-dessus de l'hyperbole $C^{(1)}$ (cas amont)
$DB - DA < EB - EA$ ( (5) < (6) ).

(1) Nous désignons

par $\sim_C$ l'hyperbole $XA - XB = CA - CB$,

par $\sim_B$ l'hyperbole $XC - XA = BC - BA$,

par $\sim_A$ l'hyperbole $XC - XB = AC - AB$.
Pour D sur l'hyperbole $\tilde{C}$
DB - DA $\le$ EB - EA ($\bigcirc 5 \le \bigcirc 6$).

Pour D ous l'hyperbole $\tilde{C}$
le sens de l'inégalité dépend des positions relatives de D et E.
(cas amont ou aval).

Etudions les valeurs relatives des permutations non obtenues avec
l'heuristique. Nous comparerons ensuite les meilleures à celles
obtenues par l'heuristique. Donc $\bigcirc 5$, $\bigcirc 6$ et $\bigcirc 9$ peuvent être optimales ;
prolongeons les hyperboles $\tilde{C}$ et $\tilde{B}$.

Nous obtenons, à la figure 11 les régions $\alpha$, $\beta$, $\gamma$ et $\delta$.

Suivant la répartition de D et E dans ces régions, la meilleure
de $\bigcirc 5$, $\bigcirc 6$ et $\bigcirc 9$ est différente.

<figure><img src="image_16.png" /><figcaption>Figure 11. Découpage du triangle en zones.</figcaption></figure>

1°) D appartient à $\bigcirc \delta$

D $\in$ $\bigcirc \delta$ signifie $DB - DA < EB - EA$

Quand D $\in$ $\bigcirc \delta$, nous avons $\bigcirc 5 < \bigcirc 6$ (cas amont).

En effet $\bigcirc 5 < \bigcirc 6$ se traduit par :
$AE + ED + DB + BC + CA < AD + DE + EB + BC + CA$.

Soit en simplifiant :
$DB - DA < EB - EA$.
De la même façon, si E appartient à Ⓟ, Ⓓ < Ⓒ.

En effet Ⓓ < Ⓒ se traduit par :

$$AB + BD + DE + EC + CA < AE + ED + DB + BC + CA.$$

Soit EC - EA < BC - BA, par définition vérifié pour E appartenant à Ⓟ et non vérifié pour E appartenant à Ⓟ.

Soit en résumé :

E ∈ Ⓟ, D ∈ Ⓢ ou Ⓢ Ⓟ, Ⓓ < Ⓒ < Ⓓ Ⓒ est meilleur.

E ∈ Ⓟ, D ∈ Ⓢ ou Ⓢ Ⓟ et Ⓓ < Ⓒ < Ⓓ Ⓒ est meilleur.

2°) D appartient à Ⓐ.

Suivant les positions relatives de D et E, on a :

⑤ < ⑥ (cas amont) ou ⑤ > ⑥ (cas aval).

2. 1.) Prenons E en Ⓟ soit Ⓓ < Ⓒ donc pour Ⓓ < Ⓒ on a Ⓓ < Ⓒ < Ⓓ ; prenons Ⓓ > Ⓒ et comparons Ⓓ et Ⓒ, Ⓓ < Ⓒ se traduit par :

$$EC - EB < DA - DB + BC - BA.$$

Cette relation n'est pas vérifiée dans tout Ⓐ Ⓟ.

En résumé pour Ⓐ Ⓟ :

⑤ < ⑥ (cas amont) alors Ⓓ est meilleur.
⑥ < ⑤ (cas aval) alors Ⓓ ou ⑥ meilleurs.
2. 2.) Prenons E en $\beta$.

On a alors EC - EA > BC - BA soit $\textcircled{9} > \textcircled{5}$.

Pour $\textcircled{5} > \textcircled{6}$ on a $\textcircled{9} > \textcircled{5} > \textcircled{6}$.

Pour $\textcircled{5} < \textcircled{6}$ $\textcircled{5}$ est meilleur.

En résumé pour $\gamma \in \beta$:

$$ \left\{ \begin{array}{l} \textcircled{5} > \textcircled{6} \text{ alors } \textcircled{6} \text{ est meilleur} \\ \text{(cas aval).} \\[1em] \textcircled{5} < \textcircled{6} \text{ alors } \textcircled{5} \text{ est meilleur} \\ \text{(cas amont).} \end{array} \right. $$

Ceci prouve le lemme 6.

C.Q.F.D.

Nous allons voir maintenant dans chaque cas de figure si ou à quelles conditions une des solutions $\textcircled{1}$, $\textcircled{2}$, $\textcircled{12}$ de l'heuristique peut être meilleure que la meilleure de $\textcircled{9}$, $\textcircled{6}$, $\textcircled{5}$.

* Cas 1

$\textcircled{5} > \textcircled{6}$ ou $\text{DB} - \text{DA} > \text{EB} - \text{EA}$ (cas aval).

E est en $\beta$:

alors $\textcircled{1} < \textcircled{6}$.

En effet $\text{AD} + \text{DE} + \text{EC} + \text{CB} + \text{BA} < \text{AD} + \text{DE} + \text{EB} + \text{BC} + \text{CA}$, soit $\text{EC} - \text{EB} < \text{AC} - \text{AB}$, condition vérifiée en $\alpha$ et $\beta$.

E est en $\alpha$:

alors $\textcircled{1} < \textcircled{9}$.

En effet $\text{AD} + \text{DE} + \text{EC} + \text{CB} + \text{BA} < \text{AB} + \text{BD} + \text{DE} + \text{EC} + \text{CA}$, soit $\text{DA} - \text{DB} < \text{CA} - \text{CB}$, condition vérifiée en $\gamma$.
* Cas 2

Donc
(1) < (9)
(1) < (6) pour (γα) et (γβ),
(5) < (6) (cas aval).

Reste à examiner le cas 2 du théorème 6.

Il se subdivise en fonction des répartitions suivantes :

<figure><img src="image_17.png" /></figure>

Répartition 1

Le cas est résolu :

pour (5) > (6) et (5) < (6), on a (1) < (9),
dans la combinaison (γα).

Ceci fournit la démonstration du théorème 5. C.Q.F.D.

Nous allons montrer que dans les autres cas la solution
obtenue n'est pas toujours optimale.

Répartition 2

(5) < (6) D en (δ) E en (α) (figure 12).
<figure><img src="image_18.png" /><figcaption>Figure 12. Répartition 2.</figcaption></figure>

① étant supérieur à ⑨ dans ce cas, restent ⑫ et ②.

② // ⑨ se traduit par :

EA - EC // DB - DC + CA - CB,

on a EA - EC > DB - DC + CA - CB,

EA - EC > BA - BC prenons EA - EC = BA - BC + ε,

DB - DC < AB - AC prenons DB - DC = AB - AC - ζ.

Soit BA - BC + ε > AB - AC - ζ + CA - CB.

Soit ε + ζ > 0.

Nous avons bien ② > ⑨ .

Voyons dans quel cas ⑫ < ⑨ .

Ceci se traduit par :

DA - DE + EA < AB + CA - CB.

Ce n'est pas vrai dans tout ◌⑧ ◌α ◌, mais plus les segments auxquels les points appartiennent sont grands, et/ou plus DE est grand, plus on a de chances de vérifier l'inégalité.

Quand D et E sont très près des segments, ⑫ est le
Meilleur parce que $AB \sim DA + DB$,
et $AC \sim EA + AC$.

L'équation $DA - DE + EA < AB + CA - CB$ devient alors :
$CB < DB + CE + DE$, et par conséquent la solution (12)
est optimale.

Répartition 3

(5) < (6) E en (β) D en (γ) (figure 13).

<figure><img src="image_19.png" /><figcaption>Figure 13. Répartition 3.</figcaption></figure>

On a (②) > (⑤).

Soit DC - DB > AC - AB .

Restent (12) et (1).

(12) < (5) se traduit par :

$EC - ED < AC - AD$

Ceci est vrai pour D proche de A, E proche de C et
ED grand. D'autre part plus AC est grand et plus on a
de chances d'avoir (12) < (5) .

(①) < (⑤) se traduit par :

$EC - EA < DB - DA + AC - AB$

Ceci est vrai pour E proche de C, D proche de B ;
soit DE grand.
Plus AC est grand, plus on a de chances d'avoir Ⓟ < Ⓡ et par conséquent la solution Ⓟ est optimale.

Répartition 4.

E en Ⓐ D en Ⓑ et Ⓟ < Ⓑ.

<figure><img src="image_20.png" /><figcaption>Figure 14. Répartition 4.</figcaption></figure>

On a toujours Ⓑ > ⒵.

Restent Ⓑ < ⒵ EC - ED < AC - AD,
 Ⓟ < ⒵ EC - EA < DB - DA + AC - AB.

Les conclusions sont les mêmes que pour la répartition 3 mais DE a plus de chances d'être plus grand.

## II. 5. 2. Situation 2.

### THEOREME VII.

Dans le cas de la figure 15, D et E appartenant au segment le plus grand, une solution de l'heuristique est la solution optimale.

### Démonstration.

Les chemins obtenus par l'heuristique sont :

1 2 3 4 5

②

A B C D E,

1 2 3 5 4

①

A B C E D •
Nous posons que E ne peut se trouver à gauche d'une perpendiculaire
à AC menée de D (symétrie du problème).

Nous avons donc

<figure><img src="image_21.png" /></figure>

Les chemins susceptibles d'être optimaux sont :

⑤ A E D B C ,

⑥ A D E B C ,

⑨ A B D E C ,

10) A B E D C •

<figure><img src="image_22.png" /><figcaption>Figure 15. Situation 2.</figcaption></figure>

On a < 10>.

Soit EC - EB < DC - DA + CA - CB .

En maximisant EC (on a EC < EA + DC - DA).

On obtient EA - EB < CA - CB qui est vrai.

1) < 9] soit DA - DB < CA - CB qui est vrai.

1) < 6] soit EC - EB < AC - AB qui est vrai.

1) < 5] soit EC - EA < DB - DA + AC - AB .

En maximisant EC - EA, on a DC - DB < AC - AB qui est vrai. Une des
solutions de l'heuristique est optimale.
De l'étude qui précède, on déduit les règles de l'heuristique.

ETANT DONNES K POINTS INTERIEURS, ON INSERE A CHAQUE PAS UN POINT DANS L'ENVELOPPE QUI SE MODIFIE JUSQU'A CE QU'IL N'Y AIT PLUS DE POINTS INTERIEURS. LE POINT CHOISI APPARTIENT AU SEGMENT LE PLUS LONG ET PARMI LES POINTS APPARTENANT A CE SEGMENT, IL EST LE PLUS PROCHE (DISTANCE EUCLIDIENNE D'UN POINT A UN SEGMENT). D'AUTRE PART, SI SON PLUS PROCHE VOISIN APPARTIENT A UN AUTRE SEGMENT, ON CHOISIT D'ABORD L'AUTRE SEGMENT.

Un moyen d'obtenir l'enveloppe ayant été donné en [2], nous partirons d'une enveloppe de N points et de K points intérieurs.

Le théorème suivant présente le fondement qui justifie cet heuristique.

**Définition :**

Soit un segment IJ soit un point K.

Soit $d(I,K) = c$ ; $d(K,J) = d$ ; $d(I,J) = D$.

Nous appelons distance de K à IJ la quantité h, autrement appelée hauteur du triangle IKJ, telle que :

$$h^2 = \min^2(c,d) - \left| \frac{D}{2} - \frac{|c^2 - d^2|}{2D} \right|^2 = \frac{D^2 + c^2}{2} - \frac{D^2}{4} - \left( \frac{c^2 - d^2}{2D} \right)^2$$

### THEOREME PRINCIPAL VIII.

Soit un segment IJ. La droite IJ partage le plan en deux. Soit un point $K_0$ de coût minimal en IJ. Si tous les points sont du même côté que $K_0$ (toujours vrai pour un segment de l'enveloppe), et si $K_0$ a la plus petite distance à IJ, alors $K_0$ apparaît entre I et J dans la solution optimale.

**Démonstration :**

1) Cas de la figure 16 : $K_0$ est entouré de deux points intérieurs,
$K_1$ et $K_2$, dans la solution. Plaçons $K_0$ entre M et N : quelque soit le chemin réarrangé entre I et J avec les mêmes points intérieurs sauf K, il coupera $K_0M$ et $K_0N$ puisque tous les points sont plus loin de IJ que K. Il ne pourra être optimal, donc K doit rester à sa place.

2) Cas de la figure 17 : $K_0$ est relié directement à J. Comme $K_1$ est plus loin de IJ que M, nous avons :

$K_0I + K_1J > K_0K_1 + IJ$ ($K_0I$ et $K_1J$ se coupent, sinon on est dans le cas précédent).

Soit

$$K I + K_1 J - K K_1 - IJ > 0.$$

Par définition, quels que soient M et N, nous avons :

$$K_0 I + K_0 J - IJ < K_0 M + K_0 N - MN.$$

Ajoutons une quantité positive au membre de droite, nous obtenons :

$$K_0 I + K_0 J - IJ < K_0 M + K_0 N - MN + (K_0 I + K_1 J - K_0 K_1 - IJ).$$

Soit finalement :

$$K_0 J + K_0 K_1 - K_1 J < K_0 M + K_0 N - MN.$$

Si l'on place $K_0$ entre M et N, le chemin sera plus coûteux que si l'on place $K_0$ entre $K_1$ et J soit entre I et J.

D'où la démonstration du théorème 8.

C.Q.F.D.

Il est utile de se servir également de la propriété suivante :
Propriété.

Si un point K apparaît dans la solution entre I et J ;

Si un segment MN apparaît dans la solution ;

Si $\delta_K(MN) < \delta_K(IJ)$, alors on changera K de place pour le mettre en MN et on aura un chemin de coût moindre.

Notons que Lin [7] a étendu cette propriété à l'échange d'insertion d'un groupe de points entre 2 segments.

Basée sur le théorème 8, la recherche de la solution optimale devient heuristique parce que :

1) on ne cherche les coûts d'insertion minimaux que parmi les segments déjà construits.

2) quand le contour s'éloigne de l'enveloppe, il y a des points plus proches de IJ que $K_0$, qui n'appartiennent pas à IJ. Ils sont situés en général de l'autre côté de K par rapport à IJ et on ne cherche pas à les insérer parce qu'ils n'appartiennent pas à IJ.

Nous montrerons au § IV. 1 qu'il y a une limite acceptable à la déformation de l'enveloppe.

<figure><img src="image_23.png" /><figcaption>Figure 16. Démonstration du Théorème Principal.</figcaption></figure>
<figure><img src="image_24.png" /><figcaption>Figure 17. Démonstration du Théorème Principal.</figcaption></figure>

### III. 1. L'algorithme VRP est le suivant.

* Partir de l'enveloppe convexe.

1) Pour chaque $K_i$, calculer le coût d'insertion minimum parmi les segments existants. Placer $K_i$ dans la queue d'appartenance au segment trouvé.

2) Chercher le segment du contour le plus long.

3) Dans la queue d'appartenance à ce segment, chercher le point le plus proche du segment.

4) Insérer ce point entre les 2 extrémités du segment, calculer le coût du nouveau contour.

5) S'il reste des points intérieurs, aller en 1, sinon fin.
### III. 2. Analyse des résultats obtenus.

Nous avons traité les problèmes des 10, 33 et 42 villes (voir [1] ),
sur une machine CII 10070 [10].

La solution pour les 10 villes est obtenue (figure 18).

En considérant les instants auxquels des points sont insérés de
façon non optimale, nous avons dégagé trois points :

1) Lors de la construction d'une solution, il faut tenir compte
d'un certain voisinage du point à insérer. En effet, des ensembles de points
ou agrégats apparaissent dans la solution optimale, qui englobent des points
n'appartenant pas au segment auquel ils sont reliés.

#### Exemple des 33 villes [1].

Dans la figure 19, on voit qu'il ne faut pas introduire $K_{16}$ en $K_1 K_{10}$
car il faut que l'agrégat $P_{6}K_{18}K_{17}K_{12}$ se construise.

#### Exemple des 42 villes [1].

Dans la situation de la figure 23, le segment $P_1 K_{15}$ est le plus long
et $K_{14}, K_{25}$ lui appartiennent. $K_{14}$ est le plus proche, on doit donc
l'insérer ; mais cette insertion n'est pas optimale car il faut
construire l'agrégat $K_{14}K_{25}K_{24}K_{26}K_{27}$ entre $K_{16}$ et $K_{15}$. Nous obtenons
la solution de la figure 24 (traits pointillés).

On peut essayer de tenir compte des aggregats en les laissant se
développer prioritairement.

Ils peuvent être décelés par voisinage ; on essaye alors la règle
suivante :
<figure><img src="image_25.png" /><figcaption>Figure 18. Exemple des 10 villes. Solution optimale.</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>Figure 19. Problème des 33 villes.</figcaption></figure>

Le chemin obtenu par VRP est indiqué par les traits pointillés.
<figure><img src="image_27.png" /><figcaption>Figure 20. Problème des 42 villes.</figcaption></figure>

Étape de la construction de la solution à laquelle on introduit le point $K_{14}$ de la façon non optimale pour les 42 villes.
Si le point le plus proche du point à insérer appartient à un autre segment, on choisit cet autre segment ; s'il appartient au même segment, de deux choses l'une : ou son point le plus proche est le point initial à insérer ou c'est un autre. Dans le dernier cas, on choisit le segment auquel appartient l'autre. Dans le premier cas, on choisit le segment du point initial.

2) On constate que lorsque l'on a inséré les points les plus proches de l'enveloppe convexe, les points intérieurs restants ont une grande probabilité d'appartenir à des segments du contour alors construit dans lesquels ils ne figurent pas dans la solution optimale. C'est équivalent à dire que les agrégats qui sont situés vers le centre de la surface ou qui pénètrent jusque là sont difficiles à construire.

### Exemple des 33 villes.

En essayant le critère du point le plus proche du milieu du segment, nous avons construit un contour plus régulier (figure 22) qu'avec le critère du point le plus proche (figure 21). Il reste donc les points proches du centre de la figure (nous expliquerons au § IV. 1. cette notion). Le segment le plus long est $K_{24}K_{15}$, mais aucun point ne lui appartient ; pourtant l'agrégat $K_{10}K_{11}K_{21}$ lui est relié dans la solution optimale. Le segment de longueur inférieure est $K_7K_{19}$ où l'on introduit $K_{10}$. Il n'y a alors plus de possibilité d'introduire un point intérieur quelconque dans sa zone pour arriver à la solution optimale.

3) Un dernier point mérite d'être souligné : les figures des problèmes courants de la littérature sont peu représentatives des matrices de distances ; quant à ces dernières, elle ne respectent pas toujours l'inégalité triangulaire ; il s'en faut de beaucoup quelquefois. Les distances ont été prises dans un atlas ; celui-ci rend compte fidèlement :

1) du fait que les routes sont dans l'espace à 3 dimensions,

2) du fait que les routes n'empruntent jamais la ligne droite entre deux points.
<figure><img src="image_28.png" /><figcaption>Figure 24. Chemin optimal probable du tour des 33 villes.</figcaption></figure>
<figure><img src="image_29.png" /><figcaption>Figure 22. Problème des 33 villes. Les pointillés montrent les appartенances des points intérieurs. Les traits doubles montrent la solution obtenue à la dernière étape après correction de voisinage.</figcaption></figure>
### III. 3. Résultats et comparaisons avec d'autres algorithmes.

#### **Problème des 33 villes.**

Le tour supposé optimal [1], [7] a une longueur 10 861.

Nous trouvons 68 de plus soit 0,62 pour cent en plus avec le critère du point le plus proche du segment. Dans le cas du point le plus proche du milieu d'un segment, on dépasse de 175 soit 1,6 % (figure 19) ; les corrections de voisines réduisent ce dépassement à 172. (chemins en doubles traits, figure 22).

La solution est obtenue en 13 secondes et diffère de l'optimal par 4 segments non communs. On peut approcher le temps de calcul par la formule $T = 2K \left[ N + \frac{K-1}{2} \right]C$ montrée plus haut où C est une constante calculée expérimentalement à la valeur $\frac{1}{70}$.

* K = nombre de villes intérieures,

* N = nombre de villes extérieures et

* T = en secondes.

#### **Problème des 42 villes.**

Les critères autres que le point de moindre hauteur donnent de mauvais résultats. Si l'on prend ce dernier, par rapport à la solution optimale, nous avons un dépassement de 0,71 %. La solution est obtenue en 30 secondes. Elle diffère de l'optimal par 3 segments non communs. La solution obtenue en [7] prend 25 secondes de calcul et dépasse l'optimal de 0,75 % par 7 segments non communs.

Le problème des 10 villes [1] est obtenu en 4 secondes ; on obtient la solution optimale ; le temps de calcul ne peut être approché par la formule ci-dessus à cause de la prépondérance des opérations autres que celles concernant les recherches d'appartenance.
<figure><img src="image_30.png" /><figcaption>Figure 23. Problème des 33 villes. Solution obtenue pour VRP, avec critère du point le plus proche du milieu du segment et sous correction de voisinage.</figcaption></figure>
<figure><img src="image_31.png" /><figcaption>Figure 24. Chemin optimal des 42 villes.
Le chemin pointillé montre la différence entre l'optimal et la solution VRP.</figcaption></figure>
Le tableau ci-dessous compare les résultats de VRP avec ceux obtenus en [7], [1] et [2].

<table><thead><tr><th colspan="2">33 VILLES</th><th colspan="2">42 VILLES</th></tr><tr><th>Longueur</th><th>: Temps calcul</th><th>Longueur</th><th>: Temps calcul</th><th>: Machine</th></tr></thead><tbody><tr><td>VRP : opt. + 0,62 %</td><td>: 13 s</td><td>opt. + 0,71 %</td><td>: 30 s</td><td>: CII<br>: 10070</td></tr><tr><td>[2] :</td><td>:</td><td>opt. + 0,75 %</td><td>: 25 s</td><td>: IBM<br>: 7030</td></tr><tr><td>[1] : opt.</td><td>: 2.29 mn</td><td>opt.</td><td>: 4.27 mn</td><td>: BENDIX<br>: G.20</td></tr><tr><td>[7] : opt.</td><td>: 10.7 s</td><td>opt.</td><td>: 36.3 s</td><td>: IBM<br>: 7094</td></tr></tbody></table>

## IV. CRITERES ET CONFIGURATIONS DE POINTS

Nous avons vu que les points situés vers le centre de la figure sont les plus difficiles à insérer.

Pour ces points, en effet, l'approximation du contour qui reste convexe devient assez grossièrement fausse.

### IV. 1. Une évaluation de la limite de validité des critères.

Il convient donc d'évaluer un contour à l'intérieur duquel les points ne seraient pas pris pour insertion. Le contour extérieur pourrait alors être un sous-ensemble de la solution optimale ; la dimension du problème aurait été réduite et le reste de la solution pourrait être résolu par une méthode exacte (type branch & bound).

Une approche de l'évaluation du contour intérieur peut être obtenue de la façon suivante.

Parmi les 2 chemins dessinés en figure 25, lequel devons-nous choisir en fonction des rayons des deux cercles concentriques.
<figure><img src="image_32.png" /><figcaption>Figure 25 (a)</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>Figure 25 (b)</figcaption></figure>

Cas limite pour VRP.

On voit que plus le rayon inférieur est petit, plus la solution 25 (a) est préférable.

Dans le cas des n points, nous allons évaluer la longueur des 2 chemins

Soit

R : le grand rayon,

r : le petit rayon.

A : le côté du grand polygone.

b : le côté du petit polygone,

a : le segment joignant un point du cercle extérieur au point voisin du cercle intérieur.
$$A = 2R \sin \frac{\pi}{2n},$$

$$b = 2r \sin \frac{\pi}{2n},$$

$$a = \sqrt{R^2 + r^2 - 2r R \cos \frac{\pi}{2n}}.$$

Le chemin 25(a) a pour longueur :

$$(n - 2)b + (n - 1)A + 2a.$$

Le chemin 25(b) a pour longueur :

$$A + 2a + 2(n - 2)a.$$

25(a) < 25(b) se traduit par :

$$b + A - 2a < 0.$$

Soit

$$2R \sin \frac{\pi}{2n} + 2r \sin \frac{\pi}{2n} - 2 \sqrt{R^2 + r^2 - 2r R \cos \frac{\pi}{2n}} < 0.$$

Soit

$$(R + r) \sin \frac{\pi}{2n} < \sqrt{R^2 + r^2 - 2r R \cos \frac{\pi}{2n}}.$$

Comme les deux termes sont positifs,

$$R^2 \sin^2 \frac{\pi}{2n} + r^2 \sin^2 \frac{\pi}{2n} + 2Rr \sin^2 \frac{\pi}{2n} < R^2 + r^2 - 2r R \cos \frac{\pi}{2n}.$$

Soit

$$R^2 \cos^2 \frac{\pi}{2n} + r^2 \cos^2 \frac{\pi}{2n} - 2r R \left( \cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n} \right) > 0.$$

Soit

$$\left(\frac{R}{r}\right)^2 - 2\left(\frac{R}{r}\right) \left[ \frac{\cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n}}{\cos^2 \frac{\pi}{2n}} \right] + 1 > 0.$$
$$ \Delta = \left[ \frac{\cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n}}{\cos^2 \frac{\pi}{2n}} \right]^2 - 1 . $$

Comme

$$ \cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n} > \cos^2 \frac{\pi}{2n}, $$

soit

$$ \cos \frac{\pi}{2n} > \cos \frac{\pi}{n} \quad (\text{avec } n \ge 3 \text{ c'est le cas qui nous intéresse}), $$

il y a toujours 2 racines ($\Delta > 0$).

Il y a une racine supérieure à 1 :

$$ \left(\frac{R}{r}\right)_0 = \frac{\cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n}}{\cos^2 \frac{\pi}{2n}} + \sqrt{\left(\frac{\cos \frac{\pi}{2n} + \sin^2 \frac{\pi}{2n}}{\cos^2 \frac{\pi}{2n}}\right)^2 - 1}, $$

leur produit étant 1, l'autre est inférieur et ne nous intéresse pas : par définition $\frac{R}{r} > 1$.

Donc pour

$$ 1 < \frac{R}{r} < \left(\frac{R}{r}\right)_0, $$

le polynome est négatif donc (a) > (b).

Pour un rapport $\left(\frac{R}{r}\right) > \left(\frac{R}{r}\right)_0$,

le chemin (a) devient moins coûteux.

Pour $n = 5$, (a) est meilleur quand $\frac{R}{r} \ge 1,768$.

Cette évaluation peut servir de borne à ne pas dépasser lors de l'insertion des points.
Prenons un contour de N points.

Nous compterons le nombre n à entrer dans la formule du rapport R/r de la façon suivante.

Nous supprimons les points appartenant à une ligne droite et les points bordant des segments (1 par segment) dont la longueur est inférieure par exemple au dixième du segment le plus long du contour.

Nous chercherons un contour homothétique du contour extérieur, de rapport $\left(\frac{R}{r}\right)_0$ calculé avec le nombre n trouvé.

Le centre d'homothétie sera trouvé comme le barycentre d'une densité uniforme de masse répartie sur la surface entourée du contour de N points (figure 26).

<figure><img src="image_34.png" /><figcaption>Figure 26. Parcours homothétiques.</figcaption></figure>

On n'insérera pas les points à l'intérieur de la surface hachurée.
<figure><img src="image_35.png" /><figcaption>Figure 27. Contour intérieur homothétique des 42 villes.</figcaption></figure>
<figure><img src="image_36.png" /><figcaption>Figure 28. Contour intérieur homothétique des 33 villes.</figcaption></figure>
Les points restant à l'intérieur pourront être insérés par une
méthode exacte, la taille du problème ayant été réduite. On peut voir
un exemple du contour intérieur pour les 2 problèmes traités, en figures 27
et 28. La partie combinatoire sera réduite par le fait que les solutions
construites ou en cours de construction par la méthode [6] pourront être
comparées à la solution obtenue en laissant travailler l'heuristique jusqu'au
bout.

IV. 2. Vers l'évaluation d'une borne à la solution obtenue.

Dans le cas des 2 polygones concentriques, nous pouvons évaluer
l'erreur faite.

$$
\delta = \frac{(\textcircled{2} - \textcircled{1})}{\textcircled{1}} = \frac{2a - (b+A)}{(n-2)b + (n-1)A + 2a},
$$

pour un nombre grand de points extérieurs :

$$
\cos \frac{\pi}{2n} \sim 1,
$$

$$
\sin \frac{\pi}{2n} \sim \frac{\pi}{2n},
$$

on a

$$
\delta = \frac{\frac{R}{r} [n - \frac{\pi}{2}] - [n + \frac{\pi}{2}]}{\frac{R}{r} [1 + \frac{\pi}{2}] - [1 - \frac{\pi}{2}]} .
$$
<figure><img src="image_37.png" /><figcaption>Figure 29. L'erreur relative dans VRP.</figcaption></figure>

L'erreur croit lentement avec $R/r$. Pour $\delta = -1$, (a) est deux fois plus grand que (b) et $R = r$. Pour $\underline{R} = \frac{(n-1) + \pi}{n-1-\pi}$, (b) est deux fois plus grand que (a) ce qui donne pour $n = 20$, $\underline{R} = 1,4$ et pour $n = 10$, $\underline{R} = 2$. Si l'on désire une borne d'erreur de $1/100$ pour $n = 20$, $\underline{R} = 1,1$ et pour $n = 10$, $\underline{R} = 1,4$ marge de fiabilité de l'heuristique devient donc vite réduite pour n croissant.

En conclusion, nous dirons que l'intérêt de notre solution est dans sa rapidité et la qualité des résultats obtenus. Le choix du critère permet de savoir pour quels types de répartition elle est valable.

Deux points soulevés méritent d'être développés :

1) la reconnaissance et la caractérisation des agrégats ;
2) la recherche d'un algorithme rapide pour placer optimalement les divers ensembles de points qu'on peut faire avec les points situés dans la surface homothétique interne.

Ce dernier algorithme combiné avec le premier permettrait une résolution efficace du problème du voyageur de commerce.

L'étude des problèmes combinatoires spatiaux trouvent des applications dans des domaines pratiques tels que l'assignation, le transport et le planning des systèmes économiques [6]. Le problème du partitionnement semble avoir des liens assez étroits avec le problème du voyageur de commerce et il serait intéressant d'appliquer les techniques de l'un à l'autre.
[1] R.L. KARG, G. THOMPSON. "A Heuristic approach to solving Travelling Salesman Problem". MANAGE. SCI. Vol.10. N° 2. pp.225-48. (Jan. 1964).

[2] T.A.J. NICHOLSON. "A boundary method for planar Travelling Salesman". OP. RES. QUAT. Vol.19. N° 4. pp.445-52. (1968).

[3] T.C. RAYMOND. "Heuristic Algorithm for the Travelling Salesman Problem". IBM. J RES. DEVELOP. Vol.13. pp.400-7. (Jul. 1969).

[4] A. JORRY. "An Introduction to ORDON". IV. th IFAC-IFIP. WORKSHOP ON REAL TIME PROG. BUDAPEST. (23-25 March 1974).

[5] F. BANCILHON, V. CAZIER, J. LABETOULLE. "Programmes d'échanges et moniteur d'échanges dans SPECTRE". Rapport interne IRIA.IE/38. (Jan. 1973).

[6] A.R. PIERCE. "Bibliography on algorithms for shortest Path, Shortest spanning tree, and related Circuit routing problems. (1957-1973)". BELL LAB. MURRAY HILL, N.J.

[7] S. LIN. "Computer Solutions of the travelling Salesman Problem". THE BELL SYST. TECH. J. Vol.10. pp.2245-69. (Déc. 1965).

[8] H.S. STONE, S.H. FULLER. "On the near optimality of the Shortest-Access-Time-First Drum Scheduling discipline". TECH. NOTE. N° 12. DIGITAL SYST. LAB. STANFORD UNIV. CALIF. (Oct. 1971).

[9] F. BANCILHON & AL. "Principes de conception automatique dans le système SPECTRE". RAIRO 7ème ANNEE B-3. pp.31-62. (Oct. 1973).

[10] J.F. CHALLINE. "Notice d'emploi du programme VRP". Rapport interne IRIA. IP/223. (Nov. 1974).

[11] J.F. CHALLINE, J.P. FISCHBACH. "Présentation du langage LEX pour systèmes d'exploitation portables". Rapport de Recherche LABORIA. N° 29. (Août 1973).