Une approche multi-agent pour la logistique liée à la production et au transport

21/10/2017
Publication REE REE 2005-1
OAI : oai:www.see.asso.fr:1301:2005-1:20576
DOI :

Résumé

Une approche multi-agent pour la logistique liée à la production et au transport

Métriques

10
5
3.07 Mo
 application/pdf
bitcache://de9b6f482a6594ee0763d8bca0e9f25c16dbc482

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2005-1/20576</identifier><creators><creator><creatorName>Khaled Ghedira</creatorName></creator><creator><creatorName>Meriem Ennigrou</creatorName></creator><creator><creatorName>Imen Bouda</creatorName></creator></creators><titles>
            <title>Une approche multi-agent pour la logistique liée à la production et au transport</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 21 Oct 2017</date>
	    <date dateType="Updated">Sat 21 Oct 2017</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">de9b6f482a6594ee0763d8bca0e9f25c16dbc482</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34748</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

. DOSSier) LOGISTIQUE ET TRANSPORT a Une approche multi-agent pour M'r la logistique liée à la production et au transport Par Khaled GHÉDIRA', Meriem ENNIGROU 1, Imen BOUDALI 1 UR. SOIE Stratégies d'optimisation de l'ingénierie des informations et de la connaissance 1 ENSI, Ecole nationale des sciences de l'informatique, Tunisie ISG, Institut supérieur de gestion, Tunisie 6, e e Mots clés Gestion deproduction, Transport, Systèmes muttf-agents, Optimisation, JobShop, Problème detournées devéhicules, Recherche tabou, Formation decoalitions Introduction Comment gérer un stock ou plusieurs stocks distants et/ou interdépendants, comment affecter des tâches à des ressources, comment ordonnancer une production, com- ment livrer la marchandise à des clients homogènes ou hétérogènes et dispersés géographiquement, comment transporter des voyageurs d'un point à un autre, etc. Telles sont les préoccupations de SOIE, l'objectif étant la recherche d'une solution optimale si possible, ou une très proche le cas échéant, et ce avec un temps de résolution minimal. Plusieurs travaux de recherche ont été proposés dans ce cadre, le souci étant double : qualité et complexité. Deux aspects ont ainsi été abordés : la modélisation et la résolution. Du point de vue modélisation, différents forma- lismes ont été utilisés : logique classique et non classique (Ferzan 02) (Kacem & al. 02), PLNE (Programmation Linéaire en Nombres Entiers) (Toth & Vigo 02), CSP (Constraint Satisfaction Problem) (Sadeh & Fox 91) (Nuijten & Aarts 94), SMA (Fisher & Kuhn 93) (Liu & Sycara 93), etc. Du point de vue résolution, deux familles de méthodes ont été explorées : les méthodes exactes telles que le branch and bound (Caseau & Laburthe 95) (Perregaard & Clausen 98) et les méthodes inexactes telles que (Prins 02) (Bouthilliera & Crainic 03) (Berger & Barkaoui 04) (Homberger & Gehring 04) (Tsai & al. 04). L'approche adoptée par l'équipe « logistique et trans- port » de notre unité de recherche SOIE est celle d'utili- ser les SMA et/ou le formalisme CSP pour la modélisa- tion. Ainsi, le problème classique d'allocation de tâches à des ressources a été modélisé sous forme de deux classes d'agents : des agents Tâche et des agents Ressource (Ghédira 94a) (Ghédira 94b). Un problème de Floiv Shop et un problème de Job Shop flexible ont été également ESSENTIEL SYNOPSIS La plupartdes problèmes relatifsà la gestion de production et au transportsont,d'unepart,NP-complets et d'autrepart,omniprésents dans différents domaines industriels. D'où !'intérêt de plusieurs communautésnotammentde gestion,d'automatiqueet d'informa- tique,et d'où également la propositionde plusieursapproches: des méthodesde résolutioncomplètesou incomplèteset diversforma- lismesde rechercheopérationnelle ou d'intelligence artificielle... L'approche adoptée par l'équipe « logistique et transport » de l'unité de rechercheSOIEest celle d'utiliser les systèmes multi- agents (SMA) et/ou le formalisme CSP (Constraint Satisfaction Problem)pour la modélisation.Quantà la résolution, elleest abor- dée sur la base d'interactions entre agents et/ou sur des méthodes d'optimisation incomplètes. L'objectif étant d'une part unereprésentation fidèfede l'aspect souventdistribuédesproblèmes traités et, d'autre part, uneaccélérationde la résolution.Plusieurs travauxde l'équipe sont présentéset commentés danscet article. Deuxd'entre eux sont détaillés: le premierconcerneun problème d'ordonnancementd'un atelier de type Job Shop et le secondse réfère à un problèmede tournées de véhicules. Most of problems relatedto ProductionManagementand trans- portation are, on the one hand, NP-completeand on the other hand, frequently met in different industrial domains. Therefore, several communities, like those of Management, automatic control and computer science, have been interested in such pro- blems and several approaches have been proposed for their modelingand their solving : complete and incompletemethods. The approachadopted by the team « logistlcandtransportation» of the researchunit SOIE isto use the Multi-AgentSystemand/or the Constraint Satisfaction Problem formalism for modeling. Whereas, agent interaction and/or incomplete optimization methods have been applied for solving. Theobjective is, on the one hand, to represent faithfully the aspect often distributed of the consideredproblems and on the other hand,to accelerate the solving process. ln this paper, we present and comment many researchworks of our team. Particularly, we wi focus on two of them : the firstconcernsa Job Shop SchedulingProblemand the secondrefers to a VehicleRouting Problem. REE No 1 Janvier 2005 m D o s s i e r LOGISTIQUE ET TRANSPORT abordés par des agents Ressource et des agents Job (Daouas & al. 95a) (Daouas & al. 95b) (Ennigrou & Ghédira 04a) (Ennigrou & Ghédira 04b). Un problème de transshipment ou transfert de marchandises entre des stocks appartenant à différents points de vente a été traité, lui aussi, en termes d'agents Site et agents Interface (Abdeljaouad & Ghédira 04). La chaîne logistique ou supply chain a été également étudiée par le biais d'agents Fournisseur, agents Clierzt, agents Transport, agent c tD c Place de iiiai-ché, acrent Eiitrel) rise, acrents Sous-traitant (Siala & Ghédira 02). Un système d'information lié aussi à la gestion de production d'une entreprise a été proposé sur la base d'agents Client, agents Fournisseur, agents Partenaire, agents Pilotage, agents Planification, agents Ordonnanceur, agents Fabrication, agents Maintenance, agents Concurrent, agents Contrôle Qualité, agents Gestion des stocks et des approvisionne- rnerzts et agents Etude des niéthodes (Hsairi & al. 04). Par ailleurs, un problème de tournées de véhicules à fenêtres temporelles (PTVFT) a été modélisé sous forme d'un CSP puis d'agents Clients en interactions (Kéfi & Ghédira 04a) (Kéfi & Ghédira 04b). Quant à la résolution, elle est abordée sur la base de méthodes d'optimisation incomplètes et/ou d'interac- tions entre agents. Dans le cas, par exemple, des problèmes d'affectation ou du Flokv Shop cités précé- demment, le recuit simulé a été distribué au niveau des agents Ressource. Ainsi, chaque agent Ressource possè- de son propre recuit simulé qu'il gère de manière auto- nome et locale. Par ailleurs, un mariage entre la recherche tabou et les SMA a donné lieu, dans le cadre du problème du Job Shop flexible, à un modèle qui sera détaillé dans le paragraphe 1. Quant au modèle à base d'interactions et de formation de coalitions d'agents pro- posé dans le cadre du PTVFT, il sera détaillé dans le paragraphe 2. D'autre part, d'autres travaux sont menés par les équipes « CSP » et « optimisation » de SOIE dont l'objectif est d'accélérer des méthodes d'optimisation incomplètes tout en gardant une bonne qualité de la solution finale et ce, soit par coopération entre différentes métaheuristiques, soit par distribution à l'aide des SMA comme c'est le cas des algorithmes génétiques (Bouamama & Ghédira 04) (Jlifi & Ghédira 02), soit par des enrichissements de l'algorithme à base de colonies de fourmis (Alaya & Ghédira 04) ou encore l'algorithme de recherche tabou (Hammami & Ghédira 03). Ces travaux sont validés sur la base des formalismes max-CSP (problèmes de satisfaction maximale de contraintes) ou CSOP (CSP plus optimisation d'une fonction objectif ou coût) dérivés du CSP, formalisme générique qui permet de modéliser facilement les problèmes liés à la gestion de la production et au transport. Un CSP est, en fait, la donnée d'un ensemble de variables munies chacune d'un domaine discret de valeurs possibles, et d'un ensemble de contraintes portant sur ces variables. Trouver une solution d'un CSP consiste à instancier chaque variable, c'est-à-dire lui affecter une valeur de son domaine et ce, de manière à satisfaire toutes les contraintes. Dans un CSOP, cette solution doit, en plus, optimiser une fonction coût. Dans un max-CSP, il s'agit de trouver une instan- cou tD ciation de toutes les variables qui satisfasse le maximum de contraintes. Approche multi-agent basée sur la recherche tabou pour le job shop flexible 1.1. Problématique Le problème Job Shop est un des problèmes d'ordon- nancement les plus complexes. Il consiste à réaliser un ensemble de jobs ;,..., J,,j sur un ensemble de ni ressources JRI,.... Rlllj* Chaque job Ji, i=],.... n, est composé d'une suite de ni opérations devant être exécutées sur les différentes res- sources selon un ordre préalablement défini. Cet ordre est appelé gar2nie opératoire et traduit les contraintes de précédence entre les différentes opérations du job. Par ailleurs, chaque opération possède une durée de traite- ment connue à l'avance et elle ne peut être exécutée que par une et une seule ressource. De plus, chaque job doit être réalisé dans un intervalle de temps déterminé par la date de début au plus tôt du job ou release date, avant laquelle le traitement ne peut pas commencer, et par sa date de fin au plus tard ou due date, déterminant une limite supérieure pour la fin de réalisation. Ces contraintes définissent les contraintes temporelles rela- tives au job. En outre, une ressource ne peut exécuter qu'une seule opération à un instant donné, ce qui définit les contraintes disjonctives des ressources, et une opéra- tion ne peut pas être interrompue une fois qu'elle est commencée. Une solution consiste alors à définir pour chaque opération une date de début satisfaisant l'en- semble des contraintes. Le problème Job Shop flexible représente une géné- ralisation du problème présenté précédemment, du fait qu'une opération donnée a le choix entre plusieurs res- sources et possède une durée de traitement dépendant de la ressource utilisée. L'ensemble des contraintes de ce problème est aussi composé des contraintes de précéden- ce, contraintes temporelles et contraintes disjonctives. Une solution au problème Job Shop flexible ne consiste plus uniquement à trouver une séquence des opérations sur chacune des ressources et à leur fixer une date de début, mais également à déterminer une affectation de chaque opération à l'une de ses ressources potentielles, de telle sorte que la durée totale de l'ordonnancement soit minimisée. REE ? ! Janvier 2005 Une approche multi-agent pour la logistique liée à la production et au transport 1.2. Modélisation 1.2. 1. Architecture multi-agent D'après la définition du problème Job Shop flexible, on dégage deux classes de contraintes : celles qui concer- nent les jobs, à savoir les contraintes de précédence et les contraintes temporelles, et celles relatives aux ressources, à savoir les contraintes disjonctives. Par conséquent, le modèle multi-agent proposé (Ennigrou & Ghédira 04) est constitué de deux classes d'agents : les agents Job et les b tD agents Ressozr-ce responsables de la satisfaction de ces deux types de contraintes. De plus, une troisième classe d'agents, contenant un seul agent, l'agent Inrerface, est ajoutée au modèle. Cet agent contient le noyau du pro- cessus de résolution, soit la méthode de recherche tabou. D'autre part, cet agent joue le rôle d'interface entre cette société d'agents et l'utilisateur. Après avoir déterminé le meilleur voisin à proximité de la solution courante, l'agent Interface envoie l'opéra- .face envoie l'opéra- tion en question à son agent Job correspondant pour l'in- former du mouvement à effectuer. Le nouvel état ainsi obtenu contient éventuellement des conflits de chevau- chement qui seront résolus de la même manière que décrit précédemment. Lorsque le nombre d'itérations effectuées après la dernière solution optimale dépasse un certain seuil défini au préalable, une phase de diversification est lancée. Cette phase consiste à diversifier la recherche afin d'explorer de nouvelles zones de l'espace de recherche. Dans notre approche, une telle phase est caractérisée par le replacement d'un certain nombre d'opérations choisies aléatoirement. Le replacement d'une opération est effectué sur l'une de ses ressources potentielles, choisie elle aussi de manière aléatoire. 1.2.2. Dynamique multi-agent La dynamique globale de ce modèle est composée essentiellement de deux phases : la détermination d'une solution initiale et l'application de la méthode de recherche tabou pour déterminer une solution optimale du problème. La solution initiale est le résultat de la coopération entre les différents agents du système. Initialement, l'agent Interface crée les différents agents Job et b Zn Ressource du système et demande aux agents Job de déterminer une affectation initiale pour chacune de leurs opérations, en choisissant une ressource parmi les res- sources potentielles et une date de début d et ce, de la façon suivante : s'il s'agit de la première opération du job, alors d est égale à la date de début au plus tôt du job. Sinon, d est égale à la date de fin de son opération précédente. Cette affectation initiale est ainsi admissible, elle garantit la satisfaction des contraintes de précédence et des contraintes temporelles. Reste donc à satisfaire les contraintes disjonctives. Pour résoudre un conflit de che- vauchement entre deux opérations données, l'agent Job de l'une de ces opérations essaye de trouver un autre empla- cement et ce, en coopération avec les agents Ressource potentiels de l'opération en question. Cet emplacement doit satisfaire toutes les contraintes du problème. Si après un certain nombre de tentatives il échoue à trouver un tel emplacement alors l'agent Job demande aux agents Ressource de créer un emplacement spécialement pour cette opération. Ce dernier doit de même satisfaire toutes les contraintes du problème. La terminaison de cette étape est assurée par un nombre d'itérations maximales. Une fois la première phase terminée, et une fois cette solution initiale reçue, l'agent Interface lance alors le c processus de recherche tabou. 1.2. Méthode de recherche tabou La méthode de recherche tabou est une méthode d'optimisation combinatoire basée sur le principe de la recherche locale. Partant d'une solution initiale, le pro- cessus de recherche consiste à choisir, à chaque étape, le meilleur voisin de l'état courant qui ne soit pas tabou, c'est-à-dire non visité durant les dernières itérations. On appelle le chemin critique d'une solution un chemin dont la longueur est égale à la longueur de l'ordonnancement et qui est constitué par des opérations reliées soit : . par un lien de précédence, . par un lien disjonctif (pouvant être réalisées par la même ressource). Une opération critique est une opération appartenant au chemin critique. Quant aux paramètres de la recherche tabou proposée, ils sont définis comme suit. Le voisinage d'une solution S est alors obtenu par deux types de mouvements : 1. Permutation de deux opérations critiques adja- centes exécutées par la même ressource, 2. Replacement d'une opération critique sur une autre ressource pouvant l'exécuter. Concernant les paramètres d'évaluation, ils sont basés sur le calcul des dates de début d'un sous-ensemble d'opérations qui sont effectivement concernées par le mouvement et ce, afin de réduire la complexité de la recherche tabou. 1.3. Expérimentation Une série d'expérimentations a été effectuée sur des benchmarks connus dans la littérature définis dans : REE No 1 Janvier 2005 M L) ossier LOGISTIQUE ET TRANSPORT Brandimarte 93, Chambers & Barnes 96, Dauzerre-Peres & Paulli 97, (Hurink & al. 94. Ces benchmarks représentent des problèmes dont le nombre de jobs varie de 10 à 20, le nombre de ressources de 5 à 20, le nombre d'opérations par job de 5 à 25 et le nombre moyen de ressources potentielles par opération de 1 à 3. Ce qui donne des pro- blèmes de nombre total d'opérations variant de 50 à 500. C Q g5 1200 CD cu 800 LB .9c ; 0 LB : : J 600 ë \ DUB / " a LB 0 Min / !V) !D 400 o CO : : J 0 LI là, UJ Benchmarks proposés parBrandimarte 93 Figure 7 Réstiltats exl) éi-ii7ieiitaitx. La figure 1 présente une comparaison entre la solution initiale et la solution optimale fournies toutes les deux par notre approche, ainsi que les bomes inférieures et supérieures trouvées dans la littérature pour les benchmarks considérés. La légende est la suivante : les coûts des solutions proposées dans la littérature pour ces benchmarks sont bornés par : . UB (Ulgper Boand) : borne supérieure . LB (Loivei- Bound) : borneinférieure En plus, la figure illustre la solution initiale à partir de laquelle le processus commence, à savoir CO dans la figure, ainsi que la meilleure solution fournie par notre approche, à savoir Min dans la figure. 2. Approche basée sur la génération dynamique de coalitions pour la résolution d'un problème de tournées de véhicules 2.1. Problématique Le problème de tournées de véhicules (PTV) consiste à déterminer un ensemble de tournées pour une flotte de véhicules devant servir un ensemble de clients dispersés géographiquement dans un réseau routier et ce, avec le minimum de coût possible. Les tournées choisies doivent satisfaire certaines contraintes opérationnelles qui dépen- dent de la nature des biens transportés, de la qualité du service et des caractéristiques des véhicules et des clients. La variante du PTV à laquelle nous nous sommes inté- ressés dans notre travail est le PTV avec fenêtres de temps (PTVFT, Toth & Vigo 02) où chaque client dispo- se d'une fenêtre de temps durant laquelle il peut être servi par un véhicule. L'objectif que nous nous sommes fixé, au départ, est de contribuer à la résolution comportant des PTV avec fenêtres de temps avec une nouvelle approche distribuée. D'où l'idée d'explorer le raisonnement à base de forma- tion de coalitions entre agents (Sichman 98). Ainsi, un premier modèle, nommé Coal-PTV (résolution via la for- mation de coalitions d'un PTV, Kéfi & Ghédira 04b), a été proposé puis enrichi, ce qui a donné lieu au modèle Dy-Coal (Boudali & al. 04). Ces deux modèles font l'objet des deux sections suivantes. Mais rappelons tout d'abord la définition d'une coalition. D'après Vauvert & Seghrouchni, une coalition est une organisation à court terme basée sur des engagements spécifiques et contextuels, ce qui permet aux agents de coexister tout en bénéficiant de leurs compétences respectives. 2.2. Le modèle de base Ce modèle appelé Coal-PTV (Kéfi & Ghédira 04a) se base sur une architecture multi-agent constituée de deux types d'agents à savoir : les agents Client et un agent Interface. Un agent Client est responsable de l'ensemble de toutes ses commandes. Quant à l'agent lr2terfàce, il ,fiice, il joue le rôle de coordinateur tout au long du processus de résolution. Dans ce modèle une coalition est une liste ordonnée d'agents Client. Elle correspond à une tournée qui doit commencer à partir du dépôt, servir tous les clients associés selon l'ordre de leur apparition dans la coalition, et enfin retourner au dépôt. Le processus de résolution de ce modèle est défini par trois étapes. La première étape consiste en une génération distri- buée d'un graphe orienté et acyclique nommé graphe de parenté dont les noeuds sont les agents Client et les arcs correspondent aux liens de parenté. Ces liens de parenté sont définis sur la base des contraintes de fenêtres temporelles et les proximités géographiques des clients. ZD Durant la deuxième étape, chaque agent Client construit progressivement les coalitions auxquelles il peut appartenir. Cette construction se base sur les relations de parenté définies auparavant et doit respecter la contrainte de capacité des véhicules. De plus, cet agent doit être servi en premier dans chacune de ces coalitions. A la fin de cette étape, chaque agent Client dispose d'une liste de coalitions complète et triée dans l'ordre croissant de préférence d'une coalition par rapport à une autre. Cette préférence est quantifiée par le rapport entre le coût d'une coalition (en terme de distance parcourue) et sa taille. La dernière étape est la plus critique et la plus décisive du processus de résolution dans le sens où, parmi toutes les coalitions déterminées à l'étape précédente, elle vise à REE Wl Janvier 2005 Une approche multi-agent pour la logistique iée à la production et au transport ne retenir que la coalition la plus satisfaisante pour chaque agent Client. L'intérêt pour une coalition dépend de l'ensemble de ses membres ainsi que de son coût (durée de parcours). De ce fait, un protocole de négocia- tion entre agents a été proposé. Ce protocole respecte les intérêts individuels de chaque agent Client tout en garantissant l'obtention d'un consensus global. Il s'appuie sur six types de messages échangeant des propositions de coalition (amitié) et qui sont : deiiitiiider-aiiiitié, coiijii-lilel-- ai) iitié, qffectel,- i-ftiseitiiiiitié, deiiiaiilei--evclist, abandonner Ce modèle a fourni des résultats encourageants et prometteurs et ce, sur la base du benchmark de Solomon (URL). Cependant, il présente certains inconvénients qui limitent son utilisation à des problèmes réels. En fait, l'inconvénient majeur de ce modèle se situe au niveau de la seconde étape, puisque la formation de la liste de coalitions, ainsi que son tri pour chaque agent Client, nécessitent un temps important et un espace de stockage exponentiel. La taille de la liste de coalitions est expo- nentielle en fonction du nombre de clients. De plus, cette génération de coalitions est coûteuse, et une partie de ces coalitions s'avèrent inutiles dans la suite du processus, du fait qu'elles ne présentent pas d'intérêt pour les autres agents. 2.3. Le modèle étendu Afin de pallier les limites de Coal-PTV, nous avons été amenés à proposer une nouvelle version du modèle, nommée DyCoal-PTV (Résolution par génération dyna- mique de coalitions d'un PTV) (Boudali & al. 04), qui permet de déterminer des solutions identiques à celles fournies par Coal-PTV (Kéfi & Ghédira 04a) tout en réduisant le temps CPU et la complexité spatiale. Dans ce modèle, nous avons éliminé Ja génération de la liste entière de toutes les coalitions possibles, en introdui- sant une technique de formation dynamique des coalitions qui se fait parallèlement à la négociation. Désormais, le processus de résolution ne comporte que deux étapes. Dans la première étape, une génération distribuée du Qraphe de parenté est effectuée. Contrairement au modè- le Coal-PTV où la diffusion d'information se fait dans les deux sens (message : Foi-iiiei-IP (it-IFils), dans le modèle DyCoal-PTV elle s'effectue dans un seul sens. Avec cette restriction le coût de communication entre agents a été réduit. La seconde étape, qui est la détermination de la coalition la plus opportune pour chaque agent Client, constitue une fusion des deux dernières étapes du modèle Coal-PTV. Elle englobe la formation de coalitions qui est effectuée parallèlement à la négociation, c'est-à-dire qu'à chaque proposition de coalition acceptée, l'agent en question la négocie avec les différents agents qui la c Zn constituent. S'ils arrivent à trouver un consensus, cette coalition sera jugée comme étant la solution la plus c opportune pour cet agent, sinon ce dernier renonce à cette ZD coalition. Avec cette nouvelle technique de génération dite dynamique, nous ne sommes plus amenés à générer toutes les coalitions possibles pour chaque agent. En effet, chaque agent Clieiit dispose, à un instant donné, d'une seule coalition qui constitue sa solution individuelle. Au cas où un consensus n'est pas atteint à propos d'une coalition donnée, un nouveau processus de formation est lancé. Ainsi, la génération de coalitions se fait de manière dynamique. L'ensemble des coalitions retenues à la fin de cette étape est constitué de coalitions disjointes deux à deux. La configuration la plus satisfaisante est atteinte quand chaque agent atteint son état de satisfaction (c'est-à-dire stable dans une seule et une seule coalition). A la suite d'une comparaison expérimentale des deux modèles sur la base du benchmarck de Solomon (URL), nous avons pu constater que le modèle DyCoal-PTV a permis, d'une part, de réduire énormément la complexité spatiale devenue ainsi polynomiale, et d'autre part, d'améliorer la complexité temporelle, sans pour autant affecter la qualité des solutions. Conclusion Dans cet article nous avons présenté les approches de formalisation et de résolution de problèmes liés à la ges- tion de production et au transport qui ont été élaborées et expérimentées au sein de notre unité de recherche SOIE et plus particulièrement par l'équipe « logistique et trans- port ». Deux d'entre elles ont été détaillées. La pre- mière concerne un problème d'ordonnancement d'atelier de type Job Shop flexible abordée par une approche Multi-Agent-Recherche tabou, alors que la deuxième concerne un problème de tournées de véhicules avec fenêtres de temps traité sur la base d'interactions entre agents en vue de former des coalitions correspondant à des tournées admissibles. Références [1] A. Abdeljaouad & K. Ghédra (2004). "MATRA une approche multi-agent pour le problème du transhlpment ", 12 "'' Journées francophones des systèmes multi-agents JFSMA'04, Paris, France. [2] Alaya & K. Ghédira (2004) " An algorithm for the multidi- mensional knapsack problem, In proceedings of the BIOMA 2004 International Conference on Bioinspired Methods and their Applications " 2004, page 63-72, Slovenia. [3] J. Berger & M. Barkaoui (2004). "A parallel hybrid genetic algorithm for the vehicle routing problem with time win- REE No 1 Janvier 200 m Dossier) EOGISTIQUE ET TRANSPORT [4] 151 dows ", Computers & Operations Research 31 (2004) 2037-2053. S. Bouamama & K. Ghédira (2004) " A Dynamic Distributed Guided Genetic Algorithm for Max-CSPS ", soumis au jour- nal of Artificial Intelligence Research (JA ! R). [5] 1. Boudali, W. Fki & K. Ghédira (2004). " How to deal with the VRPTW by using multi-agent coalitions ", 4th International Conference on Hybnd Intelligent Systems HIS'04), Japan. [61 A.L. Bouthillier & T.G. Crainic (2003). " A cooperative paral- lel meta heuristic for the vehicle routing problem with time windows ", Computers & Operations Research. [7] P. Brandimarte (1 993) " Routing and scheduling in a flexible Job shop by tabu search ", Annals of Operations Research 22 : 158-183. [81 Y Caseau & F. Laburthe (1995). " Improving Branch and Bound for Job Shop Scheduling with Constraint Propagation ". [91 J.B. Chambers & J.W Barnes (1996). " Flexible Job Shop scheduling by tabu search, Graduate program in Operations Research and Industrial Engineering ", The university of Texas at Austin, Technical Report series, ORP96-09, [10] C.F. Tsai, CW Tsai & C.C. Tseng (2004). "A new hybrid heuristlc approach for solving large traveling salesman pro- blem ", Information Sciences 166 (2004) 67-81. [11] T Daouas, K. Ghédira & JP Muller (1995a). " A distributed approach for the Flow Shop scheduling problem ", In ICAIA 95. [12] T. Daouas, K. Ghédira et J.P. Muller (1 995b). " Ordonnancement distribué dans un atelier de type Flow Shop ", In Journées françaises d'intelligence artificielle dis- tribuée et systèmes multi-agents 95. [13] S. Dauzerre-Peres & J. Paulli (1997). "An integrated approa- ch for modeling and solving the general multiprocessor job shop scheduling problem using tabu search ", Annals of Operations Research 70 281-306. [14] M. Ennigrou & K. Ghédira (2004a). " Approche multi-agent basée sur la recherche tabou pour le Job Shop flexible ", 14e'eCongrès francophone AFRIF-AFIA de reconnaissance des formes et intellgence art ficie le, RFIA'04, Toulouse, France. [15] M. Ennigrou & K. Ghédtra 2004b). " Solving Flexible Job Shop Scheduling with a Multi-Agent System and Tabu Search ", à paraître dans le Journal européen des systèmes automatlsés JESA. [161 F. Ferzan (2002). "Accelerated SATbased Scheduling of Control/Data Flow Graphs, IEEE International Conference on Computer Design : VLSI in Computers and P/'ocessos " (ICCD'02), Los Angeles, USA. [17] K. Fisher & N. Kuhn (1 993) " A DAI Approach to Modelng the Transportation Domain ", DFK ! -Research Report RR-93- 25, DFKI, Saarbrucken, Germany. [181 K. Ghéd ra (1 994a), " Partial Constraint Satisfaction by a MA approach combines with a Simulated Annealing Process International Conference on AI, Paris, Paris [19] K. Ghédira (1994b). " Distributed Simulated Re-annealing for Dynamic Constraint Satisfaction ". mm Eu e u r s Khaled Ghédira a obtenu le diplôme d'ingénieur hydraulicien de 'ENSEETHT en 1983 et celui d'ingénieur informaticien à l'ENSIMAG en 1986. Il a obtenu le DEA puis le doctorat d'infor- matique option Intelllgence artificielle de l'ENSAE en 1993 et son habilitation universitaire en informatique à l'ENSI (Ecole nationale des sciences de l'informatique de Tunis) en 2001. Professeur de l enseignement supérieur au département informatique de !' ! nstitut supérieur de gestion de Tunis, II occupe le poste de directeur de !'ENS !. Responsable de SOIE et président de l'ATIA (Association tunisienne d'intelligence artificiellel, il s'intéresse essentiellement aux domaines de recherche suivants : systèmes mutti-agents, CSP (Constraint Satisfaction Problems), optimisa- tion combinatoire, problèmes d'ordonnancement et transport. Membre de plusieurs comités de programme relatifs à diverses conférences et revues, Il est auteur d'unesoixantaine d'articles Meriem Ennigrou est enseignante au département informa- tique de l'Institut supérieur de gestion de Tunis. Elle a obtenu son diplôme des Etudes approfondies en modélisation et informa- tique de gestion à l'Institut supérieur de gestion de Tunis en 2000. Actuellement, elle est inscrite en troisième année de doctorat. Ses domaines de recherche sont les systèmes multl- agents, les problèmes d'ordonnancement, le problème Job Shop flexible, la méthode d'optimisation combinatoire : recherche tabou Imen Boudali est enseignante à l'Institut supérieur d'informa- tique de Tunis. Elle a obtenu son mastère en informatique app ! i' quée à la gestion à l'Institut supérieur de gestion de Tunis en 2004 Actuellement, inscrite en première année de doctorat en automatique et informatique industrielle à l'Ecole centrale de Lille Ses domaines de recherche sont les systèmes multl- agents, les problèmes de tournées de véhicules, la régulation des réseaux de transport. REE WI Janvier 2005 Résumés RÉSUMÉS ABSTRACTS Dossier : Logistique et transport Feature : Transport and Logistic Par J. Carlier, A. Moukrim REE,ISSN 1265-6534, P'l, janvier 2005, p, 26 Mots clés : Ordonnancements disjonctifs et cumulatifs, systèmes flexibles de production, conditionnement. Le laboratoire Heudiasyc (HEUristique et DIAgnostic des SYstèmes Complexesl, est une unité mixte entre l'université de technologie de Compiègne (UTC) et le CNRS. Créée en 1981, elle est hébergée au sein de l'UTC. L'une des problématiques de recherches du thème ARO (Algorithmique pour les Réseaux et l'Optimisation) du laboratoire Heudiasyc, concerne l'optimisation des systèmes complexes. ARO développe notamment des solutions algorithmiques, validées par preuve théorique, simulation et expérimentations, pour des pro- blèmes liés à l'ordonnancement, au transport et à la logistique. Nos compétences dans ces thématiques de recherche nous ont permis de mettre en place la filière ADEL (Aide à la Décision En Logistique), dans le département génie informatique de l'UTC. Quatre membres du thème ARO assurent la responsabilité pédagogique de cette filière : Jacques Carlier, Antoine Jouglet, Aziz Moukrim et Dritan Nace. By J. Carlier, A. Moukrim REE, ISSN 1265-6534, n'1, Jaiiuary 2005, p. 26 Keywords : Disjunctive and Cumulative Schedu ng, Flexible Manufacturing Systems, Bin-packing. Heudiasyc (HEUristique et DIAgnostic des SYstèmes Complexes) is a « joint » CNRS-UTC research laboratory. Heudiasyc's guiding prin- ciple is to bring together research in control, signal, image and com- puter science with an emphasis on human factors. One of its teams ARO (Algorithmique pour les Réseaux et l'Optimisation) is working on algorithms for networks and optimization. We are especially wor- king on Scheduling, Transportation and Logistics. Four members of this team are involved in a new path ADEL (Aide à la Décision En Logistique) open to young engineers : Jacques Carlier, Antoine Jouglet, Aziz Moukrim and Dritan Nace. Par B. Descotes-Genon REE,ISSN 1265-6534, n'1, janvier 2005, p. 34 Mots clés : Logistique inverse, collecte, routage de véhicules, recherche tabou, transport. L'article concerne une application relative à la collecte de produits techniques encombrants en fin de vie issus de l'électroménager, maillon essentiel de la logistique inverse et principale approvision- neuse du système de recyclage. Parmi les différents systèmes de col- lecte existants, le ramassage à domicile des produits usagés de la population est analysé et modélisé par le problème de chargement et de déchargement des produits avec trois types de contraintes : des contraintes de capacité des véhicules, des contraintes de précédence entre les sites de chargement et de déchargement des produits et des contraintes de fenêtres temporelles. Ce problème de routage de véhi- cules est résolu en deux phases en se basant sur la méta- heuristique de recherche tabou, et en considérant successivement les cas d'un et de plusieurs véhicules. B/B. Descoes-Genon REE, ISSN 1265-6534, n'1, Jaiiuary 2005, p 34 Keywords : Reverse logistics, Collection, Vehicle routing problem, Tabu search, Transport. The paper deals to an application relating to the cumbersome tech- nical products collection at the end of the life from the electric hou- sehold appliances, essential link of reverse logistics and main sup- plier of the recycling system. Among the various existing systems, the collection at home is analyzed and modelled by a vehicle routing problem (Pickup and Delivery Problem) with three types of constraints : capacity of the vehicles, precedence between the sites of loading and unloading of the products and urne windows. This vehicle routing problem is solved with the aid of tabu search method, successively considering the cases of one and several vehicles. multiniodal (SIM) à base de systèrne multi-agent (SMA) Par/. Ben Khaled, M-A. Kamoun, K Zidi, S. Hammacli REE,ISSN 1265-6534, n'1, janvier 2005, p 41 Mots clés : Transport multimodal, calcul d'itinéraire, information multimodale, système multi-agent. S'appuyant sur la théorie multi-agent, ce travail vise à améliorer la qualité des algorithmes de calcul d'itinéraires multimodaux et à By/. Ben Khaled, M-A. Kamoun, K Zidi, S. Hammadi REE, ISSN 1265-6534, no 1, January 2005, p 41 Keywords : Multimodal transport, Itinerary computing, Multimodal information, Multi-agent system. Using the multi-agent theory, this work aims to ameliorate the itine- rary research algorithm quality for the multimodal transport, and REE Wl Janvier 2005 'Or Résumés R RÉSUMÉS ABSTRACTS concevoir une architecture optimisée du système d'information multimodal pour l'aide au déplacement. also to conceive an optimized software architecturefor the multi modal information systems deailing with travel information. pot s a 1 ParA. Ouillot REE, SSN 1265-6534, 11'1, ja [i\/ier 2005, p 48 Mots clés : Réseaux, modèles d'optimisation, transports. La pénétration des sources de production décentraliséedans les réseaux électriquesest une problématique majeure : accroîtreleur capacitéà participer aux servicessystème, déterminer leurzone d'in- fluence selon leurpoint de connexion au réseau,autant de travaux à mener afind'accroître letaux de pénétrationde ces sources dans les réseaux électriques futurs. Le développement de plates-formes expérimentales est indispensable à la validation de nombre de ces travaux. Nous présentons dans cet article un banc d'essaien phase de développement, dont le rôleest d'émuler un système de généra- tionéolienne à vitessevariable, associé à un stockage d'énergiesous forme inertielle. Nous y développons les différentes parties, et vali- dons chacune d'entreellespar des relevésexpérimentaux. , ! 2't.S''-'' ftia', !'- ; '. t.' " -' ' :''.--' !'''7. " t'ili "''J t9tl' (..3 gk a Lli : -- " L, t' : : ;' :).A,,,, t.J, ;'1. t l'j --,- " " '''- ; :.'--' " - - " -- p s.f'- Â- ,v- I0JW'<> ", " -.,.CJ,- " ci By A. Ouillot REE,ISSN 1265-6534, n'1, Jaiuary 2005 p 48 Keywords : Network, Optimization Models, Transportation Systems. The levelof penetrationof dispersed generation inthe electrical net- works isa major scientific aim :to increasethe possibility of partici- pating in the ancillaryservices,to determine the influence zone according to the network connection point,etc.The development of experimental testbenches isnecessary to validate all the theoretical studies.lnthispaper,we present a 3kW testbench, emulating a grid connected or stand-alone variablespeed wind generator associated with a flywheel energy storage system real-timeemulator. A Mu ! t !' "Agant A'pp !'cch tô Loistc atad t. fo tc Par (. Ghédira, M. Ennigrou,/. Boudali REE,ISSN 1265-6534, n'1, janvier 2005, p. 53 Mots clés : Gestion de production, transport,systèmes multi- agents, optimisation, Job Shop, problème de tournées de véhi- cules, recherche tabou, formation de coalitions. La plupart des problèmes relatifs à la gestion de production et au transportsont,d'une part,NP-complets etd'autrepart, omniprésents dans différents domaines industriels. D'où l'intérêt de plusieurscom- munautés notamment de gestion,d'automatique et d'informatique, et d'où également la proposition de plusieurs approches : des méthodes de résolutioncomplètes ou incomplètes et diversforma- lismes de recherche opérationnelleou d'intelligence artificielle. L'approche adoptée par l'équipe« logistiqueettransport »de l'unité de recherche SOIE est celle d'utiliser les systèmes multi-agents (SMA) et/ou le formalisme CSP (Constraint SatisfactionProblem) pour la modélisation. Quant à la résolution, elleest abordée sur la base d'interactions entre agents et/ou sur des méthodes d'optimisa- tion incomplètes. L'objectif étant d'une part une représentationfidè- lede l'aspect souvent distribuédes problèmes traités et,d'autrepart, une accélérationde la résolution. Plusieurstravaux de l'équipesont présentés et commentés dans cet article. Deux d'entre eux sont détaillés : le premier concerne un problème d'ordonnancement d'un atelier de type Job Shop et le second se réfèreà un problème de tournées de véhicules. By K. Ghédira, M. Ennigrou,/. Boudali RFE, ISSN 1265-6534, n'1, Jaiiuary 2005, p. 53 Keywords : Production Management, Transportation, Multl- Agent System, Optimization, Job Shop, Vehicle Routing pro- blem, Tabu Search, Coalition Formation. Most of problems related to Production Management and transpor- tationare,on the one hand, NP-complete and on the other hand, fre- quently met indifferent industrial domains. Therefore, several com- munities, like those of Management, automatic control and compu- ter science, have been interested in such problems and several approaches have been proposed for theirmodeling and theirsol- ving:complete and incomplete methods. The approach adopted by the team « logistic and transportation » of the research unitSOIE isto use the Multi-Agent System and/or the Constraint SatisfactionProblem formalism for modeling. Whereas, agent interactionand/or incomplete optimization methods have been applied forsolving. Theobjectiveis, on the one hand, to repre- sent faithfully the aspect often distributedof the considered pro- blems and on the other hand, to accelerate the solving process. In this paper, we present and comment many research works of our team. Particularly, we will focus on two of them :the first concerns a Job Shop Scheduling Problem and the second refersto a Vehicle Routing Problem. REE ? 1 Janvier 2005 Résumés RÉSUMÉS ABSTRACTS Repères : Les véhicules propres Feature : Clean Vehicles ç : : t 1 ! h,,',di r: ? : ;' 7' ! r i{'!, r' " M ''' * {i' ;'* 'i f'''..