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).