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 con­finée pour la deux­ième fois de l’année 2020, que nous avons rejoint virtuelle­ment Mer­cedes Pele­grín Gar­cía, jeune chercheuse au LIX (Lab­o­ra­toire d’informatique) et auteure d’une thèse inti­t­ulée “Set pack­ing, loca­tion and relat­ed prob­lems”, qui vient d’être récom­pen­sée par un prix de l’Informs (Insti­tute for Oper­a­tions Research and the Man­age­ment Sci­ences) et un prix d’EURO, les sociétés de recherche opéra­tionnelle aux États-Unis et en Europe.

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

C’est la deux­ième fois cette année : je venais d’arriver au LIX en jan­vi­er pour faire mon stage de post­doc quand on a eu d’abord les grèves, puis en mars le pre­mier con­fine­ment est sur­venu. Ce n’était pas très com­mode de rester à la Cité uni­ver­si­taire inter­na­tionale où je suis logée. Donc retour à Mur­cie. Je suis rev­enue en sep­tem­bre, mais voilà qu’on a un nou­veau con­fine­ment… Heureuse­ment, cela n’empêche pas trop de tra­vailler dans ma spé­cial­ité de recherche en math­é­ma­tiques. Nous avons des sémi­naires, des réu­nions d’équipe sur le net, etc. On tra­vaille de manière très intense : ça aide à faire pass­er 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­tor­at que j’ai obtenu avec une thèse sur le sujet Set pack­ing, loca­tion and relat­ed prob­lems. Ensuite, j’ai cher­ché un peu partout un endroit pour faire un post­doc. J’ai été très intéressée par les thé­ma­tiques de recherche et le pro­jet qui m’étaient pro­posés par Clau­dia D’Ambrosio, la tit­u­laire de la chaire Inte­grat­ed Urban Mobil­i­ty au LIX. Je ne la con­nais­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 prob­lème de base en recherche opéra­tionnelle, qui réu­nit de nom­breux aspects intéres­sants des math­é­ma­tiques : la théorie des graphes, l’optimisation, les algo­rithmes… et qui a de nom­breuses appli­ca­tions con­crètes. Ce type de prob­lèmes se com­plique très vite. Pour les résoudre, on fait tourn­er des pro­grammes spé­cial­isés sur ordi­na­teur, mais tout est dans la mod­éli­sa­tion qu’on fait du prob­lème, basique­ment avec un cray­on sur du papi­er. Le but est de trou­ver les mod­èles qui néces­siteront le moins de temps de cal­cul ensuite.


Le Set packing

Le Set pack­ing est un prob­lème clas­sique de com­bi­na­toire : on recherche si, étant don­né un ensem­ble fini S et une liste de ses sous-ensem­bles, k de ces sous-ensem­bles sont tous dis­joints deux à deux. Dans sa ver­sion d’optimisation, on recherche quel est le nom­bre max­i­mum d’ensembles dis­joints dans la liste.


Et sur quoi travaillez-vous maintenant ?

C’est un pro­jet de mobil­ité aéri­enne en milieu urbain, soutenu par Uber. Il s’agit d’organiser un réseau de déplace­ment en ville avec des héli­cop­tères-taxis élec­triques, pour lim­iter la pol­lu­tion, les embouteil­lages… Le sujet est dif­fi­cile, car cela doit fonc­tion­ner en temps réel ; cela sup­pose de suiv­re très pré­cisé­ment les tra­jec­toires des véhicules, de pou­voir régir très rapi­de­ment en cas de prob­lè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­pliqué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