Análisis metaheurístico en la logística inversa de residuos

UNIVERSIDAD DE MÁLAGA E . T . S . d e I n g e n i e r o s I n d u s t r i a l e s Tesis Doctoral ANÁLISIS METAHEURÍSTICO EN LA LOGÍSTICA INVERSA DE RESIDUOS A n t o n i o S e r r a n o E l e n a U n i v e r s i d a d d e M á l a g a 2 0 1 5 AUTOR: Antonio Serrano Elena http://orcid.org/0000-0001-6228-0501 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es Departamento de Economía y Administración de Empresas E.T.S. de Ingenieros Industriales Universidad de Málaga ANÁLISIS METAHEURÍSTICO EN LA LOGÍSTICA INVERSA DE RESIDUOS Autor Antonio Serrano Elena Ingeniero en Automática y Electrónica Industrial Universidad de Málaga Directores Elvira Maeso González Dra. Ingeniera Industrial Profesora Titular de Universidad Universidad de Málaga Enrique Alba Torres Dr. Ingeniero en Informática Catedrático de Universidad Universidad de Málaga Málaga, 2015 Esta página se ha dejado en blanco intencionadamente El Dr. Enrique Alba Torres, Catedrático de Universidad del Departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga, y la Dra. Elvira Maeso González, Profesora Titular de Universidad del área de conocimiento de Organización de Empresas, adscrita al Departamento de Economía y Administración de Empresas de la Universidad de Málaga, Certifican que D. Antonio Serrano Elena, Ingeniero en Automática y Electrónica Industrial por la Universidad de Málaga, ha realizado en el Departamento de Economía y Administración de Empresas de la Universidad de Málaga, bajo sus direcciones, el trabajo de investigación correspondiente a su Tesis Doctoral titulada ANÁLISIS METAHEURÍSTICO EN LA LOGÍSTICA INVERSA DE RESIDUOS Revisado el presente trabajo, estimamos que puede ser presentado al tribunal que ha de juzgarlo, y autorizamos la presentación de esta Tesis Doctoral en la Universidad de Málaga. En Málaga, Octubre de 2015 Fdo.: Dr. Enrique Alba Torres Fdo.: Dra. Elvira Maeso González Esta página se ha dejado en blanco intencionadamente A Ana y Antonio Esta página se ha dejado en blanco intencionadamente I Agradecimientos Son muchas las personas a las que quiero mostrar mi gratitud, pero me gustaría dedicarlo especialmente a mi familia, a Ana y Antonio, por su paciencia y cariño. Quiero manifestar también mi agradecimiento a las siguientes personas: A mi directora de tesis, Elvira Maeso, por su dedicación y ayuda en todo momento. A mi también director de tesis, Enrique Alba, sin cuya inestimable ayuda en el conocimiento de los metaheurísticos habría sido imposible la realización de esta tesis. Gracias de nuevo a ambos, por su calidad humana, su desinteresado apoyo, su sabiduría, sus consejos, su paciencia... A Rafael Arjona, Director Gerente de LIMASA, a Javier Pazos, Jefe de División del CAM de LIMASA y a Ángel Castillo, Jefe de Explotación del Consorcio Provincial De Residuos Sólidos Úrbanos de la Diputación de Málaga, por atenderme y facilitar toda la información necesaria para poder completar esta tesis. Y finalmente, a todas aquellas personas que con su contribución han permitido que esta tesis sea una realidad. VIII according to the models. The dynamic nature (changing the values in each time period) of these types of problems hinders its quantitative approach. Although In the organization engineering there are mathematical models that attempt to facilitate decision-making, it in general tends to be static (considering only a period of time) and deterministic models (e.g. excluding statistics and nondeterministic techniques). The aim of this thesis focuses mainly on the use of search metaheuristic techniques on a dynamic and deterministic model to analyze and solve cost optimization problems and location in reverse logistics within the field of municipal waste management (MSW) of Malaga. To do this, we first analyze and evaluate the existing approaches found in PhD theses, magazines and national and international conferences and based on the use of metaheuristic techniques. In some existing solutions based on metaheuristics is used a metaheuristic algorithm, a modeler (AIMMS, GAMS) and a solver (CPLEX) to resolve continuous linear models. This will be the pattern to be followed in this thesis. At present there are many and novel search metaheuristic techniques, ranging from those in the conventional literature such as genetic algorithms (GA, Holland (1975)), tabu search (TS, Glover (1989)), scatter search (SS, Glover (1977)), etc., to the newest and bio-inspired algorithms based on swarm intelligence such as particles swarm optimization (PSO, Kennedy and Eberhart (1995)), and many others as iterated local search (ILS, Stützle (1999)), etc. In this work we have selected two metaheuristic techniques having relevance in research to test the validity of the proposed approach: an important technique for its international presence as is the algorithm GA and another interesting technique that works with swarm intelligence as is the algorithm PSO. These metaheuristic techniques will be used to solve cost optimization problems and location of MSW recovery facilities (transfer centers and treatment plants). IX The steps we take in this thesis to solve the location of transfer facilities and treatment plants are as follows. First, linear programming is used to find the exact value in the optimization process. Second, we propose several metaheuristic techniques that are used to reach the approximate global optimum when the result of the exact calculation is not feasible. Both the exact techniques and metaheuristic algorithms have been developed with the interpreted language MATLAB R2014b. We have also analyzed other potential approaches, like competing applications to develop these techniques as GAMS 24.4.3 or 4.6 AIMMS as modelers and CPLEX as "solver" and development in C ++ of metaheuristic techniques, but eventually the power and versatility of MATLAB as a mathematical tool and their availability at the UMA, determined its use. The proposed methodology will be applied to a real case of management, carried out by the Council of Malaga, of urban waste generated by 90 municipalities. In this thesis we have searched the transfer costs optimization from municipalities to transfer centers and treatment plants, as well as its location. Finally, the results obtained with the proposed metaheuristic techniques in locating and optimization of designed mathematical model to solve the proposed real problem, suggest the validity of the hypothesis done in this thesis. We also propose some research extensions and developed model by metaheuristic used in PSO. X Esta página se ha dejado en blanco intencionadamente XI ÍNDICE GENERAL Agradecimientos..................................................................................................... I Resumen............................................................................................................... III Abstract...............................................................................................................VII 1. INTRODUCCIÓN Y OBJETIVO DE LA TESIS .......................................1 1.1. Introducción ..............................................................................................1 1.2. Consideraciones previas sobre logística inversa.......................................2 1.3. Objetivos y metodología de la tesis ..........................................................4 1.4. Estructura de la tesis..................................................................................5 1.5. Aportaciones de esta tesis doctoral ...........................................................7 2. LA LOGÍSTICA INVERSA DE LOS RSU Y ESTADO DEL ARTE .......9 2.1. Introducción...................................................................................................9 2.2. Concepto y clasificación de los RSU ..........................................................10 2.3. Gestión de los RSU .....................................................................................13 2.4. Conclusiones................................................................................................18 3. DEFINICIONES DE LA LOGÍSTICA INVERSA DE RESIDUOS Y ESTADO DEL ARTE..........................................................................................21 3.1. Introducción..............................................................................................21 XII 3.2. Definiciones de la logística inversa de residuos.........................................21 3.3. Estado del arte sobre la logística inversa y localización de instalaciones..24 3.3.1. Tesis sobre la logística inversa en España y otros países ..................26 3.3.2. Artículos, conferencias y congresos de ámbito internacional sobre la logística inversa y heurísticos.......................................................................32 3.4. Conclusiones...............................................................................................35 4. LOCALIZACIÓN DE INSTALACIONES Y METODOLOGÍA METAHEURÍSTICA EN LA LOGÍSTICA INVERSA DE RSU...................37 4.1. Introducción.................................................................................................37 4.2. Modelo matemático optimización costes y localización de instalaciones...39 4.3. Problema localización plantas de tratamiento y centros de transferencia ...40 4.3.1. Antecedentes....................................................................................41 4.3.2. Diseño del modelo matemático. Función objetivo ..........................42 4.4. Metodología.................................................................................................52 4.4.1. Metodos de resolución........................................................................52 4.5. Conclusiones................................................................................................55 5. TÉCNICAS METAHEURÍSTICAS UTILIZADAS..................................57 5.1. Introducción.................................................................................................57 5.2. Técnicas metaheurísticas.............................................................................58 5.2.1. Algoritmos genéticos (GA).................................................................59 5.2.2. Recocido simulado (AS).....................................................................60 5.2.3. Búsqueda Tabú (TS)...........................................................................60 5.2.4. GRASP................................................................................................61 XIII 5.2.5. Colonia de hormigas (ACO)...............................................................62 5.2.6. Búsqueda dispersa (SS) ......................................................................63 5.2.7. Optimización de enjambre de partículas (PSO)..................................64 5.2.8. Búsqueda local iterada (ILS) ..............................................................65 5.3. Selección del algoritmo adecuado al problema...........................................65 5.4. Aplicación de la metodología propuesta mediante GA...............................67 5.5. Aplicación de la metodología propuesta mediante PSO .............................75 5.6. Conclusiones................................................................................................83 6. MODELADO Y RESOLUCIÓN: APLICACIÓN A UN CASO REAL..85 6.1. Introducción.................................................................................................85 6.2. Buscando aplicaciones informáticas de optimización.................................86 6.2.1. Resultados en Matlab con GA ............................................................94 6.2.2. Resultados en Matlab con PSO.........................................................100 6.3. Aplicación de metaheurísticas al caso real de la provincial de Málaga ....104 6.4. Conclusiones..............................................................................................122 7. CONCLUSIONES Y FUTUROS DESARROLLOS................................123 7.1. Conclusiones..............................................................................................123 7.2. Futuros desarrollos ....................................................................................125 BIBLIOGRAFÍA ...............................................................................................127 ANEXO A.1: Algoritmo PSO básico................................................................136 ANEXO A.2: Algoritmo GA .............................................................................138 XIV ANEXO B: Parámetros algoritmo GA ............................................................146 ANEXO C: Parámetros algoritmo PSO ..........................................................147 ANEXO D: Parámetros y valores caso real.....................................................148 XV ÍNDICE DE TABLAS 2.1. Clasificación de los tipos de residuos..........................................................12 3.1.Resumen revisión bibliográfica de tesis.......................................................31 3.2.Resumen de artículos y conferencias sobre logística inversa.......................34 4.1.Índices del modelo matemático....................................................................46 4.2.Parámetros del modelo matemático..............................................................47 4.3.Variables del modelo matemático ................................................................47 4.4.Variables y restricciones por nº municipios y periodos ...............................51 5.1. Funciones y valores usados como parámetros GA......................................74 5.2. Valores usados como parámetros PSO........................................................81 6.1. Herramientas de resolución indicando problemas que resolven .................87 6.2. Herramientas de modelado indicando solvers compatibles.........................88 6.3. Resultados programación lineal en MATLAB para distintos municipios...92 6.4. Resultados programación lineal con AIMMS para distintos municipios....93 6.5. Resultados GA con MATLAB para distintos municipios...........................95 6.6. Resultados algoritmos PSO con MATLAB para distintos municipios .....101 6.7. Resumen resultados distintas técnicas y distintos municipios ..................105 6.8. Costes sin estaciones c. transferencia p. tratamiento Málaga 2013...........107 6.9. Resultados algoritmos PSO y GA con MATLAB 90 municipios.............108 6.10. Resultados prueba t-student 40 y 90 municipios GA, PSO y exacto ......113 6.11. Coste 2014 para 90 municipios según distribución actual ......................115 XVI 6.12. Coste 2014 aplicando algoritmos PSO y GA a 90 municipios................116 D.1. Costes y capacidad transferencia municipio c.transfer.-p.tratam. ............148 D.2. Transferencia residuos entre c.transferencia y p.tratamiento ...................148 D.3. Recogida residuos centros transferencia 2013..........................................149 D.4. Transferencia residuos a plantas de tratamiento.......................................149 D.5. Producción residuos 90 municipios 5 años...............................................150 D.6. Distancia entre los 90 municipios.............................................................153 D.7. Residuos centro transferencia Ronda 2010 ..............................................162 D.8. Residuos planta tratamiento Antequera 2010...........................................163 D.9. Residuos centro transferencia Axarquia 2010..........................................164 D.10. Residuos centro transferencia Guadalhorce 2010 ..................................165 D.11. Residuos centro transferencia Ronda 2011 ............................................166 D.12. Residuos planta tratamiento Antequera 2011.........................................167 D.13. Residuos centro transferencia Axarquia 2011........................................168 D.14. Residuos centro transferencia Guadalhorce 2011 ..................................169 XVII ÍNDICE DE FIGURAS 1.1. Procesos de la Logística Inversa....................................................................2 1.2. Gestión actual de los RR.SS.UU. en Europa.................................................3 2.1. Diferentes formas de gestión de RR.SS.UU. en varios paises de la UE .....10 2.2. Diferentes etapas de la logística inversa......................................................14 2.3. Evolución de la generación de RR.SS.UU. en Málaga ..............................15 2.4. Evolución de la generación de RR.SS.UU. en España...............................16 3.1. Estructura de una red de logística inversa ...................................................23 4.1. Transferencia residuos municipios, c. transferencia y p. tratamiento .........45 4.2. Esquema distintos métodos resolución por técnica y tipo problema...........54 5.1. Esquema básico de GA................................................................................68 5.2. Diagrama de flujo de GA utilizado en MATLAB.......................................71 5.3. Modificación de posición partícula i...........................................................79 6.1. Archivo Excel con datos de distancias entre municipios ............................90 6.2. Programa AIMMS con resultados óptimo 40 municipios...........................93 6.3. Resultado mejores valores función aptitud GA 20 y 40 municipios...........95 6.4. Buscando mejores valores función aptitud GA 40 municipios ...................96 6.5. Resultado función aptitud GA valores CrossoverFraction, 6 municipios...97 6.6. Resultado valores función aptitud PSO 6, 20, 40 y 90 municipios ...........102 6.7. Resultado mejores valores función aptitud PSO 90 municipios ...............109 6 En el capítulo 2 se incluyen los distintos enfoques de la logística inversa de RSU, algunas definiciones sobre gestión de residuos y del concepto de vertedero, se analiza el estado del arte de la logística inversa de residuos, se revisa la situación actual del modelo de gestión de RSU y la legislación que regula actualmente en materia de residuos y suelos contaminados. En el capítulo 3 se revisa el estado del arte de las distintas tesis nacionales e internacionales, así como artículos de reconocidas e importantes revistas, congresos y conferencias de ámbito mundial. La revisión se hará sobre el marco de la logística inversa, enfocada en modelos exactos de optimización de costes y localización de instalaciones, y en el uso de técnicas metaheurísticas. En el capítulo 4 se analizan los distintos modelos de localización de instalaciones en la literatura, que servirán de referencia para el problema matemático diseñado, así como los métodos de resolución más adecuados para resolver los problemas de optimización y localización de centros de transferencias y plantas de tratamiento de RSU. En el capítulo 5 se presentan algunas técnicas metaheurísticas usadas actualmente, así como la descripción detallada de las dos técnicas metaheurísticas seleccionadas para resolver el problema de optimización modelado, como son los algoritmos GA y los algoritmos PSO. En el capítulo 6 se analiza la herramienta informática seleccionada para modelar y resolver el problema de minimización de costes y localización de instalaciones, así como los resultados de la aplicación de la misma en la resolución de un problema real de optimización de la red de recogida y transporte de RSU, de 90 municipios de la provincia de Málaga. Finalmente, el capítulo 7 incluirá las conclusiones más significativas derivadas de la tesis, así como las líneas de investigación futuras. 7 1.5. Aportaciones de esta tesis doctoral Las principales aportaciones de esta tesis son las siguientes: Si bien, tras la revisión del estado del arte, la mayoría de los problemas de localización de tipo determinista están contemplados en dicha literatura, esta tesis pretende aportar una nueva aproximación en el ámbito de la logística inversa de gestión de RSU mediante el desarrollo de técnicas novedosas de carácter metaheurístico (como el algoritmo PSO) que permite aproximar el valor óptimo en la localización de instalaciones de transferencia y tratamiento de residuos urbanos a lo largo de diferentes periodos, y con tiempos de ejecución computacional suficientemente breves como para hacer factible la aplicación de dichas técnicas. Se introducen consideraciones de carácter más realista que lo encontrado hasta ahora en la literatura, al usar datos reales y resolver un problema de gestión de RSU de 90 municipios de la provincia de Málaga. Esto permite trasladar su estudio a un conjunto de problemas similares de ámbito global. Con carácter cualitativo, se realiza un estudio de la situación actual del sistema logístico inverso de gestión de RSU y su necesidad de adaptación conforme a la cada vez más exigente legislación medioambiental. La aplicación del lenguaje matemático MATLAB R2014b para modelar y resolver el problema de optimización. MATLAB ha permitido resolver tanto los modelos exactos iniciales, como los metaheurísticos seleccionados para resolver los modelos matemáticos donde el número de variables y restricciones convierten dichos modelos exactos en un problema NP-duro (Garey y Johnson (1979)), poniendo de manifiesto el interés e idoneidad del enfoque propuesto. 8 En definitiva, este trabajo de investigación supone un avance por el uso de un metaheurístico actual y no utilizado en este problema y que ha constatado su eficiencia al contrastar los datos obtenidos con los de otro metaheurístico ya clásico en la resolución de problemas de localización. También se introducen consideraciones de carácter más realistas de lo que generalmente se ha presentado en la literatura al usar datos reales, lo que dota a nuestros resultados y conclusiones de un mayor interés. 9 Capítulo 2 2. LA LOGÍSTICA INVERSA DE LOS RSU Y ESTADO DEL ARTE En este capítulo se van a revisar brevemente las distintas aproximaciones a la Logística Inversa de residuos, centrándonos en un tipo concreto de residuos: los RSU, que son los generados por las actividades propias de las ciudades y que comprende la recogida domiciliaria de la fracción resto (recogida no selectiva), la procedente de la recogida de residuos de poda, muebles, etc. y la recogida selectiva de vidrio, papel-cartón, envases y embalajes. 2.1. Introducción Si bien la Ley de residuos 10/1998 utilizaba una sola definición de residuos urbanos, la Ley 22/2011, de 28 de julio de residuos y suelos contaminados y que deroga a la anterior citada, establece nuevas definiciones de residuos como son los “residuos domésticos, comerciales e industriales” para entender el concepto de aquellos residuos no peligrosos generados por los ciudadanos. Aunque el volumen de los RSU es pequeño si lo comparamos con el resto de residuos (A. Del Val (1994)), en los últimos años ha experimentado un aumento significativo debido principalmente al incremento poblacional y a los hábitos de consumo. 10 2.2. Concepto y clasificación de los RSU Un primer concepto general sobre residuos los podría definir como, “aquellas sustancias u objetos abandonados o descartados en forma permanente por quien los produce, por considerarlos ya sin utilidad en su provecho” (Tchobanoglous (1994)). Sin embargo, la legislación actual pretende regular una gestión eficaz de los residuos, para evitar que estos sean descartados de forma permanente buscando una valorización para que al menos algunos de los materiales que contienen puedan ser útiles para otro actor distinto del generador. En la Figura 2.1 se observa el diferente tratamiento dado a los residuos en varios países de la Unión Europea. Figura 2.1: Diferentes formas de gestión de RSU en varios países de la UE. Fuente: Eurostat 2011. Los RSU, por tanto, pueden definirse en una primera aproximación como los desechos generados en la comunidad urbana, provenientes de los procesos de consumo y desarrollo de las actividades humanas, y que normalmente son sólidos a temperatura ambiente. Además de los producidos por los usos residenciales, comerciales e institucionales, y por los trabajos en espacios públicos, los RSU incluyen los residuos originados en las industrias y en centros sanitarios, siempre que no tengan características tóxicas ni peligrosas, en cuyo caso existe otra legislación que establece las normativas específicas de gestión y manejo de este tipo de residuos. 11 La actual legislación en materia de residuos (Ley 22/2011) establece en su artículo 3 las definiciones sobre los residuos, quedando el concepto de RSU determinado como el conjunto de varios apartados del artículo. Como definición general, se toma la siguiente: a) «Residuo»: cualquier sustancia u objeto que su poseedor deseche o tenga la intención o la obligación de desechar. La definición de RSU quedaría recogida en el conjunto de definiciones dadas en los apartados b, c y d, mostrados a continuación: b) «Residuos domésticos»: residuos generados en los hogares como consecuencia de las actividades domésticas. Se consideran también residuos domésticos los similares a los anteriores generados en servicios e industrias. Se incluyen también en esta categoría los residuos que se generan en los hogares de aparatos eléctricos y electrónicos, ropa, pilas, acumuladores, muebles y enseres así como los residuos y escombros procedentes de obras menores de construcción y reparación domiciliaria. Tendrán la consideración de residuos domésticos los residuos procedentes de limpieza de vías públicas, zonas verdes, áreas recreativas y playas, los animales domésticos muertos y los vehículos abandonados. c) «Residuos comerciales»: residuos generados por la actividad propia del comercio, al por mayor y al por menor, de los servicios de restauración y bares, de las oficinas y de los mercados, así como del resto del sector servicios. d) «Residuos industriales»: residuos resultantes de los procesos de fabricación, de transformación, de utilización, de consumo, de limpieza o de mantenimiento generados por la actividad industrial, excluidas las emisiones a la atmósfera reguladas en la Ley 34/2007, de 15 de noviembre. 12 Aunque, como se ha visto en las definiciones anteriores, los RSU están constituidos por un conjunto heterogéneo de materiales, estos se pueden dividir por su composición en dos categorías básicas: Orgánicos: restos de materiales resultantes de la elaboración de comidas, así como sus restos vegetales y animales. Inorgánicos: restos de elementos que no son fruto directo de la naturaleza sino de la industrialización de recursos naturales (plástico, vidrio, papeles, latas, textiles). Tabla 2.1: Clasificación de los tipos de residuos. Fuente: Elaboración propia. En la Tabla 2.1 se da una clasificación completa de los residuos en función de su origen, tipo y clases. 13 2.3. Gestión de los RSU La legislación en materia de residuos, Directiva Marco de Residuos Europea (Directiva 2008/98/CE) y la Ley de Residuos y Suelos Contaminados (Ley 22/2011), establece en su artículo 3, la definición de Gestión de residuos como: “la recogida, el transporte y tratamiento de los residuos, incluida la vigilancia de estas operaciones, así como el mantenimiento posterior al cierre de los vertederos, incluidas las actuaciones realizadas en calidad de negociante o agente”. Dicha Ley contempla que el tratamiento de residuos debe seguir un orden de prioridad: prevención, preparación para la reutilización, reciclado, otro tipo de valorización (energética) y eliminación. Esta normativa supone la construcción de infraestructuras de pretratamiento, clasificación y valorización del residuo antes de ir a vertedero para su eliminación. La gestión de RSU se puede dividir en cuatro fases diferenciadas: prerecogida, recogida, transporte y tratamiento. La fase de pre-recogida que incluye el almacenamiento, manipulación, clasificación y presentación para su recogida, ha mejorado en los últimos años con la instalación de contenedores y campañas de sensibilización ciudadana. Las fases de recogida y transporte hasta los puntos de tratamiento o a las plantas de transferencia donde se compactan, suelen ser las más costosas. En la Figura 2.2 se pueden ver las distintas etapas de gestión en la logística inversa. El tratamiento incluye operaciones de aprovechamiento de los materiales contenidos en los residuos o su eliminación. Los sistemas actualmente más utilizados de tratamiento son: el vertido controlado, la incineración, el reciclado y el compostaje. El vertido es el método más empleado en España en cuanto al volumen de residuo tratado. 14 Figura 2.2: Diferentes etapas de la logística inversa. Fuente: http://www.free-logistics.com Hoy en día, la gestión de los residuos tiende a modelos productivos más eficientes (menor consumo de recursos energéticos, económicos, etc.) para toda su cadena de gestión, desde la recogida selectiva, hasta la salida de los productos recuperados de dichos residuos para conseguir finalmente una mejora ambiental y de protección de la salud. En la literatura se pueden encontrar aplicaciones de este enfoque de gestión de residuos más eficaz desde el punto de vista económico y ambiental en Jacobs y Everett (1992), en Keeler y Renkow (1994) y en Huhtala (1997). Aunque este último autor indica que las acciones para una eficiente gestión de residuos debe empezar en las fases de producción y comercialización de los bienes de consumo (Huhtala (1999)). Otros autores apuntan a la economía, señalando que: “…el problema de la gestión de residuos sólidos proviene de la falta de conocimiento hacia la naturaleza económica del problema” (Goddard (1995)). El modelo actual de gestión integral de los residuos en nuestro país queda reflejado en la evolución de la generación de RSU a lo largo de los últimos años. Así, desde 2004 hasta 2007 la generación de RSU a nivel nacional ha aumentado progresivamente, para luego descender desde 2007 hasta 2013 más de un 10%, si 15 bien cabe indicar que en las cifras señaladas de descenso ha tenido un fuerte impacto la crisis económica iniciada en 2008. El descenso de la media nacional se ha situado en valores por debajo de los 500 Kg de residuo/habitante/año, teniendo como meta deseable bajar de los 1,30 Kg de RSU/habitante/día. Hasta hace relativamente poco (año 1995), casi el 100% de los residuos urbanos eran destinados a deposición en vertederos controlados. Estos se pueden entender como recursos naturales agotables y como se indica en Ready & Ready (1995), a diferencia de otros recursos cuyo agotamiento es irreversible, un vertedero al alcanzar su límite de capacidad puede reemplazarse por otro vertedero de nueva construcción. Se trata de un recurso agotable y reemplazable, en los que tanto su capacidad como su ubicación son variables de decisión con transcendencia económica. En Jacobs y Everett (1992) se presenta un modelo para determinar el empleo óptimo de vertederos con reciclaje. En Huhtala (1997) se analiza el instante óptimo en que se debe dejar de utilizar un vertedero y sustituir por uno de nueva construcción. En André, Velasco y González (2004) se analiza el problema conjunto de capacidad y localización. Figura 2.3: Evolución de la generación de RSU en Málaga. Fuente: LIMASA, Servicios de Limpieza Integral de Málaga III, S.A. 22 hasta los años 90. De las definiciones dadas sobre “logística inversa” y que recojan el término de residuos y su gestión se escoge la que dio Stock (1992) y publicada por el Council of Logistics Management (CLM): “…el término normalmente usado para referirse al papel de la logística en el reciclado, vertido de residuos y gestión de materiales peligrosos“. En el año 1998, Stock publicó lo que ha sido considerado como el libro blanco de la logística inversa de donde se ha sacado una nueva definición sobre logística inversa referente a la gestión de residuos y que se ha incluido en las consideraciones previas del capítulo 1. Hay otros autores como Kopicki (1993), que al igual que Stock enfatizan la importancia de la gestión de residuos incluida su eliminación, en este nuevo contexto de la logística inversa. Por otra parte, hay autores como Rogers y Tibben-Lembke (1999) que ya hablaban de eficiencia en la recuperación y eliminación de productos en la logística inversa y la definían como: “… el proceso de planificación, ejecución y control de la eficiencia y eficacia del flujo de las materias primas, inventario en proceso, productos terminados e información relacionada, desde el punto de consumo hasta el punto de origen, con el fin de recuperar valor o la correcta eliminación”. Si se analizan las definiciones anteriores se puede concluir que la logística inversa constituye un importante sector de actividad dentro de la logística, que incluye multitud de actividades. Algunas de estas actividades están enfocadas a aspectos ambientales, como la recuperación y el reciclaje de los productos. Otras buscan mejorar la eficiencia y eficacia en los procesos productivos y de suministro, para obtener mayores beneficios. 23 Figura 3.1: Estructura de una red de logística inversa. Fuente: Elaboración propia. En la Figura 3.1 se puede ver la estructura de una red de logística inversa. Dentro de las operaciones incluidas en la logística inversa se pueden encontrar: procesos de retorno por excesos de inventario, devoluciones de clientes, productos terminados y obsoletos, inventarios sobrantes del proceso productivo, actividades de retirada, clasificación, reacondicionamiento y reenvío al punto de venta o a otros mercados secundarios. Y por último, respecto a las instalaciones de tratamiento de los residuos (centros ambientales, incluidos los vertederos) hay autores como André y Cerda (2001) que estudian el problema de determinar óptimamente la capacidad de vertederos. Otros como André, Velasco y González (2004) estudian tanto capacidad como localización y en Gaudet, Moreaux y Salant (1998) analizan el transporte desde varias ciudades a vertederos. Los vertederos clasificados por algún autor como el destino final en el último proceso de logística inversa se pueden considerar como recursos agotables y reemplazables. Debido a su transcendencia económica, tanto por su capacidad como por su ubicación tienen una consideración especial como variables de decisión en el modelo matemático de minimización de costes en el transporte y en la localización de plantas de tratamiento desarrollado en esta tesis y cuyo diseño se detallará en los siguientes capítulos. 24 3.3. Estado del arte sobre la logística inversa y localización de instalaciones En esta sección se hace una revisión en la literatura sobre la investigación en logística inversa y la localización de instalaciones aplicando técnicas metaheurísticas, así como de las tesis en España y en Europa que tratan sobre estas líneas de investigación. Aunque existen bastantes investigaciones sobre teoría de localización de instalaciones en términos generales, sin embargo son pocas las que se han encontrado que incluyan esta teoría aplicada a la logística inversa. Lo que más ampliamente se ha desarrollado en la literatura de la logística inversa es referente a planificación de la producción, al control de inventario y la refabricación. Hay varios autores que incluyen la elección óptima de las instalaciones en su modelo de logística inversa. Krikke (1998) propone un modelo de optimización para un efectivo diseño de redes para logística inversa. Son modelos para recuperación de múltiples productos ensamblados en distintos periodos. El modelo trata también problemas de localización de instalaciones con su correspondiente función de costes. Desarrolla un algoritmo heurístico para resolver el problema y lo complementa con una aplicación práctica adicional de rediseño de una cadena de fotocopiadoras. Barros et al. (1998) proponen un modelo de localización de dos niveles para los problemas de reciclado de arena en Holanda y lo resuelven optimizando mediante técnicas heurísticas. González y Adenso Díaz (2004) proponen un metaheurístico de búsqueda dispersa para tratar problemas de secuencia de desensamble óptimo para el caso de productos complejos que son reciclados o fragmentados al final de su vida. Evalúan el heurístico sobre un conjunto de 48 productos, considerando el tiempo usado en el desensamble de sus componentes en orden inverso a la secuencia de ensamble. 25 Lu y Bostel (2005) desarrollan un problema de localización de dos niveles con tres tipos de instalaciones para ser localizado en un sistema de logística inversa. Para resolver el problema diseñan un modelo de programación lineal entera-mixta, considerando simultáneamente flujos de interacción directo e inverso. Jeung Ko y Evans (2005) proponen un modelo de programación no lineal entera-mixta para el diseño de una red de distribución integrada dinámica para la optimización de sistemas de trabajos directos e inversos. También hay un creciente interés en la mayoría de las universidades españolas por la logística inversa creando grupos de investigación, muchos de ellos financiados por el ministerio de Educación y Ciencia. Ciertamente las investigaciones sobre logística inversa están experimentando también un crecimiento notable, debido al aumento de los requisitos legislativos a las empresas en materia medioambiental. Algunas de las universidades que tienen áreas de investigación en este terreno son: la Universidad Politécnica de Madrid, la Universidad de Sevilla, la Universidad de Extremadura, la Universidad de Oviedo, la Universidad de Navarra, la Universitat Pompeu Fabra, la Universidad Carlos III de Madrid, la Universidad de Salamanca, la Universitat Politécnica de Cataluña y la Universidad del País Vasco. A nivel internacional se pueden encontrar numerosos artículos sobre logística inversa en prestigiosas revistas académicas como: European Journal of Operational Research, International Journal of Production Economics, Interfaces, en editoriales como Springer, Elsevier, o en Librerias Digitales como IEEE Xplore (Institute of Electrical and Electronics Engineers). También, nuevas líneas de investigación o grupos de investigación específicos sobre esta materia como REVLOG (European Working Group on Reverse Logistics) o RELOOP (Reverse Logistics Executive Council). En Norteamérica, el más importante grupo 26 de investigación sobre logística inversa es el formado por el CSCMP (Council of supply chain management professionals), antiguo CLM, en el que publicaban los autores norteamericanos de mayor prestigio en el asunto, como Stock, Rogers y Lembke, etc. 3.3.1. Tesis sobre la logística inversa en España y otros países Aunque como se indicó en el apartado anterior existen grupos de investigación destacados sobre logística inversa en muchas de las universidades españolas, sorprende que en la búsqueda de tesis españolas sobre logística inversa solo se hayan encontrado once. La mayoría de tesis en España sobre logística trata sobre la logística directa o de “aguas abajo”. El resultado de esta revisión indica el amplio horizonte todavía por investigar en este campo. Las distintas tesis españolas que se tratan a continuación han sido encontradas en la web “TESEO” del Ministerio de Educación del Gobierno de España. Es evidente que en España el interés investigador en las universidades respecto de la logística inversa surgió más tarde que en el resto de países europeos. La defensa de la primera tesis sobre logística inversa fue realizada por González Torre (2002), en ella se evalúan los distintos aspectos relacionados con la incorporación de las actividades de logística inversa al ciclo del envase de vidrio hueco. Se desarrolló un modelo de programación lineal multiobjetivo para reasignar eficientemente los contenedores disponibles por una empresa gestora de los residuos, maximizando el vidrio recogido con los mínimos costes logísticos. En la tesis de Rubio Lacoba (2003) se analizan las posibilidades que presentan los productos desechados por los consumidores o fuera de uso. Se realiza una simulación dinámica de un modelo de gestión de inventario en el que se considera la posibilidad de recuperar los productos fuera de uso. 27 En la tesis de Fernández Quesada (2004) se quiere contribuir por una parte, al marco teórico de la logística inversa y por otra, a incorporar escenarios reales. En una primera fase utiliza la técnica del Focus Group para recabar información de personas expertas en el tema y en la segunda fase utiliza la metodología del estudio de casos para el análisis de varias empresas. Soto Zuloaga (2006) en su tesis analiza los problemas de las empresas en los procesos de devoluciones en la industria editorial y propone modelos matemáticos y métodos de solución mediante algoritmos de ramificación y poda, para resolver problemas de casos reales en editoriales de la planificación en las devoluciones, optimizando y reduciendo los costes totales de producción. Utiliza modelos de programación lineal con variables enteras, resueltos por el software LINGO. Utiliza un heurístico de búsqueda local realizado en C++ y conectado con LINGO para resolver problemas donde el tamaño real (mayor número de variables y restricciones) complica la solución del modelo. La tesis de Ortega Mier (2008) trata sobre la utilización de métodos cuantitativos, en concreto técnicas metaheurísticas para analizar problemas de localización en logística inversa. Utiliza algoritmos GA y SS para los problemas de localización de instalaciones de recuperación de residuo ligero de fragmentación de vehículos fuera de uso. Plantea un problema teórico inspirado en los municipios de la provincia de Guipúzcoa. La técnica menos eficiente y de peores resultados es la GA. Sin embargo, técnicas metaheurísticas como la PSO utilizada en esta tesis resultarían más eficientes, con tiempos computacionales menores para el número de variables y restricciones usadas. López Parada (2010) en su tesis elabora un modelo de referencia que permite a las empresas una fácil adaptación a las necesidades derivadas de la gestión de logística inversa. En la investigación utiliza el método del caso múltiple, con el fin de encontrar patrones de comportamiento que permitan generalizar los resultados a partir de los datos obtenidos de 20 empresas de prestigio internacional. 28 Bustos Flores (2010) en su tesis analiza la incorporación de un modelo de logística inversa en el sector artesanal, para la adquisición de los insumos necesarios para la producción. En la tesis de Mihi Ramírez (2010) se investiga la relación existente entre la creación del conocimiento y la logística inversa como fuente de ventajas competitivas sostenibles, tratando de elaborar instrumentos de medida que logren un acercamiento de ambos contextos. El autor considera que un flujo inverso en la función logística, amplificará las capacidades competitivas de la empresa. La tesis de Benedito Benet (2010) propone el estudio de la influencia de la logística inversa en las capacidades de fabricación, re-fabricación (“devolver a un producto usado al menos su rendimiento original, garantizando que es equivalente o mejor que el del producto fabricado de nuevo”, Johnson et al. (2014)) y almacenaje óptimo de un sistema industrial. Se estudian tres modelos de un sistema en que el producto recuperado es indistinguible del producto nuevo, determinando la política de producción óptima utilizando una cierta función de coste. En la tesis de Castillo Díaz (2011) se analizan las posibilidades que presenta el tema de la logística inversa para los productos desechados o productos fuera de uso en el sector vitivinícola. Se presentan dos metodologías aplicables a problemas de optimización: la primera trata de la selección de alternativas en empresas con múltiples criterios y atributos. La segunda trata de minimizar o maximizar objetivos en la gestión de productos fuera de uso. Por último, en la tesis más reciente sobre logística inversa en España de Jiménez Parra (2014) se propone un modelo explicativo del comportamiento de compra del potencial consumidor de portátiles refabricados, que sirva de marco teórico de referencia para orientar a empresas interesadas en el diseño e implantación de estrategias de marketing más adecuadas para la comercialización de sus productos refabricados. 29 Respecto de las tesis españolas referidas a logística inversa, solo dos han utilizado sistemas metaheurísticos de optimización. En la tesis de Soto Zuloaga (2004) no queda muy claro el tipo de heurístico utilizado, ya que habla de uno de búsqueda local, programado en C++, pero sin citar autor alguno sobre dicho heurístico. La tesis de Ortega Mier (2008) refiere a la poca eficiencia de los GA frente a la TS, aunque para una mejor comparación se habría necesitado un tamaño de muestras mayor de 10 (al menos 30 ejecuciones de cada algoritmo). Por otra parte, la principal contribución de la tesis presentada, no es solo el uso de un algoritmo metaheurístico más eficiente como es PSO, si no porque hasta ahora no se han encontrado referencias a dicho metaheurístico, en tesis españolas e internacionales (se verá a continuación) referidas a logística inversa. Referente a las tesis sobre logística inversa a nivel internacional, las primeras tesis doctorales encontradas con referencias a la logística inversa fueron las de: Jahre (1995), Thierry (1997), Krikke (1998), Van der Laan (1997) y Fleischmann (2000). Jahre (1995) estudió cómo funcionaban los sistemas de recolección y reciclaje de basura urbana, considerando la separación en origen y la recolección conjunta. Fleischmann (2000) estudia, entre otras cuestiones, cómo pueden describirse las características de los sistemas de logística inversa a través de modelos cuantitativos y, de esta forma, mejorar el proceso de toma de decisiones. Según la asociación de bibliotecas de investigación (DART-Europe), desde el año 2000 hasta hoy, se han leído 25 tesis doctorales europeas, sin considerar las españolas referentes a logística inversa. De las tesis europeas se comentan aquellas de contenido más afín al de esta tesis, bien por desarrollar metodologías cuantitativas como el uso de metaheurísticos para aproximar soluciones de problemas de optimización combinacionales complejos, caracterizados como NP-duro, o que tratan de resolver problemas de minimización de costes en el ámbito de la logística inversa. 30 Kongar (2003) examina diferentes técnicas de decisión multicriterio sobre desensamblaje en la recuperación de productos al final de su vida, resolviendo los problemas NP-completos que se plantean mediante programación multi-objetivo y diversos metaheurísticos como TS y GA. De Brito (2004) aporta conceptos sobre la logística inversa en la toma de decisiones y establece principios teóricos de la logística como campo de investigación, proponiendo recomendaciones obtenidas de un estudio Delphi realizado con grupos internacionales de académicos expertos en la materia. Aidonis (2009) examina diferentes aspectos de la gestión de residuos de la construcción y demolición, para desarrollar metodologías cuantitativas y cualitativas innovadoras. En una primera parte, desarrolla un marco de trabajo con metodología holística para gestionar eficientemente los flujos de residuos generados en las actividades de construcción y demolición. En una segunda parte, genera modelos integrados de optimización de esos procesos de logística inversa, para maximizar el beneficio y minimizar el tiempo requerido. Saibani (2010) propone un marco de trabajo ajustado a la logística de suministros de ciclo cerrado e inversa y realizado en tres niveles, que ofrezca un enfoque práctico para la toma de decisiones y que permita realizar y gestionar la cadena de suministro inversa con mayor eficacia. Vercraene (2012) modela tres problemas de reciclado y reutilización de residuos con una capacidad de producción limitada, considerando problemas de inventario y producción operativa que se incorporan al flujo de retorno. Valora algunas políticas de heurísticos y los efectos de la capacidad de producción sobre esas políticas. Finalmente, se menciona la tesis norteamericana de Du (2006) al proponer un modelo de minimización de los costes totales para el diseño de la logística inversa de un servicio post-venta, resuelto mediante métodos simplex dual y metaheurístico SS. 31 Tabla 3.1: Resumen revisión bibliografía tesis. Fuente: Elaboración propia. 38 Dependiendo del modelo tratan en cada caso los problemas de localización y asignación con formulaciones que varían en complejidad desde la simple lineal, de una sola etapa, modelos deterministas o estocásticos no lineales. Los modelos de localización continuos han sido investigados por diferentes autores como Hamacher y Nickel (1994), Käfer y Nickel (2001) y Klamroth (2001), o con propuestas de algoritmos heurísticos rápidos como las de Taillard (1996), Hansen et al. (1998) y Brimberg et al. (2000). Son modelos en el plano, cuyo espacio de solución es continuo, es decir requieren calcular las coordenadas (x, y) ∈ RP× RPpara pinstalaciones. En los modelos de localización de redes de trabajo, las distancias se calculan como los caminos más cortos en un grafo. Corresponde a un modelo continuo Weber multi-origen, llamado problema de la p-mediana (Christofides y Beasley, (1982), Hanjoul y Peeters, (1985) y Beasley, (1993)). Klose y Drexl (2000) establecieron, dentro de los modelos que utilizan una programación entera-mixta, la siguiente clasificación aproximada para modelos de localización de instalaciones discretas: - Modelos de uno o múltiples periodos, - Modelos con capacidad conocida o no, - Modelos de uno o múltiples orígenes, - Modelos de uno o múltiples productos, - Modelos estáticos o dinámicos y - Modelos probabilísticos. Ortega Mier (2008) presenta como extensión de los modelos anteriores, modelos conjuntos para múltiples capacidades definidas y múltiples periodos y soluciones metaheurísticas basadas en GA y SS, a los casos planteados de optimización en procesos de fragmentación de vehículos fuera de uso y la localización de fragmentadoras con múltiples capacidades y en distintos periodos. 39 Esta tesis ha basado el modelo matemático de optimización y localización de los centros de transferencia y de las plantas de tratamiento de RSU, en varios de los modelos enunciados anteriormente. Es decir, la función de coste diseñada en esta tesis se basa en un modelo dinámico, de múltiples periodos, con capacidad definida y múltiples orígenes. No se han tenido en cuenta a la hora de asignar una localización, criterios políticos, medioambientales, de instalaciones que por su cercanía o lejanía puedan generar molestias o beneficios (vertederos, centros transferencia). El principal criterio, ha sido la reducción del coste en el traslado de residuos desde distintos orígenes (municipios) hasta los destinos finales (plantas de tratamiento y centros de transferencia), contemplando la apertura o cierre de dichos destinos. 4.2. Modelo matemático de optimización de costes y localización de instalaciones El modelo matemático planteado pretende optimizar la localización de los centros de transferencia y las plantas de tratamiento en el ámbito municipal de las distintas provincias españolas. Como caso práctico, en el capítulo 6 se aplicá el modelo matemático diseñado para la identificación y localización de las instalaciones de gestión de RSU de 90 municipios de la provincia de Málaga y se contrastarán con los datos facilitados por la Diputación de Málaga y la empresa municipal de limpieza y gestión de residuos de la capital malagueña: LIMASA. En primer lugar, para definir el problema de optimización combinatoria se debe considerar que la cantidad de residuos generados y transportados desde diferentes municipios a los centros asignados puede variar a lo largo de distintos periodos de tiempo, dificultando este tipo de modelo dinámico la resolución del problema. En este entorno es más difícil estimar con precisión la evolución de los valores de todos los datos y parámetros de los modelos correspondientes. Este es el caso por ejemplo de la variación en el precio de los combustibles o de la distinta cantidad de residuo generado y transportado a lo largo de los años. 40 Como ya se ha visto del análisis del estado de la cuestión, en la literatura sobre localización de instalaciones existen distintos modelos matemáticos de optimización que facilitan la toma de decisiones a ese respecto, aunque en general están planteados para modelos estáticos y deterministas. En el siguiente apartado y dentro del sistema de logística inversa de RSU planteado se va a diseñar la función objetivo de tipo determinista, así como las restricciones que delimitan el área factible de búsqueda del óptimo de coste mínimo y la localización de las distintas instalaciones que permitan cumplir con ese mínimo coste. 4.3. Problema de localización de plantas de tratamiento y centros de transferencia El planteamiento del problema de localización de instalaciones de esta tesis se corresponde con algunos de los modelos incluidos en la clasificación dada por Klose y Drexl (2000) y las aportaciones de Ortega Mier (2008). Es decir, la función de coste diseñada en esta tesis se basa en un modelo dinámico, de múltiples periodos, con capacidad definida y múltiples orígenes, correspondiente a un problema de optimización combinatoria, en el que se pretende minimizar los costes totales incluyendo los costes operativos de trasladar la producción de RSU generada en los distintos municipios, a los centros de transferencias y las plantas de tratamiento para su valorización, obtención de compost, etc., así como los costes fijos derivados de la ubicación o no, de las instalaciones. Se consideran distintos parámetros y variables en el diseño de la función objetivo y las restricciones, para hacer factible la región convergente de búsqueda donde poder encontrar el óptimo global. 41 4.3.1. Antecedentes Previo a la determinación del modelo matemático de función de coste y sus restricciones necesarios para determinar el mínimo coste de gestión de residuos y su ubicación en las distintas instalaciones, se verá el proceso de recogida, transporte y tratamiento del RSU. El proceso de recogida de RSU en España y dentro del ámbito provincial, parte de una red de intercambio de residuos entre la amplia mayoría de municipios que normalmente conforman un “Consorcio Provincial de Residuos” gestionados principalmente por las Diputaciones. Diferente e independiente tratamiento tiene la gestión de los RSU en las ciudades que suelen estar gestionadas por empresas de carácter mixto, es decir con vocación pública en su gestión de recogida, transporte, tratamiento y eliminación de esos residuos, pero con estructura organizativa con participación de ayuntamientos y accionistas privados. Los RSU son transportados desde cada uno de los municipios hasta los diferentes centros de transferencia, donde son compactados para su transporte final a las plantas de tratamiento. Estas plantas pueden ser complejos centros de tratamiento y eliminación, que procesan todos los RSU generados por los distintos municipios y cuyo objetivo principal es maximizar el reciclado de materiales, producir bioestabilizado con la materia orgánica, generar un rechazo con el mínimo de materia orgánica y optimizar la producción de energía eléctrica. Los residuos que llegan a las plantas, salen transformados en materias primas reciclables (plásticos, metal, madera, etc.), en productos elaborados (bioestabilizados), e incluso en energía eléctrica. Una planta de tratamiento puede tener unas instalaciones con la siguiente composición: vertedero controlado de residuos no peligrosos, vertedero controlado de residuos inertes, planta de reciclaje y compostaje, planta automática 42 de clasificación de envases, triturador de voluminosos, horno crematorio de animales muertos, planta de tratamiento de lixiviados, planta de desgasificación y aprovechamiento eléctrico y planta de tratamiento de escombros. Los residuos tratados pueden ser en algún caso, clasificados y embalados para su entrega a distintos recicladores autorizados por diferentes SIG como Ecoembes, en el caso de envases. De las plantas de tratamiento, al igual que los centros de transferencia, solo se considerará su capacidad anual de gestión de residuos y los costes fijos, que según datos aportados por la Diputación de Málaga y LIMASA, son estimados en función de las toneladas tratadas al año. 4.3.2. Diseño del modelo matemático. Función objetivo El planteamiento de esta tesis se basa en establecer un modelo matemático que permita optimizar todo el sistema de gestión de RSU desde que se genera y recoge en cada municipio, pasando por los distintos centros de transferencias, hasta que es tratado y valorizado en la planta de tratamiento de residuos. Cuando se formula un modelo de optimización se persigue que sea operativo, es decir que represente la realidad y así mismo sea manejable matemáticamente. Con el desarrollo actual de la informática, con ordenadores más potentes y aplicaciones más sofisticadas se ha avanzado enormemente en la resolución de problemas más complejos matemáticamente, es decir, con mayor número de variables y restricciones, aunque como se verá en el caso real desarrollado en el capítulo 6, todavía limitado por el número de dichas variables y restricciones. Para el diseño de la función objetivo se han utilizado algunos de los modelos incluidos en la clasificación dada por Klose y Drexl (2000), los trabajos de localización de plantas y uso de heurísticos de Marín y Pelegrin (1991) y las aportaciones de Ortega Mier (2008). 43 Como ya se indicó, la función objetivo se basa en un modelo dinámico, de múltiples periodos, con capacidad definida y múltiples orígenes, correspondiente a un problema de optimización combinatoria, en el que se pretende minimizar los costes totales. El modelo diseñado parte de un planteamiento general de modelo básico de minimización de costes totales y localización de instalaciones (4.3.2.1) tratado por los tres autores citados anteriormente considerando un solo periodo y sin limitación de capacidad. En este modelo básico, solo se consideran dos restricciones (4.3.2.2) y(4.3.2.3), donde jrepresenta el conjunto de posibles localizaciones para las instalaciones candidatas, iel conjunto de municipios siendo cij el coste de la transferencia de iaj,fel coste de la instalación y pel número de instalaciones. Las variables xeytoman valores 1 o 0 según se haga la transferencia o no y según se haya seleccionado una instalación o no. El modelo es el siguiente: Minimizar ∑yjfj+∑xijcij j=1,…,m , i=1,…,n (4.3.2.1) Sujeto a: ∑xij = 1 i=1,…,n (4.3.2.2) ∑yj= p j=1,…,m (4.2.2.3) y con los límites: xij ≤ yjj=1,…,m , i=1,…,n (4.3,2.4) xij, yj ∈ {0, 1} j=1,…,m , i=1,…,n (4.3.2.5) A partir de ese modelo básico y otros de los clasificados en Klose y Drexl (2000), y considerando los parámetros y variables incorporados para definir la red de recogida y tratamiento de residuos se diseña el modelo planteado en esta tesis y que puede ser de utilidad tanto para aquellas provincias que tengan que definir una nueva estrategia de redes de gestión de residuos encontrando los trayectos 44 óptimos de los transportes en función de las localizaciones idóneas de las instalaciones de transferencias y tratamiento de los residuos, como para aquellas otras provincias, que teniendo establecida su red de recogida de los residuos, quieran mejorar el coste de su gestión, lo que conllevaría un ahorro económico importante por el ahorro de combustible, de mantenimiento del parque de vehículos por un menor kilometraje y finalmente por la considerable disminución de emisión de CO2a la atmósfera, contribuyendo a la sostenibilidad medioambiental indicada en la actual legislación de residuos (Ley 22/2011). Con idea de facilitar el modelo matemático utilizado en esta tesis, así como las restricciones que delimitarán el área convexa de búsqueda del coste óptimo o su valor aproximado (al trabajar con metaheurísticas), solo se tendrán en cuenta los trayectos entre los distintos municipios, sin considerar los recorridos que dentro del municipio tienen que realizar los vehículos de recogida de contenedores, soterrados o no, de envases, orgánicos, papel y cartón o vidrio. Los centros de transferencias solo se considerarán como destino de municipios y origen en el transporte de residuos a las plantas de tratamiento y cuyos parámetros utilizados para el cálculo de costes, serán solo su capacidad y costes fijos. La mejor trayectoria se obtendrá resolviendo el problema de identificación y localización de las instalaciones de residuos, según el modelo matemático de minimización de costes que se va a diseñar en esta tesis. En la Figura 4.1 se muestra un ejemplo de cómo sería el trayecto para el traslado de los residuos desde el municipio de Álora hasta la planta de tratamiento situada en Antequera o el centro de transferencia de Ronda para su compactación y posterior traslado a la planta. 45 Figura 4.1: Transferencia de residuos desde municipios a centro de transferencia y planta de tratamiento. Fuente: Elaboración propia. El diseño de modelo de la función coste tiene en cuenta las siguientes consideraciones: 5. Se considera el mismo coste de traslado de los residuos entre municipios y centros de transferencia, independientemente de que haya municipios que utilicen vehículos con mayor capacidad, consumo de combustible y coste, respecto de otros que utilicen vehículos más económicos. 6. No se consideran los recorridos para la recogida de los distintos contenedores dentro de cada municipio. Cada municipio, a efectos de cálculo de distancias, es considerado como punto de origen y final de trayectoria. 7. Se tienen en cuenta solo los costes fijos y capacidad de los centros de transferencia y de las plantas de tratamiento. Estos costes se calculan Planta de tratamiento Receptor RSU Municipios Productores RSU Centro de transferencia Receptor RSU 46 en función de las toneladas de residuos recibidas. Dichas instalaciones pueden ser localizadas en cualquier municipio, aunque en el caso de las plantas de tratamiento se parte de una primera hipótesis con dos plantas situadas en cualquier municipio, y una segunda opción considerando un número indefinido de plantas de tratamiento. 8. Se consideran cinco periodos (en años) pudiendo variar las localizaciones de los centros de transferencias y las plantas de tratamiento debido a cambios en los costes unitarios de transporte/año y la cantidad de residuo generado en cada periodo. En las siguientes Tablas 4.1, 4.2 y 4.3 se indican los índices, parámetros y variables utilizadas en el modelo matemático propuesto. El rango Mcorresponde al número máximo de municipios generadores de residuo, Nes el número máximo de centros de transferencia que se pueden instalar (1 por municipio), Plas plantas de tratamiento a considerar y Tel número máximo de años a analizar. Tabla 4.1: Índices del modelo matemático. Fuente: Elaboración propia. 47 Tabla 4.2: Parámetros del modelo matemático. Fuente: Elaboración propia. Tabla 4.3: Variables del modelo matemático. Fuente: Elaboración propia. 54 Figura 4.2: Esquema de distintos métodos de resolución, agrupados por técnica y tipo de problema. Fuente: Elaboración propia. En la Figura 4.2 se expone un breve esquema con los distintos métodos de resolución agrupados por técnica y tipo de problema, mostrando lo amplio del campo de los métodos de resolución de problemas de optimización. Finalmente, se encuentran los algoritmos heurísticos, término empleado por primera vez, desde el punto de vista científico, por el matemático Pólya 55 (1945) que proporcionan soluciones a un problema próximas a la óptima pero sin garantía de optimalidad, aunque con un tiempo de ejecución mucho menor. Los algoritmos metaheurísticos suelen imitar fenómenos simples observados en la naturaleza, y se consideran asociados con la inteligencia artificial. Los heurísticos clásicos suelen buscar y garantizar un óptimo local, mientras que los métodos metaheurísticos están diseñados para alcanzar, aunque no siempre se puede garantizar, un óptimo global. Como ya se indicó en el capítulo donde se revisaba el estado de la cuestión, son varios los autores que han utilizado estos métodos metaheurísticos para problemas de localización y en logística inversa como Antunes y Peeters (2000), Bautista y Pereira (2006) o Min et al. (2006). En el siguiente capítulo se analizan y describen algunos de los algoritmos metaheurísticos más utilizados en la literatura y se proponen dos de ellos como la metodología a utilizar en la búsqueda a los problemas de localización y minimización de costes planteados en esta tesis. 4.5. Conclusiones En este capítulo y partiendo de una revisión previa de la literatura se ha desarrollado el modelo matemático que servirá para analizar y minimizar los costes en los problemas de localización en la gestión de RSU. Se ha concluido que debido al número de variables tanto enteras como binarias y a las restricciones que se necesitarían aplicar, el modelo diseñado sería muy difícil de resolver o de muy alto coste computacional con métodos exactos para los modelos lineales planteados, convirtiéndose en un problema del tipo NP-duro, cuya resolución solo sería factible con métodos aproximados como son las técnicas metaheurísticas. En la sección anterior se han indicado los métodos de optimización cuantitativos, y técnicas metaheurísticas utilizadas en la investigación operativa actual. 56 De estos métodos, se proponen los metaheurísticos como la mejor alternativa para resolver de forma rápida los problemas de localización y minimización de costes en logística inversa de gestión de RSU, y que resultarían irresolubles utilizando otros métodos. Las técnicas metaheurísticas más utilizadas y sus aplicaciones se describen en el capítulo siguiente. La mayoría de los metaheurísticos han sido usados para resolver problemas estáticos como son: el algoritmo TS, seguido de SA y por último los algoritmos GA. De las técnicas metaheurísticas existentes en la literatura para probar la validez del enfoque propuesto, se han escogido dos, una de reciente incorporación en su uso por parte de científicos e investigadores y no utilizada hasta ahora para resolver problemas dinámicos en logística inversa según se pudo concluir en el capítulo anterior y la otra, un metaheurístico muy utilizado en distintas aplicaciones y aceptado en la comunidad científica. El hecho de utilizar las dos técnicas indicadas permitirá comparar resultados y acreditar la validez del nuevo metaheurístico propuesto. 57 Capítulo 5 5. TÉCNICAS METAHEURÍSTICAS UTILIZADAS En este capítulo se hace una revisión de distintas técnicas metaheurísticas (Alba (2005)) comentando las aplicaciones encontradas en la literatura para problemas de localización. Tras la revisión se seleccionarán dos de ellas, que posteriormente se utilizarán para seguir la metodología propuesta en el capítulo previo y se aplicarán en el problema de localización de instalaciones de transferencia y tratamiento de RSU. 5.1. Introducción La existencia de una gran cantidad y variedad de problemas difíciles, y que necesitan ser resueltos de forma eficiente, impulsó el desarrollo de procedimientos eficientes para encontrar buenas soluciones aunque no fueran óptimas. Estas técnicas, en las que la rapidez del proceso es tan importante como la calidad de la solución obtenida, se denominan metaheurísticas. Este término fue introducido por primera vez por Glover (1986). En Blum y Roli (2003) se recogen algunas definiciones de metaheurística, de entre las que se destaca la siguiente: “Un procedimiento de generación iterativo que guía una heurística subordinada, combinando de forma inteligente diferentes conceptos para explorar y explotar el espacio de búsqueda, utilizando estrategias de aprendizaje para estructurar la información a fin de encontrar de manera eficiente soluciones casi óptimas" (Osman y Laporte (1996)). 58 Las técnicas metaheurísticas proporcionan una buena solución del problema aunque no necesariamente óptima. Al contrario, los métodos exactos si proporcionan una solución óptima, si esta existe. Por otra parte, un método exacto puede consumir un tiempo excesivamente grande para encontrar la solución óptima de un problema complejo, que en muchos casos puede ser inaplicable. Los tiempos computacionales consumidos por un metaheurístico suelen ser más cortos. El término científico NP-duro está utilizado en el contexto de la complejidad algorítmica. En esta tesis, el problema de optimización de costes y localización visto en el capítulo anterior se considera NP-duro, por el número de variables y restricciones utilizadas y que como se verá en posteriores capítulos pueden llegar a no tener solución si se aplican métodos exactos o si existen, de un tiempo computacional muy elevado. Por tanto, aunque existen muchas razones para utilizar metaheurísticas para resolver un problema difícil, para el caso de esta tesis se destacan dos: La primera es que aunque existe un método exacto para resolver el problema, su uso es computacionalmente muy costoso y la segunda es que proporciona una buena solución de partida. 5.2. Técnicas metaheurísticas En esta sección se revisarán algunas de las técnicas metaheurísticas más utilizadas por la comunidad científica en distintos campos y se seleccionarán dos, para resolver los problemas de optimización de costes y localización dinámica de instalaciones en el sistema de logística inversa establecido para la recogida y transporte de residuos. También se describe la aplicación de la metodología vista en el capítulo anterior a los dos métodos propuestos: los algoritmos GA y PSO. 59 5.2.1. Algoritmos genéticos Los Algoritmos Genéticos o Genetic Alghorithm (GA) son métodos adaptativos utilizados para la resolución de problemas de búsqueda y optimización, inspirados en los procesos de evolución de los seres vivos, en su esfuerzo por adaptarse al entorno en el que habitan. Los principios básicos de los GA fueron establecidos por Holland (1975), donde se propone una forma de estudiar la evolución tanto de los sistemas naturales como de los artificiales (dentro de los cuales se engloban los problemas de optimización combinatoria). Los patrones de evolución de las especies son tales que, por un lado, con el transcurso del tiempo se exploran continuamente nuevas posibilidades y, por otro, en condiciones normales raramente conducen a la obtención de individuos absolutamente desadaptados e incapaces de sobrevivir. Estos algoritmos están incluidos en el grupo de técnicas evolutivas debido a que disponen en cada iteración de un conjunto de soluciones a partir de las cuales obtienen un nuevo conjunto de soluciones. Los GA operan de forma iterativa, de manera que cada iteración comienza con una población inicial, es decir, un conjunto inicial de soluciones, cada una de ellas representada mediante una cadena de números (típicamente, las cadenas son binarias). A veces, se habla de individuos y no de soluciones. Partiendo de dicha población se realizan manipulaciones a partir de las cuales se obtiene una nueva población. La función objetivo suele denominarse función de adaptación o aptitud y permite evaluar la bondad de las soluciones (individuos) consideradas en cada momento. Entre las principales operaciones realizadas en cada iteración están: la selección, el cruce, la reducción y la mutación. La aplicación reiterada de los operadores anteriores, permite alcanzar soluciones con mejores funciones de aptitud. En la literatura existen algunas aplicaciones de GA en la localización de instalaciones: Kongar (2003), Chau (2004), Bautista y Pereira (2006), Min et al. (2006), Ortega Mier (2008) y Ghezavati y Saadati (2014). 60 5.2.2. Recocido simulado El recocido simulado o Simulated Annealing (SA) es uno de los más antiguos metaheurísticos y seguramente uno de los primeros algoritmos que utilizo una estrategia explicita para evitar los mínimos locales. Esta técnica fue formulada por Kirkpatrick et al. (1983) y cuyos orígenes vienen de la mecánica estadística que estudia los procesos de recocido del metal y el cristal, asumiendo una configuración de baja energía cuando son enfriados con un adecuado programa de enfriamiento. SA fue presentado como un algoritmo de búsqueda de problemas de optimización combinatoria. Para evitar quedar atrapado en mínimos locales, la idea fundamental es moverse a soluciones con valores de la función objetivo que son peores que los valores actuales. En cada iteración, una solución es aleatoriamente elegida. Así, dado un sistema de Npartículas que pueden adoptar diferentes configuraciones, a una determinada temperatura Tla probabilidad de que el sistema adopte una determinada configuración sigue una distribución de Boltzmann dada por la expresión ( ) , donde Erepresenta la energía de esa configuración, Kb es la constante de Boltzmann y Tes la temperatura del sistema. Metropolis et al. (1953) propusieron un modelo para simular el comportamiento del proceso de solidificación a partir de lo anterior. En las referencias a logística inversa en la literatura utilizando algoritmos SA se ha encontrado a Antunes y Peeters (2000), Pishvaee (2010), Kassem y Chen (2013) y Ghezavati y Saadati (2014). 5.2.3. Búsqueda Tabú La búsqueda Tabú o Tabu Search (TS) es uno de los más exitosos metaheurísticos para la aplicación de problemas de optimización combinatoria. 61 Las ideas básicas fueron introducidas por Glover (Glover, 1989, Glover, 1990, Glover y Laguna, 1997) que propuso el algoritmo TS como un procedimiento para huir de óptimos locales basado en la utilización de la información del propio proceso de búsqueda. La idea básica de la búsqueda tabú es el uso explícito de un historial de la búsqueda (una memoria a corto plazo), tanto para escapar de los mínimos locales como para implementar su estrategia de exploración y evitar buscar varias veces en la misma región. Esta memoria a corto plazo se implementa con una lista tabú, donde se mantienen las soluciones visitadas más recientemente para excluirlas de los próximos movimientos. En cada iteración se elige la mejor solución entre las permitidas y la solución es añadida a la lista tabú. Desde el punto de vista de la implementación, mantener una lista de soluciones completas no suele ser práctico debido a su ineficiencia. Por lo tanto, en general, se suelen almacenar los movimientos que ha llevado al algoritmo a generar esa solución o los componentes principales que definen la solución. En cualquier caso, los elementos de esta lista permiten filtrar el vecindario, generando un conjunto reducido de soluciones elegibles denominado Na(s). El almacenamiento de los movimientos en vez de las soluciones completas es bastante más eficiente, pero introduce una pérdida de información. Para evitar este problema se define un criterio de aspiración que permite incluir una solución en Na(s) incluso si está prohibida debido a la lista tabú. El criterio de aspiración más ampliamente usado es permitir soluciones cuyo fitness sea mejor que el de la mejor solución encontrada hasta el momento. Referencias a logística inversa en la literatura utilizando TS solo se ha encontrado en Kongar (2003). 5.2.4. GRASP El procedimiento de búsqueda miope aleatorizado y adaptativo o Greedy Randomized Adaptive Search Procedure (GRASP) es un simple metaheurístico que combina heurísticos constructivos y de búsqueda local. 62 Fue propuesto por Feo y Resende (1995) y es un proceso iterativo compuesto de dos fases: construcción de la solución y proceso de mejora de la solución. El mecanismo de construcción de la solución es un heurístico constructivo aleatorio. Es decir, se genera una solución obtenida tras la ejecución de diferentes etapas, en cada una de las cuales se completa parcialmente la solución hasta llegar a una solución completa. En cada etapa se dispone de un conjunto de elementos candidatos para completar la solución. Estos elementos candidatos están contenidos en lo que se denomina lista de candidatos restringida. La lista restringida está formada por elementos que a priori pueden ofrecer buenas soluciones. De entre los elementos candidatos se elige uno de forma aleatoria. Tras la fase constructiva se modifica la lista restringida de candidatos. La segunda fase del algoritmo es un método de búsqueda local, la cual puede ser un algoritmo de búsqueda local básico como una mejora iterativa o técnicas avanzadas como SA o TS. Es una técnica que debido a su simplicidad (requiere el ajuste de pocos parámetros, lo cual hace más sencillo su diseño) es generalmente muy rápida y para determinados problemas, ofrece buenos resultados en un tiempo computacional muy corto. En la revisión de la literatura, sólo Bautista y Pereira (2006) resuelven un problema estático de logística inversa, de la localización de contenedores de basura en el área metropolitana de Barcelona mediante un GA combinado con un heurístico GRASP. 5.2.5. Colonia de hormigas La optimización por colonia de hormigas o Ant Colony Optimization (ACO) es una propuesta de metaheurístico inspirado en el comportamiento de búsqueda de alimento de hormigas reales. Estos métodos fueron propuestos por Dorico (1992). 63 Esta técnica trata de imitar el comportamiento de las hormigas que, cuando se desplazan dejan a su paso un rastro de feromonas que les sirve de medio de transmisión de información entre ellas para encontrar el camino más corto entre fuentes de comida y su hormiguero. Esta funcionalidad es explotada en colonias de hormigas artificiales con idea de resolver problemas de optimización combinatoria. En cada iteración se construye un conjunto de soluciones, de manera que en la construcción de la solución se emplea una lógica parecida a la de las hormigas al desplazarse empleando el rastro de feromonas. En términos de un problema de optimización, el rastro de feromonas depositadas por las hormigas se traduce en la probabilidad de pasar de un estado a otro determinado. Cada hormiga genera una solución mediante un método constructivo pasando por diferentes estados, donde cada estado representa una solución parcial. El estado final representa una solución completa. En la revisión de la literatura, no se han encontrado propuestas de este tipo de algoritmo para resolver problemas de localización de instalaciones y minimización de costes en logística inversa. 5.2.6. Búsqueda dispersa La búsqueda dispersa o Scatter Search (SS) es una metaheurística cuyos principios fueron presentados por Glover (1977) y que ha recibido una gran atención por parte de la comunidad científica (Laguna y Martí (2003)). El algoritmo se basa en mantener un conjunto relativamente pequeño de soluciones tentativas (llamado conjunto de referencia o RefSet) que se caracteriza por contener soluciones de calidad y diversas (distantes en el espacio de búsqueda). Para la definición completa de SS hay que concretar cinco componentes: creación de la población inicial, generación del conjunto de referencia, generación de subconjuntos de soluciones, método de combinación de soluciones y método de mejora. 70 Se parte de la función principal (5.4.1) con la que después de las varias generaciones programadas, se obtendrá una aproximación al óptimo de la función objetivo: [x,fval,exitFlag,output,population,scores] = ga (fun, nvars, Aineq, bineq, Aeq, eq, lb, ub, nonlcon, intcon, options). (5.4.1) Esta función puede resolver problemas lineales o no lineales. El problema planteado en esta tesis tiene la siguiente forma: min F(x) (5.4.2) sujeta a las siguientes restricciones: Aineq ∙x ≤ bienq (5.4.3) y con los límites: LB ≤ x ≤ UB (5.4.4) Es decir, se trata de resolver un problema lineal (5.4.2) con restricciones (5.4.3) y(5.4.4), que no puede ser resuelto con métodos exactos debido al elevado número de variables. Los operadores incluidos en la función (5.4.1) de MATLAB tienen que ser adecuadamente parametrizados para poder obtener el valor más cercano al óptimo buscado para resolver el problema de minimización de costes de transporte de residuos y localización de instalaciones. En la Figura 5.2 se puede ver el flujograma con los operadores que utiliza el algoritmo GA. Dentro de este diagrama, también se nombran algunas de las funciones utilizadas por MATLAB que permiten definir los parámetros utilizados por cada uno de los operadores. 71 Si Figura 5.2: Diagrama de flujo de GA utilizado en MATLAB. Fuente: Elaboración propia. A continuación se describen los operadores utlizados con la función (5.4.1) de MATLAB y cuales son las mejores funciones a utilizar para buscar el óptimo del problema planteado en el capítulo 4: Operador “generación de población inicial”: Uno de los factores más importantes que determina el rendimiento de los GA es la “diversidad” de la población. Si la distancia promedio entre los individuos es grande, la “diversidad” será alta; si la distancia media es pequeña, la “diversidad” será baja. El valor correcto de “diversidad de población” se controla con el parámetro de rango inicial de población: “PopIniRange”. Por defecto, el GA crea una población inicial aleatoria con una distribución uniforme usando la función creación (@gacreationuniform). Se GENERACIÓN POBLACIÓN INICIAL (CreationFcn: @gacreationuniform) (CREA EVALUACIÓN DE LA FUNCIÓN OBJETIVO DE INDUVIDUOS DE POBLACIÓN INICIAL (FitnessScalingFcn: @fitscalingrank) FIN/HIBRIDACIÓN SELECCIÓN (SelectionFcn: @selectiontournament) CRUCE (CrossoverFcn: @crossoverintermediate) MUTACIÓN/REDUCCIÓN (MutationFcn: @mutationuniform) ¿CRITERIO SATISFECHO? 72 puede especificar el rango inicial de población, con el parámetro de población. El GA puede encontrar el óptimo, incluso si este no se encuentra en el rango inicial, si la población tiene bastante diversidad. Operador “Selección”: El GA aplica selecciones de padres de hijos de cruce o mutación. La función “Selección” asigna la mayor probabilidad de selección de individuos como padres, proporcional al valor de su función objetivo. Si los valores escalados varían demasiado ampliamente, los individuos con los valores más altos en la escala, se reproducen demasiado rápido, tomando el relevo la descendencia genética de la población con demasiada rapidez, y evitando que el GA busque otras áreas del espacio de soluciones. Por otra parte, si los valores escalados varían sólo un poco, todos los individuos tienen aproximadamente la misma posibilidad de la reproducción y la búsqueda progresará muy lentamente. Se puede parametrizar la selección a partir de un muestreo estocástico universal especificado en la función de selección (@selectionstochunif)o con la función de selección (@selectiontournament, 2) que a partir de un muestreo mediante la técnica de torneo binario, se eligen 2 padres aleatorios y se queda el mejor según su función de aptitud. Operador “Evaluación”: Obtiene los valores de la función fitness para ser utilizados por el operador “Selección”. Existen varias funciones de evaluación como (@fitscalingprop) o (@fitscalingshiftlinear), aunque se usará la función de evaluación (@fitscalingrank),que escala las puntuaciones directas basadas en el rango de cada individuo en lugar de su puntuación. El rango de un individuo es su posición en la escala de puntuaciones: el rango de la persona más óptimo es 1, el siguiente es 1√2, y así sucesivamente. Operador “Cruce”: El GA aplica hijos de cruces mediante la opción que se especifique en la función de cruce (@crossoverscattered), que crea hijos de cruce de la población dada, usando los padres disponibles en un cruce uniforme o con la función (@crossoverintermediate), donde se combinan dos padres para formar hijos de cruce para la siguiente generación. 73 Los hijos se crean como la media ponderada de los padres (child = parent1 + rand ∙ Ratio ∙ ( parent2 - parent1). Se elige un 5% de hijos élite (EliteCount), que son los individuos que sobrevivirán a la siguiente generación. El parámetro CrossoverFraction, en las opciones de reproducción, especifica la fracción de cada población, con excepción de los niños de élite que componen los hijos de cruce. Una fracción de cruce de 1 significa que todos los hijos, con excepción de los hijos élite, son los hijos de cruce, mientras que una fracción de cruce de 0 significa que todos son hijos de mutación. Ninguno de estos extremos es una estrategia eficaz para la optimización de la función. Operador “Mutación”: El GA aplica mutaciones mediante la opción que se especifique en la función elegida. Con la función mutación (@mutationuniform, 0.01) se genera una mutación aleatoria de hijos en la población, que proporciona una diversidad genética para buscar la solución en un espacio más amplio. Se selecciona la fracción 0,01 de la población que va a ser sustituida por el número aleatorio de una distribución uniforme. Otra opción de función mutación es Gaussiana (@mutationgaussian). Añade un número aleatorio o mutación elegido a partir de una distribución Gaussiana a cada entrada del vector padre. Típicamente, la cantidad de mutación, que es proporcional a la desviación estándar de la distribución, disminuye en cada nueva generación. Se puede controlar la cantidad promedio de mutación que el algoritmo aplica a cada uno de los padres en cada generación a través de los parámetros “Escala” y“Reducción”. Depués de describir los operadores y las funciones que se pueden usar con el algoritmo GA de MATLAB, en la Tabla 5.1 se indican que funciones y valores son utilizados en esta tesis para parametrizar el algoritmo GA. 74 Tabla 5.1: Funciones y valores usados como parámetros GA. Fuente: Elaboración propia. El esquema general del método propuesto se muestra en el Pseudocódigo1 del algoritmo genético utilizado en MATLAB. Pseudocódigo1: algoritmo genético -Inicializa parámetros por defecto -Comprueba argumentos de entrada -Si no es correcta la estructura argumentos mensaje de error -Llama a la función “gacommon” - Cambia las restricciones a un valor correcto si están vacías -Llama al solver adecuado para resolver la función objetivo: - gaminlp (con enteros) - galincon (lineal con restricciones) - gaunc (sin restricciones) - gacon (no lineal con restricciones) - End ga Por último, para detener el proceso se definen los criterios que determinan que el algoritmo se pare. Se pueden especificar las siguientes opciones: a. Especificando el número máximo de iteraciones que el GA puede realizar antes de parar. 75 b. Especificando el tiempo máximo en segundos que el GA se puede ejecutar antes de parar, medido por el tiempo de ordenador (cputime). c. El algoritmo se detiene si el mejor valor de fitness es menor o igual a un valor límite de fitness. d. El algoritmo se detiene si el cambio relativo medio en el mejor valor de la función de fitness es menor o igual a una función de tolerancia. e. El algoritmo se detiene si no hay una mejora en el mejor valor de la aptitud para un intervalo de tiempo (en segundos) especificado por un límite de tiempo, medido por cputime. 5.5. Aplicación de la metodología propuesta mediante optimización de enjambre de partículas Si la anterior técnica metaheurística tenía interés por su aceptación en la comunidad científica, esta segunda metodología propuesta tiene interés por una parte, por ser una técnica más moderna y actual que las utilizadas hasta ahora en aplicaciones de búsqueda y por otra parte, novedosa en cuanto su uso como técnica de localización de instalaciones ya que en la revisión de la literatura sobre PSO no se ha encontrado ningún autor que la aplique en el campo de la logística inversa de residuos ni en la identificación de instalaciones en general. PSO es un algoritmo bioinspirado en el comportamiento social de individuos dentro de enjambres en la naturaleza. Fue originalmente desarrollado para problemas continuos, pero existen adaptaciones del método a problemas discretos. Esta técnica evolutiva se basa en el paradigma de inteligencia colectiva y trata de emular el comportamiento de los bancos de peces, enjambre de abejas o bandadas de pájaros con el objetivo de solucionar problemas de optimización complejos. 76 Los agentes de búsqueda de este método son las partículas, las cuales son soluciones potenciales que tienen una posición y velocidad asociada. Estas partículas “vuelan” a través de un espacio multidimensional ayudándose de su propia experiencia, del conocimiento del enjambre y de operadores estocásticos. Así, las partículas modifican sus posiciones a las que tienen la mejor solución del momento, tendiendo a concentrarse en áreas potencialmente buenas. PSO comparte algunas similitudes con otras técnicas evolutivas, pero a diferencia de otros métodos, el número de parámetros que se deben ajustar es pequeño según Eberhart y Shi (2001). Esto hace que la implementación, comparada con otras técnicas evolutivas, sea más sencilla. PSO ha sido utilizado con gran éxito para solucionar problemas de tipo continuo. Algunos ejemplos donde se ha demostrado su efectividad son: Entrenamiento de redes neuronales por Eberhart y Shi (2001), y Funciones continuas no lineales por Ching-Jong et al. (2007). PSO puede ser utilizado para resolver la mayoría de los problemas de optimización, como el problema de localización en logística inversa de esta tesis, que al ser un problema de optimización combinatoria que pertenece a la clase NPduro, implica que es un problema no tratable con métodos tradicionales. Previo a resolver el problema de optimización de logística inversa diseñado en el capítulo anterior, se verá el modelo matemático genérico que define al algoritmo PSO y poder aplicarlo, al igual que con GA, con el lenguaje matemático MATLAB. La solución potencial es representada en PSO por un vector llamado partícula o simplemente solución. Cada una de estas partículas itiene la misma dimensión n(variables de la función obtetivo) y se representan de la siguiente manera: X (i) = (x(i1), x(i2),…, x(in) ) (5.5.1) 77 Las partículas, sobre el espacio de búsqueda n-dimensional, “vuelan” tratando de encontrar una solución óptima. Para hacer esto, cada individuo ajusta su posición de acuerdo a una combinación lineal de su inercia, su propia experiencia y del conocimiento del enjambre. Cada agente almacena en una memoria la mejor posición encontrada hasta el instante actual t. La experiencia de la partícula se denota como: P (i) = (p(i1), p(i2),…, p(in) ) (5.5.2) El conocimiento del enjambre es el conjunto de memorias de cada partícula. A diferencia de los GA, en PSO no existe la competencia entre individuos. En cada interacción, cada partícula pone a disposición de los demás su memoria de conocimiento. La asignación de informantes (vecindario) es una forma de compartir la experiencia. Cada partícula recibe información de kagentes seleccionados de forma aleatoria en cada iteración del algoritmo. Después, la partícula determina entre sus informantes aquel que tenga la mejor aptitud previa. Posteriormente, lo selecciona para que sea parte del proceso de actualización de su posición. Normalmente, el valor de kes pequeño, sin embargo, puede ser tan grande como el tamaño del enjambre. Este último criterio hace que las partículas tiendan hacia la mejor partícula encontrada hasta algún instante t. Las características del problema a solucionar determinan cual de los dos métodos es más adecuado para su implementación. La mejor partícula del vecindario se representa por: G (i) = (g(i1), g(i2),…, g(in) ) (5.5.3) Al igual que en otros algoritmos de tipo evolutivo, PSO necesita de una función de evaluación (también llamada función de aptitud). Esta permite determinar la calidad de las soluciones. Su importancia radica en que es la única forma de poder evaluar la posición de cada elemento. Cada coordenada (elemento) de Xde cada partícula tiene una velocidad o razón de cambio V, para d  1, 2,..., n. V (i) = (v(i1), v(i2),…, v(in) ) (5.5.4) 78 Para realizar un desplazamiento, la partícula determina la velocidad considerando su propia inercia W(busca evitar la convergencia prematura), su memoria de conocimiento y su confianza en el enjambre, para después, sumarla a la posición actual. El grado de confianza lo determinan los operadores aleatorios r1yr2en el rango [0-1] junto con los coeficientes de confianza c1yc2. Estos últimos, también llamados constantes de aceleración, son los términos que tiran a cada partícula hacia las posiciones PyGsegún Eberhart y Shi (2001). En otras palabras, las partículas hacen un movimiento hacia un punto intermedio tomando en cuenta la mejor posición previa, el mejor informante y un punto accesible desde la posición actual (Figura 5.3). Las ecuaciones siguientes ajustan la velocidad y posición de cada partícula: Vit+1  wtVit+ c1r1t(Pi  Xit) + c2r2t(Gi  Xit) (5.5.5) Xit+1  Xit+ Vit+1 (5.5.6) Donde: Vit+1 : Velocidad ajustada wt: Coeficiente de inercia c1: Coeficiente de confianza en la experiencia (CognitiveAttraction) c2: Coeficiente de confianza en la experiencia del grupo (SocialAttraction) Pi: Mejor posición previa de i Xit: Posición actual de i Gi: Mejor posición previa encontrada por el grupo r1tyr2t: Operadores aleatorios entre 0 y 1 Xit+1 : Posición de la partícula idespués del ajuste 79 Figura 5.3: Modificación de la posición de la partícula i. Fuente: Eberhart y Shi (2001). En el proceso de actualización de la velocidad están implicados operadores aleatorios, por lo que el método de modificación de la posición de las partículas es estocástico. En términos generales, PSO se puede describir en tres pasos. El primero es evaluar cada elemento para determinar la calidad de la posición actual. Esto permite que se puedan encontrar la mejor posición y las mejores partículas. Después, se deben realizar los ajustes necesarios de las mejores posiciones previas. Por último, se determinan los nuevos desplazamientos para cada partícula con la información ajustada. Por analogía, estos movimientos no son más que una forma de tratar de imitar a otros individuos. Para detener el proceso se necesita que un criterio de parada se cumpla. Este puede ser determinado por un número fijo de iteraciones, opcionalmente combinado con un umbral de error aceptable. Al terminar la ejecución del algoritmo, la solución mostrada es la mejor posición previa encontrada por alguna partícula. 86 6.2. Buscando aplicaciones informáticas de optimización Hoy en día es posible adquirir una gran variedad de aplicaciones que resuelvan los problemas de optimización. Una de las ventajas de usar un programa comercial es su velocidad de resolución, ya que gran parte de los cálculos de álgebra de estos programas se hacen desde librerías muy optimizadas, pero también incorpora una serie de recursos que posiblemente nunca se utilizarán. Como se ha adelantado en la introducción, para modelar y resolver el problema diseñado en el capítulo 4 se utilizarán métodos exactos y las técnicas metaheurísticas propuestas en el capítulo 5. Se podría desarrollar un programa de resolución en C u otro lenguaje adaptado al problema, y evitar así hacer operaciones internas que un programa comercial dedica a otros aspectos que no se necesitan. Sin embargo, la efectividad y la velocidad de modelado que proporciona un programa comercial es un factor que ha determinado su uso en esta tesis. Este punto no es menor, es importante realizar un estudio preliminar porque la difusión y herramientas de técnicas y software en este campo de la Organización Industrial aún no tiene unos mecanismos de trabajo establecidos para hacer el tipo de investigación que se hace en la tesis. Dentro de los programas comerciales más usados se encuentran, aparte del lenguaje matemático MATLAB (MATrix LABoratory) aplicado en ésta tesis, GAMS (General Algebraic Modeling Sistem), AMPL (A Mathematical Programming Language) ó AIMMS (Advanced Interactive Multidimensional Modeling System), que modelarían el problema de optimización lineal mixta y resolverían los solvers del tipo: CPLEX, MINOS, GLPK, el comando linprog del complemento Matlab Optimization Toolbox o incluso los solvers de Microsoft Excel yOpenOffice. 87 El inconveniente de algunos de estos lenguajes es que tanto GAMS, AMPL o AIMMS necesitan desarrollar en un lenguaje de alto nivel como C++, Java, etc., las técnicas metaheurísticas propuestas, mientras que con MATLAB se pueden programar tanto el algoritmo exacto como los metaheurísticos propuestos. Así mismo, debido a que MATLAB, GAMS, AMPL o AIMMS son software de carácter propietario, para hacer un uso total de estos sería necesario adquirir una cara licencia comercial. Aunque la comunidad de usuarios de AIMMS, ha puesto de manera pública una distribución de demostración, pero limitada a las siguientes condiciones: 1. Límites del modelo (licencias estudiantes): - Número de restricciones y variables: 300 - Número de elementos identificadores: 200 -Solvers: CPLEX, GUROBI, KNITRO 2. Límites de tiempo (licencias de demostración): - Para licencias demostración: 30 días de uso, sin limitación de variables ni restricciones, pero con limitación en el uso de solvers. Tabla 6.1: Herramientas de resolución, indicando los problemas que pueden resolver. Fuente: Elaboración propia. 88 En la Tabla 6.1 se describen algunos de los solvers más utilizados, indicando los tipos de problemas que resuelven, los algoritmos usados, tipo de licencia y limitaciones de uso. Igual ocurre con AMPL o GAMS, de los cuales se puede descargar una versión de evaluación con limitación del número de variables y restricciones (300), o limitación en el número de días de uso. Con estas limitaciones, solo se podrían modelar algunos problemas simples de optimización lineal mixta y comparar con el óptimo alcanzado con el metaheurístico. En la Tabla 6.2 se pueden ver las limitaciones de estos lenguajes, indicando los solvers que pueden usar y el tipo de licencia. Tabla 6.2: Herramientas de modelado, indicando los solvers compatibles. Fuente: Elaboración propia. 89 De todos los lenguajes citados, solo MATLAB permite modelar y resolver el problema de optimización mediante métodos exactos y técnicas metaheurísticas al mismo tiempo, sin tener que utilizar otro lenguaje de alto nivel. Por otra parte y aunque MATLAB y sus complementos también están sujetos a licencia comercial, en el entorno académico resulta más accesible utilizar esta herramienta informática disponible en la mayoría de las universidades españolas y con un alto grado de aceptación frente al uso de las otras herramientas comerciales, con alto coste económico. Como conclusión y tras ver algunas ventajas e inconvenientes de los lenguajes comerciales, en esta tesis se utilizará como herramienta informática el lenguaje matemático MATLAB al permitir unificar tanto métodos exactos como metaheurísticos. Las características generales de MATLAB son ampliamente conocidas en el ámbito de la Ingeniería por haberse utilizado en gran cantidad de asignaturas y prácticas de laboratorio, por lo que se entiende que no será necesaria su descripción. MATLAB incluye el complemento Matlab Optimization Toolbox, que permite resolver problemas de optimización global (convexos y no convexos). Mediante funciones del tipo “intlinprog” o “linprog” se resuelven los problemas lineales con variables mixtas (enteras y binarias) o continuas. En los problemas convexos se podría utilizar el comando “fmincon”, en el que se puede especificar el uso de algoritmos de punto interior. También cuenta con dos funciones metaheurísticas, como son “ga” que encuentra el mínimo de la función objetivo aplicando el algoritmo GA y “simulannealbnd” que encuentra el mínimo de la función aplicando el algoritmo SA. Como ya se indicó en el capítulo anterior, para resolver el problema de optimización de localización de instalaciones se utilizarán dos metaheurísticos: GA y PSO. Como MATLAB, en la versión utilizada en esta tesis (la R2014b), solo incluye los GA, para trabajar con el algoritmo PSO se ha tenido que desarrollar esta función. 90 La programación en MATLAB comprenderá varias etapas. En una primera etapa se desarrollará el código en MATLAB para resolver el problema de localización mediante programación lineal y para distintos rangos de variables, hasta llegar al número de variables y restricciones necesarias para resolver el problema de optimización del caso real. En una segunda se desarrollará el código en MATLAB para poder aplicar los algoritmos metaheurísticos y en la tercera etapa se comparán con los resultados obtenidos mediante programación lineal. El programa principal en MATLAB para la programación lineal tiene las siguientes funciones: -Lee los datos iniciales del problema (Pit, dij, djk), desde un archivo EXCEL (Figura 6.1) mediante el comando “xlsread” (por ejemplo: Pit=xlsread ('Produresimuni(it).xlsx','Produ90')). Esta acción, para matrices con elevado número de parámetros, puede tomar algunos segundos. Figura 6.1: Archivo Excel con datos de distancias entre municipios. Fuente: Elaboración propia. 91 -Una vez leídos todos los parámetros del problema, se calcula la función objetivo aplicando distintos bucles. En MATLAB hay que evitar, si es posible, los anidamientos en el bucle para no reducir excesivamente la velocidad de ejecución. -Un ejemplo de Bucle utilizado para el cálculo de la variable x(cantidad de residuos transportados) del problema se muestra en Código.1. Código.1: Bucle variable x for i=1:length(Pit) for j=1:length(Pit) for t=1:5 if cont~=8001 fx(cont,1)=CMTt(1,t)*dij(i,j); cont=cont+1; end end end end fx=round(fx'); -Una vez desarrollada la función objetivo, se codifican las restricciones del problema calculando las matrices Aybde la inecuación A∙x ≤ b. Si las matrices son grandes (20×20×5, 40×40×5 o 90×90×5), se puede aprovechar su estructura utilizando la descomposición de Cholesky, o el complemento de Schur para facilitar la factorización en formas más sencillas. Estas técnicas hacen que MATLAB sea más rápido. -Con las restricciones del problema ya planteadas se establecen los límites de las variables “x”,”y”, “v” y “z”, considerándolas enteras o binarias, según se especificó en el problema de optimización. -Finalmente, se calcula el óptimo utilizando el comando: “intlinprog”. Este comando se incorporó en MATLAB en el segundo semestre del año 2013 calculando problemas de programación lineal mixta (con variables enteras y binarias), que los solvers anteriores no podían resolver. 92 Los resultados obtenidos con MATLAB mediante programación lineal para diferente número de municipios en el problema de localización de instalaciones se pueden ver en la Tabla 6.3. Tabla 6.3: Resultados de programación lineal en MATLAB para distintos municipios. Fuente: Elaboración propia. Como se puede observar en la Tabla 6.3, para los primeros 40 municipios se han alcanzado los valores óptimos (Fval) mediante métodos exactos con MATLAB y con tiempos de ejecución bajos (1,46 s., para una matriz de 40×40×5). El problema surge cuando se aumenta el número de municipios. Así, para el caso de los 90 municipios, donde la función objetivo incluye 81900 variables y 41865 restricciones, MATLAB es incapaz de resolver mediante programación lineal este problema de optimización, al ser un problema NP-duro. Como se indicó en capítulos anteriores, la solución óptima solo podrá ser obtenida de forma aproximada mediante las técnicas metaheurísticas propuestas, de ahí que aparezcan guiones en la Tabla 6.3: no se pueden dar resultados en un tiempo razonable con MATLAB (días o semanas). Para comparar los resultados obtenidos con MATLAB y presentados en la Tabla 6.3, se han realizado las mismas pruebas realizando la programación con la versión de evaluación del programa comercial AIMMS 4.6 y el solver CPLEX 12.6.1 obteniéndose los resultados mostrados en la Tabla 6.4. 93 Tabla 6.4: Resultados de programación lineal con AIMMS para distintos municipios. Fuente: Elaboración propia. Los resultados de la programación con AIMMS son los mismos que los obtenidos con MATLAB, con la única diferencia de que los tiempos de respuesta de este programa dedicado son sensiblemente inferiores a los obtenidos con MATLAB, pero incluso así, tras largos tiempos de espera el óptimo aún se resiste, y AIMMS no devuelve ningún resultado en absoluto para el problema de los 90 municipios. Figura 6.2: Programa AIMMS con los resultados óptimos para 40 municipios. Fuente: Elaboración propia. En la Figura 6.2, se pueden observar los resultados obtenidos con el programa AIMMS para 40 municipios, necesitando 1531 iteraciones para 94 alcanzar el óptimo de 14581122 en un tiempo de 0,59 segundos. También se pueden ver los resultados de las variables binarias vijt yzjkt indicando los municipios donde se deberían instalar los centros de transferencia y las plantas de tratamiento. Como se ha podido comprobar en las Tablas 6.3 y 6.4, los tiempos de ejecución obtenidos en MATLAB son más largos que con los lenguajes compilados, esto se debe a que MATLAB es un lenguaje interpretado. Para compensar en parte esto, en muchas de las funciones programadas tanto en programación lineal como en la programación de los metaheurísticos se ha utilizado el comando “coder” (convierte funciones con extensión .m, en funciones compiladas con extensión .mexw64), que permite compilar parte del programa interpretado de MATLAB, obteniendo mejores tiempos de ejecución. Según los resultados reflejados en las Tablas 6.3 y 6.4, los métodos exactos usados por MATLAB y AIMMS son insuficientes para resolver los problemas de optimización con matrices de 90×90×5. Es a partir de este momento, cuando toma interés el uso de las técnicas metaheurísticas propuestas. 6.2.1. Resultados en MATLAB con algoritmos genéticos Los resultados obtenidos con MATLAB aplicando un GA (con los parámetros descritos en el capítulo 5) para los diferentes ejemplos de problemas de localización de instalaciones se muestran en la Tabla 6.5. Tabla 6.5: Resultados aplicando algoritmos genéticos con MATLAB para distintos municipios. Fuente: Elaboración propia. 95 Como se puede observar en la Tabla 6.5, los valores promedios obtenidos de la función aptitud (fval) aplicando GA mediante MATLAB son soluciones cercanas a las obtenidas con métodos exactos para 6, 20 y 40 municipios, por lo que se pueden considerar válidos los valores alcanzados para 90 municipios, que será la solución cuasi-óptima para el caso real planteado. La principal diferencia se da en unos tiempos de ejecución bastante mayores con GA, si bien existen valores de fval para cualquier número de municipios, hecho que no se da con los métodos exactos. El resultado indicado en la Tabla 6.5 corresponde al valor promedio de dichas ejecuciones. El tiempo de ejecución de una llamada al GA está en 7,54 segundos, frente a los 185,97 segundos necesario para obtener un valor promedio sobre 30 ejecuciones. En la siguiente sección, en la Tabla 6.7 se pueden comparar los datos obtenidos con las distintas técnicas utilizadas, incluidos los resultados conseguidos con los métodos exactos, tanto con MATLAB como con AIMMS. Algoritmos Genéticos 20 municipios 40 municipios Figura 6.3: Resultado de los mejores valores de la función aptitud para 30 ejecuciones de GA con 20 y 40 municipios. Fuente: Elaboración propia. En la Figura 6.3 se muestran los resultados de 30 ejecuciones del GA para 20 y 40 municipios. Nótese que la escala del eje vertical es distinta en cada problema. 102 Optimización por enjambre de partículas (PSO) 6 municipios 20 municipios 40 municipios 90 municipios Figura 6.6: Resultado de los mejores valores de la función aptitud después de 30 ejecuciones del algoritmo PSO con restricciones, para 6, 20, 40 y 90 municipios. Fuente: Elaboración propia. Como ya se expuso en la sección 5.5 del capítulo 5, una parte fundamental en la programación de la función PSO en MATLAB es escribir el código con las ecuaciones (5.5.5) y(5.5.6) que ajustan la velocidad y posición de cada partícula, de acuerdo con Eberhart y Shi (2001). Igualmente, se debería cumplir que las condiciones en (5.5.10) estén satisfechas, para garantizar que el sistema converge a un punto de equilibrio estable (Pérez y Behdinan (2007)). Estas condiciones pueden cumplirse fácilmente asignando valores a los coeficientes de confianza e inercia que los hagan cumplir. 103 Por tanto, el código en MATLAB para ajustar la velocidad y posición de cada partícula se muestra en Código.3. Código.3: Ajuste velocidad y posición PSO % Update Velocity and Position R1 = rand(N,Nvars); % random Number 1 R2 = rand(N,Nvars); % random Number 2 Velocity = W.*Velocity + C1.*(R1.*(LocalBestPosition-CurrentPosition)) + C2.*(R2.*(GlobalBestPosition-CurrentPosition)); CurrentPosition = CurrentPosition + Velocity ; Donde la mejor posición local y global corresponde a los valores de la mejor función aptitud (fitness) local y global buscada. Los parámetros R1 yR2 son números aleatorios uniformemente distribuidos entre [0, 1], cuyo objetivo es emular el comportamiento estocástico que exhibe la población o enjambre, en cada iteración. El valor inicial de la posición actual (CurrentPosition) se calcula rellenando una matriz con números de columnas igual al número de variables (81900, para el caso de 90 municipios) y 30 filas que son las semillas aleatorias del vector posición. Los números que se utilizan para rellenar esta matriz son obtenidos mediante el comando generador de números de distribución uniforme (random (‘unif’)), entre los límites inferior y superior del problema de localización de instalaciones. El valor mínimo global se obtiene de los distintos mínimos locales obtenidos en sucesivas iteraciones de la función objetivo. El pseudocódigo del algoritmo PSO se describe en Pseudocódigo.3.2.1. 104 Pseudódigo.3.2.1: Algoritmo PSO 1. Inicializar la población. 2. La mejor posición previa es igualada a la posición actual. 3. Cada posición es evaluada en la función de aptitud para determinar la calidad de la solución. 4. Se compara la aptitud de la posición actual con la mejor previa. 5. Determinar la mejor partícula del vecindario. 6. Ajustar la velocidad. 7. Ajustar la posición. 8. Verificar si se cumple el criterio de parada. 6.3. Aplicación de metaheurísticas al caso real de la provincia de Málaga En la sección anterior se obtuvieron resultados para diferente número de municipios comparando los resultados alcanzados con métodos exactos, GA y PSO. El objetivo de aquella comparación es demostrar que el único método válido para resolver el problema de los 90 municipios (caso real) es mediante las dos técnicas metaheurísticas utilizadas en las secciones anteriores. En la Tabla 6.7 se muestra un resumen de todos los valores vistos en las secciones anteriores, en la que se pueden comparar datos obtenidos con las distintas técnicas utilizadas. En negrita se indican los mejores tiempos y fitness por instancia. 105 Tabla 6.7: Resumen de resultados obtenidos con distintas técnicas y distintos municipios. Fuente: Elaboración propia. En esta sección la función objetivo, restricciones y los dos metaheurísticos utilizados solo se aplicarán para resolver el caso real de gestión de residuos de los 90 municipios diseminados por la provincia de Málaga. Al final de la sección se presentará como quedaría dibujada la nueva red de distribución de RSU entre municipios, centros de transferencia y plantas de tratamiento con las dos técnicas metaheurísticas usadas. El problema real que se pretende resolver consiste en la optimización de la red de recogida de RSU de 90 municipios de la provincia de Málaga, que junto a la Diputación de esta provincia, constituyen un “Consorcio Provincial de Residuos Sólidos Urbanos”. Los RSU recogidos de los distintos municipios son transportados a distintos centros de transferencia y finalmente, valorizados y eliminados (si es el caso) en las plantas de tratamiento o complejos medioambientales. 106 Actualmente, existen dos plantas de tratamiento que reciben todos los RSU procedentes de los 90 municipios: La planta de tratamiento, clasificación y recuperación de Antequera (Complejo Medioambiental de Valsequillo) y la de Casarabonela. También, existen cinco Centros de transferencia: 1Centro de Transferencia de RSU de Vélez-Málaga (recibe residuos de 31 municipios) (136.000 T/año) 2Centro de Transferencia de RSU de Ronda (recibe residuos de 21 municipios) (32.000 T/año) 3Centro de Transferencia de RSU de Cártama (recibe residuos de 6 municipios) (74.300 T/año) 4Centro de Transferencia de RSU de Archidona (recibe residuos de 6 municipios) (14.500 T/año) 5Centro de Transferencia de RSU de Campillos (recibe residuos de 8 municipios) (15.500 T/año) Sobre el escenario real descrito con la ubicación actual de cada instalación se plantea la hipótesis de reestructurar esta red de recogida de residuos, de forma que se minimicen los costes de gestión de estos residuos aplicando las ecuaciones diseñadas en el capítulo 4 y los metaheurísticos propuestos en el capítulo 5. El número de municipios (90) y lo expuesto en las secciones del capítulo anterior definen la necesidad de aplicar técnicas metaheurísticas al problema. Evidentemente, tanto las fórmulas desarrolladas como los metaheurísticos utilizados son extrapolables a cualquier provincia española con una dimensión municipal parecida (≥90 municipios). Tras diversas reuniones con distintos responsables de la Diputación de Málaga (Jefe de Explotación) y de la Gerencia de LIMASA (Director Gerente y Jefe de División de CAM), se obtuvieron los datos necesarios para poder resolver la hipótesis planteada en esta tesis, sobre el sistema actual de recogida malagueño. 107 Todos los datos recopilados están incluidos en el Anexo D y se corresponden con los parámetros necesitados de producción (Pit), distancias entre los 90 municipios (dij, djk), costes unitarios de transporte entre municipios, centros de transferencia y plantas de tratamiento (CMTt, CTPt), costes fijos (CFjt, CFkt) y capacidades anuales (QTjt, QPkt). En algún caso, los datos se han ajustado a las necesidades del diseño matemático, como en los siguientes casos: -Los costes de transferencia entre centros de transferencia y plantas de tratamientos vienen indicados independientes como costes totales (€), toneladas transferidas (T), número de viajes y kilómetros realizados de ida y vuelta. Para el modelo matemático, estos costes deben venir en €/km∙T. En la Tabla 6.8 se pueden ver algunos de estos datos. -Los costes fijos de centros y plantas según LIMASA se estiman en €/T transferida. En el modelo solo se utilizarán €. -En el modelo matemático no se consideran los costes de recogida de los contenedores dentro de cada municipio, solo el total de residuos transportados. Tampoco se consideran otros conceptos de costes de las instalaciones como pueden ser: costes de amortización de la instalación, de mantenimiento y reparación, iluminación, agua, generales, personal, etc. Solo se consideran los costes en €/T transferida. Los datos manejados corresponden a un periodo de cinco años, entre el 2010 y el 2014. Tabla 6.8: Costes sin estaciones, entre centros de transferencia y plantas tratamiento en Málaga 2013. Fuente: Diputación de Málaga. 108 Todos los resultados obtenidos hasta ahora con los distintos algoritmos se han alcanzado con un ordenador Intel Core i7-4720-HQ (doble núcleo) con CPU 2,60 GHz, 1 TB HD, 16 GB de RAM, bajo Windows (×64). Como inicio para resolver el problema se considerará la restricción de que el número de plantas de tratamiento sean dos a fin de poder comparar los datos obtenidos, al resolver el problema de optimización, con los datos reales. Para la ubicación de los centros de transferencia se considerarán todos los municipios como candidatos. Las mejores soluciones obtenidas con cada uno de los metaheurísticos se muestran en la Tabla 6.9, y corresponden al promedio de 30 ejecuciones por cada algoritmo. Tabla 6.9: Resultados aplicando algoritmos PSO y GA con MATLAB para 90 municipios. Fuente: Elaboración propia. Se ha partido con una población de 20 individuos y se han establecido 100 generaciones, antes de detener la ejecución de los algoritmos. El resto de parámetros de cada técnica quedaron especificados en el capítulo anterior. No se conoce solución óptima, ya que con el método exacto no se ha podido alcanzar. En las Figuras 6.7 y 6.8 se muestran los resultados obtenidos tras una ejecución con cada uno de los metaheurísticos. 109 Optimización por enjambre de partículas (PSO) Figura 6.7: Resultado de los mejores valores de la función aptitud para una ejecución con PSO, para 90 municipios. Fuente: Elaboración propia. Optimización GA 30 generaciones Figura 6.8: Resultado de los mejores valores de la función aptitud para una ejecución de GA y 30 generaciones, para 90 municipios. Fuente: Elaboración propia. 110 Optimización GA 100 generaciones Figura 6.9: Resultado de los mejores valores de la función aptitud para una ejecución de GA y 100 generaciones, para 90 municipios. Fuente: Elaboración propia. En la Figura 6.9 se ve la evolución de los mejores valores de GA tras 100 ejecuciones. Optimización por PSO Optimización por GA Figura 6.10: Resultado de los mejores valores de la función aptitud para 30 ejecuciones con PSO y GA para 90 municipios. Fuente: Elaboración propia. 111 En la Figura 6.10 se muestra la evolución de los mejores valores tras 30 ejecuciones con cada uno de los metaheurísticos. Los valores promedio de estas últimas ejecuciones se corresponden con los datos mostrados en la Tabla 6.9. Aunque los resultados obtenidos con las dos técnicas son parecidos, el algoritmo PSO se muestra más eficiente que los GA, al resolver problemas grandes (matriz de 90×90×5 variables) con bastante menos tiempo de computación y con la facilidad de tener que configurar menos parámetros. La verificación de los resultados de las figuras anteriores se realiza aplicando la prueba de la “t de Student” para una muestra. La prueba se aplica a tamaños de 40 y 90 municipios por ser más significativos. El valor contraste, en el caso de 40 municipios, se realiza entre el óptimo alcanzado con métodos exactos (las 30 muestras iguales) y los dos metaheurísticos. En el caso de 90 municipios, el valor contraste es medido entre las muestras obtenidas con la técnica GA y los valores fitness de la muestra PSO. Se toman como muestra los 30 valores fitness de cada técnica metaheurística (GA y PSO), y el t-test evalua si es razonable mantener la Hipótesis nula de que las dos muestras de GA y PSO son similares o rechazarla, lo que supondría aceptar la Hipótesis alternativa de que las dos muestras son distintas en un 95%, en cuyo caso se elegirá la técnica de mejor fitness. Como se trata de un test paramétrico, las variables analizadas siguen una distribución normal. Es decir, los valores fitness obtenidos dibujarán un estadístico que sigue la distribución t de Student. Si cae en una zona central de esa distribución de probabilidad (el 95%, porcentualmente) se mantendrá la hipótesis nula. Si cae fuera de esa zona se rechazará y se optará por la alternativa. Los resultados son obtenidos aplicando el comando de MATLAB mostrado en (6.2.9). 118 Figura 6.14: Distribución del transporte RSU en la actualidad, en la provincia de Málaga. Fuente: Elaboración propia. Figura 6.15: Propuesta de distribución del transporte RSU en la provincia de Málaga, según cálculos obtenidos con metaheurísticos GA (rojo) y PSO (azul). Fuente: Elaboración propia. 119 El óptimo en el caso de las plantas de tratamiento y como se podía intuir en el diseño del modelo matemático se corresponderá con el mínimo número de ellas. Es decir, solo será necesaria una planta de tratamiento manteniéndose en este caso, la de Antequera. Esta nueva distribución considerando que el objetivo último era una minimización de costes supondrá, en base a los datos obtenidos, un ahorro final para el periodo analizado entre 2010 y 2014 cercano al 20% del coste total. En la Figura 6.16 se puede observar como quedarían distribuidos los municipios entre los nuevos centros de transferencia localizados mediante los métodos metaheurísticos. Cada columna está encabezada por un centro de transferencia (azul), quedando debajo aquellos municipios (verde) que le transfieren sus residuos. Según se ve en la Figura 6.17 se han abierto 5 nuevos centros de transferencia manteniendo 4 de los 5 existentes y se ha cerrado una planta de tratamiento. Hay que considerar que los Fondos de Cohesión de la Unión Europea financian el 80% de la construcción de nuevas estaciones de transferencia, por lo que el coste total de cada nueva instalación sería inferior a 100.000 € (Diputación (2015)). La nueva organización quedaría como se muestra a continuación: Se mantienen: 1Centro de Transferencia de RSU de Vélez-Málaga (18 municipios) 2Centro de Transferencia de RSU de Ronda (24 municipios) 3Centro de Transferencia de RSU de Archidona (7 municipios) 4Centro de Transferencia de RSU de Campillos (6 municipios) Los nuevos centros serían: 5Centro de Transferencia de RSU de Alhaurín Torre (2 municipios) 6Centro de Transferencia de RSU de Alhaurín Grande (6 municipios) 7Centro de Transferencia de RSU de Nerja (6 municipios) 8Centro de Transferencia de RSU de Pizarra (7 municipios) 9Centro de Transferencia de RSU de Rincón de la Victoria (4 municipios) 120 Figura 6.16: Nueva distribución de los centros de transferencia en la provincia de Málaga. Fuente: Elaboración propia. El análisis de optimización de costes sugiere utilizar el menor número de plantas de tratamiento posibles, por lo que la planta de tratamiento de Casarabonela se cerraría, manteniendo solo la de Antequera: 10Planta de Tratamiento de RSU de Antequera (10 municipios) En la Figura 6.17 se muestra como quedaría la nueva distribución de centros de transferencia (círculo naranja) y planta de tratamiento (círculo verde) según los resultados obtenidos con los metaheurísticos (en trazo en azul se indican las transferencias de residuos entre centros y planta). También se dibuja la situación actual de los centros de transferencia (círculo azul) y plantas de tratamiento (círculo rojo) y como se realiza la transferencia de residuos (en trazo en rojo se indican las transferencias de residuos entre centros y plantas). 121 Figura 6.17: Comparativa entre la actual distribución y la propuesta por metaheurísticos, de los centros de transferencia y planta de tratamiento en la provincia de Málaga. Fuente: Elaboración propia. 122 6.4. Conclusiones En este capítulo se ha descrito la herramienta informática utilizada para modelar y resolver tanto el modelo exacto, como las técnicas metaheurísticas propuestas. Se han discutido las ventajas e inconvenientes de usar una herramienta informática como es el lenguaje matemático MATLAB, o el uso de otras herramientas comerciales como son el lenguaje de simulación y modelación matemática GAMS ó AIMMS. Los resultados obtenidos con GA se presentan peores frente a PSO debido a una mayor dispersión (en el diagrama de cajas se ven mayores valores de RIC y de máximos y mínimos, en GA) y también una desviación estándar e intervalos de confianza mayores según el test t-student. En el caso del algoritmo GA, los tiempos computacionales para resolver el problema de 90 municipios son más elevados que con PSO (7500 segundos frente a los 1470 segundos de PSO). Los resultados obtenidos con los metaheurísticos demuestran un ahorro de al menos 740.000 euros (20% anual) en el año 2014 y un ahorro final para el periodo analizado entre 2010 y 2014, cercano a los 3,7 millones de euros. Después de comprobar que los resultados obtenidos con la aplicación de las técnicas metaheurísticas propuestas han permitido resolver el problema determinista del caso real de localización de instalaciones y optimización de costes planteado en el capítulo, se puede confirmar la validez de este enfoque, de las técnicas metaheurísticas utilizadas y la herramienta aplicada. 123 Capítulo 7 7. CONCLUSIONES Y FUTUROS DESARROLLOS En este capítulo se describen las conclusiones más importantes respecto de la tesis realizada y otros posibles futuros desarrollos. 7.1. Conclusiones En resumen, las conclusiones más importantes son las siguientes: Este trabajo de investigación supone un avance por el uso de metaheurísticos actuales como los algoritmos de PSO no utilizados hasta ahora, para el que se ha constatado en esta tesis su interesante eficiencia en problemas reales de localización. Se introducen consideraciones de carácter más realista de lo que generalmente se ha presentado en la literatura. Este hecho queda plasmado en los resultados obtenidos con los metaheurísticos para el caso real de los 90 municipios de la provincia de Málaga. Los resultados muestran un ahorro para el periodo de 5 años, de unos 3,7 millones de euros, lo que supone un 20% de ahorro anual. 124 Aunque existen bastantes investigaciones sobre teoría de localización de instalaciones, son pocas las que se han encontrado que incluyan esta teoría aplicada a la logística inversa. Así, en la revisión sobre el estado del arte de las distintas tesis nacionales e internacionales y de artículos, congresos o conferencias de ámbito mundial, se han encontrado muy pocas que propongan, dentro el marco de la logística inversa, modelos cuantitativos de localización de instalaciones y uso de técnicas metaheurísticas para resolver el problema NP-duro planteado. En este sentido, esta tesis profundiza en la aún tenue línea de trabajo internacional con metaheurísticas en este dominio. Así mismo, el algoritmo PSO se ha mostrado más efectivo, rápido y fácil de programar que GA. Este último, con problemas pequeños presenta una respuesta similar a PSO, pero para grandes problemas se ha comportado bastante peor en tiempos de ejecución. También el algoritmo PSO en los estudios estadísticos con t-student y diagramas de cajas ha demostrado una menor dispersión para las diferentes muestras de municipios utilizadas (percentiles al 25 y 75% más cercanos a la mediana e igualmente para los valores máximos y mínimos). Esto supone una mayor robustez y confiabilidad, aspectos clave para su uso real. Los resultados finales obtenidos con las dos técnicas metaheurísticas establece unos valores cercanos entre si y próximos a los valores exactos. Aunque PSO tiene la ventaja de que es más sencillo de programar y rápido de ejecutar, con valores fitness para 30 muestras que presentan mucha menor dispersión. GA tiene desviaciones (sd) en la distribución en tsobre el valor exacto, de 1.4479e+06 frente a los 6.1472e+05 de PSO. También PSO localiza el óptimo en un espacio factible más reducido, con un 50% de los valores fitness más cercanos a la mediana que en el caso GA. Por otra parte, GA tiene la dificultad añadida de su complejidad para parametrizar adecuadamente los distintos operadores. 125 Finalmente, y después de contrastar que los resultados obtenidos con la aplicación de las técnicas metaheurísticas propuestas, se puede confirmar la validez de este enfoque, de las técnicas metaheurísticas utilizadas y la herramienta diseñada, frente al uso de métodos exactos, ineficaces para grandes problemas. 7.2. Futuros desarrollos En este trabajo de investigación se han abordado problemas de tipo monoobjetivo exactos junto con la aplicación de dos técnicas metaheurísticas. El método GA, según se ha comprobado en la revisión de la literatura, ha sido utilizado en alguna ocasión en logística inversa para la optimización de costes y localización de instalaciones con resultados aceptables. Sin embargo, de la técnica PSO no hay referencias en el estado del arte sobre su aplicación en logística inversa. Desde este punto de partida, se podrían sugerir otros posibles futuros desarrollos como: Utilizar otras herramientas informáticas, como Java, C++, Phyton, etc., que mejoren los tiempos de ejecución de los metaheurísticos usados para resolver problemas difíciles, con gran número de municipios (≥90). En el caso de la técnica GA, los tiempos computacionales para resolver el problema con todas las restricciones siguen siendo elevados. Por otra parte, el uso de otras aplicaciones informáticas podrían reducir la dispersión numérica mostrada en GA. Aplicar los metaheurísticos para la localización de instalaciones utilizando un enfoque estocástico, considerando el carácter dinámico del problema, ya que esta tesis se ha limitado al caso estático. Utilizar técnicas híbridas, como algoritmos meméticos y búsqueda dispersa o algoritmos genéticos híbridos (AGHMO). 126 Extender las técnicas metaheurísticas al dominio multi-objetivo, lo que permitiría resolver problemas de optimización más complejos, como la metodología denominada MOPSO (Multi-Objetive PSO) presentada por Coello et al. (2002). Por último, considerando el avance tecnológico en las redes de computadoras, se propone el uso de metaheurísticas paralelas, que reducirían el tiempo de cálculo, la resolución de problemas de mayor tamaño en un tiempo dado y obtener soluciones de mejor calidad. 127 BIBLIOGRAFÍA Abdel-kader, R. F. (2011). An Improved Discrete PSO with GA Operators for Efficient QoS-Multicast Routing. International Journal of Hybrid Information Technology. Vol. 4, No. 2, pp. 23-38. Afsahi, Z., Javadzadeh, R., Meybodi, M. (2011). Hybrid Model of Particle Swarm Optimization and Cellular Learning Automata with New Structure of Neighborhood. ICMLC 2011 3rd. International Conference on Machine Learning and Computing. Vol 1, 3, pp. 419-423. Aidonis, D. (2009). Applied operations research methodologies on the optimal design and operation of construction and demolition materials reuse and recycling networks. Tesis Doctoral, Aristotle University of Thessaloniki, Grecia. http://www.didaktorika.gr/eadd/handle/10442/27136?locale=en AIMMS, Tutorial by Marcel Roelofs and Johannes Bisschop (2015). The User's Guide. LS Haarlem, The Netherlands. http://www.aimms.com/solutions/supplychain-optimization-solutions/supply-chain-network-optimization/ Alba, E. (2005). Parallel metaheuristics: a new class of algorithms. John Wiley, pp. 3-62, USA. André, F. J. y Cerdá, E. (2001). Optimal Sequence of Landfills in Solid Waste Management. Optimal Control. Applications and Methods, Vol. 25, 4, pp. 1-25. André, F. J.; Velasco, F. y González, L. (2004). Intertemporal and Spatial Location of Disposal Facilities. Documento de Trabajo, Centro de Estudios Andaluces E2204/74. http://citec.repec.org/p/a/pan65.html Angell, L.C. y Klassen, R.O. (1999). Integrating environmental issues into mainstream: an agenda for research in operations management, Journal of Operations Management, Vol. 15, nº 4, pp. 293-315. Antunes, A. y Peeters, D. (2000). A dynamic optimization model for school network plannig. Socio-Economic Planning Sciences, 34, pp. 101–120. Ballou, R. (1968). Dynamic warehouse location analysis. Journal of Marketing Research, 5: pp. 271–276. Barros, A. I., Dekker, R. y Scholten, V. (1998). A two-level network for recycling sand: a case study. European Journal of Operational Research, 110, pp. 199–214.