Du placement optimal de caméras pour la surveillance d'évènements urbains : une approche combinatoire assistée par l’utilisateur pour l’aide à la décision dans le monde réel

As part of a French-German joint research project, this thesis tackles issues related to video-based surveillance networks, more specifically their design in terms of optimal camera placement and the integration of user input for deployment in the context of decision support systems. We begin with an in-depth review of two bodies of literature, one related to our practical application and the other to a popular and closely related theoretical problem. This survey covers both problem modelling and solving, and highlights several open lines of research. In terms of modelling, we begin by focusing on the design of a middle ground between unrealistic simplicity and prohibitive complexity, both popular extremes in optimal camera placement literature. We design an instance generation and preprocessing framework which uses real-world data to extract accurate information about our surveillance area. Taking advantage of the availability of such instances, we then move on to benchmarking the state of the art, a study which had so far not been performed, most likely due to the large number of problem variants and constraints in the literature. Our results suggest several hypotheses on the complexity of the problem, which we investigate further. Our conclusions lead us to the construction of a new model for our problem, which we then use to design a time-efficient solving algorithm. The latter is then integrated into a small decision support system through which a user can negotiate solutions withCette thèse, contribution à un projet de recherche franco-allemand, s'intéresse aux réseaux de vidéo-protection, plus particulièrement au problème de placement optimal de cameras et à l'intégration de cette problématique au sein de systèmes d'aide à la décision. Nous commençons avec une revue approfondie de deux corpus, l'un portant sur notre application et l'autre sur un populaire problème théorique lié à cette dernière. Cette étude couvre à la fois modélisation et résolution, et met en avant diverses pistes de recherche. En terme de modélisation, nous nous intéressons particulièrement à la mise au point d'un compromis entre les deux extrêmes typiques de la littérature : trop simpliste ou trop coûteux. Nous implémentons ainsi un système de génération et de pré-traitement d'instances basé sur des données réelles et capable d'extraire une représentation fidèle de la zone à couvrir. Ces instances nous permettent ensuite de mettre en place une étude comparative de l'état de l'art, jusqu'ici resté sans point de référence en raison du large panorama de variantes et de contraintes autour de notre problème. Nos résultats posent plusieurs hypothèses au sujet de la complexité de ce dernier. Nos conclusions associées nous permettent de construire un nouveau modèle, que nous utilisons afin de définir un algorithme de résolution efficace, et directement intégrable à un système d'aide à la décision. Un prototype est d'ailleurs implémenté afin de permettre à un utilisateur de négocier avec l'algorithme jusqu'à obtenir une solution jugée satisfaisante