Offre de doctorat – Collecte de données interactive lors de la tournée d’un drone Voyageur de commerce sur les voisinages convexes de nœuds capteurs enterrés – Clermont Ferrand , France

Superviseurs :

Fatiha Bendali, Jean Mailfert 1, Christophe Cariou, Laure Moiroux-Arvis 2, Juan José Salazar González 3.

Sujet

La surveillance automatisée des champs agricoles fait de plus en plus appel à des capteurs sans fil souterrains conçus pour collecter des variables locales telles que la température, l’humidité ou la présence de certains éléments chimiques. Ces appareils de détection électronique sont enfouis à différentes profondeurs pour les protéger de la destruction par des équipements motorisés ou des passages d’animaux. Il en résulte des caractéristiques d’émission de signal très variées et des portées de communication courtes. L’originalité du projet réside dans la réalisation de la tâche de collecte de données à l’aide d’un drone, dont la mission est de survoler les zones où les transmissions avec les capteurs sont possibles. La détermination de l’ordre de prise en charge optimal entre ces zones doit prendre en compte les distances parcourues et l’énergie totale consommée par le drone. Ce thème s’inscrit naturellement dans le cadre de l’optimisation combinatoire, où de nombreuses variantes du problème classique du voyageur de commerce ont été étudiées. Certains d’entre eux intègrent des incertitudes sur la position des nœuds [Bertsimas et al. [1]], ou permettre la sélection de destinations représentant des zones à visiter, [Fischetti et al. [2]] et [Di Placido et al. [5]].

L’objectif de la thèse est de rechercher des formulations mathématiques déterminant un tour optimal qui dessert chaque domaine convexe associé à un capteur. Des algorithmes exacts et approximatifs devront être développés et comparés dans le but d’utiliser le meilleur pour la collecte automatisée de données.

Un état de l’art sera réalisé sur les deux aspects du voyageur de commerce. En fait, le problème à étudier est lié au problème du voyageur de commerce généralisé et de quartier ainsi qu’au problème du voyageur de commerce avec les drones [Macrina et al. [3]] et [Meng et al. [4]].

Ce travail considérera l’existence d’obstacles (bâtiments, arbres, etc.) lors du parcours, l’influence du vent sur la trajectoire ainsi que la possibilité de gérer toute une flotte de drones. Enfin, les différentes solutions algorithmiques seront évaluées dans le cadre de collecte de données dans des zones agricoles tests gérées par INRAE ​​(site de Montoldre).

Compétences:

Le candidat doit avoir une solide expérience en optimisation combinatoire, notamment en programmation linéaire en nombres entiers et en algorithmes d’optimisation sur graphes. De préférence, ils doivent avoir complété un master en recherche opérationnelle ou en mathématiques appliquées et avoir un bon niveau de programmation en C++ et Python.

Les références

1. Bertsimas D., Howel, L. H.. Autres résultats Sur le problème probabiliste du voyageur de commerce. Journal européen de recherche opérationnelle. 65(1), 1993.
2. Fischetti M., Salazar-Gonzalez JJ., Toth P., Le voyageur de commerce généralisé et les problèmes de course d’orientation. Chapitre d’un livre The Travelling Salesman Problem and Its Variations de Gutin, G. et Punnen, A. P, Springer US. 2007
3. Macrina G., Di Puglia Pugliese L., Guerriero F., Laporte G., Routage assisté par drone : une revue de la littérature Recherche sur les transports, partie C : Technologies émergentes. Tome 120.2020
4. Shanshan Meng, Xiuping Guo, Dong Li, Guoquan Liu. Le problème du routage des drones multi-visites pour les services de ramassage et de livraison. Recherche sur les transports, partie E : Examen de la logistique et des transports. Vol. 169, 2023 Di Placido A., Archetti C., Cerrone C., Golden B., Le problème généralisé du voyageur de commerce assez proche. Journal européen de recherche opérationnelle. Vol. 310(3), 2023

1LIMOS- Université Clermont Auvergne

2INRAE-UR TSF-Aubière

3IMAULL-Université de La Laguna