Algorithme génétique avec contrôle des opérateurs pour l’optimisation multicritère d’un déplacement dans un réseau de transport multimodal

30/09/2017
Publication e-STA e-STA 2005-4
OAI : oai:www.see.asso.fr:545:2005-4:19995
DOI : You do not have permission to access embedded form.

Résumé

Algorithme génétique avec contrôle des opérateurs pour l’optimisation multicritère d’un déplacement dans un réseau de transport multimodal

Métriques

15
8
46.6 Ko
 application/pdf
bitcache://b7548de6548c5ae8706416eb89af8d38b6039d5d

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/545:2005-4/19995</identifier><creators><creator><creatorName>Slim Hammadi</creatorName></creator><creator><creatorName>K. Zidi</creatorName></creator></creators><titles>
            <title>Algorithme génétique avec contrôle des opérateurs pour l’optimisation multicritère d’un déplacement dans un réseau de transport multimodal</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Sat 17 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">b7548de6548c5ae8706416eb89af8d38b6039d5d</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34009</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Algorithme génétique avec contrôle des opérateurs pour l’optimisation multicritère d’un déplacement dans un réseau de transport multimodal K.ZIDI Laboratoire LAGIS Ecole centrale Lille, France. Zidi.kamel@ec-lille.fr S.HAMMADI Professeur université Laboratoire LAGIS Ecole centrale Lille, France. Slim.hammadi@ec-lille.fr Abstract - Dans cet article, nous définissons un algorithme génétique fournissant un support pour l’aide au déplacement multimodal. Le calcul des plus courts chemins est réalisé par l’utilisation d’une méthode évolutionniste. Cette méthode est basée sur l’hybridation entre un algorithme de Dijsktra modifié avec un algorithme génétique. Pour trouver rapidement de bonnes solutions en cas de perturbation du réseau de transport, nous avons ajouté dans cet algorithme une étape de contrôle des opérateurs génétiques. Keywords:Dijsktra, algorithme génétique, perturbation du réseau de transport, contrôle des opérateurs génétiques. 1 Introduction Le projet national PREDIM a été créé au sein du programme français de recherche et d'innovation dans les transports terrestres (PREDIT). PREDIM vise à assurer la complémentarité des différents modes de transport et de déplacement, tant individuels que collectifs en améliorant la qualité et la disponibilité de l’information multimodale. Nous avons commencé la réalisation d’un système interactif d’aide au déplacement multimodal (SIDAM). Dans ce contexte, une des difficultés théoriques qui apparaît est la recherche dans un graphe dynamique de l’itinéraire optimal, en temps réel, à partir de plusieurs sources d’information et en mode perturbé. L’objectif ici est de réaliser un système permettant d’aider les voyageurs des transports collectifs et de faciliter leur déplacement en mode normal et en mode dégradé de fonctionnement du réseau. Ce système vise par ailleurs à minimiser le temps d’attente des voyageurs, en mode dégradé, dans les pôles d’échanges et de leur assurer, dans la mesure du possible, la continuité des déplacements dans les réseaux multimodaux. Il s’agit donc d’améliorer la qualité du service rendu aux voyageurs et de les maintenir informés. Face à l'augmentation du nombre et de la complexité des déplacements, les usagers des transports en commun souhaitent disposer d'une information fiable sur l'ensemble des modes de transport qui sont mis à leur disposition. Cette information multimodale est difficile à mettre en oeuvre pour de nombreuses raisons : organisationnelles, économiques, juridiques et techniques etc… les sources d'information sont nombreuses, dispersées entre les différents opérateurs de transport, et les technologies de diffusion et de présentation qui leur sont attachées sont multiples et en constante évolution. Notre article est organisé en deux grandes parties. Dans une première partie, nous commençons par définir les fonctionnalités d’un système d’information dans le transport multimodal ainsi que les problématiques associées. Par la suite, nous introduisons les notions d’optimisation mutiobjectif et l’approche envisagée pour concevoir un tel système. La dernière partie est consacrée à la présentation de la méthode évolutionniste proposée pour optimiser l’itinéraire multimodal. 2 Problématique de l’information dans le transport multimodal De nombreux blocages au développement de l'information multimodale ont été identifiés, notamment en France par l'INRETS et ITS France [18]. La plupart sont non techniques. Il y a globalement trois types de rais ons pour lesquelles un acteur sollicité pourrait refuser de participer à la mise en place d'un système (et notamment de fournir des données), soit c'est trop cher, soit cela n'a jamais été fait jusqu'à présent et il pourrait y avoir un risque technique (de non faisabilité), soit cela ne répond pas à sa stratégie institutionnelle ou commerciale (typiquement en matière de diffusion d'information). L’information multimodale constitue l’un des maillons essentiels de cette problématique. Il s’agit de fournir toute information utile et pertinente sur les différents modes de déplacement (métro, tramway, bus, etc.), afin d’une part d’améliorer le confort et l’efficacité des trajets à un niveau individuel, et d’autre part de favoriser l’usage multimodal et raisonné des différents modes de transport à l’échelle collective. Les acteurs français de l’information multimodale développent des solutions spécifiques sans rendre public leurs algorithmes, ni même souvent les spécifications d’interface, et ne s’appuient pas beaucoup sur les compétences des autres acteurs ni sur les résultats obtenus à l’étranger [1]. En conclusion, l’information multimodale est un thème actuel de recherche. De nombreuses études s’effectuent de manière à mieux concevoir les systèmes ; certaines portent notamment sur les besoins des utilisateurs [13]. Cependant, il est actuellement difficile de trouver un système fournissant à la fois la possibilité de planifier son itinéraire en tenant compte de tous les modes de transport possibles, des critères fournis par l’utilisateur, et accompagnant celui-ci tout au long de son déplacement [4]. 3 Déplacement dans un graphe dynamique Afin de réagir en cas de perturbation, pour un système d’aide au déplacement, la gestion en temps réel est très importante. Dans ce cas, le système gère la préparation du voyage et le suivi du voyageur tout au long du déplacement. En outre, la mise à jour des informations et la prise en compte des perturbations constituent un enjeu important d’un point de vue opérationnel, car les usagers ont besoin d’informations fiables avant et pendant le voyage. Pour cette raison, la perturbation d’un déplacement présente plusieurs cas possibles. En effet, un utilisateur sollicite l’information nécessaire à un déplacement entre un point de départ ‘D’ et un point d’arrivée ‘A’. Mais ces deux points peuvent bouger dynamiquement. Autrement dit, l’usager peut changer son point de départ ou bien sa destination avant le début du déplacement. De même, au cours du déplacement une perturbation éventuelle dans le réseau de transport peut entraîner des changements sur les points de départ et d’arrivée. En conclusion on distingue quatre cas possibles: Cas 1 : Le premier cas est statique, les deux points ‘D’ et ‘A’ sont fixes. Dans ce cas, le problème est la recherche d’un bon itinéraire multimodal satisfaisant les critères imposés par un client du transport Cas 2 : Le deuxième cas est celui où le point de départ ‘D’ bouge. En effet, quand l’usager change son choix de départ éventuellement à cause d’une perturbation, ‘D’ n’est plus accessible par le réseau de transport. De même pendant le déplacement, une perturbation provoque un changement du prochain noeud qui peut être considéré comme un nouveau point de départ « D’ ». Cas 3 : Le troisième cas concerne la dynamique du noeud d’arrivée « A ». De même que dans le cas précédent, la cause peut être un nouveau choix de l’utilisateur ou une inaccessibilité due à une perturbation. Il y a donc changement du point « A». Cas 4 : Le dernier cas regroupe les deux précédents. Autrement dit les deux noeuds « D » et « A » bougent simultanément. La différence avec les deux cas précédents est qu’on a deux points dynamiques. Ce cas demande un traitement spécifique parce que l’optimisation du chemin n’est plus entre deux points mais plutôt entre deux zones. 4 Optimisation multiobjectif Les problèmes de cheminement sont parmi les plus anciens de la théorie des graphes. Le problème le plus typique de cette catégorie est celui du plus court chemin. En effet, il se rencontre dans de nombreuses applications. L’algorithme le plus utilisé pour la recherche du plus court chemin est sans doute celui de Dijsktra [1] [14]. Dans la littérature, une attention particulière a été portée aux problèmes à deux critères en utilisant les méthodes exactes telles que le « branch and bound » [6] [12] [17][16], l’algorithme A* [3], et la programmation dynamique [15]. Ces méthodes sont efficaces pour des problèmes de petites tailles. Pour des problèmes à plus de deux critères ou de grandes tailles, il n’existe pas de procédure exacte efficace, étant donné les difficultés simultanées de la complexité NP- difficile, et le cadre multicritère des problèmes [5][7] [9][19]. Les métaheuristiques sont représentées essentiellement par les méthodes de voisinage comme le recuit simulé, la recherche tabou, et les algorithmes évolutifs en particulier les algorithmes génétiques ainsi que les algorithmes à stratégie d'évolution [8]. Les algorithmes génétiques sont inspirés des mécanismes de l’évolution des êtres vivants et de la génétique moderne, et constituent un outil puissant d’optimisation. Nous présentons également les possibilités de combiner différentes méthodes pour créer des méthodes hybrides. Le mode d'hybridation qui semble le plus fécond concerne la combinaison entre les méthodes de voisinage et l'approche évolutionniste. Les algorithmes hybrides sont sans doute parmi les méthodes les plus puissantes. 5 Calcul de plus court chemin entre deux points Nous utilisons ici une méthode multicritère de recherche d’itinéraire qui s’appuie sur une hybridation entre un algorithme de Dijkstra modifié [11] et un algorithme génétique pour générer une population de chemin minimum [10]. L’algorithme de Dijkstra modifié nous donne un ensemble de solutions. Nous utilisons par la suite cet ensemble de solutions comme population initiale pour l’algorithme génétique. Dans ce sens, nous proposons une fonction de fitness f qui calcule le coût de chaque arc du graphe du réseau. L’objectif est de minimiser le coût total du chemin qui représente la somme des coûts des arcs traversés. (1) 3 2 1 * * * C C C f δ β α + + = 1 C , 2 C et 3 C représentent les valeurs des critères d’optimisation tels que le coût, le temps de parcours et le confort. (2) i variant de 0 à z; représente les zones. i c3 représente le coefficient de confort correspondant à la zone i. ik c1 est le prix de titre de transport dans la zone i en utilisant le mode k. χ ≤1 est le coefficient utilisé par les modes de transport pour le calcul du prix inter-zones. (3) i m i t le temps de parcours de l’arc i par le mode de transport i. j Att T est le temps d’arrêt dans la station j i C C 3 3 ≡ (4) Est un facteur défini par la compagnie de transport selon les zones et la période de voyage. Alors que les α, β et δ sont des coefficients de pénalité pour ces critères, leur somme est égale à 1. Cette fonction f ramène le problème d’optimisation multicritère à un problème d’optimisation monocritère. L’utilisation d’une méthode d’optimisation évolutionniste nous permet de proposer plusieurs solutions à l’utilisateur pour choisir celle qui lui convient le mieux. 6 Méthode évolutionniste avec contrôle des opérateurs génétique Aujourd’hui, les systèmes d’optimisation des itinéraires sont presque aussi nombreux que les exploitants de réseaux de transport. Ces systèmes sont centralisés, et ne communiquent pas ou très peu entre eux [1] comme TransCAD par exemple. Par ailleurs, il existe également des algorithmes de calcul réparti, permettant de distribuer le calcul par exemple entre réseaux urbains et interurbains et reconstituant l'itinéraire optimal de bout en bout ; ces solutions ont été mises en oeuvre dans le projet allemand DELFI. Ce dernier reste à notre connaissance un prototype encore en test. Dans ce sens, l’algorithme évolutionniste de recherche d’itinéraire (Figure 1) commence par construire une population initiale de solutions. L’Algorithme Dijkstra Modifié « AMD» nous donne un ensemble de bons chemins entre deux nœuds [10]. Le principe de cet algorithme est la répétition de Dijkstra plusieurs fois avec un test de changement de chemin entre les itérations. P est la population initiale de (2*w) individus résultant de cette étape de l’algorithme [11]. Cette population est la population initiale pour notre algorithme génétique. Dans cet algorithme, nous proposons deux Opérateurs de Croisements par Conjugaison du Mode, OCCM [11] le premier à deux-points sur les colonnes, le deuxième à un seul point. Toutefois, le respect de faisabilité des itinéraires est toujours assuré par ces opérateurs. Alors que l’Opérateur de Mutation « OM » correspond à des changements aléatoires de passage par un noeud d’une solution. Cependant, ces changements doivent respecter la réalisabilité du chemin [2]. Pour évaluer un individu dans une population, nous utilisons le coût final f C . Ce dernier est calculé par la formule (1). L’évolution d’une population est contrôlée donc par la minimisation de f C . En général, une perturbation concerne un ensemble de stations dans la zone et un ensemble de modes de transport. Pour gérer les cas de perturbation, nous avons besoin d’une population finale dont les individus sont dispersés sur toute la zone et utilisant le plus de modes possibles. Autrement dit, si nous disposons des solutions robustes représentatives des différentes régions et des différents modes de transport, nous augmentons aussi la probabilité de trouver une solution de secours en temps réel lors des perturbations qui surviennent dans le réseau de transport. Ceci sera possible grâce à la diversification des solutions dans notre population finale. Pour contrôler les opérateurs génétique, nous utilisons deux variables. ij A est le nombre d’arcs communs entre deux solutions i et j, minimiser cette variable permet d’augmenter l’exploration des solutions sur la zone. L’avantage de cette méthode est d’augmenter la probabilité de trouver une solution en cas de perturbation. Ceci représente l’un de nos objectifs. Le deuxième variable i M qui est le nombre de modes utilisés dans une solution (pour les individus initiaux, ce paramètre est égal à 1). Avec la maximisation des i M nous améliorons la population en garantissant la multimodalité des solutions ainsi que la diversification. Cette diversification est intéressante pour la population finale pour donner plus de choix aux usagers. De plus, elle augmente aussi la probabilité de trouver une solution en cas de perturbation du réseau de transport. Soit P la probabilité de trouver une solution dans la population finale en cas de perturbation. mj Nb : Nombre de solutions utilisant le mode j dans la population finale. pi Nb : Nombre de solutions passant par la partie i de la zone. Supposons que nous ayons m modes de transport et que la zone soit coupée en k parties géographique. Une ∑ = = z i ik i C C C 0 1 3 1 * * χ T C ≡ 2 ∑ ∑ = = Τ + = Τ p i n j j Att m i i t 0 0 µ × = i Ci 3 µ perturbation concerne en général un mode de transport ou bien une partie géographique de la zone. La probabilité des solutions non valables dans la population finale si un mode j est perturbé est mj m m Nb P * 1 = . (5) La probabilité des solutions non valable dans la population finale si une partie i est perturbée est pi k p Nb P * 1 = . (6) ) ( 1 p m P P P + − = (7) Si pi Nb décroît alors p P diminue aussi ce qui permet à P d’augmenter. De même aussi si mj Nb décroît alors m P diminueaussi et P augmente. Figure 1. Algorithme génétique global. 7 Résultats et simulation Nous avons testé l’algorithme de calcul du plus court chemin sur des zones de la région lilloise. Dans notre exemple, nous simulons avec 4 modes de transport en commun. Ces modes sont le métro, le bus, le tramway, et le train régional. Nous avons divisé le réseau en trois zones. Dans la figure suivante, nous montrons les résultats de notre méthode appliquée sur des données de la région de Lille par un tableau (Figure 2). Ces solutions représentent une partie de notre population de solutions finales. Il reste à signaler que l’affichage de ces résultats pour les utilisateurs n’est pas encore fini. Pour ce point, l’amélioration de l’interface utilisateur en lui proposant plusieurs solutions est envisageable prochainement. En remarquant aussi que les coûts et les temps donnés sont calculés en utilisant des données de test que nous avons introduit dans nos bases des données. Remarques : Les indices M1, M2 indiquent les lignes de métro 1 et 2, alors que T1 et T2 les tramways 1 et 2. (T2 10:32) indique le changement de mode vers le tramway 2 qui part à 10h 32 minutes. Le Coût n’indique pas que le prix, il représente le résultat rendu en utilisant la formule (1). Si une perturbation se produit avant le début de voyage dans les 2 cas (cas 1 : sur le métro 1 et cas 2 : sur le métro 2). Dans le cas 1, notre approche montre que la première solution du tableau ci-dessus n’est plus valide alors que la deuxième l’est. Dans le deuxième cas, ni la première ni la deuxième solution ne sont valables alors que la troisième l’est. En générant d’autres types des perturbations qui concernent un ensemble de stations, nous remarquons que la population finale contient des solutions qui ne passent pas par les mêmes stations par rapport aux autres comme la cinquième ou bien la dernière solution. Donc si une perturbation couvre une partie de la zone, alors la probabilité de trouver la solution dans la population finale est grande grâce à la diversification des individus dans la population par rapport aux zones. Quant aux perturbations pendant le voyage, nous remarquons que les points de changement de mode sont nombreux dans les solutions générées. Le changement du trajet dans ces points explique les cas de graphe dynamique que nous avons détaillé auparavant. L’application de contrôle des opérateurs a donné des très bonnes solutions de secours dans ces types de perturbations. Solutions Coût f C Temps de parcours(mn) Initialisation AMD Test stop Oui Non Selection Crossover OCCM Evaluation Comparaison Mutation OM Population Finale & (M1 ) Porte des postes,Wazemmes,Gambetta,Republique,Rihour, (M2) Gare Lille Flandre, Gare Lille Europe,St Maurice,Mons Sarts,Mairie de Mons,Fort de Mons,les Prés,Jean Jaurès,Wasquehal Pavé de Lille 14 00:32 (M2 ) Porte des postes,port d'Arras,Port de Douai,Port de Valenciennes, Lille Grand palais,Mairie de Lille,Gare Lille Flandre, Gare Lille Europe,St Maurice,Mons Sarts,Mairie de Mons,Fort de Mons,les Prés,Jean Jaurès,Wasquehal Pavé de Lille 15 00:37 (M1) Porte des postes,Wazemmes,Gambetta,Republique,Rihour, (T2 10:32) Gare Lille Flandre, Gare Lille Europe,Romarin,Botanique,St Maur, Buisson,Brossolette, Clemenceau, (T1 10: 56) Croisé Laroche,Acacias,Pt de Wasquehal,La Terrasse,Wasquehal Pavé de Lille 29 00:45 (M1) Porte des postes,Wazemmes,gambetta,Republique,Rihour, Gare Lille Flandre, Coulier, Fives, Marbrerie, Hellemmes, Lezennes, (L41 10:38) Pont de bois,Stadium, Château,Chanterelle,Parc Urbain, Comices, courtilles,Cuisinerie,I.U.T.Crest, Peupliers,La Fontaine,Collège Molière, Cité Babylone, Luis Constant,(M2)Jean Jaurès, Wasquehal Pavé de Lille 45 00:57 (M2 10:22) Porte des postes,Montebello,Cormontaigne (L12 10:25) Cormontaigne, Leclerc,Colbert,Faculte catholique,Sacre coeur,Foch, De Gaulle,Théatre,(M2) Gare Lille Flandre, Gare Lille Europe,St Maurice, Mons Sarts,Mairie de Mons,Fort de Mons,les Prés,Jean Jaurès,Wasquehal Pavé de Lille 45 00:45 (M2 10:22) Porte des postes,Montebello,Cormontaigne (L12 10:25) Cormontaigne, Leclerc, Colbert,Faculte catholique,Sacre coeur,Foch, De Gaulle,Théatre, (M1)Gare Lille Flandre, Coulier, Fives, Marbrerie, Hellemmes, Lezennes, (L41 10:57) Pont de bois,Stadium, Château, Chanterelle,Parc Urbain,Comices, courtilles, Cuisinerie, I.U.T.Crest, Peupliers, La Fontaine,Collège Molière, Cité Babylone, Luis Constant, (M2)Jean Jaurès, Wasquehal Pavé de Lille 76 01:15 (M2 10:22) Porte des postes,Montebello,Cormontaigne (L12 10:25) Cormontaigne, Leclerc,Colbert,Faculte catholique,Sacre coeur,Foch, De Gaulle,Théatre, (T1 10: 35) Gare Lille Europe,Romarin, Botanique,St Maur,Buisson,Brossolette, Clemenceau, Croisé Laroche, Acacias,Pt de Wasquehal,La Terrasse, Wasquehal Pavé de Lille 59 01:07 Figure 2. Tableaux des résultats Avec une population de taille 30 individus par génération nous avons obtenu les résultats suivants pour 100 itérations. En notant P la probabilité de trouver une solution alternative dans la population finale en cas de perturbation. Les valeurs de cette probabilité sont calculées statistiquement. Apres plusieurs scénarios de perturbation de test nous avons trouvé les résultats reportés dans le tableau suivant. Nous avons effectué plusieurs tests d’optimisation en changeant le nombre de critères à optimiser. Par la suite, nous générons des perturbations aléatoires pour calculer les chances de trouver une solution alternative dans la population finale de l’algorithme d’optimisation. perturbation en mode C1 C2 C3 C2,C 1 C1,C 3 C2,C 3 C1,C2,C 3 sans Contrôle P 74 % 73 % 74 % 79% 81% 80% 83% avec Contrôle P 91 % 92 % 89 % 96% 95% 92% 97% Figure3 : Tableau des résultats (perturbation en mode) des deux approches (sans & avec) contrôle des opérateurs perturbation en mode 40% 50% 60% 70% 80% 90% 100% C 1 C 2 C 3 C 2 , C 1 C 1 , C 3 C 2 , C 3 C 1 , C 2 , C 3 critères probabilité P P Sans Contrôle P Avec Contrôle Figure 4 : Probabilité de trouver une solution dans la population finale en cas de perturbation en mode D’après l a figure précédente nous remarquons que les chances de trouver une solution alternative dans la population finale sont plus élevées si o n applique le contrôle des opérateurs. Dans le cas de perturbation en mode les résultats donnés par l’utilisation du contrôle des opérateurs sont toujours meilleurs même si le nombre de critère à optimiser varie. 8 Conclusion Nous avons commencé la réalisation d’un système interactif d’aide au déplacement multimodal. Au début de ce projet, nous avons étudié les problématiques d’un tel système (SIDAM). Les problèmes liés à l’information multimodale montrent la complexité et les difficultés de réalisation. Nous avons ensuite travaillé sur le module de calcul d’itinéraire. Notre solution repose sur une méthode multicritère permettant d’hybrider l’algorithme de Dijkstra et un algorithme génétique. Parmi nos perspectives pour les prochains travaux, nous étudierons la séparation entre la recherche d’itinéraires optimums dans le cas de fonctionnement normal du réseau et ceux des cas de perturbation. Références [1] A.Meskine, P.Gendre. Algorithmes et calculs d’optimisation d’itinéraires pour l’information multimodale ; implémentation d’un prototype pour les transports collectifs avec horaires.Novembre 2001. http://www.predim.org. [2] B.Fayech Chaar. Urban Bus Traffic Regulation By Evolutionary Algorithms. Proceedings of the 2001 IEEE Systems, Man, and Cybernetics conference. [3] B.S.Stewart et C.C.White. Multiobjective A*. Journal of the ACM, 38(4) : 775-814, 1991. [4] C.Petit-Rozé, A.Anli, E.Grislin-Le Strugeon, M.Abed, C.Kolski, G.Uster. AGENPERSO Interfaces home- Machine à base d’AGENts logiciels PERSOnnels d’information aux usagers des TC. 15èmè Francophone Conference for Interaction Homme Machine Université de Caen Campus 1. du 25 au 28 novembre 2003. [5] D.S.Johnson, C.R.Argon, L.A.Mcgeoch, C.Schevon. Optimization by simulated annealing : an experimental evaluation ; Part II, graph coloring and number partitioning. Operation Research 39(3): 378-406, 1991. [6] E.L.Ulungu and J.Teghem. The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. In Foundations of Computing and Decision Sciences, volume 20, pages 149-165. 1995. [7] El-g.Talbi. Métaheuristiques pour l’optimisation combinatoire multi-objectif : Etat de l’art. http://www.citeseer.nj.nec.com/382692.html [8]J.Dréo, A.Pétrowski, P.Siarry, E.Taillard. Métaheuristiques pour l’optimisation difficile. Edition EYROLLES pages 69-112, 2003. [9]J.Hao, P.Galinier, M.Habib. Méthaheuristiques pour l’optimisation combinatoire et l’affectation sous contraintes. Revue d’Intelligence Artificielle 1999. http://www.info.univ- angers.fr/pub/hao/papers/RIA.pdf [10]K.Zidi, S.Hammadi, CGOMFP Control Genetic Operators with Management of the Final Population to optimize a multimodal transport moving. IEEE SMC 2004 the Hague- de 10 au 13 October 2004. [11]K.Zidi, S.Hammadi, P.Borne. Méthode évolutionniste pour l’aide au déplacement dans le transport multimodal perturbé. 5e Conférence Francophone de MOdélisation et SIMulation“Modélisation et simulation pour l’analyse et l’optimisation des systèmes industriels et logistiques”MOSIM’04 – du 1er au 3 septembre 2004 - Nantes (France). [12]M.Visée, J.Teghem, M.Pirlot, and E.L.Ulungu. Two- phases method and branch and bound procedures to solve Knapsack problem. Journal of Global Optimization, 12: 139-155, 1998. [13]N.Lecomte, R.Patesson. Le panel des voyageurs : Une étude des activités et des besoins d’information des utilisateurs des transport s publics. In Actes de la conférence ERGO-IHM, D.L.Scapin et E.Vergison(eds) . pp. 129-135, Biarritz, France, 3-6 oct 2000. [14]P.lacomme, C.Prins, M.Sevaux. Algorithmes de graphes. Edition EYROLLES chapitre6175-214 2003. [15]R.L.Carraway, T.L.Morin and H.Moskowitz. Generalized dynamic programming for multicriteria optimization. European Journal of Operational Research, 44:95-104, 1990. [16]S.Sayin, S.Karabati. A bicriteria approach to the two- machine flow shop scheduling problem. European Journal of operational research, 113:435-449,1999. [17]T.Sen, M.E.Raiszadeh, et P.Dileepan . A branch and bound approach to the bicriterion scheduling problem involving total flowtime and range of lateness. Management Science, 34(2):254-260, 1988. [18]Uster.Guillaume. Information Multimodale voyageurs aspects Institutionnels et Juridiques. Centre de documentation de l'INRETS, Lille – Villeneuve d'Ascq code : LI-UTG0078. 2001. [19] Y. Collette et P. Siarry. Optimisation multiobjectif. Eyrolles, 2002.