Quelques problèmes NP-difficile

d’optimisation combinatoire

01/04/2022 Optimisation combinatoire 1

Le problème de voyageur de commerce

Un voyageur de commerce doit visiter n villes données en passant par chaque ville exactement une
fois. Il commence par une ville quelconque et termine en retournant à la ville de départ. Les
distances entre les villes sont connues.

Problème classé NP complets difficile à résoudre exactement, du moins quand le nombre de

villes dépasse quelques centaines.

01/04/2022 Optimisation combinatoire 2

 Le problème de voyageur de commerce
Formalisation Mathématique:
1 si i est visité avant j
x ij = 
0 sinon

n n
Min c
i =1 j=1
ij xij

SC
n

x
i =1
ij =1 j = 1,...., n (1)
n

x
j=1
ij =1 i = 1,...., n (2)

(i, j) / x ij = 1 forme un seul circuit (3)

xij  0,1

• La contrainte (1) (resp. (2) ) exprime que le voyageur de commerce n’empruntera qu’un seul arc
incident intérieurement à j (resp. incident extérieurement à i)
• (1) et (2) définissent des circuits passant une fois et une seule par chaque sommet leur appartenant.
• La contrainte (3) permet d’éviter les solutions de (1) et (2) qui seraient des circuits disjoints.
• (1), (2) et (3) définissent un circuit hamiltonien.

01/04/2022 Optimisation combinatoire 3

 Le problème de voyageur de commerce

(3) (i, j) / x ij = 1 forme un seul circuit   x ij  S -1 S  X

iS jS

Définition d' un circuit parasite : i  S, j  S, x ij = 0 ou  x ij =0

iS jS

Exemple de circuits parasites pour un problème où |X|=7

1
3 6

5
4
2
7
01/04/2022 Optimisation combinatoire 4
 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Soit le TSP de matrice symétrique:

1 2 3 4 5
1 ∞ 3 4 5 4
2 3 ∞ 2 2 1
3 4 2 ∞ 1 2
4 5 2 1 ∞ 3
5 4 1 2 3 ∞

01/04/2022 Optimisation combinatoire 5

 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Heuristique du plus proche voisin (Nearest Neighbour NN):

• Choisir aléatoirement un sommet (le premier sommet d’une chaine hamiltonienne)
• Le sommet suivant est le sommet le plus proche du dernier choisi et qui
n’appartient pas déjà à la chaine
• Joindre le sommet extrémité finale de la chaine à celui d’extrémité initiale

Algorithme :
Choisir un sommet v1 ∈ V
poser k 1
tant que k < n
k k+1
choisir vk dans V \{v1, v2,…. , vk-1} qui minimise d(vk-1,vk)
Retourner le tour (v1, v2,…. , vn)

01/04/2022 Optimisation combinatoire 6

 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Heuristique de meilleure insertion:

• Choisir un cycle arbitraire C passant par un sous-ensemble de sommets.
• Chercher le sommet j n’appartenant pas à C ( le plus proche de n’importe quel
autre sommet de C)
d ji = min d kl
kC ,lC

• L’insérer entre deux sommets de C à la place qui provoque la plus faible

augmentation de la valeur du cycle construit.

Le cycle initial peut être une boucle sur un sommet tiré au hasard.

01/04/2022 Optimisation combinatoire 7

 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Heuristique 2-optimalité:
• Choisir un cycle hamiltonien.
• Ôter de ce cycle deux arêtes (par exemple [i,j] et [k,l]) afin de le scinder en 2 chaines.
i k

j
l
• Ces 2 chaines peuvent être reliées d’une seule façon (par [i,l] et [k,j])de manière à
construire un autre cycle hamiltonien. Cette opération est appelée 2-échanges.
i k

j
l
• Un cycle hamiltonien est 2-optimal si aucun des 2-échanges ne permet d’obtenir un
cycle hamiltonien de valeur inférieure.

01/04/2022 Optimisation combinatoire 8

 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Heuristique k-optimalité:

Un cycle est k-optimal si tout k-échange (échange de k-arêtes) conduit à des cycle de
valeur supérieure ou égale.

Après avoir ôter k-arêtes, il y a plusieurs façons de reconstituer un nouveau cycle

Hamiltonien si k est supérieur à 2.

01/04/2022 Optimisation combinatoire 9

 Le problème de voyageur de commerce:
Résolution par des heuristiques approchées

Heuristique 3-optimalité: exemple

01/04/2022 Optimisation combinatoire 10

 Algorithme de Little (pour la recherche d’une solution optimale)

• Réduction de la matrice(ligne et colonne/Méthode Hangroise)

• Choisir la case nulle dont le regret/coût d’éviction est le plus élevé
(le coût d’éviction/regret est le surcoût minimal engendré par le fait de ne pas
choisir la case (ie) choisir une autre case sur la même ligne et une sur la même
colonne)
rij = min d ik' + min d lj'
k j l i

• Enlever la ligne de la ville de départ et la colonne de la ville d’arrivée

correspondantes
• Rendre infini le coût de retour
• Recommencer avec le tableau partiel
• Présenter l’algorithme sous la forme d’une arborescence (Branch and bound)
• Examiner tous les chemins dont le coût est inférieur au premier coût final
trouvé
• Dérouler l’arborescence jusqu’au bout

01/04/2022 Optimisation combinatoire 11

 Algorithme de Little (pour la recherche d’une solution optimale)

Soustraire de chaque rangée son minimum

1 2 3 4 5
1 ∞ 3 4 5 4 -3
2 3 ∞ 2 2 1 -1
D 3 4 2 ∞ 1 2 -1
4 5 2 1 ∞ 3 -1
5 4 1 2 3 ∞ -1
-2
1 2 3 4 5 1 2 3 4 5
1 ∞ 0 1 2 1 1 ∞ 0 1 2 1
2 2 ∞ 1 1 0 2 0 ∞ 1 1 0
3 3 1 ∞ 0 1 D’ 3 1 1 ∞ 0 1
4 4 1 0 ∞ 2 4 2 1 0 ∞ 2
5 3 0 1 2 ∞ 5 1 0 1 2 ∞
01/04/2022 Optimisation combinatoire 12
 Algorithme de Little (pour la recherche d’une solution optimale)

Pour chaque arête de coût nul dans le tableau D’, on calcule son regret (augmentation
de la valeur du cycle construit provoquée par le fait qu’il n’empruntera pas cette arête)

rij = min d ik' + min d lj'

k j l i

1 2 3 4 5
1 ∞ 01 1 2 1
2 01 ∞ 1 1 01
3 1 1 ∞ 02 1
4 2 1 02 ∞ 2
5 1 01 1 2 ∞

01/04/2022 Optimisation combinatoire 13

 Algorithme de Little et al. (pour la recherche d’une solution optimale)

Les cycles hamiltoniens ont au moins pour valeur la somme des éléments soustraits : 9

L’arête de regret le plus fort choisie est [3 4] avec r34=2

E0
S0=9

34 Non 3 4

01/04/2022 Optimisation combinatoire 14

 Algorithme de Little et al. (pour la recherche d’une solution optimale):

Evaluation des solutions de S1: on raye la ligne 3, la colonne 4 et on interdit

l’arête [4, 3]
1 2 3 5
1 ∞ 0 1 1
2 0 ∞ 1 0 E0
4 2 1 ∞ 2 -1 S0=9

5 1 0 1 ∞
34 Non 3 4
-1
1 2 3 5
E2
1 ∞ 00 00 1 E1
S2=11
S1=11(=9+1+1)
2 01 ∞ 00 01 (9+r34)=9+2
D(2)
4 1 01 ∞ 1
5 1 00 00 ∞

01/04/2022 Optimisation combinatoire 15

 Algorithme de Little et al. (pour la recherche d’une solution optimale):

L’arête de plus fort regret [2 1] avec r21=1

1 2 3 5
1 ∞ 00 00 1 E0
S0=9
2 01 ∞ 00 01
4 1 01 ∞ 1 34 Non 3 4
5 1 00 00 ∞

E1 E2
S1=11 S2=11

21 Non 2 1

E4
E3 S4=12
(11+r21)=11+1
01/04/2022 Optimisation combinatoire 16
 Algorithme de Little et al. (pour la recherche d’une solution optimale):

L’arête de plus fort regret [2 1] avec r21=1

2 3 5
1 ∞ 0 1 E0
S0=9
4 0 ∞ 1
5 0 0 ∞ 34 Non 3 4
-1
2 3 5 E1 E2
S1=11 S2=11
1 ∞ 0 0
D(3) 4 0 ∞ 0 21 Non 2 1
5 0 0 ∞

E3 E4
S3=12(11+1) S4=12

01/04/2022 Optimisation combinatoire 17

 Algorithme de Little et al. (pour la recherche d’une solution optimale):

2 3 5
1 ∞ 0 0
D(3) 4 0 ∞ 0 E0
S0=9
5 0 0 ∞
34 Non 3 4
On peut construire deux cycles
hamiltoniens en utilisant les arêtes E1 E2
de coût nul dans D(3) S1=11 S2=11

[1 3], [4 5], [5 2] ---→[1 3 4 5 2 1] 21 Non 2 1 Pas de solution

meilleure
[1 5], [5 3], [4 2] ---→[1 5 3 4 2 1]
E3 E4
S3=12 S4=12
La valeur de ces cycles est 12

01/04/2022 Optimisation combinatoire 18