La planification des t�ches dans les Syst�mes de Gestion de Transport Routier (SGTR) est un �probl�me qui peut �tre consid�r� comme dynamique, dans la mesure o� les ordres ne sont pas tous connus � l?avance. Les compagnies peuvent recevoir de nouveaux ordres de mani�re asynchrone et dynamique et doivent les inclure dans leur processus de planification. De plus, l?aspect dynamique est induit par les changements que peuvent subir les ordres. La taille r�elle d?un ordre, par exemple, peut �tre corrig�e au moment o� le v�hicule est sur le lieu du ramassage. Les v�hicules peuvent avoir du retard, d?autres probl�mes impr�vus, comme les pannes ou les accidents qui peuvent rendre les v�hicules indisponibles temporairement.

Dans ce travail, nous proposons un Syst�me Multi-Agent pour g�rer les probl�mes de planification des t�ches li�es au transport routier des marchandises. Dans notre approche, nous �visons principalement les objectifs suivants�:

Dans un premier temps, nous nous int�ressons � la �mod�lisation d?un SGTR en utilisant une infrastructure multi-agents, en particulier des agents sp�cialis�s, tout en d�ployant les techniques de coop�ration (Jensen et al., 2003), n�gociation (Kraus, 1997), d�composition et affectation des t�ches, comp�tition (Michael et al., 2003) et planification distribu�e afin de permettre au syst�me de g�rer des ordres qui arrivent de mani�re asynchrone et dynamique et de r�agir en temps r�el aux �v�nements impr�dictibles qui peuvent survenir au cours de l?accomplissement des ordres.

En second lieu, nous proposons une mod�lisation des agents, leur coop�ration et leurs interactions en utilisant l?approche AUML.

En troisi�me lieu, nous abordons le probl�me de la planification. Pour cela, nous proposons deux planifications. La premi�re est une planification statique qui concerne la g�n�ration des plans de chaque v�hicule. A ce niveau, nous proposons une planification coop�rative entre les diff�rentes compagnies en vue d?optimiser les plans de chacune d?entre elles. La seconde est une planification dynamique, qui traite de la planification propre � chaque v�hicule. Au niveau de cette derni�re, nous proposons une approche hybride qui utilise plusieurs heuristiques. Enfin, nous illustrons par une application le fait que l'impact relatif d'une planification coop�rative augmente avec la complexit� du probl�me. Nous offrant en m�me temps des solutions comp�titives en temps r�el � des probl�mes de grandes tailles, gr�ce aux techniques de coop�ration et de planification d�centralis�e et nous montrons que les ordres dynamiques ne pr�sentent aucune difficult� de gestion. Nous montrons dans une s�rie de r�sultas exp�rimentaux qu?une augmentation significative des performances est r�alis�e par les compagnies qui peuvent n�gocier et coop�rer entre elles, par opposition aux compagnies qui utilisent les techniques de planification usuelles.

Le reste de ce papier est organis� comme suit. Dans la deuxi�me section, nous pr�sentons notre approche. La troisi�me section donne une description d�taill�e des diff�rents composants de notre syst�me multi-agents et pr�sente le mod�le construit en utilisant les sp�cifications du langage unifi� de mod�lisation agent (AUML). Dans la quatri�me section, nous d�finissons les protocoles de communication et de n�gociation entre les diff�rents agents du SGTR. La section 5 d�crit �la coop�ration entre compagnies et explique le processus de d�composition des t�ches�sur les v�hicules transporteurs en utilisant les r�seaux de neurones de Hopfield. Dans la sixi�me section, nous introduisons le probl�me de planification des tourn�es et nous d�crivons bri�vement les diff�rentes heuristiques utilis�es pour planifier les tourn�es de chaque v�hicule transporteur. Les r�sultas exp�rimentaux sont illustr�s par une application dans la septi�me section. Et enfin, nous terminons ce papier par une conclusion et les perspectives de ce travail.

Dans notre approche, nous avons mod�lis� le SGTR par un syst�me multi-agents bas� sur la classification des diff�rents agents en cinq sous-syst�mes�: sous-syst�me de supervision, sous-syst�me de planification, sous-syst�me client, sous-syst�me ergonomique et sous-syst�me prestataire. Ensuite, nous avons proc�d� � la mod�lisation des diff�rents agents par le langage AUML.

La planification se fait en deux phases�: une planification statique et une planification dynamique. La premi�re concerne le d�but du processus de routage. Dans cette phase, la compagnie se charge de distribuer tous les ordres sur ses v�hicules transporteurs en r�solvant un Probl�me de Tourn�es des V�hicules (PTV) statique par l?heuristique R�seaux de Neurones de Hopfield (Hopfield, 1982); il en r�sulte la g�n�ration des tourn�es initiales. Ensuite, la compagnie subdivise l?ensemble des clients � desservir en plusieurs secteurs (par exemple secteur A, secteur B,?). Les v�hicules qui desservent une r�gion sp�cifique constituent une caste (Zhu et al., 2005) qui porte le m�me nom du secteur (donc on aura caste A, caste B, ?). Les v�hicules faisant partie de la m�me caste peuvent coop�rer et n�gocier entre eux des appels d?offre mono caste (au sein de la m�me caste) pour optimiser �leur propre plan ou bien pour r�soudre des impr�vus qui surviennent au cours de la distribution comme l?embouteillage, les accidents ou les pannes.

La deuxi�me phase se d�roule au cours de la distribution des ordres dynamiques. A ce stade, la compagnie peut recevoir de nouveaux ordres de mani�re asynchrone et dynamique. Pour chaque nouvel ordre, elle lance un appel d?offre dynamique � l?ensemble des castes. Nous parlons dans ce cas d?appel d?offre multi-caste. Le v�hicule ayant d�croch� l?ordre doit mettre � jour sa tourn�e de mani�re dynamique, en d�ployant plusieurs heuristiques � savoir�: les Algorithmes g�n�tiques, l?heuristique de Lin- Kernighan et la Recherche Taboue, de fa�on � �inclure le nouvel ordre.

Dans notre approche, nous consid�rons un syst�me SGTR comme un ensemble de compagnies, de v�hicules, de prestataires et de clients (voir Figure 1). Le but de chaque compagnie est de distribuer des ordres qui leur arrivent de mani�re asynchrone et dynamique d?un ensemble de clients �tout en optimisant la planification de ses t�ches, ce qui explique l?aspect comp�titif et concurrent entre diff�rentes compagnies. Toutefois, il se peut que la complexit� ou la taille d?un ordre octroy� � une compagnie exc�de ses capacit�s, c?est l� o� la coop�ration entre diff�rentes �compagnies risque de s?imposer afin de mieux r�pondre � la demande de mani�re satisfaisante.

Dans notre approche, nous proposons une mod�lisation d?un SGTR en deux niveaux�: le premier concerne la mod�lisation d?un SGTR par un Syst�me Multi-Agents de Gestion de Transport Rotier (SMAGTR) et le second traite la mod�lisation des agents par l?approche AUML.

Nous proposons de d�ployer la technologie des agents intelligents pour la mod�lisation d?un SGTR. Les qualit�s des agents d?un SMAGTR sont les suivantes�:

• L?autonomie : l'agent agit sans l'intervention d'humains ou d'autres intervenants, et a un certain contr�le sur ses actions et ses �tats internes.

• L?habilit� sociale : l'agent interagit avec d'autres agents (pouvant �tre des �tres humains) � l'aide d'un langage de communication d'agent.

• La r�activit� : l'agent per�oit son environnement (pouvant �tre un monde physique, un utilisateur via une interface graphique, un ensemble d'autres agents ou encore tous ces �l�ments combin�s), et r�pond de mani�re opportuniste aux changements qui y surviennent.

• La pro-activit� : l'agent n'agit pas simplement aux stimuli de son environnement, il est aussi capable de d�montrer des comportements dirig�s par des buts en prenant des initiatives.

De plus, ces �agents sont �quip�s de techniques de planification et d?optimisation, de connaissances sur les objets qui utilisent des protocoles de communication et de n�gociation pour l?interaction et la coop�ration entre eux.

Le premier objectif de notre travail est la mise en place d?une infrastructure multi-agents sur la base d'une classification d?un SGTR suivant ses diff�rentes t�ches. Cette classification permet de regrouper toutes les t�ches fortement li�es dans un sous-syst�me et celles n?ayant pas ou peu de relations entre elles dans d?autres sous-syst�mes diff�rents. Le r�sultat de cette classification est un ensemble de sous-syst�mes caract�ris�s par une forte coh�sion et un faible couplage. Ainsi, toutes les t�ches se rapportant � la gestion du fret et du chargement des marchandises seront regroup�es dans un sous-syst�me, les t�ches se rapportant � la gestion v�hicule-conducteur �seront regroup�es dans un sous-syst�me et enfin les t�ches se rapportant � la gestion de la flotte de v�hicule seront regroup�es dans un sous-syst�me. Un SGTR sera par cons�quent compos� des cinq sous-syst�mes suivants�(voir figure 2) :

• Un sous-syst�me de Supervision charg� de la supervision du SGTR. Il est constitu� d?un seul agent superviseur; il poss�de une interface de communication et de n�gociation avec les autres sous-syst�mes. Ce sous-syst�me sera mod�lis� par un agent superviseur.

• �Un sous-syst�me de Planification charg� de la gestion du fret, la planification des tourn�es des v�hicules et la planification des op�rations de chargement/d�chargement. Ce sous-syst�me re�oit des ordres (messages) de la part du sous-syst�me superviseur. Pour servir un ensemble de clients, il doit optimiser les itin�raires (en d�ployant plusieurs heuristiques) afin de minimiser le co�t total. �Ce sous-syst�me sera mod�lis� par un ensemble d?agents (Agents planificateurs).

• Un sous-syst�me Client compos� de l?ensemble des clients et charg� de g�rer et de suivre ses diff�rentes commandes. Ce sous-syst�me sera mod�lis� par un ensemble d?agents (Agents Clients).

• Un sous-syst�me Prestataire charg� de g�rer les diff�rentes prestations de transport. Ce sous-syst�me sera mod�lis� par un ensemble d?agents (Agents prestataires).

• Un sous-syst�me Ergonomique charg� de la mise en oeuvre des connaissances relatives � un �v�hicule et aux itin�raires n�cessaires. Il s?occupe aussi de g�rer les infrastructures mat�rielle et logicielle disponibles pour que les missions de transport puissent �tre accomplies avec un maximum de confort, de s�curit� et d'efficacit�. Ce sous-syst�me sera mod�lis� par un ensemble d?agents (agents ergonomiques).

Donc un SGTR sera mod�lis� par un Syst�me Multi-Agents de Gestion du Transport Routier (SMAGTR). Dans ce qui suit, nous pr�sentons les diff�rents agents qui composent le SMAGTR (voir Figure 3).

L?Agent PRestataire (APR) peut repr�senter une unit� de production, un d�p�t de produits finis ou encore le d�partement de distribution d?une entreprise, sa t�che principale est d?octroyer des prestations de transport aux agent Superviseurs sous forme�: ��transporter A unit�s de marchandises du d�p�t d et distribuer les quantit�s q₁,?,q_n respectivement sur les Agents Clients C₁,?,C_n�.

L?Agent Superviseur (AS) repr�sente une compagnie de transport, apr�s avoir re�u un ordre de la part d?un APR, le d�composer en sous-ordres qui feront l?objet de n�gociation avec ses Agents Planificateurs, le m�canisme de n�gociation est r�git par le protocole Contract Net (Smith, �1980).

L?Agent PLanificateur (APL) repr�sente un v�hicule transporteur avec son conducteur, sa t�che principale est l?�laboration de ses plans locaux. Il doit �tre capable d'effectuer des livraisons de commandes pour plusieurs clients, g�n�rer des plans locaux et n�gocier avec les autres agents planificateurs faisant partie de sa caste afin �de minimiser le co�t de son plan commun. Chaque agent re�oit des sous-ordres sous la forme: " transporter A unit�s de marchandises du d�p�t d et distribuer les quantit�s q₁,?,q_n respectivement sur les Agents Clients C₁,?,C_n. Apr�s avoir livr� toutes les commandes, les agents planificateurs doivent retourner � leur ville de d�part.

Chaque ordre re�u par l?agent superviseur est attribu� � un groupe d?agents Planificateurs qui constituera une caste. Seuls les agents issus d?une m�me caste peuvent coop�rer et n�gocier entre eux.

Il est charg� de �la mise en oeuvre des connaissances relatives � un �v�hicule et aux itin�raires n�cessaires. Il s?occupe aussi de g�rer les infrastructures mat�rielle et logicielle disponibles pour que les missions de transport puissent �tre accomplies avec le maximum de confort, de s�curit� et d'efficacit�.

Les autres fonctions qui seront associ�es � un agent Ergonomique peuvent �galement �tre assez vari�es �:

• La v�rification, avant le d�part, de la bonne maintenance du v�hicule conform�ment aux interventions planifi�es par l?applicatif.

• Le contr�le automatique de l?�tat du v�hicule et notamment des fonctions �lectrom�caniques et �lectromotrices et la m�morisation des valeurs d�s que le v�hicule entre dans une zone d?alerte.

• L?aide � la conduite par la pr�sence d?une s�rie d?outils (destin�s � saisir et � analyser les donn�es relatives � l?environnement dans le but de d�tecter des anomalies (d�tection d?obstacles, embouteillage?).

• L?assistance au conducteur regroupe des outils et services import�s temporairement (via Internet ou par chargement � bord) tels que des cartes g�ographiques num�ris�es, des programmes p�dagogiques.

L?Agent Client (AC) repr�sente les destinataires finaux de la marchandise � distribuer. Cet agent coop�re avec l?APL charg� de le servir pour le tenir inform� de tout changement concernant les fen�tres de temps ou le temps de service. Apr�s avoir re�u sa livraison, l?agent client envoie un message � l?APR responsable de cette prestation contenant�: l?heure d?arriv�e, l?heure de d�part de l?APL , la d�signation et la quantit� de marchandise livr�e. Un message semblable est transmis par l?APL responsable vers son AS.

Le langage unifi� de mod�lisation agent (AUML) (Odell and al., 2000) a �t� d�velopp� par le comit� technique de mod�lisation de FIPA (Fondation for Intelligent Physical Agents) comme nouvelle �m�thodologie capable de traiter les particularit�s des syst�mes multi-agents et de construire des mod�les bas�s sur �le concept d'agent comme concept de base.

Le premier niveau de la mod�lisation AUML d�finit les classes d?agents qui forment le SMAGTR et les fonctionnalit�s qu?elles offrent dans les actes communicatifs. La figure 4 repr�sente un diagramme d?agents qui d�taille les diff�rentes fonctions des agents en montrant la hi�rarchie des classes utilis�es pour l?impl�mentation des agents. L?agent g�n�rique de FIPA au sommet du diagramme d�finit les fonctionnalit�s basiques qu?un agent doit impl�menter afin d?�tre compatible avec la plateforme du SMAGTR et qui sont limit�es � l?enregistrement de l?agent avec la plateforme local FIPA-OS. L?intention derri�re la cr�ation d?un agent g�n�rique est tout simplement de montrer les diff�rentes �tapes n�cessaires pour cr�er un agent qui peut �tre instanci� et enregistr� dans la plateforme du SMAGTR.

Pour donner une repr�sentation plus appropri�e que le diagramme de la figure 4�, nous d�taillons les fonctionnalit�s et les comportements des agents en utilisant le diagramme d?agent AUML, qui a �t� propos� par Bauer en 2001 (Bauer, 2001).

Chaque agent est repr�sent� sous la forme d?un rectangle divis� en cinq compartiments. Les �figures 5, 6, 7, 8 et 9 d�crivent respectivement la mod�lisation des Agents Superviseur, Prestataire, Ergonomique, Client et Planificateur. Le nom de chaque agent est d�fini au sommet d?un rectangle; en dessous sont repr�sent�s ses attributs relatifs � son �tat (ses croyances); les actions que l?agent peut ex�cuter sur son environnement sont repr�sent�es dans le troisi�me compartiment; les autres fonctions �num�r�es dans le quatri�me compartiment sont des m�thodes standards Java. Le dernier compartiment repr�sente la librairie des actes communicatifs que l?agent peut ex�cuter en tant que parties de protocoles sp�cifiques.