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.