Abstract :
[en] GIS (Geographical Information Systems) bring an ever increasing range of solutions to decision makers seeking ever more accurate situational awareness in the issues they are facing. In particular, a GIS can provide a broad range of visual information resulting from computations that may be complex. These require to develop and implement efficient algorithms because of the massive amount of computations or data that are induced by the geographical nature of the processed data.
The Urban and Rural Planning and Study Lab of University of Liege seeks to compute accessibility profiles for so-called "slow transport modes" in the Walloon Region. In this context, a relevant issue of computation of a socio-economical index based on spatial and population data is considered.
The objective of this work is to modelize a problem of computation accessibility index, then solve it. The central part consists of the developement of a consistent and efficient algorithm chain to compute optimal shortest paths in geographical zones by avoiding barriers. The integration of the involved algorithms as well as the exploitation of intermediary results are fundemental aspects of the proposed solution.
Two variants of the problem are modelized: DLOSP (Discrete Line-Of-Sight Paths, that does not take barriers into account) and DGSP (Discrete Geodesic Shortest Paths, that takes barriers into account).
The detection and indexation of the barrieres, the refitting of the considered search space, the optimization of visibility requests and the computation of shortest paths constitute the main steps of the proposed algorithm chain.
A distributed computing setup, naturally stemming from the structure of the problem itself, is briefly presented.
[fr] Les GIS (Systèmes d'Information Géographique) apportent un nombre sans cesse croissant de solutions aux décideurs recherchant une perception toujours plus claire des situations auxquelles ils sont confrontés. En particulier, un GIS peut fournir une vaste gamme d'informations visuelles résultant de traitements pouvant s'avérer complexes. Ceux-ci requièrent le développement et l'implémentation d'algorithmes performants pour faire face aux calculs massifs et/ou à la très grande quantité de données induits par la nature géographique de l'information traitée.
Le Laboratoire d'Etude en Planification Urbaine et Rurale de l'Université de Liège doit calculer des profils d'accessibilité des modes de transport lents en Région wallonne. Dans ce contexte, un problème concret de calcul d'un indice socio-économique sur base de données spatiales et de population est abordé.
L'objectif de ce travail est de modéliser et résoudre un problème de calcul d'indices d'accessibilité. La partie centrale est le développement d'une chaîne d'algorithmes consistante et performante calculant des chemins optimaux dans des zones géographiques données en contournant les barrières (ou obstacles) rencontrées. L'intégration des différents algorithmes et l'exploitation de résultats intermédiaires sont deux aspects fondamentaux de la solution envisagée.
Deux variantes du problème posé sont modélisées : DLOSP} (Discrete Line-Of-Sight Paths, pas de prise en compte des barrières) et DGSP (Discrete Geodesic Shortest Paths, avec contournement des barrières).
La détection et l'indexation des obstacles, le reconditionnement de l'espace de recherche, l'étude de requêtes de visibilité et le calcul de chemins les plus courts constituent les principales étapes du développement de la chaîne d'algorithmes.
Un processus de distribution des calculs, naturellement envisageable étant donné la structure du problème, est brièvement présenté.
