PhD position - Interactive data collection during the tour of a Travelling salesman drone on convex neighborhoods of buried sensor nodes

Supervisors:

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

Topic

The automated monitoring of agricultural fields is increasingly using underground wireless sensors designed to collect local variables such as temperature, humidity, or the presence of certain chemical elements. These electronic detection devices are buried at various depths to protect them from destruction by motorized equipments or passages of animals. This results in highly varied signal emission characteristics and short communication ranges. The originality of the project lies in performing the data collection task using a drone, whose mission is to fly across areas where transmissions with the sensors are possible. Determining the optimal pickup order between these areas has to take into account the distances traveled and the total energy consumed by the drone. This theme naturally falls within the scope of combinatorial optimization, where many variations of the classical traveling salesman problem have been studied. Some of them incorporate uncertainties about the position of nodes [Bertsimas et al. [1]], or allow the selection of destinations representing areas that must be visited, [Fischetti et al. [2]] and [Di Placido et al. [5]].

The thesis goal is to research mathematical formulations determining an optimal tour that serves each convex domain associated with a sensor. Exact and approximate algorithms will need to be developed and compared with the aim of using the best one for automated data collection.

A state-of-the-art review will be conducted on both aspects of the traveling salesman. Actually, the problem to be studied is related to the generalized and neighborhood traveling salesman problem as well as to the Traveling Salesman Problem with Drones [Macrina et al. [3]] and [Meng et al. [4]].

This work will consider the existence of obstacles (buildings, trees, etc.) during the tour, the influence of wind on the trajectory as well as the possibility to manage an entire fleet of drones. Finally, the various algorithmic solutions will be evaluated in the context of data collection in test agricultural areas managed by INRAE (Montoldre site).

Skills:

The candidate must have a solid background in combinatorial optimization, particularly in integer linear programming and optimization algorithms on graphs. Preferably, they should have completed a master's degree in operations research or applied mathematics and have a good level of programming in C++ and Python.

References

1. Bertsimas D., Howel, L. H,. Further results On the probabilistic traveling salesman problem. European Journal of Operational Research. 65(1), 1993.
2. Fischetti M., Salazar-Gonzalez JJ., Toth P., The Generalized Traveling Salesman and Orienteering Problems. Chapter of a book The Traveling Salesman Problem and Its Variations by Gutin, G. and Punnen, A. P, Springer US. 2007
3. Macrina G., Di Puglia Pugliese L., Guerriero F., Laporte G., Drone-aided routing: A literature review  Transportation Research Part C: Emerging Technologies. Volume 120.2020
4. Shanshan Meng, Xiuping Guo, Dong Li, Guoquan Liu. The multi-visit drone routing problem for pickup and delivery services. Transportation Research Part E: Logistics and Transportation Review. Vol. 169, 2023 Di Placido A., Archetti C., Cerrone C., Golden B., The generalized close enough traveling salesman problem. European Journal of Operational Research. Vol. 310(3), 2023

1LIMOS- Université Clermont Auvergne

2INRAE-UR TSF-Aubière

3IMAULL-Universidad de La Laguna