Les Agents dans le SMAGTR communiquent par échange de messages. Ces messages expriment les informations qu’un agent émetteur désire que les autres agents prennent en considération. Dans notre approche, nous proposons l’utilisation du langage de Communication agent de FIPA (FIPA TC 2002), que nous décrivons ci dessous de manière succincte:

(bid

:sender (agent-identifier :name agentSuperviseur1@SGTR.192.176.68.2)

:receiver (set (agent-identifier :name agentPlanificateur2@SGTR.152.255.100.5))

:content “((annonce nouvel ordre élémentaire Γ(a,d,l) avec

             l={(l1,q1),(l2,q2),…,(ln,qn)}))”

:language fipa-sl

:ontology auction

:protocol Contract Net

)

Ce message est envoyé par l’agent superviseur à tous ses agents planificateurs pour leur annoncer un nouvel ordre élémentaire Γ(a,d,l).

Un message est le support d’information pour les ordres de transport. Un agent superviseur octroie un ordre de transport à un agent planificateur via l’envoi d’un message contenant les caractéristiques de cet ordre.

Dans notre approche, nous proposons l’utilisation du protocole Contract-Net  pour gérer la négociation entre l’Agent Superviseur et ses Agents Planificateurs. C’est un mécanisme de négociation entre deux types d’agents : contractant et gestionnaire. Il permet  à un gestionnaire, suite à quelques échanges avec un groupe d’agents, de retenir les services d’un agent appelé contractant pour l’exécution d’une tâche contrat. Ce protocole est qualifié de type « sélection mutuelle » puisque, pour  signer un contrat,  l’agent élu doit s’engager envers le gestionnaire pour l’exécution de la tâche qui lui sera confiée et le gestionnaire, de sa part, ne sélectionne que l’agent ayant fourni la proposition la plus avantageuse. La version originale du protocole décrite dans ce qui suit  comporte trois étapes principales : l’appel d’offre, la soumission des propositions et l’attribution de contrat.

Etant donné un ordre élémentaire, un agent superviseur et une caste d’agents planificateurs :

1. L’agent superviseur envoie un message de type « annonce-ordre-élementaire» à l’ensemble de ses Agents Planificateurs d’une caste.

2. Chaque agent planificateur évalue l’ordre élémentaire annoncé à l'aide d'une fonction locale "évalue-annonce".

3. L'évaluation précédente permet à certains agents planificateurs de soumettre une proposition à l'aide d'une "soumission-Proposition" à l’Agent superviseur.

4. Si une  proposition est jugée satisfaisante  (à l'aide de la fonction "évalue-soumission"), alors l’agent superviseur envoie un message de type "acceptation" au propriétaire de la proposi­tion retenue. Il envoie également un message de type "refus" aux autres agents planificateurs dont les propositions n'ont pas été retenues.

5. Après un délai de soumission, l’agent superviseur peut mettre fin à l’appel d’offre si le temps d'expiration est dépassé.

6. Si aucune proposition n'a été retenue, alors l’agent superviseur fait parvenir à tous les Agents Planificateurs un message de type "refus" pour indiquer le rejet de chacune des propositions. Il peut alors se retirer de la négociation, retenir la proposition la plus acceptable, redémarrer un nouvel appel d'offre (nouveau " annonce-ordre-élementaire ") ou prolonger le délai de soumission des propositions.

7. L'agent planificateur ayant obtenu le contrat, remet un rapport d'exécution lorsque la tâche est accomplie.

Les agents planificateurs appartenant à une même caste peuvent coopérer entre eux  afin d’améliorer leurs plans locaux. Ce type de coopération intra-caste est assuré par l’heuristique du commerce simulé (Bachem et al., 1996). Le commerce Simulé est un algorithme qui tire ses origines du mécanisme commercial : les agents planificateurs au sein d’une même caste optimisent leurs plans locaux en effectuant des transactions (achat ou vente)  relatives successivement aux différents clients à servir. Chaque Agent Planificateur construit une liste appelée liste des Ventes (LV) contenant les différents clients qu’il désire vendre. En pratique, cette liste contient les clients les plus coûteux relativement au plan local de l’agent planificateur. Cette liste  n’est accessible qu’aux Agents Planificateurs appartenant à la même caste de l’agent initiateur de l’offre. Par la suite, chaque APL calcule le coût d’insertion dans son plan local, pour chaque client dans les LV de tous les APL  appartenant à sa caste. Un APL n’accepte d’acheter un client que si le coût d’insertion de ce dernier dans son plan local est inférieur au coût proposé par l’APL propriétaire de la LV à qui appartient ce client.

L’optimisation de l’utilisation des ressources de transport est un but principal pour toutes les compagnies de transport. Ceci est dû à la distribution aléatoire spatio-temporelle des ordres qu’elles reçoivent et qui affecte de manière considérable l’état de disponibilité des ressources. La coopération avec les autres compagnies semble être d’une grande utilité dans le processus de gestion. Par exemple, les compagnies peuvent échanger des informations à propos de leurs ressources disponibles, aussi elles peuvent négocier des ordres offerts par d’autres compagnies. Cependant, contrairement à la coopération interne entre une compagnie et ses APLs qui est gérée par le protocole Contract-Net, la coopération entre compagnies est un processus pair à pair (Peer to Peer) (Rowstron et al., 2001) dans lequel deux compagnies contractantes ne peuvent adopter un consensus que si les deux compagnies à la fois sont d’accord sur toutes les clauses d’un contrat. Nous avons introduit cette modification dans le protocole de négociation initial pour permettre au SGTR de prendre en compte les fluctuations qui surviennent dans les décisions des compagnies durant le temps de négociation.

Définition1 :

Un ordre Γ(a,d,l) avec l={(c₁,q₁),(c₂,q₂),…,(c_n,q_n)},               et, i=1…n est équivalent à transporter a unités de marchandises du dépôt d et distribuer les quantités q₁,…,q_n respectivement sur les clients c₁,…,c_n.

Définition2 : un ordre Γ(a,d,l) avec est dit élémentaire ou ss-ordre si , Q étant la capacité maximale d’un agent planificateur.

Définition3 : un Plan local P_k d’un agent planificateur k représente l’ensemble des ordres qui doivent être accomplis par l’agent Planificateur k.

A la réception d’un ordre de transport de la part de l’agent prestataire (APR), l’agent superviseur se charge de le structurer afin de générer les plans initiaux qui seront exécutés  par ses agents planificateurs. Après décomposition, pour chaque ordre élémentaire, l’AS lance un appel d’offre à l’ensemble de ces APL qui, à leur tour, évaluent cet appel  en utilisant plusieurs heuristiques (les Algorithmes Génétiques, l’heuristique de Lin-Kernighan et la Recherche Taboue) et soumettent leurs propositions. Un ordre est décroché par l’APL ayant offert la meilleure proposition. Un APL peut décrocher plusieurs ordres, à chaque fois qu’il reçoit une acceptation finale pour l’exécution d’un nouvel ordre élémentaire, il doit adapter son propre plan à la nouvelle situation et définir à nouveau sa tournée. Après avoir reçu un ordre de la part d’un agent Prestataire, l’agent superviseur doit décomposer cet ordre en un ensemble d’ordres élémentaires afin d’être servi par plusieurs Agent planificateurs tout en minimisant le coût total. Cette décomposition des tâches constitue un problème crucial. Elle consiste à mettre au point des algorithmes et des stratégies performantes pour la résolution du problème d'affectation du trafic dans le transport routier. Ce problème connu dans la littérature sous le nom de problème de tournées des véhicules (PTV) (voir Figure 10) à été largement étudié par les chercheurs. Pour une étude plus détaillée du PTV, voir ( Fukasawa et al., 2004)

La plupart des techniques citées dans la littérature fournissent de meilleures solutions même pour de grandes instances du PTV, mais le problème qui persiste toujours, c’est le temps d’exécution prohibitif qui rend le choix d’implémentation de l’une de ces techniques dans le processus de prise de décision d’un SMA une tâche très délicate.

Dans ce travail, nous avons adopté une heuristique basée sur les réseaux de neurones de Hopfield (RNH) afin de permettre aux agents superviseurs de prendre des décisions temps réel face à ce problème combinatoire de  génération du plan global.

Le réseau de neurones de Hopfield (Hopfield, 1982) est un réseau de neurones analogues non linéaires extrêmement interconnectés (voir figure 11).

La sortie V_i de chaque neurone est calculée comme suit :

représente l’entrée d’une neurone i.

La fonction tanh(x) représente la tangente hyperbolique de x et λ est un paramètre constant.

Hopfield a prouvé il y’a deux décennies qu’un tel  réseau est très effectif en calcul combinatoire et peut  fournir rapidement des solutions calculées collectivement à une large classe de problèmes d’optimisation combinatoire (Hopfield, 1984). L’idée de base de l’algorithme d’optimisation combinatoire de Hopfield consiste à incruster la fonction objective et les contraintes du problème d’optimisation combinatoire original à résoudre dans la fonction d’énergie d’un RNH et laisser  la dynamique neuronale  conduire l’algorithme  à un état stable dans lequel toutes les sorties des neurones restent stables.

Pour une description plus détaillée de l’algorithme de RNH, se référer à  (Hopfield, 1984). Notre implémentation du RNH pour résoudre le problème de génération des plans est décrite dans le papier (Nejeoui, 2006).

Chaque agent planificateur se charge de planifier sa tournée afin de servir tous les AC inclus dans son plan commun à moindre coût, et à chaque fois qu’il décroche un accord pour l’exécution d’un nouvel ordre élémentaire, ce dernier doit mettre à jour son plan commun et, par suite, planifier à nouveau sa  tournée. Cela revient en pratique à résoudre un problème de voyageur de commerce .

Le PVC est défini comme suit : étant donné un ensemble fini de villes, on associe à chaque couple de villes (Li,Lj) un coût de transport dij, le problème consiste à trouver le chemin le moins coûteux pour visiter chaque ville une et une seule fois  et revenir au point de départ (voir figure 12). 

La résolution de ce problème NP-DUR par des méthodes exactes nécessite des temps de calculs prohibitifs pour les problèmes de taille réelle (Gutin et al., 2002). L’utilisation de méthodes approximatives qui tentent d’exploiter une certaine structure dans l’espace de recherche de solutions, en occurrence les heuristiques, fournissent parfois des résultats de qualité acceptable dans des temps raisonnables.    .

Par contre, nos expérimentations ont montré qu’aucune heuristique ne fournit à elle seule les meilleurs résultats pour la résolution des problèmes de l’ensemble de test TSPLIB (Reinelt, 1991). Il y’a donc pas d’heuristique universelle mais plutôt un sous-ensemble d’heuristiques qui, prises individuellement, fonctionnent correctement pour certaines instances de PVC. La qualité de la solution produite par les heuristiques dépend non seulement de la méthode de résolution mais est aussi influencée par les paramètres utilisés. Ainsi, un ensemble de paramètres pour une heuristique donnée fonctionnera bien pour un sous ensemble d’instances du PVC mais moins bien pour d’autres. Pour pallier ce  problème nous proposons de doter  chaque agent planificateur d’un ensemble d’heuristiques basées sur (les Algorithmes Génétiques (AG), l’heuristique de Lin-Kernighan (HLK) et la Recherche Taboue (RT)) qu’il déploie à chaque fois qu’il veut re-confectionner son plan afin d’adopter l’heuristique la plus appropriée dans un environnement coopératif distribué où chaque heuristique utilise différentes configurations de paramètres. Nous allons démontrer que cette combinaison d’heuristiques et de paramètres, en plus d’offrir une plus grande rapidité d’exécution, permet d’offrir une plus grande robustesse de la qualité de solution du PVC en comparaison avec les heuristiques prises individuellement.

Dans un travail antécédent (Nejeoui et al., 2006) nous avons traité l’aspect dynamique du SGTR,  En vue de montrer l’impact de la coopération inter compagnies sur les résultats de la planification statique, nous ne nous intéressons qu’à cette dernière, par application des RNH, et  nous insistons plus particulièrement sur la coopération inter compagnie via les agents superviseurs.

Dans le but d’illustrer notre proposition, nous allons considérer un exemple d’une compagnie de transport qui coopère avec une autre. Chacune des deux compagnies est caractérisée par un identificateur, ses coordonnées et sa flotte de véhicules. D’après notre approche, aux deux compagnies seront associées deux agents superviseurs AS₁ et AS₂ caractérisés par :

Chacune des deux compagnies dispose d’une flotte homogène de 10 véhicules de capacité maximale Q=1679.

Supposons que les deux agents superviseurs reçoivent respectivement les ordres suivants :  Γ₁(a₁,d₁,l), Γ₂(a₂,d₂,l), Γ₃(a₃,d₃,l) et Γ₄(a₄,d₄,l) répartis comme suit :

 Γ₁ et Γ₂ sont octroyés à AS₁, Γ₃ et Γ₄ sont octroyés à AS₂

Dans ce qui suit nous présentons les caractéristiques de chaque ordre :

d_i : quantité de marchandises demandée par le client i, L_i : son Numéro, (X_i,Y_i) : sa position.

La première étape consiste à générer les plans initiaux en décomposant chacun des ordres Γ₁, Γ₂, Γ₃ et Γ₄ en ordres élémentaires. Pour cela, chaque agent superviseur structure ses ordres en utilisant l’algorithme des réseaux de neurones de Hopfield. Après cette étape, nous obtenons la structuration des plans suivante :

Après cette étape, chaque agent superviseur aura deux plans initiaux à négocier et à attribuer à ses agents planificateurs

Chaque agent superviseur négocie ses ordres élémentaires avec ses agents planificateurs en incluant l’autre agent superviseur dans le processus de négociation.

La figure 13.a montre la solution pour distribuer les 4 ordres sans prendre en compte la coopération entre les deux AS et la figure 13.b montre la solution avec prise en charge de la coopération entre les deux AS.

Les paramètres qui influencent la qualité de la solution sont la distance totale (mesurée par une unité de mesure de distance arbitraire) parcourue par l’ensemble des APLs pour servir toutes les commandes des ACs ainsi que le nombre des APLs nécessaires pour accomplir la mission de transport (ce paramètre représente un critère important du point de vue économique). La figure 13 montre les résultats qui comparent les performances relatives de la solution obtenue par le SMAGTR avant et après l’intégration des techniques de coopération entre compagnies. Les résultats montrent que l’ordre élémentaire Γ¹₂  dont le coût d’accomplissement minimum par les APLs de AS₁ est  313.0958 (itinéraire rouge, Fig. 13.a) a été affecté par effet de coopération à AS₂ avec le coût 117.2835 (itinéraire rouge, Fig. 13.b). De même l’ordre élémentaire Γ²₂ dont le coût d’accomplissement minimum par les APLs de AS₁ est  551.3949 (itinéraire turquoise, Fig. 13.a) a été affecté par effet de coopération à AS₂ avec le coût 327.4671 (itinéraire turquoise, Fig. 13.b). De même l’ordre élémentaire Γ³₂ dont le coût d’accomplissement minimum par les APLs de AS₁ est  506.2059 (itinéraire vert brillant, Fig. 13.a) a été affecté par effet de coopération à AS₂ avec le coût 224.0676 (itinéraire vert brillant, Fig. 13.b). L’agent superviseur AS₂ a aussi sous-traité l’ordre Γ₃,  dont le coût d’accomplissement par ses propres APLs est estimé à 230.0052 (itinéraire vert d’eau, Fig. 13.a), à AS₁ avec le coût 72.6308 (itinéraire vert d’eau, Fig. 13.b).

On constate que l’introduction des techniques de planification coopérative entre compagnies a permis au SMAGTR de passer d’un coût total de 2221.7981 pour servir les 4 ordres sans prise en compte de la coopération entre AS1 et AS2 à un coût de  1505.3596 avec la prise en compte de la coopération, soit un gain de performance égal à 716.4385, c’est-à-dire un taux de 32.24%.

Réaliser une telle performance permet de justifier l’intégration d’une planification coopérative dans la démarche de prise de décision des compagnies de transport routier.

Dans ce papier, nous avons présenté une approche basée sur la classification des agents pour la modélisation des SGTR. Nous avons couplé les techniques de l’IAD notamment la décomposition et l’allocation des tâches d'une part, la planification décentralisée et la négociation,  d'autre part et enfin les heuristiques de la Recherche Opérationnelle, afin de gérer des ordres de transport reçus par les compagnies de manière asynchrone et dynamique.

Au niveau de la planification des tâches, nous avons adopté une stratégie à deux niveaux. Le premier prend en compte la génération des plans initiaux en se basant sur une approche coopérative. Le second prend en charge la planification locale des agents planificateurs. Cette planification est basée sur plusieurs heuristiques, dont seule la plus appropriée est adoptée.

Dans ce travail, nous avons prouvé que l’approche multi-agent a des avantages certains, elle fournit une flexibilité accrue en permettant de varier dynamiquement le nombre d’agents. De plus, alors que la portée des algorithmes de la recherche opérationnelle reste limitée aux problèmes de routage statique, l’approche multi-agent permet de concevoir des systèmes temps réel capables de faire face à des problèmes de planification dynamiques et de prendre en charge l’évolution de l’environnement au cours de l’exécution. Elle assure une meilleure adaptabilité du système à son environnement.

L’approche proposée est très prometteuse dans le domaine de la conception et de l’analyse des systèmes distribués (caractérisés par une inhérente distribution des connaissances et des contrôles). Mais c'est le cas également dans tous les modes de transport : routier, maritime, ferroviaire et aérien. Actuellement, nous sommes en train d’étudier l’intégration du raisonnement à base de cas au niveau de la planification dynamique. Dans un futur travai,l nous projetons d’adopter cette approche pour englober les autres modes de transport, dans le but de modéliser un système multi-agents de gestion de transport intermodal (SMAGTI). En vue de compléter la conception d’un SMAGTI, nous visons l’implémentation du sous-système Ergonomique selon les spécifications de la plate-forme FIPA-OS afin de permettre au SMAGTI de gérer, dans un environnement ergonomique, les prestations de transport incidentes indépendamment du moyen de transport utilisé (camions, bateaux, trains, avions).