These theses that change life: Lower limits and exact computational methods used to solve the bin-packing problem with a set orientation

“Small and very nar­row box­es …”. This could have been the leit­mo­tiv phrase to fill in François Clautiaux’s hours lead­ing up to his PhD. 

Already hold­ing his Master’s degree in com­put­er sci­ences and appli­ca­tions, before com­ing to UTFC, François reg­is­tered for the Infor­ma­tion and Sys­tem Tech­nolo­gies Mas­ter at UTC to spe­cial­ize on oper­a­tional research (OR). In 2002 he defend­ed a PhD the­sis. “Ini­tial­ly, the prob­lem came via a for­mer indus­tri­al part­ner­ship with a Picardie Region SME who had encoun­tered prob­lems to fit var­i­ous objects into box­es”, he recalls. In order to opti­mize the prob­lem, François Clau­ti­aux, with finan­cial sup­port from the French HE & Research Min­istry, start­ed his the­o­ret­i­cal work. “The issue I inves­ti­gat­ed was to see how to fit objects in a 2‑D recip­i­ent con­text. The aim was to fit small rec­tan­gles in larg­er tri­an­gles”. The prob­lem framed this way appears sim­ple. “But, in fact, it is very com­plex, a com­bi­na­to­ry prob­lem with bil­lions of pos­si­ble solu­tions”. In prac­ti­cal terms, there are numer­ous appli­ca­tions, run­ning from print­ed cir­cuit designs to posi­tion­ing con­tain­ers in a warehouse. 

Math­e­mat­i­cal meth­ods alone do not pro­vide a solu­tion. “To find applic­a­ble solu­tions you need to use computers”.

There were pre-exist­ing papers on this ’best-fit’ sub­ject lead­ing to var­i­ous rapid­ly applied solu­tions. “The real prob­lem was to prove that the solu­tion cho­sen was the best pos­si­ble”. The algo­rithms designed by François Clau­ti­aux have been used by oth­er research sci­en­tists pro­duc­ing solu­tions that are used in indus­tri­al sec­tors. The logis­tics sec­tor for exam­ple, was obvi­ous­ly inter­est­ed in this the­sis work to opti­mize load­ing ques­tions. The glass indus­tries too, inas­much as stor­ing plate glass and car­ry­ing out opti­mized glass plate cuts would lead to low­er wastes“. François Clau­ti­aux today is Pro­fes­sor of Math­e­mat­ics at the Uni­ver­si­ty of Bor­deaux and is involved in con­sul­tan­cy work for Renault to solve truck load­ing issues. He is also going to start a sec­ond the­sis with and for Saint-Gob­ain Group who wish to acquire opti­mized glass cut­ting tech­nolo­gies and processes.

Le magazine

Juin 2023 - N°60

Une recherche tournée vers un avenir soutenable

linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram