Abstract (FR)

Étant donné un graphe G= (V, E) orienté, on appelle distance la longueur d’un plus court chemin entre 2 sommets de V. Le problème du p-Centre, noté pCP, consiste à trouver un sous-ensemble de sommets C⊆V,|C|=p, qui minimise la distance maximum entre un sommet v∈V et un sommet dans C [2]. Dans le cadre du projet GEO-SAFE - projet Horizon 2020 entre l’UE et l’Australie - sur la gestion des feux de forêts, nous nous intéressons à une variante non-déterministe du pCP. Dans ce contexte là, les centres sont associés à des refuges que nous voulons localiser dans une région "sauvage" peu densément peuplée (qui correspondrait au "bush" australien). Dans notre modèle, le graphe G représente un terrain, chaque noeud représente une région de ce terrain et un arc relie deux régions si le passage de l’une à l’autre est possible. Un feu peut démarrer sur une région et s’étendre sur une zone d’impact d’une ou plusieurs régions. On apelle scénario la description d’une situation future causée par un départ de feu. Des scénarios de feu réalistes peuvent impliquer des zones d’impact très larges et dynamiques dans le temps. Nous nous intéressons dans notre travail à la courte période suivant le départ du feu, dans l’idée que cette période correspond au temps requis, pour les personnes en danger, à se mettre à l’abri dans un refuge, où elles seront considérées hors de tout danger. Ce choix justifie de considérer des zones d’impact peu étendues, restreintes dans notre cas à un sommet. Nous définissons donc n scenarios possibles. Dans le scenario sj , 1 ≤ j ≤ n, le sommet vj devient non opérationnel, ce qui revient à considérer uniquement le sous-graphe Gj , issu du graphe G auquel on retire les arcs entrant en vj . Uniquement un sommet à la fois peut devenir non opérationnel. Notre problème est alors une version du problème de localisation-affectation avec incertitude. Une solution décrit non seulement la localisation des centres C, mais affecte aussi automatiquement pour chaque scénario et pour chaque noeud, un centre à atteindre pour les individus sur ce noeud (processus d’évacuation). La localisation des centres peut s’effectuer durant la phase préparatoire et peut alors demander des calculs chronophages pour la prise de cette décision. L’affectation a par contre lieu durant la phase de réponse d’urgence, et ne permet pas de processus chronophage. En effet, même si les plans d’évacuation peuvent être préparés en avance, ils doivent rester simples et faciles à suivre pour des personnes peu entraînées à ce genre de situations. C’est pourquoi nous considérons la stratégie de modification des chemins d’évacuation suivante : à partir d’un sommet donné, les individus cherchent à rejoindre le refuge accessible le plus proche, sans devoir traverser la zone d’impact du feu. Ces contraintes seront clarifiées dans la mesure où, pour un scénario sj , le chemin d’évacuation d’un sommet v dans Gj peut être similaire, ou non, au plus court chemin de v vers C dans G. Par ailleurs, pour le scénario sj , le chemin d’évacuation à partir du sommet vj est construit sur l’hypothèse que les individus à proximité du départ du feu fuient dans un premier temps dans la mauvaise direction. Notre modélisation permet de prendre en compte de façon réaliste les caractéristiques de notre problème, en particulier d’appréhender la réaction des individus en danger (via des stratégie de modification) face aux impacts d’un feu de forêt localisé (via des scénarios). Lorsque la probabilité de réalisation d’un scénario est connue, nous sommes dans le cas probabiliste, autrement nous sommes dans le cas robuste. Ces hypothèses induisent de nouveaux problèmes dans la mesure où, dans les versions stochastiques et robustes du pCP existantes, l’inconnu est davantage basé sur des valeurs (temps de parcours d’une arête, poids d’un sommet, capacité d’un centre..) que sur la structure même du graphe opérationnel. Dans le cas probabiliste, chaque scénario sj dispose d’une probabilité pj d’advenir. Notre modèle répond alors au paradigme de l’Optimisation Combinatoire Probabiliste [5] qui intègre la stratégie de modification dans la définition du problème. Nous définissons donc le Problème du p-Centre Probabiliste - noté PpCP - comme le problème de trouver un ensemble de sommets C de taille p qui minimise la moyenne, sur tous les scénarios, des longueurs maximales des chemins d’évacuations. Dans le cas robuste (RpCP), la probabilité des scénarios n’est pas connue. Notre modèle correspond alors à un problème robuste avec recours [4]. Nous définissons donc le Problème du p-Centre Robuste - noté RpCP - comme le problème de trouver un ensemble de sommets C de taille p qui minimise le maximum, sur tous les scénarios, de la longueur maximale des chemins d’évacuations. Dans ce travail nous proposons des formulations PLNE du PpCP et du RpCP, inspirées de travaux sur le pCP [1] [3], et présentons de premiers résultats expérimentaux.