Régulation Spatio-Temporelle d’un Réseau de Transport Multimodal

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

Résumé

Régulation Spatio-Temporelle d’un Réseau de Transport Multimodal

Métriques

8
4
207.4 Ko
 application/pdf
bitcache://c678ee7d4e14945bd4687ee7bad32dc42fdb8cff

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-2/20015</identifier><creators><creator><creatorName>Slim Hammadi</creatorName></creator><creator><creatorName>Besma Fayech Chaar</creatorName></creator></creators><titles>
            <title>Régulation Spatio-Temporelle d’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">c678ee7d4e14945bd4687ee7bad32dc42fdb8cff</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34030</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Résumé— Il s’agit dans cet article d’une nouvelle vision à l’égard de la régulation du trafic dans un réseau de transport multimodal. En effet, nous considérons la régulation comme une réaffectation des horaires et itinéraires aux véhicules concernés par la perturbation à traiter. Nous proposons ainsi une approche évolutionniste de la régulation spatio-temporelle qui s’appuie sur une étude de la flexibilité des déplacements des véhicules, afin de proposer des nouveaux horaires de passage et éventuellement des nouveaux itinéraires. Cette approche nécessite ainsi des techniques de recherche de chemins hamiltoniens afin d’assurer la faisabilité des itinéraires alloués. Mots clés— Réaffectation horaires et itinéraires, algorithmes évolutionnistes, graphes, recherche chemin hamiltonien. I. INTRODUCTION Afin de pallier à certains incidents qui affectent sérieusement le trafic au sein d’un réseau de transport collectif multimodal, d’éventuelles modifications des itinéraires de certains véhicules peuvent s’avérer nécessaires. Par exemple, dans le cas d’une panne de métro, certains bus sont souvent détournés de leurs parcours initiaux afin de desservir les arrêts du métro et assurer le service, surtout en absence de véhicules de réserve. Nous procédons par conséquent à une reconfiguration partielle du réseau initial. Ce processus est en fait réalisé par une approche évolutionniste de régulation qui contient une étape de « rerouting » qu’on appellera reconfiguration [1] [2]. Par rapport aux outils existants de la régulation, l’approche présente ne concerne pas seulement les horaires mais aussi les itinéraires. Il s’agit d’une approche plus générale qui englobe la plupart des décisions possibles à travers une reconfiguration partielle du réseau. L’étendue de la reconfiguration sur l’horizon étudié dépend de l’incident et de la flexibilité des déplacements des véhicules. La régulation temporelle n’est en fait qu’un cas particulier de la présente approche dans un réseau à flexibilité nulle [1]. Nous avons jugé nécessaire de caractériser d’abord la problématique de la régulation d’un réseau multimodal avant de décrire l’approche proposée. Nous expliquons dans ce but le contexte de l’approche tout en présentant brièvement le modèle graphique utilisé. Nous proposons aussi les variables de décisions concernées et une étude de la flexibilité du réseau. Lors de la description de l’approche de la régulation spatio-temporelle, nous présentons le codage, les différentes étapes de l’algorithme correspondant et les opérateurs de reproduction utilisés. Nous exposons aussi l’Algorithme de Recherche d’Itinéraires, ARI, en spécifiant les techniques adoptées d’extension et de transformation. La dernière partie est consacrée aux applications de la présente approche. II. CARACTERISATION DE LA REGULATION D’UN RESEAU MULTIMODAL A. Contexte Afin de présenter une modélisation des réseaux de transport multimodal qui est adéquate à la problématique qui nous concerne, il est nécessaire de revenir à la définition même de la régulation. Nous pouvons en fait définir cette dernière comme un processus qui fonctionne en temps réel afin de contrôler le trafic au sein d’un réseau de transport multimodal et satisfaire au mieux la demande en appliquant des décisions qui concernent principalement les horaires et les itinéraires des véhicules. Nous décelons à partir de cette définition cinq principaux paramètres à considérer dans la construction d’un modèle pour la régulation des systèmes de transport multimodal : la multimodalité, la surveillance (détection des perturbations et diagnostic), la demande, les horaires et les itinéraires. En ce qui concerne la surveillance du trafic en temps réel, qui constitue une tâche indispensable de la régulation, nous avons conçu un Système Multi-Agent d’Aide à la Décision, SMAAD, qui comporte un module de supervision composé d’agents VEHICULE et d’agents ARRET et un module de régulation composé d’agents INCIDENT, ZONEPERT et ZONEREG [2]. Ces deux modules coopèrent afin de prévenir, détecter, diagnostiquer et réguler les perturbations. En outre, deux cas de situations perturbées peuvent se présenter : les situations familières et les situations non familières [3]. Les décisions sont fournies par les agents ZONEPERT en cas de situations familières à travers une base de règles et en cas de situations non familières, ce sont les agents ZONEREG qui proposent des solutions à travers l’approche évolutionniste de la régulation qui fait le sujet de cet article. Par ailleurs, afin de représenter tous les paramètres cités ci- dessus, nous avons conçu une modélisation hybride basée sur les graphes pour la représentation des itinéraires et sur les agents pour la représentation spatiale et temporelle du réseau. Notons GR le graphe associé aux différents déplacements dans le réseau. Les nœuds représentent les arrêts et les arêtes représentent les déplacements directs des véhicules. Il est en outre nécessaire de spécifier un horizon spatio-temporel afin de limiter l’étendu des décisions de régulation. Les perturbations évoluant selon un axe temporel et un axe spatial, cet horizon est en fait composé d’un ensemble de véhicules, VH , pour la configuration temporelle du réseau et d’un ensemble de stations, SH , pour la configuration spatiale [1][2]. Notons GR•H le graphe de déplacement associé à cet horizon. BESMA FAYECH CHAAR1 , SLIM HAMMADI2 1 Institut National des Sciences Appliquées et Technologies, INSAT, Département Informatique et Math., Centre Urbain Nord, BP 676, 1080, Tunis, Tunisie 2 Laboratoire d’Automatique et d’Informatique industrielle de Lille Ecole Centrale de Lille, BP 48, 59651, Villeneuve d’Ascq Cedex, France Régulation Spatio-Temporelle d’un Réseau de Transport Multimodal d 1 2 3 6 7 f 4 5 8 9 B. Variables de décision La régulation spatio-temporelle consiste en une réaffectation des horaires et itinéraires aux véhicules. Autrement dit, il est nécessaire de résoudre le problème d’affectation des arêtes et des nœuds du graphe de déplacement GR•H afin de fixer les nouveaux itinéraires des véhicules. En prenant l i V comme le i-ème véhicule de la ligne l et m j S comme la j-ème station de la ligne m, le but de l’approche évolutionniste de la régulation spatio-temporelle est alors de chercher pour les différents véhicules et arrêts de VH et SH : - les variables binaires de passage, lm ij a , pour l’affectation des nœuds associés aux arrêts m j S aux véhicules l i V (égaux à 1 en cas de passage et à 0 sinon) ; - les variables de destination, lmr ijk x , pour l’affectation des arêtes associées aux déplacements directs des véhicules l i V de l’arrêt m j S à l’arrêt r k S (cette variable est égale à 1 quand ce déplacement a lieu et à 0 sinon); - les décisions de modification des durées des arrêts, lm ij ε , pour l’affectation des horaires de passage des véhicules l i V aux stations m j S (cette variable a une valeur entière comprise dans un intervalle prédéfini et représente l’augmentation ou la diminution de la durée d’arrêt prévu à chaque station). C. Flexibilité du réseau Selon l’horizon étudié, la nature du véhicule et de la perturbation, les véhicules peuvent être autorisés ou non à passer par certaines stations. Ils peuvent aussi être autorisés ou non à changer leurs itinéraires initiaux en annulant ou pas leurs passages aux arrêts habituels. Nous illustrons la possibilité de passage de l i V à la station m j S de SH par le paramètre a( l i V , m j S ) [1]. Ce paramètre est égal à : 1 si m j S fait partie de l’itinéraire initial de l i V , 0,5 si l i V peut passer par m j S et 0 si l i V ne peut pas passer par m j S . Le paramètre de flexibilité, u( l i V , m j S ), concerne l’annulation du passage de l i V par m j S . Il est égal à : - 0 quand l i V doit absolument passer par m j S ; - 1 quand l i V peut ne pas passer, comme prévu, par m j S . Ces deux paramètres permettent, dans certains cas, de fixer les variables de passage. Il est évident que si a( l i V , m j S )=0 alors lm ij a =0. En effet, si le véhicule ne peut jamais passer par cette station, alors il est impossible d’insérer cette dernière dans son itinéraire. Aussi, si a( l i V , m j S )=1 et u( l i V , m j S )=0, alors lm ij a =1. Autrement dit, si le véhicule n’est pas autorisé à sauter cet arrêt, la variable de passage correspondante doit être égale à 1 dans toutes les solutions. Dans les autres cas, le véhicule peut passer ou pas par la station concernée, d’où le symbole (*) signifiant 0 ou 1 et aussi traduisant des arrêts à passage flexible. Nous présentons dans le tableau suivant un exemple de paramètres relatifs au graphe de déplacement d’un véhicule l i V , G( l i V ). Nous y illustrons a( l i V , m j S ) et u( l i V , m j S ) pour tout arrêt m j S de SH . Tab.1, Exemple de paramètres de passage et de flexibilité. Arrêt d f 1 2 3 4 5 6 7 8 9 10 … 14 a 1 1 1 1 1 1 1 0,5 1 0,5 0,5 0 0 0 u 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Nous décelons alors à travers ces paramètres les nœuds où les passages sont flexibles. Nous pouvons construire un schéma d’affectation des nœuds traduisant l’ensemble des possibilités de passage de l i V , à travers les variables lm ij a pour tout arrêt m j S de SH . Toute solution générée doit être conforme à ce schéma (tab.2). Tab.2, Schéma d’affectation des arrêts au véhicule l i V . Arrêt d f 1 2 3 4 5 6 7 8 9 10 … 14 lm ij a 1 1 1 1 1 * * * 1 * * 0 0 0 Nous proposons de considérer ce schéma d’affectation dans le graphe de déplacement G( l i V ). En effet, nous illustrons, ci- dessous, les nœuds à passage flexible par des cercles pointillés afin de les distinguer des nœuds à passage ferme. Le problème qui se pose maintenant réside dans le choix de l’itinéraire affecté à l i V selon le schéma d’affectation qui lui correspond. Notons que tout itinéraire doit absolument comporter les arrêts d1 , 1, 2, 3, 7 et f. Nous appelons S* ( l i V ) l’ensemble des arrêts par lesquels l i V doit absolument passer. Fig.1, Considération du schéma d’affectation des nœuds dans G( l i V ). III. APPROCHE EVOLUTIONNISTE DE REGULATION SPATIO- TEMPORELLE A. Codage Le codage des nœuds et des horaires, CNH, propose les stations par lesquelles chaque véhicule doit passer, ainsi que les modifications des durées d’arrêts associées. Pour un véhicule r k V et une station m j S , il s’agit de fixer le couple 1 d et f représentent les extrémités fixées de chaque itinéraire recherché du véhicule. Initialisation Test Arrêt Oui Non Sélection Croisement et mutation CNH Recherche Itinéraires Evaluation Comparaison Résultats ( rm kj a , rm kj ε ) représentant respectivement la variable de passage (0 ou 1) et la modification du temps d’arrêt (en nombre de minutes). La figure suivante présente un exemple de ce codage pour des graphes de déplacements semblables illustrés par fig.1. Par ailleurs, ces décisions ne résolvent pas le problème de l’affectation des arêtes des graphes de déplacement afin de fixer les itinéraires des véhicules. La recherche de l’itinéraire adéquat à chaque ensemble de nœuds choisis est effectuée dans une autre étape de l’algorithme évolutionniste. Notons ainsi Ci le vecteur des itinéraires ou chemins affectés aux véhicules de VH , pour tout individu i dans la population courante. Pour tout r k V de VH , Ci( r k V ) est le chemin correspondant à r k V pour l’individu i. Par exemple, Ci( r k V ) = (d,1,2,3,6,7,f), selon le graphe de déplacement de fig.1. S d 1 2 3 4 5 6 7 8 9 f l V0 1,0 1,1 1,1 1,3 0,0 1,0 0,0 1,0 1,2 0,0 1,0 l V1 1,0 1,0 1,3 1,0 1,1 1,1 0,0 1,1 0,0 1,2 1,0 …. …. …. …. …. …. …. …. …. …. …. …. l i V 1,0 1,1 1,2 1,1 0,0 0,0 1,3 1,1 0,0 0,0 1,0 l i V 1 + 1,0 1,1 1,1 1,2 0,0 1,1 1,0 1,0 0,0 0,0 1,0 Fig.2, Codage des nœuds et des horaires (CNH). B. Algorithme global L’algorithme de régulation spatio-temporelle commence par une étape d’initialisation dans laquelle il y a la construction de la population initiale P. Cette dernière peut être formée, le cas échéant, à partir des décisions primaires recommandées par les agents ZONEPERT après le diagnostic et avec des mesures de duplication. Faute de solutions primaires, l’agent ZONEREG en effectue aléatoirement la genèse. Dans la même étape, les individus de la population initiale sont évalués pour commencer directement la sélection dans l’étape suivante. Cette sélection conduit à une population intermédiaire, P* , formée des meilleurs individus. Nous utilisons dans notre approche une version avancée de la sélection par la roulette de Goldberg. En effet, cette dernière souffre de l’inconvénient lié à une large différence entre le nombre réel et le nombre prévu de copies réalisées pour un individu. Pour remédier à ce problème, l’opérateur stochastique de sélection par les restes sans remplacement a été développé [4] [5]. L’avantage de cet opérateur de sélection réside dans la chance qui est attribuée aux moins bons individus d’être sélectionnés, ce qui procure une meilleure diversité dans la population intermédiaire [1]. Après la sélection, les individus de P* subissent des croisements et des mutations avec des probabilités de pcrois et pmut, pour former une nouvelle population P. L’étape de l’évaluation est ensuite réalisée pour calculer les coûts des individus. Dans ce but, il est nécessaire de calculer, pour chaque solution, les horaires régulés et l’impact des décisions sur la charge des véhicules (nombre de personnes montant et descendant). Une phase de recherche des itinéraires est ensuite nécessaire afin de construire les chemins faisables affectés à chaque véhicule dans chaque solution ou individu. Cette phase sera détaillée plus tard. L’étape de l’évaluation a pour but de calculer pour chaque individu sa fonction coût en fonction des critères choisis et relatifs à la situation perturbée et aux objectifs de la régulation. Afin d’améliorer la convergence de l’algorithme, nous avons choisi d’imposer une étape de comparaison partielle entre les individus parents et les enfants, pour en garder les meilleurs. Par exemple, si parent 1 et parent 2, de la population P* , ont subi un croisement pour générer enfant 1 et enfant 2 dans P. Si le coût de parent 1 est meilleur que celui de enfant 1, parent 1 remplace enfant 1 dans P. De même, nous effectuons une comparaison entre parent 2 et enfant 2. Puisque c’est une comparaison partielle, nous ne prenons effectivement pas les deux meilleurs des quatre individus pour ne pas risquer de perdre la diversité des solutions. Aussi, nous prenons le meilleur parmi l’individu et sa réplique mutée. Le processus de comparaison partielle sert alors à contrôler l’évolution des individus tout en respectant la diversité des populations. La dernière étape consiste en un test de la condition d’arrêt. Cette condition est pour l’instant liée au nombre de générations de l’algorithme. Elle peut cependant être liée à la limite de la durée d’exécution de l’algorithme fixée selon l’urgence de la régulation. Toutefois, l’algorithme peut être interrompu si l’agent ZONEREG reçoit un ordre de l’agent INCIDENT à ce propos. Dans ce cas, les meilleures solutions atteintes sont fournies à l’agent INCIDENT. Si le test n’aboutit pas, l’algorithme reprend, pour la génération suivante, à partir de l’étape de sélection. Fig.3, Approche évolutionniste de la régulation spatio-temporelle. C. Fonction d’évaluation L’évaluation des solutions est basée sur trois critères de régulation liés à la régularité (considération des intervalles de passage entre les véhicules), la correspondance (durée des transfert entre les lignes) et la ponctualité (respect des horaires de passage) [1][2]. Ces critères à maximiser sont issus d’une comparaison entre l’état perturbée du réseau sans mesures de régulation et une simulation de l’état régulé selon les décisions proposées. Notés f1, f2 et f3, ils représentent respectivement : - l’amélioration apportée par les décisions sur la durée d’attente des passagers dans les stations de SH (durée pondérée par le nombre de clients en attente); - l’amélioration apportée par les décisions sur la durée totale des correspondances aux nœuds de SH (pondérée par le nombre des passagers en transfert) ; - l’amélioration apportée par les solutions de régulation sur la durée totale des trajets à bord des véhicules (pondérée par les charges des véhicules). L’optimisation qui constitue l’objet de l’approche évolutionniste de la régulation devient ainsi multicritère, ce qui induit une complexité additionnelle au problème. En effet, il est nécessaire de concilier les trois critères qui peuvent être contradictoires. Par exemple, en tenant compte du critère de régularité, l’algorithme tend à équilibrer les intervalles entre les passages des véhicules, ce qui nécessite des décisions de retardement. Ainsi, les parcours des véhicules seront rallongés, ce qui défavorise le critère de ponctualité. La fonction coût, f, est ainsi calculée à partir d’une agrégation des trois critères de régulation avec différents poids traduisant leur importance relative et tenant compte de leur ordre de grandeur : ∑ = = 3 1 c c c f f α . D. Opérateurs génétiques 1) Opérateur de croisement Nous proposons un croisement à deux-points sur les colonnes qui ne conserve pas les itinéraires, auquel cas l’utilisation d’un ARI est nécessaire. Toutefois, le respect des schémas d’affectation est toujours assuré par cet opérateur. Deux points de croisement sont choisis au hasard, l’échange concerne les colonnes qui se trouvent entre ces deux points. La figure ci-dessous illustre le fonctionnement de ce croisement. Supposons que les solutions sont complètes. Des itinéraires sont alors déjà affectés aux 4 véhicules concernés. Par exemple, pour le parent 1, l’itinéraire (d, 1, 3, 2, 5, 8, 7, f) est affecté au véhicule 0. La zone qui subit l’échange est composée par les décisions sur les arrêts 4, 5, 6, 7. Les zones externes du parent 1 (respectivement 2) sont transmises à l’enfant 1 (respectivement 2) et la zone interne du parent 2 (respectivement 1) est copiée dans celle de l’enfant 1 (respectivement 2). Cet échange a modifié les décisions de passage et par conséquent les itinéraires. Les enfants doivent ensuite subir un ARI pour que les solutions qui leur correspondent puissent fixer toutes les variables de décision. Par exemple, dans enfant 1, pour le véhicule 0, il s’agit de trouver un chemin qui relie d à f et qui passe par 1, 2, 3, 5 et 7. Avant croisement Parent 1 d 1 2 3 4 5 6 7 8 9 f 0 1,0 1,1 1,1 1,3 0,0 1,0 0,0 1,0 1,2 0,0 1,0 1 1,0 1,0 1,3 1,0 1,1 1,1 0,0 1,1 0,0 1,2 1,0 2 1,0 1,1 1,2 1,1 0,0 0,0 1,3 1,1 0,0 0,0 1,0 3 1,0 1,1 1,1 1,2 0,0 1,1 1,0 1,0 0,0 0,0 1,0 Parent 2 d 1 2 3 4 5 6 7 8 9 f 0 1,0 1,2 1,0 1,2 1,0 0,0 0,0 1,0 0,0 0,0 1,0 1 1,0 1,3 1,1 1,2 0,0 0,0 0,0 1,2 0,0 0,0 1,0 2 1,0 1,0 1,0 1,3 1,2 1,0 0,0 1,1 1,1 0,0 1,0 3 1,0 1,2 1,2 1,0 1,2 0,0 1,0 1,1 0,0 1,1 1,0 Après croisement Enfant 1 d 1 2 3 4 5 6 7 8 9 f 0 1,0 1,1 1,1 1,3 1,0 0,0 0,0 1,0 1,2 0,0 1,0 1 1,0 1,0 1,3 1,0 0,0 0,0 0,0 1,2 0,0 1,2 1,0 2 1,0 1,1 1,2 1,1 1,2 1,0 0,0 1,1 0,0 0,0 1,0 3 1,0 1,1 1,1 1,2 1,2 0,0 1,0 1,1 0,0 0,0 1,0 Enfant 2 d 1 2 3 4 5 6 7 8 9 f 0 1,0 1,2 1,0 1,2 0,0 1,0 0,0 1,0 0,0 0,0 1,0 1 1,0 1,3 1,1 1,2 1,1 1,1 0,0 1,1 0,0 0,0 1,0 2 1,0 1,0 1,0 1,3 0,0 0,0 1,3 1,1 1,1 0,0 1,0 3 1,0 1,2 1,2 1,0 0,0 1,1 1,0 1,0 0,0 1,1 1,0 Fig.4, Exemple ce croisement à deux-points sur les colonnes. 2) Opérateur de mutation La mutation des individus correspond à des changements aléatoires des variables de passage et de modification des temps d’arrêt. Cependant, ces changements doivent respecter les schémas d’affectation des véhicules. La mutation n’a pas à se soucier des itinéraires ou des arêtes entre les nœuds puisque les individus subissent l’ARI dans l’étape qui suit. L’algorithme de mutation est présenté par la figure ci-dessous. Fig.5, Algorithme de mutation. IV. ALGORITHME DE RECHERCHE D’ITINERAIRE, ARI A. Objectif Le problème de réaffectation des arrêts étant déjà résolu, l’objectif du ARI est de trouver pour un ensemble de nœuds donné, un chemin qui lie les extrémités fixes de l’itinéraire recherché et qui passe une seule fois par chaque nœud. Il s’agit en fait d’un problème de recherche d’un chemin hamiltonien qui est NP-Complet [6]. Dans chaque solution, les arrêts à desservir par chaque véhicule sont fixés conformément aux schémas d’affectation. Nous pouvons alors construire pour l i V le graphe extrait de G( l i V ) adapté à ce nouvel ensemble d’arrêts qui lui est affecté. Nous appelons ce nouveau graphe de déplacement G’( l i V ). Nous savons que les opérateurs de reproduction proposés conservent les nœuds à passage non flexible. Par conséquent, l’ensemble S* ( l i V ) doit être représenté dans G’( l i V ). Par rapport aux Problèmes du Voyageur de Commerce (PVC), la difficulté qui s’ajoute à la résolution de notre problème de recherche d’itinéraire réside dans les extrémités fixées des chemins. Le choix du début d’un chemin est réduit et les itinéraires faisables doivent finir dans un même nœud. Choisir le nombre de mutations dans l’individu et leurs positions ; Pour chaque position de mutation ( r k V , m j S ) Si m j S ∉ S* ( r k V ), alors Si rm kj a =0, alors la mettre à 1 et changer rm kj ε ; Sinon, la mettre à 0 et mettre rm kj ε à 0. Sinon, changer rm kj ε . Fin pour. d 1 2 3 6 7 f ’ 4 5 8 9 f Afin de nous assurer du respect des extrémités dans chaque chemin hamiltonien, nous proposons d’utiliser la propriété qui stipule que si un nœud a un degré 1, alors il doit forcément être l’une des extrémités du chemin hamiltonien recherché. En effet, puisque tout nœud de degré égal à 1 doit correspondre à une extrémité d’un chemin hamiltonien éventuel, nous imposons ce degré aux nœuds de début et de fin dans les graphes. De ce fait, nous sommes amenés à ajouter des nœuds fictifs pour respecter cette condition. Ces nœuds fictifs ajoutés doivent alors être à passage non flexible dans le schéma d’affectation. Par exemple, dans la figure suivante, nous avons ajouté le nœud f’ entre f et les nœuds qui sont liés à ce dernier. Le nœud f a finalement un degré de 1 et l’arête (f’,f) doit faire partie de tout chemin hamiltonien possible. Fig.6, Respect des extrémités dans la recherche d’un chemin hamiltonien. B. Algorithme Nous utilisons dans ce qui suit le terme degré courant d’un nœud x, afin de désigner, au cours de l’extension d’un chemin, le nombre d’arêtes incidentes décrémenté du nombre des nœuds qui sont voisins de x et qui sont inclus dans le chemin. Autrement dit, le degré courant de x est le nombre d’arêtes actives dans le graphe (incidentes liées à des nœuds non inclus dans le chemin). En s’appuyant sur différentes propriétés liées aux chemins hamiltoniens afin de parcourir efficacement les différents chemins possibles, les algorithmes heuristiques de recherche des chemins ou cycles hamiltoniens ont la même structure générale. L’algorithme que nous proposons s’appuie sur une technique d’extension de la longueur d’un chemin partiel jusqu’à ce qu’un chemin hamiltonien soit atteint. Le nœud ajouté à un chemin est choisi selon son degré courant. Afin d’avoir un chemin de longueur maximale, il faut éviter de s’arrêter très tôt à un nœud qui ne possède plus d’arêtes actives. Pour remédier à ce problème, nous proposons de choisir à chaque fois le nœud qui a le minimum d’arêtes actives. Cette technique a été utilisée dans la recombinaison génétique des arêtes dans l’extension d’un chemin hamiltonien pour le PVC [7] [8]. Elle permet de diminuer les chances d’être bloqué dans un nœud sans issue. Cependant, cette technique ne peut malheureusement pas assurer l’arrivée à un chemin hamiltonien, puisque le risque de tomber sur un nœud, avec un degré courant nul, existe toujours. En effet, la recherche s’arrête lorsqu’elle a traité tout le voisinage du nœud extrême en-cours en tant qu’extrêmes. Il est ainsi nécessaire d’utiliser une technique de transformation pour changer le nœud final du chemin courant. Nous avons choisi la transformation rotationnelle. Le concept de transformation rotationnelle est illustré par la figure suivante. Pour un graphe G et un chemin C = (x1, x2,…, xk) dans G. S’il y a une arête (xj, xk), 1