Le Set packing permet de modéliser un problème, il trouve des applications concrètes dans le projet de mobilité aérienne en milieu urbain, soutenu par Uber.

Du Set packing au taxi aérien autonome, rencontre avec une jeune chercheuse en recherche opérationnelle

Dossier : Nouvelles du platâlMagazine N°762 Février 2021
Par Robert RANQUET (72)

C’est dans sa ville d’origine de Murcie, en Espagne, où elle est confinée pour la deuxième fois de l’année 2020, que nous avons rejoint virtuellement Mercedes Pelegrín García, jeune chercheuse au LIX (Laboratoire d’informatique) et auteure d’une thèse intitulée « Set packing, location and related problems », qui vient d’être récompensée par un prix de l’Informs (Institute for Operations Research and the Management Sciences) et un prix d’EURO, les sociétés de recherche opérationnelle aux États-Unis et en Europe.

 

Tout d’abord, Mercedes, comment se passe ce confinement pour vous ?

C’est la deuxième fois cette année : je venais d’arriver au LIX en janvier pour faire mon stage de postdoc quand on a eu d’abord les grèves, puis en mars le premier confinement est survenu. Ce n’était pas très commode de rester à la Cité universitaire internationale où je suis logée. Donc retour à Murcie. Je suis revenue en septembre, mais voilà qu’on a un nouveau confinement… Heureusement, cela n’empêche pas trop de travailler dans ma spécialité de recherche en mathématiques. Nous avons des séminaires, des réunions d’équipe sur le net, etc. On travaille de manière très intense : ça aide à faire passer le temps et l’isolement.

Qu’est-ce qui vous a amenée à l’X ?

J’ai fait mes études universitaires à Murcie, jusqu’à mon doctorat que j’ai obtenu avec une thèse sur le sujet Set packing, location and related problems. Ensuite, j’ai cherché un peu partout un endroit pour faire un postdoc. J’ai été très intéressée par les thématiques de recherche et le projet qui m’étaient proposés par Claudia D’Ambrosio, la titulaire de la chaire Integrated Urban Mobility au LIX. Je ne la connaissais pas avant, mais c’était quelqu’un dont j’avais beaucoup entendu parler dans mon domaine.

Pourquoi avoir choisi le Set packing ?

C’est un problème de base en recherche opérationnelle, qui réunit de nombreux aspects intéressants des mathématiques : la théorie des graphes, l’optimisation, les algorithmes… et qui a de nombreuses applications concrètes.  Ce type de problèmes se complique très vite. Pour les résoudre, on fait tourner des programmes spécialisés sur ordinateur, mais tout est dans la modélisation qu’on fait du problème, basiquement avec un crayon sur du papier. Le but est de trouver les modèles qui nécessiteront le moins de temps de calcul ensuite.

 


Le Set packing

Le Set packing est un problème classique de combinatoire : on recherche si, étant donné un ensemble fini S et une liste de ses sous-ensembles, k de ces sous-ensembles sont tous disjoints deux à deux. Dans sa version d’optimisation, on recherche quel est le nombre maximum d’ensembles disjoints dans la liste.


Et sur quoi travaillez-vous maintenant ?

C’est un projet de mobilité aérienne en milieu urbain, soutenu par Uber. Il s’agit d’organiser un réseau de déplacement en ville avec des hélicoptères-taxis électriques, pour limiter la pollution, les embouteillages… Le sujet est difficile, car cela doit fonctionner en temps réel ; cela suppose de suivre très précisément les trajectoires des véhicules, de pouvoir régir très rapidement en cas de problème, d’intégrer les aléas de la météo, les retards imprévus. Les modèles mathématiques sont donc très compliqués. Nous en sommes encore au stade de la modélisation.

Et après ?

Je ne me suis pas encore posé la question : j’ai encore deux ans de postdoc devant moi. Ensuite, sans doute la recherche en mathématiques, mais où ? Je ne sais vraiment pas…

Poster un commentaire