Chapitre 3
Application au Problème de
8
3
7
1
4
6
7
8 3
5 7 9
7
9
8
0
6
3
9
4
10
4
3
2
7
5
2
1
l'Acheteur Itinérant
3.1 Introduction au problème de l'Acheteur
Itinérant
Le problème de l'Acheteur Itinérant
(Traveling Purchaser Problem ou TPP) est une
généralisation du problème du Voyageur de Commerce,
introduite pour la première fois par Ramesh (1981). Dans le
problème du Voyageur de Commerce, l'objectif est de trouver le tour de
longueur minimale qui passe par m villes données. Chaque ville
doit être visitée une et une seule fois. Dans le problème
de l'Acheteur Itinérant, les villes représentent des
marchés. Chaque marché fournit un sous-ensemble de produits. Le
prix de vente de chaque produit est connu et les prix des produits
dépendent du marché à partir duquel ils sont
achetés. Le problème de l'Acheteur Itinérant consiste
à trouver un tour qui part d'un dépôt, connectant un
sous-ensemble de marchés, de telle sorte que l'ensemble des produits
soit acheté et que la somme des coûts de transport et des
coûts d'achats des produits soit minimisée.
Ce problème apparaît dans plusieurs contextes
industriels, comme par exemple, dans l'achat de parties de matériels
pour des usines (Pearn et Chien, 1998). L'ordonnancement de n
tâches sur une machine à m états peut aussi
se modéliser comme un TPP, comme cela a été proposé
par Ong (1982). Les marchés, produits, coûts de transport et
coûts d'achats, représentent respectivement les états des
machines, les tâches, les temps de préparation et les temps
d'utilisation.
Le TPP peut être décrit de la façon
suivante (Singh et Oudheusden, 1997). Posons G = (V,
A) un graphe complet. Considérons V = {v0, .
. . , vm} où v0 est le dépôt
et v1, . . . , vm sont les marchés. P
= {p1, .. . , pn} est l'ensemble des
produits. Chaque produit pk E P est disponible dans un
ensemble de marchés Vk C V. Les coûts de
transport sont notés cij > 0 quels que soient (vi,
vj) E A. Les coûts d'achats des produits sont
notés ski = 0 quels que soient pk E P et
vi E Vk. Un tour réalisable est un tour comprenant le
dépôt et un sous-ensemble des marchés, vérifiant la
contrainte que tous les produits sont achetés. Les produits sont
achetés au plus petit coût disponible parmi les marchés
visités. L'objectif est de trouver un tour réalisable qui
minimise la somme des coûts de transport et des coûts d'achats des
produits.
Le TPP est NP-difficile, puisque le cas particulier pour
lequel chaque marché ne vend qu'un produit ne pouvant être
acheté dans aucun autre marché est un problème de Voyageur
de Commerce. Dans ce cas, chaque marché doit être visité et
le problème revient à trouver le tour hamiltonien qui minimise
les coûts de transport.
Dans un souci de simplicité, on suppose que les
coûts de transport sont symétriques (cij = cji
quels que soient (vi, vj) E A) et que les
inégalités triangulaires sont respectées.
Soit Xik = 1 si le produit pk est
acheté à partir du marché vi et Xik = 0
dans le cas contraire. Soit Yij = 1 si le marché vj
suit immédiatement le marché vi dans le tour et
Yij = 0 dans le cas contraire. Le problème de l'Acheteur
Itinérant peut être modélisé de la manière
suivante :
3.1. Introduction au problème de l'Acheteur
Itinérant
minimiser ? ? skiXik + ? ? cijYij (3.1)
pkEP viEVk viEV
vjEV
sujet à
? Xik = 1 (pk E P), (3.2)
viEVk
Xik ? Yij (pk E P, vi
E Vk), (3.3)
vjEV
Xik ? Yji (pk E P, vi
E Vk), (3.4)
vjEV
G.S.E.C. (3.5)
Xik E {0,1} (pk E P, vi E
Vk),
Yij E {0,1} (vi, vj E V)
La fonction objectif 3.1 représente la somme des
coûts de transport et des coûts d'achats des produits. La
contrainte 3.2 oblige à ce que l'ensemble des produits soit
acheté. Les contraintes 3.3 et 3.4 assurent que seuls les marchés
présents dans la solution sont considérés pour l'achat des
produits. Les contraintes 3.5 représentent les contraintes sur les
sous-tours (Generalized Subtour Elimination Constraints),
présentés notamment par Fischetti et al. (1995, 1997).
Elles assurent que les marchés sélectionnés sont
connectés avec le dépôt dans un tour unique.
Les premiers travaux concernant la résolution du TPP
ont été proposés par Ramesh (1981), qui a
présenté un algorithme basé sur une procédure de
recherche lexicographique, qui pouvait être déclinée en
résolution exacte ou heuristique. La plupart des travaux sur la
résolution du TPP proposent des solutions du problème avec des
méthodes heuristiques. On peut mentionner les travaux de Golden et
al. (1981) qui ont basé leur heuristique sur une stratégie
d'économie : Generalized Saving Heuristic (GSH). Leur
heuristique a été modifiée par Ong (1982) qui a
proposé un Tour Reduction Heuristic basé sur la
suppression de marchés à partir d'un tour complet, visitant
l'ensemble des marchés. Pearn et Chien (1998) ont suggéré
quelques améliorations pour ces heuristiques et ont proposé une
autre heuristique, Commodity Adding Heuristic, qui part du principe
que l'ensemble des produits est disponible dans chaque marché.
Récemment, Teeninga et Volgenant (2004) ont décrit des
procédures de pré-traitement des données qui peuvent
être ajoutées à des heuristiques déjà
existantes. Les résultats expérimentaux ont montré
l'efficacité de leurs procédures sur la plupart des heuristiques
citées auparavant, en permettant des diminutions dans les temps de
calcul pour la résolution du problème.
Depuis une dizaine d'années, des heuristiques plus
évoluées et des approches par métaheuristiques ont
été proposées. Voß (1996) a présenté
une approche métaheuristique basée sur de la recherche tabou
dynamique et recuit simulé. Il proposa deux stratégies dynamiques
pour la gestion de la liste tabou : Reverse Elimination Method et
Cancellation Sequence Method. Boctor et al. (2003) ont aussi
proposé plusieurs algorithmes
efficaces basés sur de la recherche tabou. Ces
heuristiques sont comparées avec des méthodes de
résolution exacte sur des instances avec un nombre de marchés
allant jusqu'à 200 et un nombre de produits allant jusqu'à 200.
Riera-Ledesma et Salazar-González (2005) ont obtenu les meilleurs
résultats à ce jour, avec une stratégie heuristique
consistant en un échange de k marchés au lieu d'un
échange classique d'un seul marché.
En plus de ces recherches pour résoudre le TPP de
manière heuristique, des méthodes exactes ont été
développées par Ramesh (1981), Singh et Oudheusden (1997) et
Laporte et al. (2003). Ces derniers ont proposé une
méthode de résolution par séparation et
génération de coupes qui a permis de résoudre de
manière exacte des problèmes contenant jusqu'à 250
marchés et 200 produits, avec des solutions dont le nombre de
marchés visités reste réduit. Pour les instances de
tailles plus importantes, les temps de calcul nécessaires
s'avèrent trop long.
Nous proposons de résoudre le TPP avec une optimisation
par Colonie de Fourmis (Ant Colony Optimization ou ACO), introduite
par Dorigo et al. (1991) (voir aussi (Dorigo et al., 1996)).
Inspirée par le comportement des fourmis pour la recherche de nourriture
dans la nature, l'optimisation par Colonie de Fourmis est un algorithme de
recherche basé sur des agents coopératifs. Les fourmis
communiquent en utilisant une substance chimique appelée
phéromone. Quand une fourmi se déplace, elle dépose une
quantité de phéromone que les autres fourmis peuvent suivre.
Quand une fourmi trouve une trace de phéromone, elle peut décider
de la suivre ou de l'ignorer. Si elle suit cette trace, sa propre
phéromone renforce la trace existante, et l'augmentation de
phéromone augmente la probabilité que la prochaine fourmi suive
cette trace. Ainsi, l'attractivité du chemin augmente avec le nombre de
fourmis qui l'empruntent. De plus, une fourmi qui emprunte une route courte
pour aller à la source de nourriture, reviendra au nid rapidement et
donc, déposera deux fois de la phéromone sur son chemin. Au fur
et à mesure que le nombre de fourmis empruntant les routes courtes
augmente, la phéromone s'accumule davantage sur les chemins courts et
les chemins longs sont délaissés. L'évaporation de la
phéromone dans l'air accentue ce phénomène en diminuant
l'utilisation de chemins longs.
L'optimisation par Colonie de Fourmis a été
utilisée avec succès pour un nombre important de problèmes
d'optimisation combinatoire : problème du Voyageur de Commerce ou
Traveling Salesman Problem (Dorigo et al., 1991),
problème de Tournées de Véhicules ou Vehicle Routing
Problem (Bell et McMullen, 2004), problème de Couverture d'Ensemble
ou Set Covering Problem (Lessing et al., 2004) ou encore
problème de Coloration de Graphe ou Graph Coloring Problem
(Costa et Hertz, 1997). Pourtant, à notre connaissance, cette
métaheuristique n'a jamais été utilisée pour
résoudre le TPP. Une étude complète sur l'optimisation par
Colonie de Fourmis a été développée dans le livre
de Dorigo et Stutzle (2004).
Faisant partie des métaheuristiques, l'optimisation par
Colonie de Fourmis fournit un schéma de solution
générique. Néanmoins, ce schéma a besoin
d'être adapté au cas spécifique de chaque problème
afin d'accroître son efficacité. Le schéma de notre
algorithme s'appuie sur une implémentation efficace de l'optimisation
par Colonie de Fourmis. Dans le but de préserver la diversité des
solutions, les opérateurs de recherche
locale sont utilisés pour intensifier la recherche. Ce
schéma est appelé l'algorithme de Fourmis Anamorphiques
Parallèles sur Plans Multi-Dimensionnels Dynamiques (Dynamic
Multi-Dimensional Anamorphic Traveling Ants, ou plus simplement
l'algorithme DMD-ATA.
Le schéma du DMD-ATA est décrit dans la section
3.2. La section 3.3 présente en-suite les opérateurs de recherche
locale utilisés. L'efficacité de notre algorithme est
évaluée dans la section 3.4. Nous comparons notre algorithme avec
la procédure de recherche locale (Local Search algorithm ou LS)
de Riera-Ledesma et Salazar-González (2005). Les résultats
montrent l'efficacité de notre algorithme, qui a permis de trouver un
ensemble de nouvelles meilleures solutions connues.
| 
