Postdoctorat en Graphes Temporels H/F

Service Public

Dans le cadre de travaux menés par l'Unité, une option étudiée est d'enterrer les capteurs agricoles afin de ne pas gêner les travaux. Une méthode de collecte permettant d'éviter de les déterrer est alors d'utiliser un drone, qui effectuera une tournée afin de relever les données. Une approche utilisée est de générer un graphe à partir de la carte des rayons de diffusion des capteurs, puis de résoudre un TSP [1]. L'objectif du projet DCoDE est de poursuivre dans cette étude en explorant différents axes de recherche:

- proposer différentes manières de générer un graphe sur lequel chercher une trajectoire (l'approche actuelle est une heuristique réduisant deux disques s'intersectant à leur intersection et itérant, ce qui ne génère pas nécessairement de « bons » graphes);

- ajouter au modèle les effets de la météo: le vent peut augmenter le coût de certains déplacements, cela implique de passer à une version temporelle du TSP [3] ou à d'autres problèmes d'exploration de graphes temporels avec des sommets spéciaux [2];

- énumérer différentes solutions acceptables et significativement différentes, via des approches aussi efficaces que possible, afin d'offrir un choix de tournées à un.e utilisateur.trice.

Les contributions attendues sont principalement théoriques, mais des implémentations et résultats expérimentaux sur des jeux de données de l'Unité seront un plus.

La personne recrutée sera coencadrée par Antoine Dailly (TSCF) et Vincent Limouzy (LIMOS). Elle s'investira dans le groupe de recherche AlCoLoCo (https://alcoloco.isima.fr/).

[1]C. Cariou, L. Moiroux-Arvis, F. Bendali and J. Mailfert (2024). Optimal Route Planning of an Unmanned Aerial Vehicle for Data Collection of Agricultural Sensors. IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Vancouver, BC, Canada, 2024, pp. 1-6.

[2] A. D'Ascenzo, G. F. Italiano, S. Kanellopoulos, A. Mpanti, A. Pagourtzis and C. Pergaminelis (2025). Beer Path Problems in Temporal Graphs. arXiv preprint arXiv:2507.08685, to be presented at IWOCA 2026.

[3] O. Michail and P. G. Spirakis (2016). Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634, 1-23.