Problème de logistique inverse : utilisation dune méta-heuristique dans une application de transport de marchandises

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

Résumé

Problème de logistique inverse : utilisation dune méta-heuristique dans une application de transport de marchandises

Métriques

5
3
1.99 Mo
 application/pdf
bitcache://b9cc46d0d02d99a4587742c67e8a8453ee844c08

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/20573</identifier><creators><creator><creatorName>Bernard Descotes-Genon</creatorName></creator></creators><titles>
            <title>Problème de logistique inverse : utilisation dune méta-heuristique dans une application de transport de marchandises</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">b9cc46d0d02d99a4587742c67e8a8453ee844c08</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34745</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

. Dossier) LOGISTIQUE ET TRANSPORT m m a Problème de logistique inverse : uti) isation dune méta-heuristique m dans une application de transport de marchandises Mots clés Logistique inverse, Collecte, Routage devéhicules, Recherche tabou, Transport Par Bernard DESCOTES-GENON Laboratoire d'Automatique de Grenoble -Institut National Polytechnique de Grenoble - Université Joseph Fourier 1. Introduction Cet article présente un des aspects du travail initialisé dans le cadre d'un projet intitulé « Rester propre » soutenu par la région Rhône-Alpes. Le contexte général concerne les problèmes de désassemblage et de recyclage de produits techniques en fin de vie (les marchandises), mais nous nous intéressons plus particulièrement ici à la problématique de la collecte (ramassage - transport). Les produits techniques encombrants considérés relèvent de ce que l'on appelle les produits « blancs » (lave-linge, réfrigérateur...). Nous nous plaçons au niveau de la planification opé- rationnelle de la collecte, et pour affiner notre analyse, nous nous restreignons à un mode de collecte particulier (collecte par enlèvement à la demande), qui peut être modélisé par un problème de tournées de véhicules sous contraintes : contraintes de précédence (chargement, puis déchargement), contraintes de capacité des véhicules, contraintes de fenêtres temporelles. Cette étude a débouché sur un exemple particulier qui se traduit en fait par un problème d'optimisation combi- natoire : problème de chargement et de déchargement avec fenêtres temporelles (en anglais, PDPTW - Pickup and Delivery Problem with Time Windows) [3, 4]. Nous présentons ici quelques résultats obtenus en utilisant une méta-heuristique (recherche tabou) pour résoudre le problème. 2. La problématique du recyclage Nous sommes aujourd'hui dans une ère où la société de consommation génère de plus en plus de déchets de toutes sortes, qu'il est nécessaire de traiter de façon cohérente avant que la situation ne devienne incontrôlable. Il y a progressivement une certaine prise de conscience générale de cette nouvelle situation, et les pouvoirs publics (en France, mais aussi au niveau européen par 5 5 SYNOPSIS L'articleconcerne uneapplication relative à lacollectede produits techniques encombrants en fin de vie issusde l'électroménager, maillon essentiel de la logistiqueinverseet principale approvi- sionneusedu systèmede recyclage. Parmiles différentssys- tèmesde collecteexistants, le ramassage à domicile desproduits usagésde la population est analyséet modéliséparle problème de chargement et de déchargement desproduits avectroistypes de contraintes : des contraintes de capacitédes véhicules,des contraintes de précédenceentre les sitesde chargement et de déchargement des produitset des contraintes de fenêtrestem- porelles. Ceproblème de routagedevéhicules est résoluen deux phases en se basantsurla méta-heuristique de recherche tabou, et en considérant successivement les cas d'un et de plusieurs véhicules. The paper deals to an application relating to the cumbersome technical products collection at the end of the life from the elec- tric household appliances, essential linkof reverse logistics and mainsupplierof the recyclingsystem.Among the variousexisting systems, the collection at home is analyzedand modelled by a vehicle routing problem (Pickupand Delivery Problem)with three types of constraints: capacity of the vehicles, precedence bet- ween the sites of loadingand unloadingof the productsand time windows. This vehicle routing problem is solved with the aid of tabu search method, successivelyconsideringthe cases of one and several vehicles. REE ? i Janvier 2005 Problème de logistique inverse : utilisation d'une méta-heuristique dans une application de transport de marchandises Matières premières MOdUler p Distriutioll t 1 le**r Consommateurs t Pt6C6S Pièces Modules Pro Distrib détaché Consomi Revellte Réparation Rénovation Re-production (,Mnn Cannibalisation C Recyclage ération incinération Mise au rebut Figure 1. Stratégies de réctipératioti des produits. Production Distribution . Stock Transformation Assemblage Transport Extraction Utilisation " OG.ST.QUE DtRECT " ' " Y \ Transport tLOG) ST)QUEtNVERSE Ramassage/ Transport Tri COllecte Redistribution Options de Diagnostic Stock récupération Recyclage - :.''.âë'S '::'-. Figure 2. Cycle de vie cowplet d'uu produit. exemple) réfléchissent donc à ce problème économique, écologique et social depuis maintenant plus d'une dizaine d'années. Ainsi, au niveau européen, la loi votée le 1" juillet 2002 stipule que : « Seuls les déchets ultimes sont acceptés en décharge ». En dehors de ces déchets ultimes, il s'agit de réaliser ce que l'on appelle le recyclage noble, c'est-à-dire un recyclage avec récupération de valeur (matière, pièces détachées, produits) et réintégration sur les marchés. Seulement, la viabilité économique de la revalorisation des produits en fin de vie doit obligatoirement passer par la création de valeur dans le cadre du processus de récu- pération pour que celui-ci puisse être autonome et puisse s'autogérer, sans bénéficier par exemple de subventions extérieures. Les différentes stratégies de récupération des produits peuvent être présentées conformément à la figure 1. Ainsi, on peut voir que l'ensemble des options de récupération se distinguent par un degré plus ou moins prononcé de conservation de l'identité du produit, qui va d'une simple réparation (où il s'agit de ramener un produit dans son état de marche normale) à la cannibalisation ou au recyclage, qui se situe au niveau de la récupération matière. Ces stratégies répondent au critère recyclage noble défini précédemment. Par ailleurs, une analyse des différents éléments de la chaîne logistique du cycle de vie complet du produit met clairement en évidence les deux chaînes (voir figure 2) : . la chaîne logistique directe : extraction des matières, pour fabriquer un produit par des opérations de transformation et d'assemblage, avant d'être distribué et vendu pour la consommation et l'utilisation ; · la chaîne logistique inverse débute par la collecte des produits en fin de vie et rassemble le ramassage, REE WI Janvier 2005 . Dossier) LOGISTIQUE ET TRANSPORT le tri et le diagnostic : acheminement vers des installations de récupération, puis redistribution sur les marchés secondaires ou primaires. Ainsi, la collecte est donc le premier maillon de la logistique inverse, et le principal approvisionneur du système de récupération des produits : c'est donc un aspect essentiel dans l'optique de la rationalisation du processus de recyclage. c Avec l'émergence du recyclage noble et des incitations des pouvoirs publics, les réflexions se font jour sur la ou les manières les plus pertinentes de traiter efficacement les produits en fin de vie. En particulier, la plupart des experts reconnaissent que la collecte des produits techniques est actuellement encore sous-dimensionnéc, et que des efforts importants sont de ce fait nécessaires pour approvisionner de la meilleure façon les installations de récupération, et cela dans une maîtrise des coûts évidente. Des études ont en effet montré que la collecte était responsable d'une part importante des coûts globaux de la chaîne inverse, notamment à cause des transports et des stocks de produits. 3. La collecte Nous nous intéressons donc plus particulièrement à l'aspect « collecte » des produits, aux différentes poli- tiques possibles, aux différents mécanismes mis en jeu. Les systèmes de collecte existants sont de deux grands types et sont souvent combinés pour offrir le ser- vice maximal à la population : . le premier est la collecte par apport volontaire, qui se base sur le fait que c'est la population qui fait l'effort d'apporter les produits usagés dans des installations prévues à cet effet. Il existe quatre grandes options de réception de ce mode de collecte : la décharge municipale, la déchetterie, la grande distribution, les associations (Emmaus, UTILE, ENVIE) ; . la collecte par enlèvement est le deuxième grand mode qui se combine avec la collecte par apport volontaire. Ce deuxième mode peut se décliner de diverses façons : . la collecte périodique est relativement efficace, même si elle comporte plusieurs gros inconvénients au niveau de l'anonymat des produits récupérés (impossibilité de tracer le passé du produit), du tri (déchets hétérogènes), de la cannibalisation (produits dépouillés de leurs pièces détachées et matières premières qui ont de la valeur) ; . l'enlèvement par livreur est un argument de vente des sociétés pour fidéliser leur clientèle. Il s'agit, au moment de la livraison d'un produit neuf, de faire l'échange avec le produit en fin de vie dont le consommateur veut se débarrasser. Même s'il est intéressant, il semble difficile d'utiliser ce mode isolément des autres modes, car toutes les sociétés n'ont pas les moyens de l'assurer ; 'la collecte sur demande, en utilisant le plus souvent un numéro de téléphone vert. C'est généralement un service gratuit proposé par les communes et réalisé au domicile des particuliers, mais que peu de gens connaissent. Les options de collecte les plus prometteuses pour pou- voir prendre en compte les flux de retour des produits usa- gés dans l'objectif du recyclage noble sont certainement la collecte par apport volontaire (apport en déchetterie et gran- de distribution) et la collecte par enlèvement à la demande. Cependant, devant la contrainte principale des produits blancs, qui reste leur encombrement, nous avons choisi de cibler nos efforts en priorité sur la collecte par enlèvement à la demande, car c'est cette collecte qui semble la plus adap- tée pour répondre aux objectifs de rentabilité escomptés. 4. Planification opérationnelle (cas d'un véhicule) Ayant retenu la collecte par enlèvement à la demande, nous allons maintenant nous situer au niveau opérationnel, de façon à proposer un outil permettant d'effectuer la plani- fication opérationnelle des politiques de collecte retenues. Pour cela, nous allons nous baser sur les hypothèses de travail suivantes : . un réseau d'installations de récupération réparties sur une zone géographique, chacune accomplissant une ou plusieurs des options de récupération, . une flotte de véhicules homogènes (même capacité, Zn même vitesse). Par ailleurs, il faut également retenir les principales caractéristiques de ce type de collecte : . la nature encombrante des produits techniques, . les contraintes horaires, . les destinations multiples d'un produit en fin de vie, selon son état et selon les diverses stratégies de récupération qu'il est possible de lui appliquer, . la gestion des coûts qui passe par l'optimisation des flux de transport au sein du réseau. Ainsi, un tel système se modélise comme un problème de tournées de véhicules (VRP - Vehicle Routing Problem) sous contraintes, avec l'objectif de minimiser la distance totale parcourue par la flotte de véhicules (un seul dans un premier temps), et sous des contraintes de capacité, de fenêtres temporelles et de précédence entre les points de chargement et de déchargement. REE N 1 Janvier 2005 Problème de logistique inverse : utilisation d'une méta-heuristique dans une application de transport de marchandises Q= 15 15 401 1 + [10, 401 +2' +21 1 40 01 [OP6 (D 25 15 .' ; [0,1201 eo0ooo, 1 \\ I Q=15 [0,1201 L I,-îgtire 3. Exeiille cltiiis le ccis d'i (il ,éhictile. Pour illustrer ce cas, considérons l'exemple suivant (figure 3). Nous disposons de quatre centres de chargement (notés + 1 à + 4) et de quatre centres de déchargement (notés 1 à - 4) répartis sur une certaine zone géogra- c phique ; lepoint central étant le point de départ et de retour. Q correspond à la capacité à charger aux différents postes de chargement. La capacité du véhicule est de 75. [x, y] représente la fenêtre temporelle associée à chaque poste (chargement ou déchargement) : x est la date d'arrivée au plus tôt et y la date d'arrivée au plus tard. Le temps de service est supposé égal à Q/5 pour le ZD chargement et à Q/10 pour le déchargement. Le temps de transfert d'un noeud à un autre est pris égal à 1,5 fois la distance. Le modèle mathématique construit à partir de cette définition comporte plusieurs types d'équations : certaines expriment les contraintes du problème en terme de respect de la précédence entre les villes, de respect des fenêtres temporelles, et de respect de la capacité des véhicules. . Respect de la précédence entre les sommets : Ti + Pi + t ; +,+,< T +, pour tout i e P+ . Respect des fenêtres temporelles : e ; < T, < 1, pour tout i E P co TO : 10 < 1, e,l, + 1 : 9 T,l, + j : 1,l, + 1 e Respect de la capacité des véhicules : Yo = 0, di < Yi < D, pour tout i E P+ . Fonction objectif : miny-,,. V, i c N,,i'Ei N Cij Xij Dans ces équations, les différentes variables ont la signification suivante : . n = nombre de clients indicé sur i (i chargement, n + i déchargement), 'N = ensemble des indices des noeuds (0, 1,.... n, n + 1,..., 2n, 2n + 1) ; 0 et 2n + 1 indices du noeud de dépôt (départ et retour), 'P+ = ensemble des indices des noeuds de chargement, 'P- = ensemble des indices des noeuds de déchargement, e,ement, Ti, T,,, i = date de chargement ou de déchargement, To, T2,, + 1 date de départ, date de retour au dépôt, 'p = temps de service au noeud i, ti, + i = temps de transport du noeud i (chargement) au noeud n + i (déchargement), . (ei, Il), (e,, + i, 1,, + i) = intervalle de temps pour chargement ou déchargement du client i, . (eo, 10), (e211 + 1, 1,,,, 1) = intervalle de temps pour départ ou retour, 'D == capacité véhicule, 'Y, = capacité chargée sur le véhicule i, Yo 0 (capacité nulle au départ), . di == demande capacité à transporter client i, * v = indice véhicule ; V = nombre de véhicules, . Xij = variable de flot = 1 si véhicule v voyage du noeud i au noeudj, 0 sinon. Pour résoudre un tel problème, les méthodes habi- tuellement utilisées sont : . des méthodes exactes (programmation dynamique, séparation et évaluation,...) ; . des méthodes approchées (décomposition de Bender, procédure k OI) t'...). Par contre, bien que, pour l'instant peu souvent utilisées dans le cas des problèmes de chargement et de décharge- ment avec fenêtres temporelles, il semble intéressant de considérer une approche basée sur les méta-heuristiques. C'est ainsi que nous avons choisi, parmi les différentes méthodesexistantes (recuit simulé, algorithmes génétiques, m e e ZD colonies de fourmis... [5]), la méthode dite de recherche REE NC 1 Janvier 2005 . DOSSier) LOGISTIQUE ET TRANSPORT tabou qui a, par ailleurs, déjà fait ses preuves dans diffé- rents types d'applications (problèmes de graphes, pro- blèmes d'ordonnancement, problèmes de finances, pro- blèmes de création d'horaires...). Cette méthode d'op- timisation a été introduite par Glover [1] afin d'ouvrir une nouvelle voie dans la résolution des problèmes d'optimisation. Le principe de la recherche tabou est générique, ce qui fait que des problèmes de natures très diverses peuvent être traités. En revanche, l'obtention de solutions de bonne qualité passe nécessairement par une bonne compréhension du problème, ainsi que par une bonne implémentation et un bon paramétrage de la méthode. Sans rentrer dans les détails, le principe de la méthode est le suivant. La recherche tabou se base sur une stratégie de recherche locale pour améliorer itérativement la solu- tion courante. Pour une itération donnée, qui correspond à une solution donnée du problème, un ensemble de solu- tions voisines de la solution courante est construit, ce qui constitue le voisinage de cette solution. Chaque solution du voisinage est déterminée par des opérations de mouve- ment. Le passage à l'itération suivante du processus de recherche se fait par la sélection de la meilleure solution du voisinage. Néanmoins, comme dans tout processus de recherche locale, il est possible de se retrouver à un moment donné sur un optimum local. Pour dépasser cet optimum local et converger vers un optimum global, il faut alors accepter de dégrader la solution courante pendant un certain nombre de pas. Cependant, pour éviter le phénomène de cycle de la recherche, les derniers mouvements utilisés, ceux qui nous ont permis d'arriver sur cet optimum local, sont considérés tabou et ne peuvent être autorisés pendant un certain nombre d'itérations. La recherche tabou est un processus itératif : il est donc nécessaire de l'initialiser. Pour ce faire, une combi- naison de deux règles est utilisée : . la première règle est une règle de tri des sommets de chargement en considérant la borne inférieure de la fenêtre temporelle ; . la deuxième règle est une règle d'insertion des sommets de déchargement juste après chaque sommet de chargement. Ainsi, nous disposons d'une première solution, dans laquelle, sur les trois contraintes du problème, les contraintes de capacité et de précédence entre les sommets sont respectées, mais où nous n'avons pas l'assurance que la contrainte de temporalité soit res- pectée. Il se peut alors que la solution initiale ne soit pas réalisable, mais cette solution est le départ du pro- cessus d'optimisation, qui rendra au final une solution réalisable. Dans le processus de recherche locale, un facteur important porte sur la construction du voisinage d'une solution courante. Nous ne rentrerons pas ici dans les détails de construction de ce voisinage. Néanmoins, dans le problème de tournées de véhi- cules qui nous intéresse, nous avons retenu deux types de mouvement : . le premier est un mouvement d'échange entre les noeuds d'une route. Il consiste à échanger la position de deux sites dans la route du véhicule, et d'évaluer le coût de la nouvelle solution obtenue ; . le deuxième mouvement utilisé pour la construction du voisinage d'une solution est le mouvement d'insertion. Il s'agit dans cette situation, pour deux sommets de la route du véhicule, d'insérer un sommet à la position occupée par l'autre sommet. Pour notre part, dans la sélection des mouvements, nous évaluons toutes les solutions du voisinage, qu'elles soient réalisables ou non. Il y a en effet deux types d'implémentation : se restreindre aux solutions réalisables du voisinage (espace de solutions qui est plus petit), ou, comme nous, englober toutes les solutions potentielles (espace de solutions plus grand, plus de choix de la prochaine solution, et pondération du coût des solutions non réalisables). 5. Résultats obtenus (cas d'un véhicule) Nous avons distingué deux étapes dans notre évaluation : . dans un premier temps, nous avons voulu jauger notre méthode par rapport à d'autres méthodes existantes, au niveau de la qualité des solutions obtenues et du temps d'exécution. Pour ce faire, nous avons sélectionné des jeux de tests trouvés sur le Web, issus d'un problème de tournées de véhicules ne comprenant que les contraintes de fenêtres temporelles, mais qui a l'avan- tage de fournir les solutions exactes optimales pour chaque instance du jeu de tests ; . dans un deuxième temps, nous avons généré un jeu de tests du problème de chargement et de déchar- gement et nous avons observé le comportement de notre méthode par rapport aux meilleures solutions connues. Les principales conclusions montrent que la recherche tabou converge bien vers l'optimum du problème et qu'elle sait donc dépasser les optima locaux, et que sur l'en- semble des exécutions pour une même instance, l'erreur relative moyenne reste très faible en fin d'exécution. En revanche, il est possible d'améliorer sensiblement le temps d'exécution, notamment en restreignant le voisi- nage d'une solution aux solutions réalisables (contrairement c au cas précédent), et en appliquant une stratégie d'oscillation sur les mouvements employés. REE WI Janvier 2005 Problème de logistique inverse : utilisation d'une méta-heuristique dans une application de transport de marchandises Coût 50000 Coût 48000 - 46000 - 44000 - 42000 -. 40000 - 38000 - 36000 - 47879 43839 Amor 42330 -41 j -1 il o Insertion parallèle . Insertion spatio temporelle o PTS partition o PTS global . TS global Figure 4. 7ibleait coiiilgai-atf de 5 heuristiques (etis de plitsietir, véliicitles). 6. Planification opérationnelle (cas de plusieurs véhicules) Reprenons le même exemple que nous avons introduit dans la partie précédente, avec les mêmes données, et imaginons maintenant qu'un nouveau produit en fin de vie soit à considérer dans la planification de la collecte (+5 et -5). L'apparition de ce cinquième produit usagé complexifie le problème, car désormais un seul véhicule ne peut traiter les cinq produits en respectant toutes les contraintes du problème. Un deuxième véhicule est donc introduit pour pouvoir trouver une solution au problème posé, l'objectif étant toujours d'essayer de minimiser la distance globale parcourue par la flotte de véhicules. Pour ce problème à plusieurs véhicules, il n'existe pas à notre connais- sance de méthode exacte, car la complexité est trop importante. Les méthodes approchées existantes fonctionnent avec plus ou moins de succès, et sont toujours un compromis entre le temps d'exécution et la qualité des solutions obtenues. Qu'en est-il alors de la recherche tabou pour le cas de plusieurs véhicules ? L'approche est décomposée en deux phases : 'la première consiste à partitionner l'ensemble des requêtes de transport sur l'ensemble des véhicules, de manière à construire une solution initiale, cette fois-ci réalisable. Pour ce faire, on réutilise les règles de tri et d'insertion qui ont été introduites dans ! a partie précédente pour affecter un produit usagé sur un véhicule. Lorsque l'insertion ne peut être faite sur l'ensemble des routes déjà existantes, avant d'introduire un nouveau véhicule, chaque route existante est optimisée selon le principe déjà décrit précédemment, à la fois pour réduire le coût des routes et pour éviter l'apparition inutile d'un nouveau véhicule. Si l'insertion ne peut toujours pas être faite, alors seulement on introduit un nouveau véhicule. La solution initiale pour la recherche tabou est donc déjà optimisée localement au niveau de chaque route ; comme il est vrai que la somme d'optima locaux ne garantit pas l'optimum global d'une solution, la deuxième étape de notre approche consiste à optimiser globalement la solution. L'optimisation globale se base sur la recherche tabou probabiliste (PTS). Contrairement à la recherche tabou déterministe (TS) que nous avons employée dans le cas d'un véhicule, cette variante opère sur les probabilités au moment du choix de la prochaine meilleure solution, lors du passage d'une itération à la suivante. Nous avons voulu évaluer cette variante de la recherche tabou, car elle a également donné des résultats prometteurs dans d'autres domaines. En ce qui concerne la construction du voisinage d'une solution globale, nous opérons également par des mou- vements d'échange et d'insertion, mais ici les mouve- ments se font uniquement sur des sommets appartenant à des routes différentes : ce sont uniquement des mouvements entre routes qui sont effectués. Cependant, dès qu'une modification de la structure d'une route par un mouvement d'optimisation globale a lieu, le module d'optimisation locale de la route est relancé sur ce véhicule, pour tenter d'améliorer son coût. On réutilise le module avec un véhicule dans le contexte multivéhicules. Alors, le diagramme donné sur la figure 4 présente une comparaison des coûts issus des cinq heuristiques. Les deux premières (l'heuristique d'insertion parallèle-IP et l'heuristique d'insertion spatio-temporelle-ISP) sont des méthodes de construction d'une solution initiale basées sur des règles d'insertion : elles servent de référence dans notre exemple. Les deux suivantes REE WI Janvier 2005 m D 0 s s i e r LOGISTIQUE ET TRANSPORT s'appuient sur la recherche tabou probabiliste avec partition et optimisation locale ou globale (PTS partition et PTS globale), la dernière sur la recherche tabou déter- ministe avec optimisation globale (TS global). Chaque barre représente la somme des coûts des solutions sur les six instances significatives que nous avons retenues pour l'évaluation. Pour les heuristiques de recherche tabou, les coûts moyens sont une moyenne obtenue sur dix exécutions pour chaque instance. En ce qui concerne la recherche tabou, les résultats montrent clairement l'intérêt d'une optimisation globale, ce qui était tout à fait logique. Par contre, on pourrait conclure que les deux heuristiques semblent meilleures que la recherche tabou puisque les coûts totaux sont moindres. En réalité, ce constat doit être pondéré au moins par deux points : . le premier point est que les résultats des variantes de la recherche tabou sont une moyenne. Il y a des exécutions qui ont donné des solutions de meilleur coût, mais ces solutions ont été pondérées par des solutions très mauvaises ; . le deuxième point concerne la très mauvaise qualité de notre solution initiale, en comparaison de la solution fournie par rapport aux deux heuristiques. En réalité, notre construction initiale est basée uni- quement sur le facteur temporel, sans prendre en compte le facteur distance. Or ces deux facteurs sont étroitement liés, et sont bien pris en compte dans les règles de construction des heuristiques. A titre expérimental, nous avons voulu tester la recherche tabou à partir des solutions fournies par les heuristiques, et nous avons constaté une amé- lioration sensible du coût. En effet, l'analogie peut s'établir de la façon suivante : . véhicule (un ou plusieurs) = bus (un ou plusieurs) ; . marchandises (produits blancs) = passagers ; . contraintes : - précédence : montée d'un passager à une station (chargement) avant sa descente à une autre sta- tion (déchargement) ; - capacité : limitation de la taille des bus en nombre de passagers ; - fenêtres temporelles : arrivée des bus aux stations à des dates données (avec marges positives ou négatives) respect des horaires. Un travail dans ce sens en collaboration avec un partenaire industriel est en cours. Références M] G ! over F. " Future paths for integer programming and links to artificial intelligence ". Computers and Operations resear- ch 13, p. 156-166, 1986 [21 Gendreau M, Soriano P. : "Fondements et applications des méthodes de recherche avec tabous ". Operations resear- ch 31 (2), p. 133-159, 1997. [3] Antoine Landrieu : "Logistique inverse et collecte de pro- duits techniques en fin de vie - Tournée de véhicules avec contraintes " Doctorat INP Grenoble, 21 septembre 2001. [41 Antoine Landrieu, Yazid Mati, Zdenek Binder : "A tabu sear- ch heuristic for the single vehicle pick-up and delivery pro- blem with time windows ". Journal of Intelligent Manufacturing, special issue : Global optimization meta heuristics for industrial systems design and management, vol. 12, p 497-508, 2001. [51 Johann Dréo, Alain Pétrovvski, Patrick, Siarry, Eric Taillard : "Méta-heuristiques pour l'optimisation difficile ". Editions Eyrolles, 09/2003. 7. Conclusions et perspectives L'application de la méthode de recherche tabou s'avère novatrice et prometteuse dans le contexte des problèmes de tournées de véhicules que nous avons abordé. En ce qui concerne la méthode elle-même, des amé- liorations sont possibles, notamment pour la construction du voisinage ou la recherche d'une « bonne » solution initiale. Par ailleurs, une telle problématique semble tout à fait proche des problèmes de transport de passagers par bus dans une ville, la différence est que les passagers ne sont pas des produits en fin de vie ! a u ETj Bernard DESCOTES-GENON est né à Grenoble (France) en 1947. Il obtient un doctorat en automatique à l'université de Grenoble en 1974, et l'habilltation à diriger des recherches à l'Institut national polytechnique de Grenob ! e () NPG) en 1990. Il est actuellement professeur des universités à l'université Joseph Fourier (Grenoble 1) et effectue ses recherches au labo- ratoire d'automatique de l'INPG. Ses enseignements portent principalement sur l'automatique et l'informatique industrielle ; ses recherches concernent la supervision, la surveillance et la commande des systèmes de production, ainsi que les pro- blèmes de logistique dans les systèmes de transport. REE No 1 Janvier 2005