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 Mur­cie, en Espagne, où elle est confi­née pour la deuxième fois de l’année 2020, que nous avons rejoint vir­tuel­le­ment Mer­cedes Pele­grín García, jeune cher­cheuse au LIX (Labo­ra­toire d’informatique) et auteure d’une thèse inti­tu­lée « Set packing, loca­tion and rela­ted pro­blems », qui vient d’être récom­pen­sée par un prix de l’Informs (Ins­ti­tute for Ope­ra­tions Research and the Mana­ge­ment Sciences) et un prix d’EURO, les socié­tés de recherche opé­ra­tion­nelle 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 jan­vier pour faire mon stage de post­doc quand on a eu d’abord les grèves, puis en mars le pre­mier confi­ne­ment est sur­ve­nu. Ce n’était pas très com­mode de res­ter à la Cité uni­ver­si­taire inter­na­tio­nale où je suis logée. Donc retour à Mur­cie. Je suis reve­nue en sep­tembre, mais voi­là qu’on a un nou­veau confi­ne­ment… Heu­reu­se­ment, cela n’empêche pas trop de tra­vailler dans ma spé­cia­li­té de recherche en mathé­ma­tiques. Nous avons des sémi­naires, des réunions d’équipe sur le net, etc. On tra­vaille de manière très intense : ça aide à faire pas­ser le temps et l’isolement.

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

J’ai fait mes études uni­ver­si­taires à Mur­cie, jusqu’à mon doc­to­rat que j’ai obte­nu avec une thèse sur le sujet Set packing, loca­tion and rela­ted pro­blems. Ensuite, j’ai cher­ché un peu par­tout un endroit pour faire un post­doc. J’ai été très inté­res­sée par les thé­ma­tiques de recherche et le pro­jet qui m’étaient pro­po­sés par Clau­dia D’Ambrosio, la titu­laire de la chaire Inte­gra­ted Urban Mobi­li­ty au LIX. Je ne la connais­sais pas avant, mais c’était quelqu’un dont j’avais beau­coup enten­du par­ler dans mon domaine.

Pourquoi avoir choisi le Set packing ?

C’est un pro­blème de base en recherche opé­ra­tion­nelle, qui réunit de nom­breux aspects inté­res­sants des mathé­ma­tiques : la théo­rie des graphes, l’optimisation, les algo­rithmes… et qui a de nom­breuses appli­ca­tions concrètes. Ce type de pro­blèmes se com­plique très vite. Pour les résoudre, on fait tour­ner des pro­grammes spé­cia­li­sés sur ordi­na­teur, mais tout est dans la modé­li­sa­tion qu’on fait du pro­blème, basi­que­ment avec un crayon sur du papier. Le but est de trou­ver les modèles qui néces­si­te­ront le moins de temps de cal­cul ensuite.


Le Set packing

Le Set packing est un pro­blème clas­sique de com­bi­na­toire : on recherche si, étant don­né un ensemble fini S et une liste de ses sous-ensembles, k de ces sous-ensembles sont tous dis­joints deux à deux. Dans sa ver­sion d’optimisation, on recherche quel est le nombre maxi­mum d’ensembles dis­joints dans la liste.


Et sur quoi travaillez-vous maintenant ?

C’est un pro­jet de mobi­li­té aérienne en milieu urbain, sou­te­nu par Uber. Il s’agit d’organiser un réseau de dépla­ce­ment en ville avec des héli­co­ptères-taxis élec­triques, pour limi­ter la pol­lu­tion, les embou­teillages… Le sujet est dif­fi­cile, car cela doit fonc­tion­ner en temps réel ; cela sup­pose de suivre très pré­ci­sé­ment les tra­jec­toires des véhi­cules, de pou­voir régir très rapi­de­ment en cas de pro­blème, d’intégrer les aléas de la météo, les retards impré­vus. Les modèles mathé­ma­tiques sont donc très com­pli­qués. Nous en sommes encore au stade de la modélisation.

Et après ?

Je ne me suis pas encore posé la ques­tion : j’ai encore deux ans de post­doc devant moi. Ensuite, sans doute la recherche en mathé­ma­tiques, mais où ? Je ne sais vrai­ment pas…

Poster un commentaire