Modèles basés sur les problèmes d’optimisation

Le choix des différents chemins d’évacuation pour les personnes est un aspect crucial lors d’une opération d’évacuation car il détermine sa réussite ou son échec. L’optimisation des opérations d’évacuation peut être vue selon deux approches, que nous détaillons dans les sections suivantes : soit cette optimisation est réalisée sur des modèles de flots, soit sur des modèles d’affectation du trafic. L’approche par flots est généralement utilisée pour les modèles macroscopiques. Pour les modèles microscopiques, l’approche utilisée est l’affectation du trafic. Parfois, cette dernière est utilisée pour les modèles macroscopiques. Modèles de flots Les premières modélisations sont basées sur des calculs de plus courts chemins. [Fahy, 1994] a proposé un algorithme de plus court chemin pour l’évacuation d’une tour. Ce genre d’algorithme a été utilisé par [Yamada, 1996] pour définir un plan d’évacuation d’une ville. Ce plan fait abstraction de la capacité d’accueil des centres de secours. [Yamada, 1996] a proposé également une autre modélisation plus efficace en utilisant les problèmes de flots statiques à coût minimum qui permettent de prendre en compte la capacité des centres de secours. La fonction objectif est la minimisation de la distance totale parcourue par tous les évacués pour rallier les centres de secours. Une variante du problème du plus court chemin, appelée problème du chemin le plus rapide (quickest path problem) a été également utilisée (voir [Chen and Chin, 1990], [Hung and Chen, 1991], [Kagaris et al., 1999]).

Son objectif est d’évacuer rapidement les personnes (des flots) à travers un seul chemin à partir d’un noeud source vers un noeud destination. Les flots de personnes sont envoyés à plusieurs reprises. Le nombre de flots envoyés est calculé à partir de la durée nécessaire pour traverser ce chemin et de sa capacité. Cette modélisation est couramment utilisée dans le cas de l’existence d’un seul chemin d’évacuation. Par exemple, l’évacuation par une seule sortie des spectateurs d’un concert ou un événement sportif. Malgré leur efficacité, les algorithmes de flots statiques ne sont pas applicables pour les problèmes d’évacuation tenant compte de l’aspect temporel. Par conséquent, il est pertinent de les modéliser par des problèmes de flots dynamiques (flots statiques dupliqués dans le temps). Les problèmes de flots dynamiques sont utilisés de manière extensive pour modéliser les problèmes d’évacuation d’une structure (des immeubles par exemple). Nous citons les travaux de [Chamlet et al., 1982], [Choi et al., 1988], [Kisko and Francis, 1985], [Dunn, 1992] et [Opasanon and Miller-Hooks, 2009]. Dans ce contexte, [Choi et al., 1988] ont proposé trois modélisations où ils ont montré que la capacité résiduelle d’arc, à chaque instant de temps, dépend des flots passés par cet arc.

Nous trouvons également un état de l’art détaillé sur la modélisation mathématique des problèmes d’évacuation de structures dans [Hamacher and Tjandra, 2001]. Dans cet état de l’art, ils ont extensivement étudié les modèles macroscopiques et d’une façon générale les modèles microscopiques. Tous ces modèles sont capables de refléter les flots d’évacuation des personnes au fil du temps. L’approche macroscopique peut optimiser le système indépendamment des comportements des évacués. L’approche microscopique, quant à elle, est capable de capturer et d’utiliser les comportements de chaque évacué. Pour l’approche macroscopique, le modèle de flots dynamiques à coût minimum permet d’estimer la durée moyenne d’évacuation par évacué. Les modèles de flots maximum (dynamiques) sont utilisés pour estimer le nombre maximal de personnes évacuées durant une période de temps. Les modèles du chemin le plus rapide permettent d’estimer la durée minimale nécessaire pour évacuer un nombre donné de personnes. L’approche microscopique est utilisée souvent pour simuler les plans d’évacuation. Les modèles les plus répandus sont les automates cellulaires. [Hamacher and Tjandra, 2001] stipulent que ces modélisations peuvent être appliquées dans le cas d’une évacuation à grande échelle. [Opasanon and Miller-Hooks, 2009] ont proposé un nouveau problème qui est une variante du problème du chemin de probabilité maximale (Maximum probability path).

Cette variante est appelée problème d’évacuation la plus sûre (the safest Escape problem, SEP). Ce problème permet de fournir un plan d’évacuation des personnes lors d’une évacuation d’un immeuble ou d’une zone urbaine. Son objectif est de déterminer un ensemble d’arcs et un nombre d’évacués qui peuvent être envoyés à travers chaque chemin, de sorte que la probabilité de succès de la personne la plus en danger soit maximale. Le réseau routier considéré est dynamique et varie au cours du temps. Les capacités des arcs sont recalculées au cours du temps, et les durées de traversées des arcs et les probabilités de succès sur chaque arc changent également au cours du temps. Ce réseau routier est modélisé par un graphe avec une seule source et une seule destination. [Opasanon and Miller-Hooks, 2009] ont proposé un algorithme optimal de complexité pseudo-polynomial. Cet algorithme a été testé sur des instances dont le réseau routier est inférieur à 500 noeuds. L’exemple suivant montre le principe de ce problème. Exemple 1 Nous considérons deux graphes du problème SEP. Nous supposons que nous voulons évacuer trois personnes du noeud 1 au noeud 4. Le chemin qui a une probabilité minimale de succès est coloré en bleu. La solution optimale du graphe de la figure (b) est optimale pour le problème SEP (deux personnes traversent le chemin 1-2-4 et une personne traverse le chemin 1-3-4), car la probabilité de succès associée au chemin 1-2-4 dans la figure (b) est supérieure à la probabilité minimale du chemin 1-3-4 du graphe (a) qui est égale à 0,08.

Systèmes d’aide à la décision Le premier système d’aide à la décision est TEVACS. Il a été développé par [Han and Yuan, 2005]. Ce logiciel a été utilisé pour évaluer plusieurs scénarios d’évacuation. Pour un plan d’évacuation donné, le logiciel donne la date de fin d’évacuation. L’utilisateur peut voir dynamiquement sur un graphique le taux de congestion du réseau routier sur des intervalles de temps. [Tufekci and Kisko, 1991] ont développé un outil d’aide à la décision régional en-ligne (REMS). Cet outil est capable de tester plusieurs scénarios d’évacuation après un ouragan, un déversement chimique ou un accident radiologique. Le logiciel a la capacité de visualiser le processus d’évacuation dans le temps et d’afficher les flux de circulation sur les voies du réseau de transport. [Hobeika et al., 1994] et[Hobeika, 2002] ont développé un outil d’aide à la décision du réseau de transport (TEDSS). Il est utilisé dans les cas d’évacuation due à une catastrophe nucléaire (i.e. évacuation des personnes autour des centrales nucléaires).

Ce support d’aide à la décision tient compte des conditions météorologiques. Le logiciel de simulation utilisé par TEDSS est MASSVAC qui est un logiciel de simulation en temps réel. Les sorties de ce système sont : la date de fin de l’évacuation, l’affectation des routes aux évacués et la congestion éventuelle du réseau de transport. Ce système offre la possibilité aux décideurs de choisir les règles d’affectation intégrées pour obtenir la meilleure stratégie d’évacuation. TEDSS a été mis à jour en 2002 après la mise à jour de MASSVAC en 1998. [Pidd et al., 1996] ont développé un logiciel qui est une combinaison entre un simulateur et un système d’information géographique, nommé (CEMPS). CEMPS permet aux utilisateurs de spécifier les incidents, les choix de route et les conditions météorologiques. Le logiciel de simulation utilisé pour CEMPS ne permet que l’affectation statique du trafic. [Franzese and Han, 2001] ont développé un système d’aide à la décision dans le cas d’évacuation des personnes après un ouragan. L’évacuation est faite en deux phases. La première consiste à fixer le périmètre de la zone impactée puis à estimer la population de cette zone et décider du nombre de personnes qui seront effectivement évacuées. Pour cela, une analyse est faite sur les comportements des personnes. La deuxième phase est l’évaluation de l’efficacité d’évacuation par le simulateur de ce système qui utilise les sorties de la première phase.

Problèmes d’évacuation par bus et par voiture avec réseau routier réel Le problème présenté dans la section 2.2.1 est restrictif : le réseau routier est approximatif et l’évacuation se fait uniquement par bus. Nous y supposons également que tous les évacués sont disponibles aux points de rassemblement dès le début de l’évacuation. Dans la deuxième partie de cette thèse, nous considérons un problème d’évacuation général. Le calcul des plans d’évacuation se fait sur un réseau routier réel, ce qui rend le problème significativement plus difficile à traiter. Sur chaque arc de ce réseau routier, nous avons les données suivantes : la durée de passage par cet arc, la capacité maximale de cet arc, et une valeur de risque associée au risque d’effondrement des bâtiments sur cet arc. Nous considérons deux types de flots : les flots de bus pour les personnes arrivant à pied aux points de rassemblement et les flots de voitures pour les personnes utilisant leurs propres voitures pour quitter la zone endommagée. Il est supposé que les conducteurs de voitures partent aux points de rassemblements afin de récupérer un plan d’évacuation. De plus, les décideurs ont la prérogative de choisir le nombre de centres à ouvrir. L’objectif de ce problème est de choisir les centres de secours à ouvrir afin de minimiser la date de fin d’évacuation et la somme des risques encourus durant l’opération d’évacuation. Dans la littérature, nous distinguons deux types de problèmes d’évacuation traitant simultanément la localisation et le routage.

Dans le premier type, nous citons les travaux de [Sherali et al., 1991], [Coutinho-Rodrigues et al., 2012], [Bish, 2011], [Goerigk et al., 2013], qui supposent que les autorités ont le pouvoir total de choisir les centres de secours ainsi que les chemins à emprunter par les évacués pour atteindre un centre de secours. Cette hypothèse sera supposée tout au long de cette thèse. Dans le deuxième type de travaux ([Kongsomsaksakul et al., 2005]), les autorités ont uniquement la capacité de choisir les localisations des centres. Les centres de secours et les chemins vers ces centres sont choisis par les évacués. Certes cette deuxième approche peut paraitre réaliste mais n’est pas applicable dans le cas d’un désastre où les évacués n’ont pas forcément une connaissance totale de l’état du réseau routier. Dans ces deux types de problème, les flots d’évacués sont soit les piétons, les bus, ou les voitures. Une étude qui gère l’évacuation à commodités multiples (les bus et les voitures) a été proposée par [Bretschneider, 2012]. [Bretschneider, 2012] aborde uniquement le problème de routage des voitures et des bus. De plus, la capacité de chaque centre est considérée suffisamment grande pour accueillir toute la population à évacuer. Le but de son étude est de minimiser une combinaison linéaire de deux critères. Le premier critère est le nombre de lignes d’urgence utilisées par les bus durant l’évacuation. Tandis que le deuxième critère est le nombre de flots arrivés à chaque centre de secours.