Gestió de la implementació d’una aplicació per optimitzar cistelles d’aliments i desenvolupament de la seva generalització

Treball de Fi de Grau Grau en Enginyeria en Tecnologies Industrials Gestió de la implementació d’una aplicació per optimitzar cistelles d’aliments i desenvolupament de la seva generalització MEMÒRIA Autor/a: Pol Gonzàlez Surinyach Director/a: Marc Juanpera Gallel Co-director/a: Pol Gil Figuerola Convocatòria: Abril 2025 Escola Tècnica Superior d’Enginyeria Industrial de Barcelona Pàg. 2 Memòria Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 3 Resum Al Centre de Distribució Social d’Aliments El Rebost, situat a Terrassa, s'ha instal·lat, per part del grup de recerca DOPS de la UPC, una aplicació que permet millorar el repartiment d’aliments a les famílies beneficiàries, usant cistelles per a classificar-les en funció del nombre de beneficiaris; maximitzant així el cobriment nutricional, la varietat d’aliments entregats i la equitat entre famílies. El model actual te limitacions que poden ser adreçades per a millorar la seva funcionalitat. Es vol poder distingir el tractament que se li dona al producte sobrant fresc i al sec, poder distribuir en lots certs aliments i es necessita que sigui més robust enfront a canvis en la distribució d’aliments, com per exemple decidir a quines cistelles es pot repartir cada aliment o la classificació de les famílies per assignar cistelles. El treball presentat implementa les millores necessàries per a superar aquestes limitacions, i aprofitant els canvis, es fa una reestructuració del codi de programació per a que sigui més robust, comprensible i generalitzable, de cara a un possible futur en que es vulgui implementar en altres entitats. Per concloure, es realitzen experimentacions amb el nou model en les que veiem com es superen les limitacions anteriors, aconseguint resultats de mínim cobriment nutricional i equitat millors comparats amb el model anterior. També es proposen noves formes de distribucions de cistelles que milloren els valors d’ambdós indicadors. Pàg. 4 Memòria Resumen En el Centro de Distribución Social de Alimentos ‘El Rebost’, situado en Terrassa, se ha instalado, por parte del equipo de investigación DOPS de la UPC, una aplicación que permite mejorar la repartición de alimentos a las familias beneficiarias, utilizando cestas para clasificarlas en función del nombre de beneficiarios; maximizando así el cubrimiento nutricional, la variedad de alimentos entregados y la equidad entre familias. El modelo actual tiene limitaciones que pueden ser afrontadas para mejorar su funcionalidad. Se quiere poder distinguir el tratamiento que se le da a los productos sobrantes secos y los frescos, poder distribuir en lotes ciertos alimentos y se necesita que sea más robusto frente cambios en la distribución de alimentos, como por ejemplo decidir a que cestas se puede repartir cada alimento o la clasificación de las familias para asignar las cestas. El trabajo presentado implementa las mejoras necesarias para superar estas limitaciones, y aprovechando los cambios, se hace una reestructuración del código de programación para que sea más robusto, comprensible y generalizable, de cara a un posible futuro en el que se quiera implementar el modelo en otras entidades. Para concluir, se realizan experimentaciones con el nuevo modelo en las que se aprecia como se superan las limitaciones anteriores, consiguiendo resultados de mínimo cubrimiento nutricional y equidad mejores comparados con el modelo anterior. También se proponen nuevas formas de distribución de cestas que mejoran los valores de ambos indicadores. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 5 Abstract At the Center of Social Food Distribution ‘El Rebost’, located in Terrassa, an application has been installed by the research group DOPS at UPC, this app allows to better distribute the food available at the center throughout the beneficiary families, using baskets to classify in function of the members per family; therefore, maximizing nutritional coverage, the variety of food commodities distributed and the equity between families. The current model has some limitations that can be addressed to improve functionality. It’s desired to differentiate how fresh and dry food leftovers are treaded by the model, also to be able to distribute some foods commodities in lots, and a more robust model is needed when parameters like the distribution of baskets or to which basket can be assigned each commodity want to be changed. This report implements the upgrades needed to overcome the limitations, and taking advantage of the changes, a refactoring of the programming code is done, to make it more readable, robust and generalizable, in case in the future this model wants to be implemented in other entities. To conclude, experimentations are done with the new model in which the new functionalities can be observed, while also improving parameters like minimum nutritional coverage or equity. Also new ways of distributing the families and baskets are proposed that improve the parameters values. Pàg. 6 Memòria Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 7 Contingut GLOSSARI I NOMENCLATURA ____________________________________________________ 9 LLISTAT DE FIGURES ____________________________________________________________ 10 LLISTAT DE TAULES _____________________________________________________________ 11 1. INTRODUCCIÓ ______________________________________________________________ 13 1.1. Justificació ................................................................................................................................... 13 1.2. Abast del treball ....................................................................................................................... 14 1.3. Objectius ...................................................................................................................................... 14 2. ESTAT DE L’ART ____________________________________________________________ 16 2.1. Problemes d’optimització .................................................................................................... 16 2.2. Antecedents ............................................................................................................................... 18 2.3. Estat de la qüestió.................................................................................................................... 18 3. DESENVOLUPAMENT DEL MODEL ________________________________________ 19 3.1. Descripció del problema ....................................................................................................... 19 3.2. Formulació matemàtica ........................................................................................................ 21 3.2.1. Conjunts .............................................................................................................................................. 22 3.2.2. Dades/Paràmetres ......................................................................................................................... 23 3.2.3. Variables de decisió ....................................................................................................................... 24 3.2.4. Funcions objectiu ........................................................................................................................... 25 3.2.5. Restriccions ....................................................................................................................................... 25 3.3. Adicions al model..................................................................................................................... 28 4. APORTACIONS DEL CODI __________________________________________________ 30 4.1. Estructura i funcionament del nou codi ......................................................................... 30 4.1.1. Pre-procés.......................................................................................................................................... 30 4.1.2. Execució model................................................................................................................................ 34 4.1.3. Post-procés ........................................................................................................................................ 35 4.2. Millores i canvis menors ....................................................................................................... 35 5. RESULTATS _________________________________________________________________ 37 5.1. Experimentació ........................................................................................................................ 37 5.1.1. Anàlisi de l’impacte dels paràmetres % màxim de producte fresc i sec per repartir i Gap .................................................................................................................................... 38 Pàg. 8 Memòria 5.1.2. Anàlisi de l’impacte del nombre de cistelles en la nutrició i equitat ....................... 45 6. PLANIFICACIÓ ______________________________________________________________ 48 7. ESTUDI ECONÒMIC _________________________________________________________ 49 8. ESTUDI AMBIENTAL _______________________________________________________ 50 9. ESTUDI SOCIAL I D’IGUALTAT DE GÈNERE _______________________________ 51 10. CONCLUSIONS ______________________________________________________________ 52 11. AGRAÏMENTS _______________________________________________________________ 53 12. BIBLIOGRAFIA ______________________________________________________________ 54 Referències bibliogràfiques.............................................................................................................. 54 Bibliografia complementària ........................................................................................................... 55 13. ANNEX _______________________________________________________________________ 56 13.1. A1. Resultats 30 instàncies .................................................................................................. 56 13.2. A2. Mitjana de les combinacions de paràmetres ........................................................ 57 Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 9 Glossari i Nomenclatura DOPS: Disseny i Optimització de Processos i Serveis (grup d’investigació de la UPC) Eina: Conjunt de codis i dades que serveixen per implementar el model a la entitat Refactoring : Millora del codi per a fer-lo més llegible i eficient MILP: Problema Lineal Enter-Mixta DRI: Dietary Reference Intakes Python: Llenguatge de programació de codi obert FNDDS: Food and Nutrient Database for Dietary Studies eQualiment: Sistema per a gestionar la distribució d’aliments solidaris DataFrame: Estructura de dades integrada a Python Biblioteca (Python): Conjunt de funcions i mòduls que afegeixen funcionalitats a Python Solver: Programa que resol problemes d’optimització Clúster de càlcul: Conjunt d’ordinadors destinats a fer càlculs en grans proporcions ONU: Organització de les Nacions Unides ∈ : Descriu que un element pertany a cert conjunt ⊆ : Subconjunt de cert conjunt ⋂ : Intersecció d’elements o conjunts ∖ : Diferència de conjunts o exclusió d’un element ℤ+ : Conjunt de nombres enters ℝ+ : Conjunt de nombres reals Pàg. 16 Memòria 2. Estat de l’art A continuació es presenta una introducció als problemes d’optimització i com es solucionen (2.1), tractem els elements del model anterior que farem servir per a la nova versió (2.2) i finalment es fa un anàlisi d’altres models que s’han implementat per a solucionar problemes similars (4.3). 2.1. Problemes d’optimització Quan es parla d’un problema d’optimització s’està definint una situació en la que volem trobar la millor solució possible, o punt òptim, d’un conjunt de solucions possibles. Aquest punt òptim pot referir-se a multitud d’aspectes, depenent de l’àmbit en el qual estiguem treballant. Aquest tipus de problemes abracen les branques de la física, matemàtiques, economia, biologia, entre d’altres, i depenent del sistema que hagis definit voldràs trobar el mínim cost, màxim benefici, menor desaprofitament energètic, màxim cobriment nutricional... Aquests problemes generalment inclouen una funció objectiu, que serà la que es busqui minimitzar o maximitzar, i un seguit de restriccions que defineixen el problema i limiten les possibles solucions. Depenent del número de funcions objectiu que es tingui, es tracta d’un problema mono objectiu, en el cas d’una sola, o multi objectiu, quan es tenen dos o més funcions a optimitzar a la vegada. Els problemes d’optimització es poden classificar en dos tipus, lineals o no lineals. Per a que un problema sigui definit com a lineal ha de tenir totes les seves restriccions i funcions objectiu com a expressions lineals, aquestes solen ser més fàcils de resoldre, donat que les no lineals solen requerir d’iteracions per a determinar una direcció de cerca de la solució. [3] També es poden diferenciar els problemes d’optimització per com son les dades que tracten. Serà d’especial interès per aquest treball els problemes anomenats MILP o “ Mixed Integer Linear Problems ”, aquests es caracteritzen per fer servir variables continues i enteres que apareixen de forma lineal tant a les funcions objectiu com a les restriccions [4]. Aquests problemes que tenen variables enteres, se’ls hi pot aplicar una relaxació, que consisteix en tractar les variables enteres com a contínues, resoldre el problema lineal i després mirar si hi ha alguna solució amb valors enters a prop d’aquesta. Algunes de les opcions que es tenen per a solucionar aquest tipus de problemes són [4]: - Mètode de pla de tall: Es relaxa el problema i es divideix la zona de solucions factibles en dominis, i es va reduint la regió factible imposant noves restriccions al model. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 17 - Mètodes heurístics: Troben solucions ràpidament, tot i que no sol trobar la millor solució. Busca primer una solució que compleixi tots els requisits i la va millorant poc a poc. - Branch and bound: Es relaxa el problema i es divideix en branques cada solució trobada, dividint-lo en sub problemes més petits. Es crea un arbre de decisions i tries la millor solució, descartant les branques que ja no poden millorar el millor valor de la funció objectiu. - Branch and cut: Molt semblant al mètode anterior, però aquest afegeix talls. Primer es troba una solució al problema relaxat, tot seguit s’aplica un algoritme per a trobar per quines branques tallar i així reduir l’espai de possibles solucions, per a seguir amb el mètode de Branch and bound . En el cas de tenir un problema multi objectiu, és bastant probable que no sigui possible trobar una solució que impliqui la optimització de tots els objectius. És en aquests casos que definim els punts òptims de Pareto. Un punt es defineix com òptim de Pareto quan no hi ha cap altre punt de les possibles solucions que millora com a mínim una de les funcions objectiu que es vol optimitzar sense empitjorar un altre. Figura 1: Exemple d’un front de Pareto amb dos funcions a minimitzar [5]. La Figura 1 mostra les solucions a un problema de minimització de dos funcions, f1 i f2. La solució C es diu que és dominada per les òptimes, donat que és estrictament pitjor per ambdues funcions objectiu, en cavi A i B no es dominen mútuament, sinó que defineixen el front de Pareto [5]. Pàg. 18 Memòria 2.2. Antecedents Donat que el treball és la continuació d’un projecte que ja està en procés de ser implementat, es decideix seguir amb les mateixes bases de dades que fa servir el model antic. Les tres més importants que cal comentar són: - DRI [6]: Per a obtenir les dades dels requeriments nutricionals que te cada beneficiari cal una base de dades que permeti estimar el consum que necessiten. S’agafa doncs la base de dades “Dietary Reference Intake” publicada per el “National Center for Biotechnology Information” . Amb la informació de la quantitat diària recomanada es podrà fer una estimació del cobriment nutricional mensual que se li fa a les famílies beneficiaries. - Nutrients dels aliments: Amb el model anterior es feia ja servir una taula que indicava per una sèrie d’aliments, quina era la seva aportació nutricional. Per a obtenir la informació es fa servir una base de dades anomenada FNDDS 2019-202 (“ Food and Nutrient Database for Dietary Studies ”) [7]. - Dades de beneficiaris: Les dades sobre les famílies que venen a recollir els aliments que es fan servir per als càlculs a la fase experimental son extrets de la base de dades del sistema eQualiment. 2.3. Estat de la qüestió L’optimització de la distribució d’aliments en entitats com El Rebost o similars és un problema que ha estat afrontat anteriorment; el projecte és una continuació d’una aplicació que està en proves actualment, però no existeix una formulació matemàtica exacte del codi que està implementat, i l’aplicació té aspectes que podrien millorar per a oferir un millor servei. Hi ha hagut formulacions similars, com per exemple el tractat per en Pol Gil a “Optimising food baskets in a local food pantry: The case study of El Rebost” [8]. En aquest article, s’analitza també el problema de la distribució d’aliments des de El Rebost i ofereix una solució que maximitza el mínim cobriment nutricional i minimitza la inequitat. Tot això ho fa oferint una cistella individualitzada a cada família, donant un tracte més personal als beneficiaris, però amb l’inconvenient que de cara a la gestió per part de la entitat no és òptim. És en el procés de canviar aquest projecte per a que sigui escalable a una entitat que rep milers de beneficiaris al mes que s’inicia un nou projecte, de creació i implementació d’un model que pugui ser implementat a El Rebost. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 19 3. Desenvolupament del model En aquest apartat es presenta el nou model amb totes les noves funcionalitats ja incorporades. En un primer apartat (3.1) es fa una introducció a com s’aborda el problema, tot seguit es presenta la nova formulació matemàtica (3.2) per a finalment explicar quines són les noves adicions que hem implementat al model (3.3). 3.1. Descripció del problema Per a la formulació del model és important tenir en compte els elements principals que hi participen, com ara els beneficiaris, els aliments, les necessitats nutricionals o els objectius d’optimització. La relació que tenen aquestes variables entre elles i com són definides és el que marca el tipus d’optimització que s’ha de realitzar. Beneficiaris L’entitat proporciona dades de cada família, incloent el número de membres, sexe i edat d’aquests. En funció del nombre de beneficiaris que tingui la família se li assignarà una de les quatre possibles cistelles (Petita, Mitjana, Gran o Súper Gran), per tant hi haurà varies famílies que rebran cistelles amb el mateix contingut, tot i potser tenir necessitats lleugerament diferents. Productes alimentaris Cada cistella estarà composta d’una combinació lineal de varis productes, tant dels que l’entitat tingui disponible com de possibles compres. Els aliments els considerem un sol paquet, ja que no es poden obrir per a donar una porció, per tant parlem de números enters. També es te en compte que alguns aliments venen en lots al comprar-los, i per tant, s’ha de comprar tot el lot (per exemple en un lot de llet venen 6 brics). De cada producte es te un registre de quines aportacions nutricionals dona, per a poder calcular el cobriment. Necessitats nutricionals El model tindrà en compte per cada beneficiari, les seves necessitats energètiques i tant de macro com de micronutrients. Aquestes necessitats són calculades a partir del DRI en funció de la seva edat i sexe. Diferenciem els dos tipus de nutrients donat que els macronutrients (carbohidrats, greixos i proteïnes) són els components dels aliments que el cos necessita per obtenir energia [9] i en general es necessiten en major proporció que els micronutrients, per això la diferenciació entre micro i macro. Pàg. 20 Memòria Els càlculs de cobriment nutricional seran fets amb l’energia i els micronutrients, donat que es pot trobar l’equivalència entre els grams de macronutrients i la seva aportació energètica en calories, per els carbohidrats i les proteïnes aporten 4 kcal/gram, mentre que els greixos aporten 9 kcal/gram. A demés es coneix el rang de percentatge de calories diàries que són adequades per a una dieta saludable [10], es recomana estar en un rang del 10-35% de les calories provinents de proteïnes, un 20-35% per els greixos i un 45-65% de carbohidrats, tot això tractant-se d’adults. Aquests valors seran orientatius de cara a la definició de les restriccions. Objectius d’optimització Per a trobar la distribució òptima d’aliments en les cistelles necessitarem definir varis objectius, aquests són: - Minimitzar el producte fresc sobrant per sobre del límit establert: El model conté una restricció forta que podria portar a problemes a la hora de buscar una solució. Per aquest motiu, el primer objectiu serà trobar si realment no hi ha cap altre opció que passar el límit establert, en el cas òptim, el valor del producte fresc sobrant per sobre del límit serà 0. - Maximitzar el cobriment nutricional: Donat que els aliments dels quals disposem i el pressupost són limitats, no es podrà obtenir un cobriment perfecte per a totes les famílies. L’objectiu serà trobar una solució que maximitzi el valor del cobriment de la família que menys coberta estigui. D’aquesta manera el model es focalitza en augmentar el cobriment de les famílies que pitjor cobriment tinguin. - Minimitzar la inequitat: Amb l’objectiu d’assegurar que el repartiment d’aliments és el més equitatiu possible es defineix una funció per a donar un indicador del nivell d’inequitat en la solució del model. Aquest indicador divideix el sumatori de la diferència entre la proporció d’aliments assignats per beneficiari (∆) per totes les cistelles i possibles mides de família, per el cardinal del conjunt utilitzat, és a dir, es divideix entre el número d’elements del sumatori, obtenint així la mitjana. Optimització d’un sol nivell i optimització lexicogràfica relaxada de dos nivells Per el model s’ha decidit fer dos optimitzacions diferents, la primera sent una optimització mono objectiu, en la que es mira de minimitzar el valor del producte fresc sobrant per sobre del límit permès (𝑒𝑥𝑡𝑞𝑛𝑒𝑓). Un cop s’ha trobat el valor òptim, es defineix com a restricció per a la següent fase de la optimització per a que el valor no augmenti. Tot seguit es fa una optimització multi objectiu, utilitzant el mètode lexicogràfic. En aquests Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 21 tipus de mètodes les funcions a ser optimitzades s’ordenen per importància (triat per el programador). Aquest mètode, en principi, un cop ha trobat el valor òptim d’una funció objectiu no permet que aquest empitjori als següents nivells, però si se li permet un petit marge controlat per a empitjorament, conegut com a relaxació, llavors el model pot trobar noves solucions, mentre alhora es redueix la possibilitat de que resulti en una solució no factible. El model doncs farà el següent: un cop triat l’ordre en que es vol optimitzar les funcions, la primera és optimitzada. A continuació la segona funció és optimitzada, amb la restricció addicional del valor trobat al primer nivell afegint una petita tolerància relativa δ2 (error màxim permès respecte el valor òptim trobat). La funció objectiu del primer nivell seguirà estant present al segon, però afegint una constant ε2 per assegurar que la solució trobada és un òptim de Pareto. Taula 1: Optimització Mono Objectiu i Multi Objectiu amb mètode lexicogràfic. Mono Objectiu: Nivell inicial [𝑚𝑖𝑛] 𝑓1→𝑓1∗ Multi Objectiu: Primer nivell [𝑚𝑎𝑥] 𝑓2→𝑓2∗ s.t.: 𝑓1≤𝑓1∗ Segon nivell [𝑚𝑖𝑛] 𝑓3− 𝜀2·𝑓2→𝑓3∗ s.t.: 𝑓1≤𝑓1∗ 𝑓2≥𝑓2∗·(1−𝛿2) 3.2. Formulació matemàtica A continuació es presenta la formulació matemàtica del model utilitzat per a solucionar el problema d’optimització. Com s’ha mencionat anteriorment el model proposa una repartició dels aliments dels quals es disposen en cistelles, que seran assignades a les famílies en funció del nombre de beneficiaris que siguin buscant maximitzar o minimitzar certs paràmetres. Es divideix la formulació del model en cinc components. En primer lloc els conjunts (3.2.1), definits com a una col·lecció d’elements que comparteixen alguna característica o tenen algun element comú [11]. Aquests conjunts es poden entendre com a llistes no ordenades d’elements, però no tenen valors numèrics associats, per exemple el primer conjunt (ℐ) defineix el conjunt d’elements que es poden repartir, però no la quantitat, això es defineix al següent apartat. Es tindran conjunts generals, i d’altres més específics, ja que de cara a l’execució del codi en Pàg. 22 Memòria Python aplicar les equacions a menys elements implica menys temps i menys recursos computacionals. S’han de definir també els paràmetres, o dades (3.2.2) del model, aquests són els valors fixes, que es coneixen des de un principi i no variaran al llarg del procés d’optimització. Poden estar en forma de matriu, vector o bé ser un valor escalar i quedaran totalment definits un cop acabat el pre-procés. Tot seguit tenim les variables de decisió (3.2.3), aquestes també són variables numèriques, però seran les que el model utilitzi per a trobar la millor solució possible, per tant al llarg del procés d’optimització aniran canviant. Donat que es treballa amb un MILP, aquestes variables de decisió poden ser definides com a contínues, enteres o binàries (que es troba dintre del conjunt d’enters). En quart lloc es troben les funcions objectiu (3.2.4), com el nom suggereix, marquen els objectius del model, ja que serà el valor escalar de la funció el que el model estigui minimitzant o maximitzant. Finalment, les restriccions (3.2.5), funcions que defineixen el model, limitant les solucions al imposar les condicions que ens interessin. 3.2.1. Conjunts ℐ Conjunt d’aliments disponibles, en paquets. (𝑖∈ℐ) ℐℛ Subconjunt d’aliments restringits (donat que a alguns productes se’ls hi pot posar un nombre màxim de paquets per cistella, amb la finalitat d’evitar que el model assigni molts paquets del mateix aliment a una mateixa família). (ℐℛ⊆ℐ) ℐℒ Subconjunt d’aliments adquirits en lots. (Per exemple en un lot de llet hi ha sis paquets de llet). (ℐℒ⊆ℐ) ℐ𝒫𝒞 Subconjunt d’aliments que es poden comprar. (ℐ𝒫𝒞⊆𝒥) ℐ𝒫𝒞ℳ Subconjunt d’aliments que es poden comprar i que tenen una quantitat mínima de compra. (ℐ𝒫𝒞ℳ⊆𝒥𝒫𝒞) ℐℳ𝒟 Subconjunt d’aliments que han de ser distribuïts en múltiples d’un número (per exemple la llet s’ha de repartir en lots de 6). (ℐℳ𝒟⊆𝒥) ℐℱ𝒫 Subconjunt d’aliments classificats com a frescos. (ℐℱ𝒫⊆𝒥) Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 23 ℱ Conjunt de famílies (cada família te un número assignat). (𝑓∈ℱ) 𝒩 Conjunt de nutrients. (𝑛∈𝒩) 𝒩𝐸−𝑚 Subconjunt de nutrients, concretament energia i micro-nutrients. (𝒩𝐸−𝑚⊆𝒩) ℬ Conjunt de les cistelles del model, cada una representada per un número que indica la seva mida, ordenat de petit a gran. (𝑏∈ℬ) ℳ Conjunt de possibles mides de famílies. (𝑚∈ℳ) 𝐴𝐿𝑏 Subconjunt d’aliments que poden ser assignats a la cistella 𝑏. (𝑏∈ℬ, 𝐴𝐿𝑏⊆ℐ) 𝐵𝐾𝑖 Subconjunt de cistelles a les quals l’aliment 𝑖 pot ser assignades. (𝑖∈ℐ, 𝐵𝐾𝑖⊆ℬ) 3.2.2. Dades/Paràmetres 𝑆𝑖 Quantitat de l’aliment i, en paquets, que cal distribuir. (𝑖∈ℐ) 𝐴𝑖,𝑛 Quantitat de nutrient n per cada aliment i. (𝑖∈ℐ;𝑛∈𝒩) 𝐷𝑅𝐼𝑓,𝑛 Ingesta Diària de Referència Dietètica per família 𝑓 del nutrient n. (𝑓∈ℱ;𝑛∈𝒩) 𝑇𝑓 Tipus de cistella assignada a la família 𝑓. (𝑓∈ℱ, 𝑇𝑓⊆ℬ) T𝑀𝑚 Tipus de cistella assignada a una família amb m beneficiaris. (𝑚∈ℳ, 𝑇𝑀𝑚⊆ℬ) 𝑁𝐹𝑏 Número de famílies assignades a la cistella 𝑏. (𝑏∈ℬ) 𝑃𝑖 Preu per paquet de l’aliment i. (𝑖∈ℐ) 𝑄𝑖 Número de paquets de l’aliment 𝑖 per cada lot comprat. (𝑖∈ℐℒ) 𝑀𝑃𝑖 Número mínim de paquets de l’aliment i que s’han de comprar, en cas de ferho. (𝑖∈ℐ𝒫𝒞ℳ) 𝑀𝐷𝐶𝑖 Número del qual l’aliment 𝑖 ha de ser múltiple al ser distribuït a les cistelles (𝑖∈ℐℳ𝒟) Pàg. 24 Memòria 𝐵𝐷 Pressupost total per la setmana estudiada. 𝐷 Número de dies en un període. 𝐿𝐵𝑖,𝑏 Número màxim de paquets d’aliment 𝑖 que poden ser assignats a la cistella 𝑏 (𝑖∈ℐℛ;𝑏∈ℬ) 𝐴𝐸𝐷 Número total d’aliments secs no assignats a cap cistella permès. Calculat com un percentatge del total d’aliments no frescos: ∑𝑆𝑖 𝑖∈ ℐ\ ℐℱ𝒫 . 𝐴𝐸𝐹 Número total d’aliments frescos no assignats a cap cistella permès. Calculat com un percentatge del total d’aliments frescos: ∑𝑆𝑖 𝑖∈ ℐℱ𝒫 . YMIN Número mínim d’aliments diferents que hi ha d’haver a cada cistella. En el nostre cas queda fixat a 32, basant-nos en execucions utilitzant el model anterior amb múltiples conjunts de dades, en les que es buscava maximitzar aquest valor. 3.2.3. Variables de decisió Variables principals x𝑏𝑖,𝑏∈ ℤ+ Quantitat d’aliment i, en paquets, assignats a la cistella b. (𝑏∈ℬ; 𝑖∈𝐴𝐿𝑏) x𝑝𝑖∈ ℤ+ Quantitat d’aliment i, en paquets, comprats. (𝑖∈ℐ𝒫𝒞) Variables auxiliars 𝑞𝑛𝑒𝑖∈ ℤ+ Quantitat d’aliment i, en paquets, que queden sense assignar a cap cistella. (𝑖∈ℐ) co𝑣𝑓,𝑛∈ ℝ+ Cobriment nutricional del nutrient n per la família 𝑓. (𝑓∈ℱ;𝑛∈𝒩𝐸−𝑚) 𝑦𝑖,𝑏∈{0,1} 1 si l’aliment i s’assigna a la cistella b. (𝑏∈ℬ; 𝑖∈𝐴𝐿𝑏) 𝑦𝑝𝑖∈{0,1} 1 si l’aliment i es compra (𝑖∈ℐ𝒫𝒞ℳ) 𝑛𝑝𝑏∈ ℤ+ Número d’aliments diferents que s’assignen a una cistella b. (𝑏∈𝐵) 𝑚𝑖𝑛𝑐𝑜𝑣∈ ℝ+ Mínim cobriment nutricional de tots els nutrients i famílies. 𝑚𝑖𝑛𝑛𝑝∈ ℤ+ Mínim número d’aliments diferents assignats a una cistella. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 25 𝑥𝑏𝑚𝑖, 𝑚∈ ℝ+ Proporció de paquets de l’aliment i per beneficiari assignats a famílies amb m membres. (𝑚∈𝑀; 𝑖∈𝐴𝐿𝑇𝑀𝑚) ∆𝑖,𝑚,𝑘∈ ℝ+ Diferència absoluta entre la proporció d’aliment i assignat a famílies amb m i 𝑘 beneficiaris. (𝑚∈ℳ;𝑘∈ℳ | 𝑘>𝑚; 𝑖∈𝐴𝐿𝑇𝑀𝑚∩ 𝐴𝐿𝑇𝑀𝑘) 𝑛𝑙𝑖∈ ℤ+ Número de lots comprats de l’aliment 𝑖. (𝑖∈ℐℒ) 𝑛𝑑𝑖,𝑏∈ ℤ+ Número de lots de l’aliment 𝑖 assignats a la cistella 𝑏. (𝑖∈ℐℳ𝒟;𝑏∈𝐵𝐾𝑖) 𝑒𝑥𝑡𝑞𝑛𝑒𝑓∈ ℤ+ Total d’aliments frescos no assignats per sobre del límit permès (AEF). 3.2.4. Funcions objectiu Minimització del producte fresc sobrant per sobre del permès: (1) [𝑚𝑖𝑛] 𝑓1=𝑒𝑥𝑡𝑞𝑛𝑒𝑓 Maximitzar el mínim cobriment nutricional: (2) [𝑚𝑎𝑥] 𝑓2=𝑚𝑖𝑛𝑐𝑜𝑣 Maximitzar la equitat (minimitzar la inequitat): (3) [min] 𝑓3=∑ ∑ ∑ ∆𝑖,𝑚,𝑘𝑖∈𝐴𝐿𝑇𝑀𝑚∩ 𝐴𝐿𝑇𝑀𝑘 𝑘 ∈ ℳ | 𝑘>𝑚𝑚∈ℳ ∑ ∑ |𝐴𝐿𝑇𝑀𝑚∩𝐴𝐿𝑇𝑀𝑘| 𝑘∈ℳ, 𝑘>𝑚𝑚∈ℳ 3.2.5. Restriccions La primera restricció serà un balanç. La quantitat de paquets de l’aliment 𝑖 que es tenen disponibles per la setmana (valor que ve fixat des de l’inici), més les compres per aquest mateix aliment han de ser iguals al total de paquets de l’aliment 𝑖 assignats per totes les famílies mes l’aliment sobrant no distribuït. Donat que la variable 𝑥𝑝𝑖 només està definida per els aliments que es poden comprar, s’ha de separar el balanç en dos, una per els elements del conjunt ℐ𝑃𝐶 i un altre per els elements fora d’aquest conjunt. (4.1) 𝑆𝑖+x𝑝𝑖= ∑(𝑁𝐹𝑏·𝑥𝑏𝑖,𝑏) 𝑏∈𝐵𝐾𝑖+𝑞𝑛𝑒𝑖 ∀𝑖∈ℐ𝑃𝐶 Pàg. 32 Memòria Dades auxiliars El model necessita dades per a poder realitzar els càlculs de cobriment nutricional. Dintre del codi de l’eina es presenta una carpeta amb totes les dades, en format Excel, que li podrien fer falta. Paràmetres d’execució del model En primer lloc, el programa accedeix a un arxiu que conté els paràmetres del model, similar a la taula que es mostra a continuació: Taula 4: Paràmetres d’execució del model NOM PARÀMETRE VALOR PARÀMETRE UNITATS TL1 7200 Segons TL2 7200 Segons TL3 140000 Segons relGAP 0,02 /u DELTA1 0,1 /u MAXCOV 2 /u EPSILON1 0,0001 /u P_FRESC 2 % P_SEC 5 % L’arxiu conté els paràmetres que defineixen el funcionament del model, aquests paràmetres són susceptibles a possibles canvis, ja sigui per petició de l’usuari o per a millorar els resultats, per tant és útil tenir-los tots en un mateix arxiu, facilitant l’accés i modificació. Alguns dels paràmetres que trobem al arxiu són els temps màxims d’execució de cada nivell (TL1, TL2 i TL3), el Gap relatiu per a considerar un resultat com a òptim (relGAP), el marge d’empitjorament permès per a la optimització multi objectiu (DELTA1), el cobriment màxim que es permet tenir per a qualsevol nutrient i família (MAXCOV), una constant petita que serveix per a assegurar que la solució sigui un òptim de Pareto (EPSILON1) i finalment el percentatge de producte fresc i sec que es permet deixar sense assignar a cap cistella. Propietats dels aliments distribuïts Per a futurs càlculs de cobriment nutricional ens cal saber les propietats de cada aliment que es te disponible per a ser repartit. Aquestes es treuen de la base de dades del Departament Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 33 d’Agricultura d’Estats Units, anomenada “Food and Nutrient Database for Dietary Studies” (FNDDS 2019-2020) [7]. Aquest arxiu que proporciona la composició nutricional dels aliments a distribuir haurà de ser actualitzada en el cas de que s’afegeixi algun aliment nou als possibles productes per distribuir. Com es comentarà al apartat 4.2, ara el codi, concretament la part del pre-procés, fa saltar un avís en el cas de que no es tingui informació sobre algun dels aliments a repartir, per a que el mateix usuari o algun membre de DOPS pugui afegir les dades i fer els càlculs complerts. Aquesta cerca no és exacte, donat que no trobarem exactament el mateix producte que s’està distribuint a la base de dades, per tant es busquen aliments genèrics que siguin suficientment semblants als de la entitat. Un cop acabat el procés de comparació entre els aliments que es tenen disponibles i els de la base de dades s’obté el següent DataFrame (Taula 5) que indica les propietats de cada aliment: Taula 5: DataFrame amb algunes de les propietats que es tenen d’una mostra d’aliments. Nutrients a incloure És part del pre-procés també decidir quins nutrients es faran servir per als càlculs nutricionals. Per a això hi ha un arxiu, anomenat ‘Nutrients_equivalence.xlsx’, que farem servir tant per a dir quins de tots els possibles nutrients farem servir per als càlculs, com per a deixar per escrit equivalències de noms entre diferents bases de dades que es fan. Necessitats nutricionals dels beneficiaris Com s’ha comentat a apartats anteriors, per a calcular els requeriments nutricionals dels beneficiaris es fa servir la base de dades publicada per el “National Center for Biotechnology Pàg. 34 Memòria Information” , el DRI o “Dietary Reference Intakes” [6]. Aquesta base de dades permet classificar en funció de l’edat els requeriments nutricionals que té el beneficiari. Tot seguit aquestes necessitats individuals es sumen per famílies, per a crear el DataFrame de la Taula 6: Taula 6: DataFrame amb les necessitats nutricionals de cada família. Tant les dades que ha de proporcionar l’usuari com les dades auxiliars són manipulades únicament a la etapa de pre-procés. Un cop aquesta etapa ha acabat, totes les dades hauran estat tractades i seran enviades al codi del model per a realitzar els càlculs. Abans de passar a la fase de càlcul de distribució de cistelles, encara al pre-procés, es defineixen tots els conjunts i paràmetres que hem definit prèviament a l’apartat 3.2 de Formulació matemàtica. D’aquesta manera, un possible lector o editor del codi, amb la formulació al costat podrà entendre fàcilment que està fent cada variable i ens assegurem de que cada línia de codi tingui una funció per al càlcul final. Finalment la sortida del pre-procés seran tres diccionaris, un per els conjunts, un altre per els paràmetres, i finalment un per als paràmetres d’execució del model. Aquests tres diccionaris seran els que el codi del model farà servir per a obtenir els conjunts i dades que necessita, donat que ja han processat tots els arxius. 4.1.2. Execució model Ara que els elements necessaris per a la execució del model han estat creats, els importem a la funció del model. Com hem comentat abans tenir tots els conjunts definits igual que a la formulació matemàtica fa el procés més senzill. Només queda inicialitzar el model. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 35 Per a solucionar el problema d’optimització MILP farem servir la biblioteca PuLP, un software de lliure accés que està pensat per a descriure problemes d’optimització linears com a models matemàtics [12]. La llibreria és capaç de fer servir solvers tals com GLPK, CPLEX, GUROBI o el més comú i que es farà servir per a les execucions en aquest treball, el CBC MILP Solver (versió 2.10.3), que segueix el mètode Branch and Cut [13]. Es fa servir aquest programari de lliure accés pensant en que els futurs usuaris és possible que no tinguin llicència per a fer servir solvers comercials. El solver busca una solució que s’apropi tant al òptim com sigui possible, sempre complint les restriccions del model, i quan acaba podem exportar les variables amb els seus valors finals. Aquestes variables del model que representen la solució final, com poden ser la quantitat d’aliment assignat a una cistella (𝑥𝑏), el cobriment de cada nutrient per família (𝑐𝑜𝑣) o la quantitat d’aliments no destinats a cap cistella (𝑞𝑛𝑒) entre d’altres, així com els valors de les funcions objectiu són enviades a la última fase del codi, el post-procés, en forma de diccionari. 4.1.3. Post-procés Finalment es recopilen totes les dades que es tenen de l’execució, tant les obtingudes al preprocés com els resultats del model, i es genera automàticament un fitxer Excel amb totes les dades que poden ser rellevants per a analitzar si el model està funcionant com era esperat. Gràcies al solver podem saber el temps d’execució de cada nivell, així com el GAP relatiu i el valor final de la funció objectiu. 4.2. Millores i canvis menors En una primera revisió del codi que s’agafa com a punt de sortida per al projecte, s’identifiquen alguns aspectes que poden ser millorats i que s’afrontaran de cara a la programació de la nova eina. Com s’ha comentat al apartat d’objectius, es busca fer noves implementacions al model (això serà tractat al següent apartat), i crear un codi més robust i compacte, per a facilitar una possible generalització del codi i poder-ho implementar en altres entitats de caire similar. A continuació es comenten els canvis que s’han fet en el codi: - S’han detectat aliments que se li proporcionaven al model i que no eren comptats per la distribució donat que no es tenien dades nutricionals, a continuació s’enumeren, juntament amb la referència de l’equivalent trobat a la base de dades: els Embotits (FNDDS 526), les llaminadures (FNDDS 5162) i la pizza (FNDSS 3343). S’ha afegit al arxiu Excel les dades corresponents. També s’han modificat dades de l’arxiu de composició nutricional dels aliments, com per exemple dels ous, donat que en un paquet en venen 12 però les propietats nutricionals es corresponien a un sol ou. Pàg. 36 Memòria - S’afegeix una funció al pre-procés que notifica sobre els aliments que no entraran al càlcul de les cistelles, això es dona quan un aliment no te estoc i tampoc es pot comprar per tant és impossible que es pugui assignar a cap cistella. - S’afegeix una alarma en cas de que un dels aliments del model no tingui dades nutricionals per a que l’usuari pugui afegir les dades pertinents, i tenir en compte que l’optimització es farà sense tenir en compte aquest aliment. - Totes les dades necessàries per als càlculs del model (conjunts, paràmetres i variables) són guardades en diccionaris, facilitant la seva extracció i compactant el codi. - Es separen clarament les fases d’execució, calculant tots els conjunts i paràmetres al pre-procés i enviant-los al model (on es fan els càlculs) i al post-procés (per a compactar els resultats obtinguts. - Es defineixen les variables del model com a subconjunts, igual que a la formulació, per a que el solver treballi amb menys variables, necessitant així menys memòria. - Es canvia la fórmula per al càlcul de la equitat, donat que ara pot haver aliments que no estiguin a dos cistelles que s’han de comparar, definim ∆𝑖,𝑚,𝑘 només per les dos cistelles 𝑚 i 𝑘 que comparteixin l’aliment 𝑖, per tant el sumatori ha de recórrer els mateixos elements, i el cardinal ha de ser tant sols de la intersecció entre els aliments que poden ser assignats a cada una de les cistelles per cada combinació. - Les famílies amb nadons de menys de dos anys queden comptabilitzades, que en el model anterior quedaven exclosos dels càlculs - Des de el Rebost demanen que el model accepti fitxers OpenDocument, per tant s’afegeix una funció que és capaç d’interpretar fitxers amb extensió ‘.ods’. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 37 5. Resultats En aquest apartat s’analitza: - L’impacte que te el percentatge de producte sec i fresc que es pot deixar sense repartir en els altres paràmetres del model - Com afecta a la nutrició i repartició dels aliments definir en comptes de només 4 cistelles, 6 i 8, permetent així fer conjunts de beneficiaris més homogenis. Primer al apartat d’experimentació es fa un anàlisi dels resultats que s’aconsegueixen amb el nou model. Aprofitant les noves característiques afegides, es fa un anàlisi de sensibilitat (5.1.1) per a determinar quina combinació de paràmetres ens proporciona millors resultats. Tot seguit es farà un anàlisi relatiu (5.1.2) per a veure com afecta a la solució el fet de tenir més cistelles disponibles per als beneficiaris, i poder decidir si val la pena canviar el mode d’operació de El Rebost. Cal comentar que tot i que l’objectiu és implementar les execucions en un ordinador local a la entitat, en aquest cas, El Rebost, per a fer els càlculs s’ha utilitzat Multivac, un clúster de càlcul de DOPS [14]. Per a assegurar que el codi és possible utilitzar-lo en un ordinador amb capacitat estàndard, es limita els recursos que es fan servir per cada execució a 1 CPU i 2 GB de memòria. 5.1. Experimentació Per a la experimentació es fan servir dades preparades prèviament. Serà útil fer servir aquestes dades perquè es tenen els resultats de les execucions amb el codi anterior amb aquestes, per tant es podrà comparar directament els resultats obtinguts i avaluar com funciona el nou model. Les dades que fem servir són les de les cinc setmanes d’abril del 2024, les setmanes es caracteritzen per el seu dia d’inici, sent doncs la primera setmana 24_04_01, la segona 24_04_08 i així fins a la última setmana, la 24_04_29. Cada una de les setmanes té dades diferents de beneficiaris que els tocava recollir la cistella durant la setmana, així com de producte a repartir (producte arribar per donacions i comprat). Per a poder comparar amb criteri els nous resultats amb els del model antic, configurem els nous paràmetres per a que no siguin molt més restrictius, per exemple només es permetrà repartir el producte ‘Plats preparats’ a la cistella Súper Gran (tal i com estava configurat al model antic). Es pot veure a la Taula 7 un resum de cada una de les setmanes: Pàg. 38 Memòria Taula 7: Resum de les principals característiques de les dades per cada setmana. Setmana 24_04_01 24_04_08 24_04_15 24_04_22 24_04_29 Productes (I) 43 44 45 41 41 Famílies (J) 117 259 268 229 124 Total de beneficiaris (TB) 327 704 733 684 340 Mides de les famílies (M) [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7] 5.1.1. Anàlisi de l’impacte dels paràmetres % màxim de producte fresc i sec per repartir i Gap Durant el refactoring del codi original, s’ha canviat com és enfocat el problema d’optimització, i com a conseqüència ara hi ha tres paràmetres que afecten al resultat de l’execució que han quedat pendents de definir. Són aquests: Gap: Representa la diferència entre el valor òptim de la funció objectiu trobat amb el problema relaxat i el MIP ( Mixed-Integer Problem ). Quan aquest arriba a el valor que es decideix, es considera la solució com a òptima i es passa a la següent fase. Producte fresc: Percentatge de productes frescs respecte els que es tenen originalment en estoc que es poden deixar sense repartir. Producte sec: Percentatge de productes secs respecte els que es tenen originalment en estoc que es poden deixar sense repartir. El primer pas de la experimentació computacional és per tant, decidir a quins valors es fixen els paràmetres, un cop fixats seran els que farem servir de cara als següents experiments. Agafant com a base resultats de les execucions amb el model antic, s’escullen sis combinacions de valors d’aquests paràmetres que poden donar bons resultats. S’estudien dos possibles valors per el Gap, 2 i 5%. Combinats amb aquests dos valors s’estudien tres combinacions de percentatge de producte fresc i sec que es pot deixar sense repartir, les combinacions són respectivament 2-5%, 1-3%, 0,5-2% per a fresc i sec respectivament. En termes generals s’espera que un gap més gran signifiqui un menor temps d’execució però solucions lleugerament pitjors, i percentatges de sobrant majors donarà millors resultats d’equitat però el producte sobrant serà major. Per a poder analitzar quina de les sis possibles combinacions ens dona millors resultats, es Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 39 defineixen els aspectes de la solució trobada que són importants. Interessa primerament que el resultat tingui el màxim mínim cobriment nutricional, mentre la inequitat volem que sigui el menor possible. També interessa que l’execució no sigui extremadament llarga, per això ens fixem en el temps total d’execució. Un altre aspecte important a tenir en compte és el Gap que s’assoleix a cada un dels nivells de la optimització, volent que aquest estigui el més proper a 0 o al valor de Gap definit prèviament. Finalment però no menys important, cal vigilar la quantitat d’aliments frescs i secs que la solució deixa sense repartir, volent que aquests siguin el menor possible. Com es veurà, no és possible trobar una combinació de paràmetres que ens doni el millor resultat en tots aquests aspectes, per tant s’ha de triar quins aspectes considerem que són més importants per al nostre model. Fent servir les dades de les cinc setmanes proporcionades per el Rebost, combinades amb les sis possibles combinacions de paràmetres ens dona un total de 30 instàncies. Tot seguit s’agafen els resultats per cada combinació de paràmetres i es fa la mitjana dels valors a analitzar entre totes les setmanes per a que no influeixin en la decisió, podem trobar els indicadors de totes les 30 instàncies al Annex 1. A continuació, a la Taula 8, es mostren les sis combinacions que s’han esmentat anteriorment: Taula 8: Mitjana de cada indicador per cada combinació de totes les setmanes combinades. Producte fresc (%) Producte sec (%) Gap Mínim cobriment Inequitat Temps total Gap 1 Gap 2 Gap 3 Sobra Fresc Sobra Sec 0,5 2 2 0,359 0,234 5,339 0 2,8 19,4 22 171,8 0,5 2 5 0,353 0,233 3,610 0 4,2 18,2 23,2 173,8 1 3 2 0,361 0,213 4,462 0 2 7 46,6 257,4 1 3 5 0,354 0,214 3,127 0 4,2 10,6 42 261,4 2 5 2 0,362 0,208 5,055 0 2,2 8 87,4 438,2 2 5 5 0,354 0,201 2,904 0 3,8 6,2 82,8 442,4 Es pot confirmar de la taula que a menor Gap, major temps d’execució, com era d’esperar. També s’aprecia que en general sembla que el cobriment es manté relativament constant mentre que la inequitat si que varia significativament amb els canvis de paràmetres. Els resultats es mostren gràficament ara (Dades al Annex 2): Pàg. 40 Memòria Figura 3: Gràfic mostrant tres indicadors, en diagrama de barres el producte sobrant sec (taronja) i fresc (blau), i en gràfic lineal els valors de mincov (verd) i inequitat (blau). Es pot apreciar millor a la Figura 3 com canviar els paràmetres, modifica els resultats obtinguts. Al gràfic tenim al eix de les ordenades, cada una de les sis combinacions, començant per els percentatges 05-1% per els Gaps 2% i 5% als dos primers gràfics de barres respectivament. Al eix de les abscisses tenim tres llegendes, a l’esquerra la quantitat de paquets sobrants, i a la dreta tant el valor de mínim cobriment com el valor d’inequitat. Del gràfic de barres podem veure que com s’esperava, quan es dona més marge de productes a deixar sense repartir, el model aprofita aquest paràmetre i el número de sobres augmenta. Fixant-se només en això, la millor opció seria agafar la combinació que amb menys sobres, però s’aprecia que com a menor producte sobrant, major inequitat. D’altre banda, també s’aprecia que el mínim cobriment nutricional es manté relativament constant en totes les combinacions, amb un petit decrement quan el Gap augmenta. Donat que tots els canvis en paràmetres tenen efectes en resultats del model, fent que alguns aspectes millorin i d’altres empitjorin, no hi ha una sola solució correcte, per tant s’escull una que s’adeqüi el millor possible a les prioritats del Rebost. Com a principal prioritat es te reduir el sobrant de productes, per tant la solució de 2-5% de producte sobrant queda descartada, per escollir entre les altres dos s’aprecia que mentre que el cobriment es manté pràcticament constant entre les dos combinacions, la inequitat augmenta significativament al disminuir el percentatge, per tant sembla que la combinació adient és 1 % de productes frescs i 3% de productes secs a deixar sense repartir. Finalment per a acabar de definir la combinació de paràmetres escollida, cal fixar-se en el Gap. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 41 Un major Gap implica en tots els casos un menor mínim cobriment, tot i que la diferència és petita. També es veu a la taula anterior que augmentar el Gap redueix el temps d’execució, tot i que en cap cas s’arriba de mitja a poder trobar un òptim dintre del marge definit per el Gap en el tercer nivell. Encara que per un Gap del 2% tenim un augment del 43% en el temps d’execució, decidim escollir aquest valor per a que el model intenti trobar la millor solució possible, encara que sigui utilitzant més temps. Per tant decidim seguir la experimentació amb els paràmetres mostrats a la Taula 8: Taula 9: Valors dels paràmetres escollits. Percentatge producte fresc Percentatge producte sec Gap 1 % 3 % 2 % Per a il·lustrar com el model gestiona els paràmetres, compararem dos solucions obtingudes per una de les setmanes (24_04_01), comparem els casos de 0,5-2 % (Taula 9) i 1-3% (Taula 10) per a un gap del 2%, en blau els productes frescos i en groc els secs: Cas 0,5-2% Taula 10: Resultats distribució de paquets per cistelles en el cas de 0,5-1%. Petita Mitjana Gran Súper Gran Estoc Compra Sobrant Brou (Bric 1000g) 1 2 4 6 211 87 0 Carn (minves) (Paquet 500g) 1 1 1 2 130 6 Formatge (Unitat 250g) 1 2 3 4 164 85 0 Fruita fresca (Bossa 1000g) 2 4 8 12 596 0 Iogurt (Pack de 4 500g) 1 2 4 6 122 176 0 Llegum cuit (Pot 400g) 1 2 4 6 155 143 0 Mongeta seca cuita (Pot 560g) 1 3 4 6 197 142 0 Ous (1/2 Dotzena 73g) 1 2 3 5 166 90 0 Pa (Unitat 500g) 1 1 2 2 162 3 Peix (LLUÇ) (Unitat 540g) 0 0 0 0 0 0 0 Pollastre (cuixes) (Porció 1000g) 0 0 0 0 3 0 3 Pollastre Sencer (Paquet 1200g) 0 0 0 2 14 0 Tonyina (Pack de 3 240g) 0 0 0 0 0 0 0 Verdura fresca (Bossa 1000g) 1 6 5 6 497 0 Embotits (Unitat 250g) 0 1 1 3 96 1 0 Arròs (Paquet 1000g) 1 2 4 6 243 55 0 Beguda vegetal (Bric 1000g) 1 3 4 6 0 339 0 Brioixeria (Bossa 250g) 1 2 3 4 252 3 Brou (pastilles) (Caixa 120g) 0 0 0 0 0 0 0 Cacau (Pot 400g) 1 1 1 3 149 18 Cereals (Paquet 500g) 1 1 3 3 68 133 0 Cigrons cuits (Pot 560g) 1 3 5 7 194 187 0 Pàg. 48 Memòria 6. Planificació Per a dur a terme aquest projecte, s’ha seguit el desenvolupament mostrat al diagrama de Gantt de la Figura 6: 2024 2025 M9 M10 M11 M12 M1 M2 M3 M4 Introducció a la optimització Plantejament objectius Familiarització amb les eines Documentació estat actual Lectura formulació matemàtica Definir abast del treball Millora del model Nova formulació Redacció nou codi Proves de funcionalitat Experimentació Sensibilitat Relatiu Anàlisi de resultats i conclusió Anàlisi de les solucions Conclusions Redacció memòria Revisió memòria Reunions de seguiment Figura 6: Diagrama de Gantt mostrant la organització del projecte. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 49 7. Estudi econòmic Aquest apartat fa una avaluació del cost del projecte de millora de la eina implementada al centre social El Rebost. L’objectiu des de un principi era implementar noves funcionalitats al model i poder fer un codi més generalitzable per a permetre que altres entitats també el puguin utilitzar. Es considera que el projecte va iniciar el 16 de Setembre de 2024, fins al dia 31 de Gener de 2025 es fa una feina de 4 hores per dia feiner. El tram que queda des del 1 de Febrer fins al 22 d’Abril es considera que es treballa 1 hora diària en el projecte. En total la feina ha suposat 67 dies de 4 hores de feina i 44 dies de una hora cada un, que en total computa en 312 hores de feina dedicades al projecte. A això se li sumen 25 hores extres per a comptabilitzar els dies que s’ha treballat més de l’estimat. Per tant un total de 337 hores. Si es valoren les hores treballades en 15 €/h , les hores treballades surten a 5.055 €. Per a realitzar el treball ha estat necessari un ordinador del qual considerarem l’amortització donat que no ha estat comprat per a aquesta finalitat sinó que s’ha assignat. Al estar en ús 8 mesos, si estimem que un ordinador pot durar uns 5 anys funcionant correctament i costa aproximadament uns 2.500 €, podem estimar la amortització en 333,33 €. L’últim punt a tenir en compte són les despeses de llum i aigua tant de casa com de la oficina, que s’estimen en uns 0,5 €/dia, per tant durant els quatre mesos suma 55 € de despeses. Per tant el cost total és de: Taula 14: Resum de les despeses durant el projecte. CONCEPTE DESPESA (€) Hores treballades 5.055 Amortització ordinador 333,33 Despeses varies 55 TOTAL 5.443,33 TOTAL (amb IVA 21%) 6.586,1 Pàg. 50 Memòria 8. Estudi ambiental Al estar col·laborant directament amb una entitat com El Rebost, que treballa per a evitar el malbaratament d’aliments i alhora en millorar els hàbits alimentaris de beneficiaris que no poden arribar a comprar aliments de qualitat, poder fer una eina que els ajudi en aquesta tasca farà que la forma en que es tracten els aliments sigui molt més eficient, ajudant a reduir els aliments que queden sense repartir. Actualment el malbaratament d’aliments és un problema d’escala global i tot i que és cert que el 42% de les pèrdues d’aliments en bones condicions ve de l’àmbit familiar i el 39% del procés de fabricació [15], tenir un banc d’aliments que sigui capaç de distribuir eficientment els aliments que li arriben pot fer que sigui capaç de gestionar més volum, rebre més donacions i donar suport a més famílies. El principal impacte que ha tingut aquest projecte en l’eina de El Rebost a nivell ambiental ha sigut la implementació de la separació entre producte fresc i producte sec a l’hora de distribuirlo en les cistelles, permetent així que el model s’enfoqui més en repartir els aliments que tenen major risc de ser rebutjats a curt termini. Reduir al màxim el producte que es perdrà i no servirà per alimentar a famílies que ho podrien necessitar és una part clau de la millora del procés d’entrega d’aliments. Per això és molt important posar especial atenció a aquells productes que són més sensibles al pas del temps i el nou model és capaç d’afrontar aquesta problemàtica i posar-li solució. També cal tenir en compte que fer servir una eina com la que es presenta al projecte te també la capacitat de reduir la càrrega de feina als voluntaris de la entitat, fent que la labor de crear les cistelles per els beneficiaris sigui més automatitzada, permetent doncs que es puguin focalitzar en altres aspectes com podria ser logística o fins i tot reduir les hores que calen de feina per part dels voluntaris, fent que el procés sigui més eficient energèticament. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 51 9. Estudi social i d’igualtat de gènere La inseguretat alimentària és un problema que podria semblar que afecta a tothom per igual, però mentre el 29,3% de la població patia inseguretat l’any 2021, estudis realitzats per la ONU en col·laboració amb altres entitats indiquen que existeix una desigualtat de gènere en la inseguretat en respecte a l’alimentació, sent aquesta més pronunciada a països en vies de desenvolupament, per exemple a América Llatina i el Carib la inseguretat alimentària afecta de manera moderada o greu a un 45,2% de les dones, mentre que per als homes el valor és de 33,9% [16]. Mirant les estadístiques dels Objectius de Desenvolupament Sostenible de la ONU Dones [17], concretament els indicadors de “Fam Zero”, es pot veure clarament la desigualtat. A nivell nacional, hi havia 422 mil dones més que homes patint inseguretat alimentària al 2021 (sent 1836,1 milers de dones comparat amb 1413,9 milers d’homes). Aquesta diferència es fa evident també a nivell mundial, amb 119 milions de dones més afectades en comparació amb els homes. Afegit a aquesta desigualtat, tenim el fet de que, en la societat actual, les dones solen ser les responsables de la nutrició a la família, tenint per tant una major càrrega emocional que pot causar estrès i malestar dintre de la mateixa família. Definir cistelles equilibrades alleugereix aquesta càrrega. Tenir la oportunitat de col·laborar amb una entitat com El Rebost permet tenir un impacte positiu sobre la comunitat en risc d’exclusió social i econòmica de Terrassa, Catalunya. Tractant una inseguretat que afecta als més desafavorits i donant un impuls a aquestes famílies, amb la esperança de que aquesta escletxa entre homes i dones es vagi tancant. Afrontar un problema com aquest és complex i es necessita un abast molt gran per a tenir impacte a nivell mundial, però el projecte ajuda a la possibilitat de que l’eina que s’està implementat a El Rebost pugui ser utilitzada en altres entitats per a optimitzar la seva forma de repartir aliments, implementant noves funcionalitats i reestructurant el codi, per a poder arribar a més gent necessitada d’aquests complements alimentaris. Pàg. 52 Memòria 10. CONCLUSIONS Al principi del projecte s’han marcat uns objectius clars que es volia assolir. En termes generals, aquest treball tractava de millorar un model, i el seu codi, que optimitza la distribució d’aliments en cistelles per a una entitat solidària. S’ha afrontat en primer lloc la modificació de la formulació matemàtica del model per a afegir noves funcions i donar als usuaris més capacitat de decisió sobre com volen distribuir els aliments. S’ha fet també el refactoring del codi, aconseguint que sigui més compacte i entenedor i detectant errors i redundàncies en el mateix codi que afectaven als resultats. A més a més, hem pogut demostrar després mitjançant experimentació computacional que el model compleix amb els nous requisits, demostrant doncs que el procés de refactoring i ampliació del model han funcionat. De cara al futur, aquest projecte encara pot recórrer camí i millorar en varis aspectes relacionats també amb els objectius que s’havien marcat, a continuació s’esmenten alguns aspectes en els que futures millores haurien de focalitzar els esforços: - Un dels principals objectius era generalitzar i fer més robust el model, i mentre s’ha aconseguit generalitzar parts del model, queden en el codi elements que el fan poc robust, i molt susceptible al format del fitxer que li és entregat com a dades de l’usuari. Seria molt interessant aconseguir que el pre-procés sigui capaç d’analitzar tot tipus de dades per exemple el cas més crític és que ara mateix el número de cistelles ve determinat per el codi, si canvies el número de cistelles que reparteixes has de modificar el codi i això no és òptim per a un hipotètic usuari que pugui voler canviar com reparteix els aliments. - Un altre aspecte que seria interessant mirar és comprovar com el model es comporta amb conjunts de dades més grans, seria doncs potser adequat deixar més temps d’execució i destinar més recursos, i comprovar si el model segueix sent capaç de trobar solucions. - Finalment, s’hauria de jugar amb els límits del codi, posant restriccions molt dures per a comprovar si el model pot trobar solucions igualment i com empitjoren aquestes. Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 53 11. Agraïments Agrair primerament a tots els membres de DOPS per l’ajuda i donar-me l’oportunitat de fer el treball final de grau en un projecte real que està tenint impacte en la vida de molta gent. Donar especial menció als meus tutors del treball, Marc i Pol, per tota la seva ajuda i paciència durant el treball, són dos professors magnífics. Gràcies als companys de despatx, Iker, Agustín, Pau i Melis per fer els dies de feina més divertits. Gràcies a la meva família per el seu suport incondicional i a la Sandra per recordar-me lo afortunat que soc i la sort que tinc de tenir bona companyia. Agraït d’haver tingut la oportunitat de fer el treball d’un tema que m’interessa rodejat de professionals. Pàg. 54 Memòria 12. Bibliografia Referències bibliogràfiques [1] Què és el Rebost? (s.f) [Online] (Accessible a: http://www.elrebostdeterrassa.cat/p/quees-el-rebost.html) [2] R. F. Ramirez, P. L. Vargas, O. S. Cardenas, (26 de Novembre, 2020) [Online], doi: 10.48082/espacios-a20v41n45p25 [3] M. Williams, O. Carlos, (19 de Febrer, 2007) “ Optimización y la Programación Lineal: Una introducción” [Online] (Accessible a: https://fglongatt.org/OLD/Reportes/RPT2007-07.pdf ) [4] Universidad de Alicante, Simulación y Optimización de los Procesos Químicos: TEMA 11: Introducción a la programación matemática con variables discretas. [Online] (Accessible a: https://rua.ua.es/dspace/bitstream/10045/19734/6/Introduccion_MILP.pdf ) [5] C. Villa, R. Labayrade, (Gener, 2011) “ Energy efficiency vs subjective comfort: A multiobjective optimisation method under uncertainty” [Online] (Acessible a: https://publications.ibpsa.org/proceedings/bs/2011/papers/bs2011_1619.pdf ) [6] National Institutes of Health: “Nutrient Recommendations and Databases” [Online] (Acessible a: https://ods.od.nih.gov/HealthInformation/nutrientrecommendations.aspx) [7] (USDA) Agricultural Research Service U.S. Department of agriculture (10 de Juliol, 2024): “Food Surveys Research Group: Beltsville, MD” [Online] (Accessible a: https://www.ars.usda.gov/northeast-area/beltsville-md-bhnrc/beltsville-human-nutritionresearch-center/food-surveys-research-group/docs/fndds-download-databases/ ) [8] P. Gil-Figuerola, M. Juanpera, A. Soler-Noguera, H. Ramalhinho, L. Ferrer-Martí, R. Pastor (Maig, 2025): “Optimising food baskets in a local food pantry: The case study of El Rebost” [Online], doi: https://doi.org/10.1016/j.cie.2025.111053 [9] C. Demarco, H. A. Dahl, The University of Texas (18 de Febrero, 2025): “Macronutrients 101: What to know about protein, carbs and fats”. [Online] (Accessible a: https://www.mdanderson.org/cancerwise/macronutrients-101--what-to-know-aboutprotein--carbs-and-fats.h00-159774078.html ) [10] S. Espinosa Salas, M. Gonzalez Arias, National Library of Medcine (8 d’Agost, 2023) “Nutrition: Macronutrient Intake, Imbalances, and Interventions” . [Online] (Accessible a: https://www.ncbi.nlm.nih.gov/books/NBK594226/ ) Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 55 [11] J. Oyarzún, “Álgebra y Geometría: Introducción a la Teoría de Conjuntos”. [Online] (Accessible a: https://www.matematicas.ciencias.uchile.cl/juaco/section-2.html) [12] S. Mitchell, A. Kean, A. Mason, M. O’Sullivan, A. Phillips, F. Peschiera, Pulp (2009): “Optimization with PuLP” . [Online] (Accessible a: https://coin-or.github.io/pulp/ ) [13] J. Forrest, R. Lougee-Heimer, “CBC User’s Guide” [Online] (Accessible a: https://coinor.github.io/Cbc/intro) [14] Institut d’Organització i Control de Sistemes Industrials: “Manual de Multivac” . Universitat Politécnica de Catalunya (UPC). BarcelonaTECH. [Online] (Accessible a: https://iocnet.upc.edu/doc/multivac/) [15] D. Hidalgo, J.M. Martín-Marroquín. IndustriAmbiente (Abril/Juny, 2020) “El desperdicio de alimentos, un problema global”. [Online] (Accessible a: https://www.industriambiente.com/media/uploads/noticias/documentos/AT_Desperdicios _alimentarios.pdf ) [16] FAO, FIDA, OPS, WFP, UNICEF. Organización de las Naciones Unidas para la Alimentación y la Agricultura. (2023) “Panorama regional de la seguridad alimentaria y nutricional – América Latina y el Caribe. Hacia una mejor asequibilidad de las dietas saludables” . [Online] doi: https://doi.org/10.4060/cc3859es; ISBN 978-92-5-137537-2 [FAO] [17] UNWomen Count “SDG: Indicator Dashnoard”. [Online] (Accessible a: https://acortar.link/5OlaBJ ) Bibliografia complementària [18] A. Martínez, “Programación entera”. [Online] (Accessible a: https://www.dma.uvigo.es/~aurea/Programaci%C3%9Bn_entera_2015.pdf ) [19] P. Gil Figuerola, M. Juanpera Gallel, L. Ferrer Martí, (02 de juny, 2023) “Optimització de la composició de les cistelles d’aliments: Aplicació de tècniques d’optimització multiobjecti per optimitzar la composició de les cistelles d’aliments tenint en compte criteris tècnics i socials”. Universitat Politécnica de Catalunya (UPC). [Online] (Accessible a: https://upcommons.upc.edu/handle/2117/388364 ) Pàg. 56 Memòria 13. Annex 13.1. A1. Resultats 30 instàncies Taula A1: Instàncies de cada setmana per cada una de les possibles combinacions de l’anàlisi de sensibilitat. Setmana P_fresc P_sec Gap mincov inequitat Temps total Gap1 Gap2 Gap3 Sobra Fresc Sobra Sec 24_04_01 0.5 2 2.0 0,392692 0,219301 4,558947 0 2 11 12 98 24_04_01 0.5 2 5.0 0,39161 0,216567 1,521719 0 2 5 12 102 24_04_01 1 3 2.0 0,392351 0,210867 3,476531 0 2 2 25 147 24_04_01 1 3 5.0 0,385636 0,208041 4,014167 0 4 7 25 153 24_04_01 2 5 2.0 0,394439 0,205609 4,806283 0 2 2 34 225 24_04_01 2 5 5.0 0,384587 0,19986 2,873792 0 4 5 39 251 24_04_08 0.5 2 2.0 0,342829 0,245078 6,002303 0 3 28 33 232 24_04_08 0.5 2 5.0 0,33779 0,229071 4,749025 0 4 19 33 226 24_04_08 1 3 2.0 0,344848 0,217573 5,074003 0 2 14 65 323 24_04_08 1 3 5.0 0,34512 0,232941 4,044722 0 2 23 40 342 24_04_08 2 5 2.0 0,346676 0,217079 4,952889 0 2 18 130 594 24_04_08 2 5 5.0 0,338251 0,203797 4,496092 0 4 11 113 590 24_04_15 0.5 2 2.0 0,332076 0,261647 6,3088 0 5 39 26 230 24_04_15 0.5 2 5.0 0,333679 0,261004 5,205772 0 5 37 33 236 24_04_15 1 3 2.0 0,342146 0,210955 5,595997 0 2 10 66 362 24_04_15 1 3 5.0 0,331967 0,209905 5,053875 0 5 13 65 362 24_04_15 2 5 2.0 0,338222 0,199918 6,042869 0 3 9 132 604 24_04_15 2 5 5.0 0,333924 0,194229 3,622508 0 4 5 126 604 24_04_22 0.5 2 2.0 0,319371 0,224771 4,854694 0 2 13 24 193 24_04_22 0.5 2 5.0 0,308572 0,247059 4,35065 0 5 25 23 198 24_04_22 1 3 2.0 0,319276 0,212189 4,776733 0 2 7 49 296 24_04_22 1 3 5.0 0,310744 0,211316 1,594517 0 5 5 50 293 24_04_22 2 5 2.0 0,319159 0,203107 4,122492 0 2 3 82 500 24_04_22 2 5 5.0 0,315299 0,203531 0,489908 0 3 5 93 501 24_04_29 0.5 2 2.0 0,406443 0,219438 4,971156 0 2 6 15 106 24_04_29 0.5 2 5.0 0,395149 0,209501 2,221347 0 5 5 15 107 24_04_29 1 3 2.0 0,407918 0,215492 3,388167 0 2 2 28 159 24_04_29 1 3 5.0 0,395149 0,209756 0,925403 0 5 5 30 157 24_04_29 2 5 2.0 0,409219 0,213165 5,349928 0 2 8 59 268 24_04_29 2 5 5.0 0,399315 0,202412 3,039906 0 4 5 43 266 Aplicació per a l’optimització del repartiment d’aliments en cistelles Pág. 57 13.2. A2. Mitjana de les combinacions de paràmetres Taula A2: Mitja dels resultats de la taula A1 classificats per combinació de paràmetres. P_fre sc P_sec Gap minco v inequi tat Temp s total Gap1 Gap2 Gap3 Sobra Fresc Sobra Sec 0,5 2 2 0,359 0,234 5,339 0 2,8 19,4 22 171,8 0,5 2 5 0,353 0,233 3,610 0 4,2 18,2 23,2 173,8 1 3 2 0,361 0,213 4,462 0 2 7 46,6 257,4 1 3 5 0,354 0,214 3,127 0 4,2 10,6 42 261,4 2 5 2 0,362 0,208 5,055 0 2,2 8 87,4 438,2 2 5 5 0,354 0,201 2,904 0 3,8 6,2 82,8 442,4