Synthèse de réseaux et applications aux transports et à la logistique : une problématique émergente

21/10/2017
Auteurs : Alain Quilliot
Publication REE REE 2005-1
OAI : oai:www.see.asso.fr:1301:2005-1:20575
DOI :

Résumé

Synthèse de réseaux et applications aux transports et à la logistique : une problématique émergente

Métriques

1
0
1.59 Mo
 application/pdf
bitcache://634f759df591b4f00e3bc8dc52eae6c76287ba32

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/20575</identifier><creators><creator><creatorName>Alain Quilliot</creatorName></creator></creators><titles>
            <title>Synthèse de réseaux et applications aux transports et à la logistique : une problématique émergente</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">Tue 22 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">634f759df591b4f00e3bc8dc52eae6c76287ba32</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34747</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

. Dossier) LOGISTIQUE ET TRANSPORT Synthèse de réseaux et applications aux transports a et à la logistique : a e une problématique émergente Mots clés Réseaux, Modèlesd'optimisation, Transports Par Alain QUILLIOT Directeur du LIMOS, UMR CNRS 615.8 Universlté BLAISE PASCAL 1. Introduction : Les objectifs essentiels associés à la synthèse de réseaux D'un point de vue pratique, on parle de problèmes de synthèse de réseaux quand on travaille sur l'organisation stratégique d'un système supportant des flux : d'infor- mations, de biens, de personnes, de fluides. Typiquement, la notion de synthèse de réseaux vue par un opérateur de transport public renvoie à la définition de l'offre de transport proposée par cet opérateur, telle que perceptible par l'usager : lignes, horaires, correspondances, tarifs. tD ZD Vue par un opérateur de télécommunications, elle renvema au dimensionnement physique du réseau (emplacements des commutateurs et des connexions), à sa structuration en réseaux virtuels associés à différents types de proto- coles, et à la tarification des accès. Vue par un industriel, elle correspondra aux choix des emplacements d'unités, de machines, et à l'organisation physique et logique de la chaîne logistique. Dans tous les cas, les niveaux de décision induits concernent le moyen et le long terme, et supposent pour le décideur de disposer de moyens d'anticiper les conséquences des choix effectués. D'un point de vue académique, le terme synthèse de réseaux évoque la contribution apportée à ce processus de décision par la mise en oeuvre de modèles et de méthodes d'optimisation, de recherche opérationnelle et de simulation, visant à la génération et à l'évaluation e automatique de scenarii prospectifs. Ces scenarii seront un des éléments sur lesquels s'appuiera la prise de décision effective : le processus qui les génèrera et les évaluera constituera l'aide inforiiititielbie cipl) oi « tée citi pi-ocesstis global de décision. Ces problèmes de s.'iithèse de résecitix (ou nentoi-k design) ont pris une importance particulière au cours de ces vingt dernières années en recherche opérationnelle. La raison en est principalement l'évolution subie par le monde des télécommunications et, à un moindre degré, par celui des transports et des systèmes de production. La tendance à la mise en compétition des différents opéra- teurs (d'infrastructure ou de service) a conduit ceux-ci à davantage se préoccuper de l'optimisation de leurs décisions en termes d'infrastructures et de modalités de fonctionnement, et à rechercher des outils leur permettant de mieux identifier leurs parts de marché La montée en puissance des outils d'acquisition et de stockage de l'information (capteurs, dispositifs de transmission mobiles, bases de données, systèmes répartis...) permet à présent une structuration des systèmes d'informations associés au suivi d'activités réparties, qui rend possible l'alimentation des modèles en données pertinentes (mesure de demandes, de coûts, de qualité de service...). Un problème de synthèse de réseaux se caractérise donc (voir par exemple AHU95 : focalisation sur le cas E 5 5 E S y N 0 P 5 Serontprésentésicidefaçonsynthétiquelesgrandsobjectifsde ce que l'on appellesynthèsede réseauxen rechercheopérationnelle, ainsique les modèles, applications et difficultésqui en dérivent. This paper starts with a general presentation of the Network Designframework. Then it discussesthe way problems related to logistics and transportationsystems may be casted into this fra- mework. It ends with some elements related to algorithms and numericalexperiments. REE N°1 J,invici 2005 Synthèse de réseaux et applications aux transports et à la logistique : une problématique émergente des télécommunications ; MAG78, MAG81 et FL084 : focalisation sur le cas des transports) par l'application sous-jacente qui fait explicitement apparaître la recherche des caractéristiques d'un ou de plusieurs réseaux d'infra- structures (télécommunications, transport, production...) sur lequel différentes classes d'objets (véhicules, messages, produits...) ont à circuler conformément à des prévisions de demandes d'accès et à des contraintes temporelles. Les caractéristiques sur lesquelles porte cette recherche concernent simultanément les dimensions des connexions et des noeuds de commutation, leurs emplacements à l'intérieur d'une géographie donnée, leurs dates et tarifs d'accessibilité. et le routage des objets usagers sur ces réseaux. Ces réseaux peuvent être super- posés selon plusieurs niveaux de virtualité ou de réalité : on pourra ainsi distinguer les réseaux associés aux parcours et horaires des différentes classes de véhicules d'un même service public de transport urbain porté par un même réseau de voirie. Les critères que l'on cherche à satisfaire concernent les coûts. la satisfaction de la demande et la qualité du service offert (délais d'achemi- nement, probabilités de congestion...). c 2. Modèles génériques et taxonomie Les principaux outils mathématiques intervenant dans les modèles de synthèse de réseaux concernent la programmation linéaire, la théorie des graphes, l'optimi- sation, la théorie des files d'attente, la théorie des jeux et la théorie des flots et de multitlots. Rappelons en quelques mots en quoi consiste ce dernier type d'objet. 2.1. Notion de flot et de multiflot Soit G = (X,E) un réseau ou graphe orienté. X est l'ensemble des sommets et E l'ensemble des arcs de G. Un a u Un flot de G, à valeur dans le K espace vectoriel E où K est le corps de base de F, est un F-vecteur f, indexé sur E, et tel que pour tout sommet x dans X. on ait : E e.oi 1 (le \ 1 c f =3 " f t1e= 1 <, eiitié, cil ift, - On a souvent F = K = nombres réels ou entiers et on parle alors de,flot simple. Si F est de dimension finie, on parle de iiiiiltiflot. Il peut arriver que F soit un espace de fonctions définies depuis un espace-temps vers un espace numérique, ou encore que F soit un espace de variables aléatoires. On dit que f achen2ine une qliaiitité d de x vers y, x,y E X, si l'on a pour tout sommet z différent de x et y et si : L E e.rwn de.c e o 1 (le f = E * " ff'nVt'.'N.v t 11 1 = y, 1 ('fV f, + d : f, - d On parle de flot teiiilioi-isé quand chaque composante fc est accompagnée d'indications sur la fenêtre de temps c qui voit la quantité correspondante de flot s'écouler le lon,g de l'arc e. 2.2. Un modèle générique et ses dérivations Dans le cas des télécommunications ou des transports, nombre de problèmes se formulent ainsi, dès lors que l'on suppose préalablement connue une topologie support sous-jacente (choix des noeuds et des liens susceptibles de servir de support à des canaux de communication), sous une forme proche de la forme suivante : Problème type CFA : Capacited Flow Assignment Trotivei-, sur un réseau de départ G = (X,E définissant une topologie sitlI) ort, un iyectelir iiifrastructure 1- >- 0 e Z et an iiiiiltiflot utilisateurj'= (fi, i dans 1) 0 tels que : . Cl (,-,),- (contraintes sti-iictiii-ellesS [il- 7, clui peut être discret ou réel et contraint du fciit (le préoccul-a- tions de sécurité ; on pourra par exer2ple exiger de z qu'il permette l'acheminement d'un certain type d'ojets par an iiioitis deux heiiiins arc disjoints) '/f9Mr fC É'J E. >/'' f9/' rV (9 M . pour tout arc e dans E, 7, >- f " e oti,f " renvoie à un vecteur agrégat (le plus souvent la soiiiiiie) construit à partir des composants du multiflotf ; chaque coiiilyoscintfi du iiit (Itiflotj' (éventitelleiiietit teiiipoi-isé) ac-heiiiiie nue certaine deiiiaiide Mi depuis un ensemble de sommets origines Oi vers un ensemble de soiiiiiiets destination Di ; Ziiiiii = U (I-) (coût d'iiistalltition) + V (z,f) (coût de f (nctionne- rrrent lié à + W Wfz,/)(i7iesiii-e de défaut de service associée Interprétation : l'objet inconnu z (objet maître), représentera suivant les cas : . des emplacements et dimensions choisis pour des connexions ou des dispositifs de commutation, c'est-à-dire des choix d'emplacements et d'infra- structures physiques ; . des parcours de navettes, de camions, de trains ou d'avions et leurs horaires, des réseaux virtuels associés à un type de communication donné, c'est- à-dire une stratégie d'organisation. L'objet f représentera quant à lui des flux moyennés « d'usagers », éventuellement temporisés : passagers, produits transpoi-tés ou transmis d'une unité de production à une autre, fichiers informatique. Ce caractère statis- tique de l'objet f fera que celui-ci pourra être exprimé en termes probabilistes. Dans la plupart des cas, la fonction U est concave (coûts dégressifs), tandis que le fonction W tend à syn- thétiser les taux de pertes ou les délais induits par un encombrement excessif du réseau : voir par exemple la fonction Délai de Kleinrock (cas des transports urbains) : W (z,f) = LII li/ (zi, - f.,). REE ? 1 Janvicr 2005 Doss ie-r) LOGISTIQUE ET TRANSPORT Le besoin de prendre en compte, au sein des modèles, des critères de qualité de service (QoS) suffisamment fins, est en train de devenir un besoin prioritaire des opé- rateurs : cela signifie l'apparition, dans ces modèles, de fonctions de performances W (x,f) plus complexes que la fonction de Kleinrock, ainsi que la prise en compte de contraintes de structure Cl (x) qui expriment le plus souvent la nécessité qu'a le système de pouvoir se recon- figurer de façon efficace en cas de perturhation. La prise en compte de contraintes temporelles et de variations des demandes dans le temps amène à introdui- re une dimension ordonnancement dans le problème, qui peut traiter par une séparation du problème de base en sous-problèmes associés à des périodes différentes, ou par une indexation sur le temps des sommets du réseau de base au sein d'un même modèle de réseau dit dynanigue ou terjiporisé : voir [AR089, MIN87]. La prise en compte de la superposition de réseaux réels et virtuels (des réseaux hétérogènes multiservices dans le cas des télécommunications), amène à décomposer l'objet inconnu z en couches, et à imposer une définition plus large de la notion de chemin ou de routage : voir [CON93]. Considérer z fixé revient à se focaliser sur la pro- blématique du routage : voir [ASH98, BENDOI, COR98]. Ce routage peut obéir à une logique centrali- sée (le planificateur contrôle les décisions de routage) ou décentralisée (les usagers décident et le planificateur se borne à prévoir ou suggérer). Supposer que la topologie support G = (X, E) n'est c pas complètement localisée à l'intérieur d'une géographie donnée revient à introduire le problème de la localisation : voir [DRE98, GEN93, JA197]. Introduire la problématique tarification signifie introduire un vecteur prix p, indexé sur le même ensemble d'indices que f : voir [GRA92, LED98]. . imposer sur p des contraintes de stabilité, expri- mant le fait qu'aucun opérateur concurrent n'est susceptible de capter une partie du trafic représen- té par f en mettant en place sa propre infrastructu- re : modèles de jeux coopératifs avec coeur ou de jeux non coopératifs avec équilibres de Nash ; . imposer à p un critère de maximisation de profit dans le cas ou les demandes sont élastiques aux prix ; considérer p comme un élément de régulation du trafic et observer l'équilibre de trafic qui découle de stratégies de moindre coût (ou de maximisation d'utilité) mises en oeuvre par les usagers. c Les problèmes ainsi posés possèdent par ailleurs les caractéristiques suivantes : . ils sont de grandes tailles et, dans certains cas, mal conditionnés ou dégénérés ; . ils admettent souvent plusieurs optima locaux ; . ils se prêtent naturellement à des types de décom- position hiérarchique ou géographique ; . la mise en forme explicite des contraintes de struc- ture Cl (z) peut être très complexe, et induire la manipulation de contraintes de coupes spécifiques. Les méthodes appliquées au traitement numérique de ces problèmes sont très diversifiées, et couvrent l'essen- tiel de la panoplie algorithmique de la recherche opéra- tionnelle. On distinguera principalement : . les méthodes heuristiques, (amélioration locale et variantes stochastiques), qui concernent principalement la résolution des problèmes de localisation et de recherche de topologies [CRAOO] . les méthodes dérivées de l'optitiisatioti coiitinite (méthodes proximales, décomposition lagrangienne, techniques de sous-gradient, décomposition maître-esclave de Benders...) [MAU991 ; . les méthodes basées sur la programmation linéaire entière ou mixte, utilisée comme formalisme uni- versel au sein de la classe de complexité np-temps, parmi lesquelles on distinguera notamment : - les méthodes de branch-and-cut articulées autour des notions de représentation polyédrale ; - les méthodes associées aux modèles de flots et mccltiflots [AHU95, ASS80, CRAOO], . les méthodes dérivées du formalisme de la théorie des jeux (coopératifs et non coopératifs), qui concernent principalement les problèmes de tarifi- cation [LED98]. Au plan des applications, celles-ci ont principale- ment concerné les télécommunications et les transports (voir ASS80, CON93, COR98, DEJ87, FL084, JAI97, LED98, MARI96, VIJ93), mais aussi la gestion de sys- tèmes de production d'énergie, celle de systèmes de pro- duction, ainsi que la conception de circuits électro- niques [AHU95, DEV96, EDG78, MAR97, PER84, SC0961. 3. Bien utiliser les modèles : la nécessité d'une approche pluridisciplinaire Le traitement pratique des problèmes d'optimisation de réseaux amène par ailleurs à se poser des questions, qui relativisent l'intérêt qu'il peut y avoir à chercher à tout prix des gains de performance algorithmique : c celle de l'acquisition et de la modélisation des données d'entrées des modèles [ASH98]. Ces données sont complexes, car elles portent à la fois sur le système tel qu'il est ou tel qu'il serait en cas de reconfiguration : mesure de performances et de b REE No 1 Janvicr 2005 Synthèse de réseaux et applications aux transports et à la logistique : une problématique émergente fiabilité, élasticité de demandes par rapport à des prix ou à des niveaux de qualité, coûts. L'acquisition de ces données suppose l'existence préalable d'un système d'information propre au système qui soit suffisamment bien structuré, et la mise en oeuvre de techniques adéquates de datami- ning (fouille de données), de simulation et de contrôle en temps réel. La qualité des données obtenues conditionne bien sûr le niveau des perfor- mances algorithmiques à viser. c celle du mode d'utilisation des résultats induits par le traitement algorithmique de ces modèles [DRE98, CUR85, CAM02]. Ceux-ci ont vocation à être des modèles d'aide à la décision, et il est dès lors important d'identifier la façon dont ils vont effectivement s'insérer au sein d'un processus de décision. Dans beaucoup de cas, il s'agira de générer des scenarii à moyen ou long terme, et d'accom- pagner des études menées parallèlement au plan technique et financier, mais dans d'autres cas, il s'agira vraiment de proposer des modalités de réorganisation ou des choix d'investissements. Dans ces derniers cas, il conviendra de se doter des outils adéquats pour l'évaluation a priori (à l'aide par exemple de modèles de simulation) d'une telle décision et l'anticipation de son degré d'acceptation par son environnement. Cet ensemble de considérations fait que, malgré l'exis- tence d'une forte communauté travaillant depuis vingt ans sur cette problématique de l'optimisation de réseaux, beau- coup de difficultés subsistent, tant sur le plan des fonde- ments mathématiques que sur le plan pratique, tandis que les modèles eux-mêmes sont en constante mutation, du fait des évolutions à la fois techniques et économiques. 4. Exemples de tests numériques La plupart des problèmes de synthèse de réseaux sont de grandes tailles et admettent, dans leurs versions simplifiées, des formulations linéaires ou convexes. Les traitements qui leur sont apportés sont de nature heuris- tique et s'appuient sur le recours à des bibliothèques de PLNE (programmation linéaire avec nombres entiers) telles que les logiciels XPRESS, CPLEX ou OSL. Comme toujours, les performances de ces traitements dépendent des instances et des contextes, ainsi que des couches logicielles utilisées, et il est dès lors hasardeux de qualifier ces traitements en termes de performances. Nous allons toutefois donner ici une idée des seuils, en termes de taille, à partir desquels les problèmes considé- rés ne peuvent plus être traités de façon exacte. On considère pour cela le problème CFA-DESIGN, dans lequel on suppose : . que le vecteur infrastructure z soit entier ; 'qu'il n'existe pas d'autre contrainte de structure sur z ; . que l'ensemble des critères de performances sont linéaires. Le problème ainsi considéré définit un programme linéaire mixte. On teste alors [CRAOO] sur une station SUN Sparc Ultra et en utilisant la bibliothèque CPLEX, différents procédés dérivés de la programmation linéaire : W : relaxation des contraintes d'intégrité sur z et des contraintes couplantes ; S : relaxation de contraintes d'intégrité sur z ; F : relaxation lagrangienne des contraintes couplantes ; BB : résultat exact obtenu par Branch and Bound ; ainsi qu'une heuristique par recherche tabou [CRAOO] : TS. D'un point de vue pratique, la mise en oeuvre de ces méthodes est perturbée par des phénomènes de dégéné- rescence. Sur des exemples relativement difficiles, on obtient : (chaque problème est identifié par son nombre de noeuds, d'arcs, et de couples origine-destination ; à chaque méthode correspond le pourcentage de la valeur qu'il induit par rapport à l'optimum, ainsi que le temps CPU qui a été utilisé). Paramètres 25,-100,30 100,400, 10 w s BB TS ,.-M, 20,300,200 30,700, 100 30,700,400 75 % 96 % 96% 100% 102% 1 s 10 5 2541 471 50% 71% 71% 100% 105% 1 63 6 6189 499 74% 93% 93% 100% 117% 5 3925 67 100220 8 110 85% 95% 95% 100% 104% 4 1 157 72 26575 11537 1.09 Échec 1.27 Échec 1.50 120 301 88310 Coiiiii7entaires : on constate ici des difficultés, dues bien sûr à la présence du vecteur infrastructure entier z, et qui se traduit par un allongement très sensible des temps de traitement. Il est difficile d'obtenir un résultat exact dès que le nombre de variables entières (ici le nombre d'arcs) dépasse la centaine. On note une difficulté à faire fonctionner la bibliothèque CPLEX sur des exemples de grandes tailles. On constate enfin un bon comportement de l'heuristique d'amélioration locale proposée par les auteurs. REE WI Janvier 2005 e o s s i e r LOGISTIQUE ET TRANSPORT 5. Conclusion Les problèmes de synthèse de réseaux renvoient donc à des domaines d'application assez diversifiés et mettent potentiellement en jeu une très large panoplie de tech- niques et d'outils logiciels. c Principalement motivée au départ par des préoccu- pations relatives au domaine des télécommunications, cette problématique de la synthèse de réseaux tend à se déployer à présent sur d'autres domaines, principalement celui du transport, de la logistique, de l'organisation des systèmes de production et à inclure en son sein certains problèmes de tarification. Il est toutefois important de noter que les modèles mis en jeu, qui sont le plus souvent de nature stratégique ou tactique, font apparaître des quantités (coûts, demandes. coefficients de qualité de service...) dont l'acquisition et l'évaluation induisent de réelles difficultés. L'opérationnalité de ces modèles, actuellement le plus souvent utilisés de façon prospective, présuppose d'une part un renforcement des systèmes d'information et d'acquisition des données associés aux systèmes étudiés et d'autre part une évolution de ces systèmes d'information vers davantage d'intégration, et enfin leur couplage avec des outils performants de simulation et de fouille de données. Références [AHU95] RK. AHUJA, T.L. MAGNANTI, J.B. ORLlN, M.R. REDDY " Applications of network opti mi zatlon, Chapter 7 of Network Models, Handbook of Operation Research and ManaemenfSc/eDce 7 ", p 1-83, (1995). [AR089] J.E. ARONSON. " A survey on dynarmc network fIows " ; Annals of Operat Research 20, p 1-66, (1989). [ASH98] K. ASHOK : " Estimation and prediction of time depen- dent origin-destination flovvs ", PHD Thesis (D ! r. M. BEN-AKIVA, MIT, 1998 [ASS801 A. ASSAD " Models for rail transportatlon " ; Transp Research A, 14, p 205-220, (1980). [BENDOCI F. BENDALI, J. MAILFERT, A. OU LLIOT " Jeux coopératifs et demandes élastiques " ; RAIRO RO 35, p 367-381, (2000). [BENDOI] F. BENDALI, J. MAILFERT, A. OU LLOT " Flots entiers et multiflots fractionnaires couplés par contrainte de capacité " ; Investiga Operatlva 9, 31 pages, (2001). [CON931 i. CONSTANTIN : " L'optimisation des fréquences d'un réseau de transport en commun ", Rapport CRT 881, Université de MONTREAL, 1993. [COR981 J.P. CORDEAU, P. TOTH, D. VIGO " A survey of optl- mization models for train routing and scheduling ? p " ; Transportation Science 32, p 380-404, (1998) [CRAOO] T. CRAINIC, M. GENDREAU, J.M. FARVOLDEN : " simplex based tabu search method for network des/- gn " ; INFORMS Jour on Computing 12, p 223-236, (2000). [CRA881 T. CRAINIC, J,M. ROUSSEAU " Mu/ticommodity, mu/- timode frerght transportation : a general modeling and algorithmic framework for th service network design problem " ; Transport Research B 20-B, p 290-297, (1988), [DEJ87] P. DEJAX, T. CRAINIC " A review of empty flow and fleet management models in freight transportation "; Transportation Science 21, p 227-247, (1987). [DEV96] D. DE WOLF, Y. SMEERS " Optimal dimensionning of pipe networks with application to gas transmission networks " ; Operat Research 44-4, p 596-608, (1996). [DRE981 Z. DREZNER, T. DREZNER : " Applied location theory models " ; ln " Modern Methods for Business Research ", p 79-120, MAHWA, N.J Lawrence Erlbaum Eds, (1998). [EDG78] T.F. EDGAR, D.M. HIMMELBLAU, T CBICKEL " Optimal design of gas transmission networks " ; SPE J 18, p 96-104, (1978), iFLO841 M. FLORIAN " An introduction to network models used ii transportation planning ", ! n M.FLORtAN Ed. Transp. Plann. Models, North Holland, p 137-152, (1984). [GEN93] M. GENDREAU, G. LAPORTE, J.A. MESA " Locating rapid transit lines : decision criteria and methodology ", Rapport CRT 907, Université de MONTREAL, 1993. [GRA92] D. GRANOT, F. GRANOT : " On some network flow games " ; Maths Operat Research 17, p 792-841, (1992) [JA 971 P. JAILLET, G. SONG, G. YU " Alrline network design and hub location problems " ; Location Science 4-3, p 195-212, (1997). [LED981 P.J. LEDERER, R.S. NAMBIMADOM : " Airline network [LED98] [MAG81 design " ; Operai Resea rch 46-6, p 785-804, (1998). [MAG81] T. MAGNANTI : " Combinatorial optimization and vehicle fleet planning " : perspectives and prospects, Networks 11, p 179-214, 1981 [MAG78] T. MAGNANTI, B.L. GOLDEN " Transportation plan- ning. network i) odels and their implemeitatloi ", in A.C.Hax ed : Studies in Operation Management, p 465- 518, (1978). [MAR97] 0. MARIANI, F. ANCILLAI, E DONATI " Design of a prpeline optimal configuration ", n Proceedings 29 th PSIG Conf TUCSON, USA, (1997). (MAR1961 A. MAR N, J. SALMERON : " Tactical design of rail freight tetworks. part 1- exact ancl leuristic methods ", EJOF 90, p 26-44, (1996) [MAU99] J. MAUBLANC, D. PEYRTON, A. QUILLlOT " Multrple routing strategies in a labelled graph ", 1 vest gacion Operativa 7, 3, p 101-133, (2001). [MIN871 M. MINOUX " Network synthesis and dyiai-nic net- work optimrzation " ; n S. MARTELLO, G- LAPORTE, M. MINOUX, C. RIBEIRO Ed, Surveys in Combinatorial Optimization, Chap 9, p 283-324, North Holland, (1 987. [SC0961 T. SCOTT, E. READ : " Modelling hydroreservoir opera- tion in a deregulated electricity market " ; ITOR 3 (3-4), p 243-253, (1996) [VIJ931 R. VIJAY, A. KANDA, P. VRAT " Multiperiod capacity expansion of road networks : formulation and algo- rithms " ; Operation Research 30, p 117-140, (1993). [SC0961 [VIJ931 Et e u r Alain QUILLIOT est un ancien élève de 'ENS Saint-Cloud. Professeur d'informatique à l'université Blalse Pascal de Clermont- Ferand, il est actuellement directeur de l'Ecole d'ingénieurs ISIMA et du laboratoire CNRS L ! MOS (UM,9 6158). REE Nu 1 Janvier2005