5 7 7 0

0.85
Chargement en cours…

Gestion de la production et des flux

Vincent Giard

Détermination de la tournée optimale du voyageu

commerce

Ce programme a pour objet de résoudre des problèmes de type «tournée de voyageur de

au plus 20 villes à visiter. La méthode de résolution utilisée et illustrée pas à pas est c
Sweeney & Karel (cf. § I-2.1 du chapitre V) qui relève de l'approche branch a

À partir de l'option Menu de la barre d'outils du haut de l'écran, vous pouvez:

- Créer un nouveau problème.

- Sauver un problème et sa solution sous un nouveau fichier ; le fichier sauvegardé compo

- Examiner les étapes de calcul ou la solution du problème que vous venez de créer. Si vo
nouveau problème, vous traitez alors celui qui a été enregistré avec le fichier du programm

- Agrandir ou réduire l'affichage

ion et des flux

timale du voyageur de
e

«tournée de voyageur de commerce» comportant

et illustrée pas à pas est celle de Little, Marty,
ève de l'approche branch and bound.

vous pouvez:

e fichier sauvegardé comporte le programme.

vous venez de créer. Si vous n'avez pas créé de

avec le fichier du programme.
 A B C D E
A -1 -1 -1 -1 -1
B -1 -1 -1 -1 -1
C -1 -1 -1 -1 -1
D -1 -1 -1 -1 -1
E -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1
G -1 -1 -1 -1 -1
F G
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
 Détermination de la tournée optimale du voyageur de commerc
Liste des décisions prises pour un cout final minimum de 33

Niveau 1 (décision 1) F --> G (coût: 31) F -/-> G (coût: 35)

Niveau 2 (décision 2) B --> D (coût: 32) B -/-> D (coût: 34)

Niveau 3 (décision 3) E --> B (coût: 33) E -/-> B (coût: 37)

Niveau 4 (décision 4) D --> C (coût: 33) D -/-> C (coût: 34)

Niveau 5 (décision 5) A --> E (coût: 33) A -/-> E (coût: 33)

Niveau 6 (décision 6) C --> F (coût: 33) C -/-> F (coût: 33)

Niveau 7 (décision 7) G --> A (coût: 33) G -/-> A (coût: 33)

Tournée optimale : G -> A -> E -> B -> D -> C -> F -> G

Cout final minimum : 33 = 0 + 0 + 3 + 10 + 7 + 4 + 9
male du voyageur de commerce
un cout final minimum de 33
 Détermination de la tournée optimale du voyageur de commerce
Saisie des temps de trajet pour 7 villes

Attention, si vous importez les données par 'copier-coller', les valeurs de la

diagonale doivent toutes être égales à -1.

Ville d'arrivée

A B C D E F G

A -1 0 0 0 0 0 -1
B -1 -1 14 10 13 15 52
Ville de départ

C -1 3 -1 3 4 4 14
D -1 6 7 -1 8 8 29
E -1 3 8 4 -1 9 24
F -1 2 2 2 3 -1 9
G 0 -1 -1 -1 -1 -1 -1
de commerce
 Détermination de la tournée optimale du voyageur de commerc
Fin de la résolution du problème du voyageur de commerce

Trajet déjà sélectionnés: F --> G ; B --> D ; E --> B ; D --> C

Trajets restants: A --> E ; C --> F ; G --> A

Ville d'arrivée

A B C D E F G

A -1 -1 -1 -1 -1 -1 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 -1 -1 -1 -1 -1 -1
D -1 -1 -1 -1 -1 -1 -1
E -1 -1 -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1 -1 -1
G -1 -1 -1 -1 -1 -1 -1
oyageur de commerce
geur de commerce
 Détermination de la tournée optimale du voyageur de com
Résolution de l'itération 4

Etape 1 de la résolution du problème de l'itération 4

Ville d'arrivée

A B C D E F G

A -1 -1 0 (0) -1 0 (0) 0 (0) -1 0

B -1 -1 -1 -1 -1 -1 -1 0
Ville de départ

C -1 -1 -1 -1 0 (0) 0 (0) -1 0
D -1 -1 0 (1) -1 -1 1 -1 1
E -1 -1 -1 -1 -1 -1 -1 0
F -1 -1 -1 -1 -1 -1 -1 0
G 0 (0) -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 0 0

Etape 2 de la résolution du problème de l'itération 4

Ville d'arrivée

A B C D E F G

A -1 -1 -1 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 -1 -1 -1 0 0 -1
D -1 -1 -1 -1 -1 -1 -1
E -1 -1 -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
minimum 0 0 0 0 0 0 0

Etape 3 de la résolution du problème de l'itération 4 : D --> C (coût: 33) [D -/-> C (coû

Trajets sélectionnés: E->B et B->D et D ->C : trajet C -> E interdit

Ville d'arrivée

A B C D E F G

A -1 -1 -1 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 -1 -1 -1 -1 0 -1
Ville de départ
D -1 -1 -1 -1 -1 -1 -1
E -1 -1 -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
u voyageur de commerce
on 4

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 1 1 1 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

minimum
Ville d'arrivée

A B C D E F G

A -1 -1 -1 -1 0 0 -1 0 -1
B -1 -1 -1 -1 -1 -1 -1 0 -1
Ville de départ

C -1 -1 -1 -1 0 0 -1 0 -1
D -1 -1 -1 -1 -1 -1 -1 0 -1
E -1 -1 -1 -1 -1 -1 -1 0 -1
F -1 -1 -1 -1 -1 -1 -1 0 -1
G 0 -1 -1 -1 -1 -1 -1 0 0

oût: 33) [D -/-> C (coût: 34)]

-1 0 -1 0 0 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 0 0 -1
-1 0 -1 -1 1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
 Détermination de la tournée optimale du voyageur de com
Résolution de l'itération 3

Etape 1 de la résolution du problème de l'itération 3

Ville d'arrivée

A B C D E F G

A -1 0 (0) 0 (0) -1 0 (1) 0 (1) -1 0

B -1 -1 -1 -1 -1 -1 -1 0
Ville de départ

C -1 0 (1) -1 -1 1 1 -1 1
D -1 -1 0 (1) -1 1 1 -1 1
E -1 0 (5) 5 -1 -1 6 -1 5
F -1 -1 -1 -1 -1 -1 -1 0
G 0 (0) -1 -1 -1 -1 -1 -1 0
0 0 0 0 1 1 0

Etape 2 de la résolution du problème de l'itération 3

Ville d'arrivée

A B C D E F G

A -1 -1 0 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 -1 -1 -1 1 1 -1
D -1 -1 0 -1 1 1 -1
E -1 -1 -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
minimum 0 0 0 0 0 0 0

Etape 3 de la résolution du problème de l'itération 3 : E --> B (coût: 33) [E -/-> B (coût

Trajets sélectionnés: E->B et B->D : trajet D -> E interdit

Ville d'arrivée

A B C D E F G

A -1 -1 0 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 -1 -1 -1 0 0 -1
Ville de départ
D -1 -1 0 -1 -1 1 -1
E -1 -1 -1 -1 -1 -1 -1
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
u voyageur de commerce
on 3

0 0 0 0 1 1 0
0 0 0 0 1 1 0
1 1 1 1 2 2 1
1 1 1 1 2 2 1
5 5 5 5 6 6 5
0 0 0 0 1 1 0
0 0 0 0 1 1 0

minimum
Ville d'arrivée

A B C D E F G

A -1 -1 0 -1 0 0 -1 0 -1
B -1 -1 -1 -1 -1 -1 -1 0 -1
Ville de départ

C -1 -1 -1 -1 0 0 -1 1 -1
D -1 -1 0 -1 1 1 -1 0 -1
E -1 -1 -1 -1 -1 -1 -1 0 -1
F -1 -1 -1 -1 -1 -1 -1 0 -1
G 0 -1 -1 -1 -1 -1 -1 0 0

oût: 33) [E -/-> B (coût: 37)]

 0 0 -1 0 0 -1
-1 -1 -1 -1 -1 -1
0 -1 -1 1 1 -1
-1 0 -1 1 1 -1
0 5 -1 -1 6 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
 Détermination de la tournée optimale du voyageur de com
Résolution de l'itération 2

Etape 1 de la résolution du problème de l'itération 2

Ville d'arrivée

A B C D E F G

A -1 0 (0) 0 (1) 0 (0) 0 (1) 0 (1) -1 0

B -1 -1 4 0 (3) 3 5 -1 3
Ville de départ

C -1 0 (0) -1 0 (0) 1 1 -1 0
D -1 0 (1) 1 -1 2 2 -1 1
E -1 0 (1) 5 1 -1 6 -1 1
F -1 -1 -1 -1 -1 -1 -1 0
G 0 (0) -1 -1 -1 -1 -1 -1 0
0 0 1 0 1 1 0

Etape 2 de la résolution du problème de l'itération 2

Ville d'arrivée

A B C D E F G

A -1 0 0 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 0 -1 -1 1 1 -1
D -1 -1 1 -1 2 2 -1
E -1 0 5 -1 -1 6 -1
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
minimum 0 0 0 0 0 0 0

Etape 3 de la résolution du problème de l'itération 2 : B --> D (coût: 32) [B -/-> D (coû

Ville d'arrivée

A B C D E F G

A -1 0 0 -1 0 0 -1
B -1 -1 -1 -1 -1 -1 -1
Ville de départ

C -1 0 -1 -1 1 1 -1
D -1 -1 0 -1 1 1 -1
E -1 0 5 -1 -1 6 -1
Ville de départ
F -1 -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1 -1
u voyageur de commerce
on 2

0 0 1 0 1 1 0
3 3 4 3 4 4 3
0 0 1 0 1 1 0
1 1 2 1 2 2 1
1 1 2 1 2 2 1
0 0 1 0 1 1 0
0 0 1 0 1 1 0

minimum
Ville d'arrivée

A B C D E F G

A -1 0 0 -1 0 0 -1 0 -1
B -1 -1 -1 -1 -1 -1 -1 0 -1
Ville de départ

C -1 0 -1 -1 1 1 -1 0 -1
D -1 -1 0 -1 1 1 -1 1 -1
E -1 0 5 -1 -1 6 -1 0 -1
F -1 -1 -1 -1 -1 -1 -1 0 -1
G 0 -1 -1 -1 -1 -1 -1 0 0

oût: 32) [B -/-> D (coût: 34)]

 0 0 0 0 0 -1
-1 4 0 3 5 -1
0 -1 0 1 1 -1
0 1 -1 2 2 -1
0 5 1 -1 6 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
 Détermination de la tournée optimale du voya
Résolution de l'itération 1

Données du problème du voyageur de commerce

Ville d'arrivée

A B C D E F

A -1 0 0 0 0 0
B -1 -1 14 10 13 15
Ville de départ

C -1 3 -1 3 4 4
D -1 6 7 -1 8 8
E -1 3 8 4 -1 9
F -1 2 2 2 3 -1
G 0 -1 -1 -1 -1 -1

Tableau intermédiaire du processus de réduction

Ville d'arrivée

A B C D E F

A -1 0 0 0 0 0
B -1 -1 4 0 3 5
Ville de départ

C -1 0 -1 0 1 1
D -1 0 1 -1 2 2
E -1 0 5 1 -1 6
F -1 0 0 0 1 -1
G 0 -1 -1 -1 -1 -1
minimum 0 0 0 0 0 0

Résultat du processus de réduction de la matrice des coûts

Ville d'arrivée

A B C D E F

A -1 0 0 0 0 0
B -1 -1 4 0 3 5
Ville de départ

C -1 0 -1 0 1 1
D -1 0 1 -1 2 2
E -1 0 5 1 -1 6
F -1 0 0 0 1 -1
G 0 -1 -1 -1 -1 -1
Etape 1 de la résolution du problème de l'itération 1

Ville d'arrivée

A B C D E F

A -1 0 (0) 0 (0) 0 (0) 0 (1) 0 (1)

B -1 -1 4 0 (3) 3 5
Ville de départ

C -1 0 (0) -1 0 (0) 1 1
D -1 0 (1) 1 -1 2 2
E -1 0 (1) 5 1 -1 6
F -1 0 (0) 0 (0) 0 (0) 1 -1
G 0 (0) -1 -1 -1 -1 -1
0 0 0 0 1 1

Etape 2 de la résolution du problème de l'itération 1 : F --> G (coût: 31) [F -/-> G (c

Ville d'arrivée

A B C D E F

A -1 0 0 0 0 0
B -1 -1 4 0 3 5
Ville de départ

C -1 0 -1 0 1 1
D -1 0 1 -1 2 2
E -1 0 5 1 -1 6
F -1 -1 -1 -1 -1 -1
G 0 -1 -1 -1 -1 -1
née optimale du voyageur de commerce
lution de l'itération 1
minimum

-1 0
52 10
14 3
29 6
24 3
9 2
-1 0

-1
42
11
23
21
7
-1
7

-1
35
4
16
14
0
-1
 G

-1 0 0 0 0 0 1 1
35 3 3 3 3 3 4 4
4 0 0 0 0 0 1 1
16 1 1 1 1 1 2 2
14 1 1 1 1 1 2 2
0 (4) 0 0 0 0 0 1 1
-1 0 0 0 0 0 1 1
4

> G (coût: 31) [F -/-> G (coût: 35)]

-1
-1
-1
-1
-1
-1
-1
4
7
4
5
5
4
4
 Détermination de la tournée optimale du
voyageur de commerce
Saisie des données

Attention, si vous importez les données par "copier-coller", les

valeurs de la diagonale doivent toutes être égales à -1.

Ville d'arrivée

A B C D E F

A -1 1 7 3 14 2

B 3 -1 6 9 1 24
Ville de départ

C 6 14 -1 3 7 3

D 2 3 5 -1 9 11

E 15 7 11 2 -1 4

F 20 5 13 4 18 -1
 Bar

.DisplayFormulaBar 0
Standard 0
Formatting 0
PivotTable 0
Chart 0
Reviewing 0
Forms 0
Stop Recording 0
External Data 0
Full Screen 0
Circular Reference 0
Visual Basic 0
Web 0
Exit Design Mode 0
Drawing 0
WordArt 0
Picture 0
Shadow Settings 0
3-D Settings 0
.DisplayFormulas 0
.DisplayGridlines 0
.DisplayHeadings 0
.DisplayOutline 0
.DisplayZeros 1
.DisplayHorizontalScrollB 0
.DisplayVerticalScrollBar 0
.DisplayWorkbookTabs 0

Page 29