Développement d'une extension logicielle implémentant le parcours d'un graphe par temps régressif

Abstract

Le parcours de graphes routiers est couramment utilisé, notamment par les applications de calcul d’itinéraires. La transposition de ces parcours de graphes en mode maillé utilise un algorithme de propagation appliqué au réseau routier désormais matérialisé par un ensemble de pixels. Cette transposition est utilisée dans le cadre du profilage géographique, afin de mettre en évidence le point d’ancrage d’un auteur de plusieurs crimes localisés dans l’espace et dans le temps en se basant sur un ensemble de postulats. Le parcours de ce graphe en mode maillé est réalisé depuis chaque site de crime, à partir duquel on « remonte le temps » en se propageant sur l’ensemble du réseau routier rasterisé en fonction de la vitesse autorisée en chaque pixel. Le point d’ancrage est alors donné par le pixel minimisant la différence entre l’heure de passage maximale et minimale (i.e. l’étendue des heures de passage). L’objectif de ce mémoire est de construire une extension logicielle implémentant ce processus, tout en étudiant les différentes erreurs qui affectent le résultat final et en tentant de les résoudre afin d’améliorer celui-ci. Pour ce faire, des données spatio-temporelles virtuelles ont été utilisées. La méthode de l’étendue des heures de passage a été implémentée ainsi qu’une méthode calculant la variance de ces mêmes heures, qui a été proposée afin de déterminer si elle pouvait améliorer le résultat. Une analyse comparative a montré que la méthode de l’étendue est plus efficace étant donné qu’elle apparaît plus discriminante et plus proche de la solution. Certaines erreurs ont été solutionnées (amélioration des coûts propagés, rattachement des sites de crimes sur le graphe routier), là où d’autres n’ont pu être résolues pour cause de manque de données (adaptation du temps de parcours à la date et à l’heure). Deux méthodes relatives à la prise en compte respectivement du sens de circulation et de la non-planéité des graphes routiers ont été proposées et implémentées, par mise en évidence des mouvements non permis entre pixels. Cependant, ces méthodes sont en pratique fortement limitées par le résultat de la rasterisation, et n’ont donc pas pu être ajoutées au processus. Au final, l’extension logicielle a bien été développée avec la méthode de l’étendue, ainsi que deux autres solutions de mise en évidence d’un point d’ancrage également énoncées dans le cadre du profilage géographique : la minimisation de la moyenne et de la variance des temps de déplacement du point d’ancrage vers les différents crimes. Une comparaison des temps d’exécution montre que l’efficacité des méthodes est proche, et par ailleurs que cet ajout de méthodes a du sens étant donné que le temps d’exécution combiné des trois méthodes implémentées n’est pas significativement plus important que celui de la seule méthode de l’étendue.

Road graphs traversal is commonly used, especially by route calculation applications. The transposition of these graphs traversals in raster mode uses a propagation algorithm applied to road network materialized from now on by a set of pixels. This transposition is used for geographic profiling, in order to highlight the anchor point of an author of several space and time localized crimes according to some assumptions. This raster graph traversal is realized from each crime site, from which one “go back in time” by propagation on the whole rasterized road network in function of the authorized speed in each pixel. The anchor point is then given by the pixel that minimizes the difference between maximal and minimal hours passing through each pixel (i.e. range method of these hours). The objective of this master’s thesis is to build a plugin that implements this process, while studying the possible errors that affect the final result and trying to resolve them in order to improve it. To do so, virtual space-time data has been used. The range method has been implemented, as well as another method calculating the variance of hours passing through each pixel that has been proposed in order to determine if it could improve the result. A comparative analysis showed that the range method is more efficient as it appears more discriminant and closer to the solution. Some errors have been solved (improvement of the propagated costs, connection of crime sites on road graph), while others have not been fixed because of the lack of data (adaptation of time traversal to date and time). Two methods taking into consideration respectively the traffic direction and the non-planar aspect of road graphs have been proposed and implemented, by revealing movements that are not allowed between two pixels. However, these methods are in practice forcefully limited by the result of the rasterization, and then have not been added to the process. At the end, the plugin has been correctly developed with the range method, as well as two other solutions of highlighting an anchor point also announced in the geographic profiling literature: the minimization of journeys-to-crime mean and variance. A comparison of the times of execution shows that the efficiency of the methods is similar, and also that this addition makes sense as the total time of execution of the three implemented methods is not significantly greater than the one with the range method only.