RESUMEN
En este artículo se presenta el estudio de un problema de diseño de territorios de máxima dispersión territorial, motivado por una aplicación real en el campo de recolección y reciclaje de aparatos eléctricos y electrónicos en desuso en Europa. El problema consiste en encontrar una asignación de los centros de recolección a las corporaciones recolectoras que maximice una medida de dispersión territorial. El contexto matemático incluye como criterios de planificación, equilibrar la distribución de los hogares entre las distintas corporaciones de acuerdo a sus porcentajes de venta de mercado, así como evitar monopolios regionales. Se aplica una metaheurística tipo Greedy Randomized Adaptative Search Procedures (GRASP) que incorpora tres mecanismos de construcción de soluciones y tres diferentes tipos de vecindarios para las estrategias de búsqueda, para la mejora de soluciones. El algoritmo se ha evaluado en varios conjuntos de instancias generados aleatoriamente a partir de datos reales proporcionados por la empresa en territorio alemán. Los resultados obtenidos indican la eficacia del método propuesto dado que en tiempos de cómputo relativamente rápidos, pudieron obtenerse soluciones de calidad muy superior a la de las obtenidas por la empresa, tanto respecto a la medida de compacidad como respecto a las restricciones de balanceado.
ABSTRACT
The problem studied in this paper is motivated by the recycling Directive on Waste Electrical and Electronic Equipment of the European Commission. The core of this law is that each company selling electrical or electronic equipment in a European country has the obligation to recollect and to recycle a number of returned items that is proportional to its market share. To assign collection stations to companies in Germany for one product type, a territory design approach is planned. However, in contrast to classical territory design, the territories should be as geographically dispersed as possible to avoid that a company, based on its logistics provider, responsible for the recollection, gains a monopoly in some regions. We present the application of a solution based on the Greedy Randomized Adaptive Search Procedure methodology. Extensive computational results assess the effectiveness of the heuristics.
INTRODUCCIÓN
En 2003 en la Unión Europea entró en vigor la nueva ley de reciclaje para aparatos eléctricos y electrónicos en desuso, también referida como Ley Waste Electrical and Electronic Equipment (WEEE, 2003). La esencia de la ley establece que cada compañía vendedora de bienes eléctricos y electrónicos en un país europeo tiene la obligación de recolectar y reciclar una cantidad de artículos retornados proporcional al porcentaje de ventas en el mercado (market share) de esa compañía en ese país absorbiendo los costos del proceso. Para facilitar este proceso, se establecen estaciones recolectoras regionales donde los habitantes pueden retornar sus artículos en desuso al final de su tiempo de vida sin pagar ningún costo adicional. Si un recipiente contenedor en una estación dada se llena, una de las compañías debe recogerlo y reemplazarlo por otro vacío.
En 2005, esta ley fue transferida y adoptada en la legislación alemana y española. Aún cuando la ley permite que la recolección y reciclaje se haga individualmente por cada compañía, la misma ley favorece que las compañías se asocien en una corporación común (también llamado esquema de recolección) para recolectar conjuntamente una cantidad de artículos en desuso igual a la suma de sus correspondientes porcentajes de venta en el mercado.
En Alemania y España, por ejemplo, la coordinación y supervisión de la recolección se efectúa por un organismo central que también determina los porcentajes de venta de mercado de cada una de las compañías que venden equipo eléctrico y electrónico en su respectivo país.
En el sistema de reciclaje alemán, las estaciones de recolección (las cuales son operadas por los municipios) se asignan dinámicamente a las corporaciones. Es decir, cada estación va siendo asignada a una corporación tan pronto se vaya llenando y la corporación a su vez cuenta con 48 h para efectuar la recolección.
Este sistema actualmente cubre todas las diferentes categorías de productos. Sin embargo, para un grupo de productos, los denominados de línea blanca (refrigeradores, lavadoras, secadoras, etc.), se prepara un diseño territorial. Aquí, cada estación de recolección debe ser asignada estáticamente de antemano a una corporación específica por un cierto periodo de tiempo. Cada vez que un contender está lleno, una misma corporación es responsable de recogerlo y reemplazarlo, y de su respectivo tratamiento de reciclaje durante el periodo de tiempo que su asignación sea válida. En esencia, la asignación de estaciones a corporaciones debe efectuarse de tal modo que la cantidad promedio de artículos retornados sea proporcional al porcentaje de ventas de mercado de la corporación. Más aún, las estaciones asignadas a una corporación deben estar lo más dispersamente distribuidas como sea posible sobre toda la región con el fin de evitar concentraciones monopólicas en determinadas subregiones.
Aunque desde la perspectiva logística esta característica de tener una mayor dispersión, no es enteramente satisfactoria debido a que se tendrán que recorrer mayores distancias, existe otra razón predominante para esto. Esta consiste en lo siguiente, antes de la implementación de esta ley, existían un gran número de instituciones y proveedores logísticos regionales de mediana y pequeña escala que estaban involucrados en este proceso de recolección y reciclaje. Las autoridades temían que si se implementaba un diseño territorial en el sentido tradicional (esto es, minimizando la dispersión territorial), estas pequeñas compañías quedarían fuera del mercado empujadas por las grandes corporaciones. Porque de ese modo, las corporaciones minimizarían su sobrecarga administrativa mediante la subcontratación de un número pequeño de proveedores de gran escala para cubrir el territorio entero. Este efecto negativo, es mucho más improbable que ocurra bajo un esquema de mayor dispersión territorial.
Nótese que este criterio de máxima dispersión es exactamente opuesto al criterio tradicional de mínima dispersión presente en la gran mayoría de problemas y aplicaciones clásicas en el campo de diseño territorial ya que por lo general se busca tener territorios más compactos para minimizar costos de transporte (Kalcsics, Nickel & Schröder, 2005). Es precisamente este concepto de máxima dispersión lo que convierte a nuestro modelo en el primero en desarrollar este enfoque en el campo de diseño territorial, lo cual lo convierte en una contribución significativa y avance al estado del arte en el campo.
En este trabajo de investigación nos enfocamos, como caso práctico, en el sistema alemán territorial para la recolección de aparatos electrodomésticos en desuso. Hasta donde tenemos conocimiento, aunque hay algunas aplicaciones similares en la literatura, este problema no ha sido abordado anteriormente. Dentro del contexto de los artículos electrónicos en desuso y su correspondiente implementación, Queiruga, Walther, González-Benito & Spengler (2008) discuten la localización de plantas de reciclaje en España y presentan una aproximación basada en Preference Ranking Organization, Method for Envichment Evaluations (Promethee, técnica de optimización multi-criterio) para proveer una selección de buenas alternativas para posibles sitios potenciales de ubicación. Algunos sistemas de reciclaje en otros países europeos se describen en Hischier, Wäger & Gauglhofer (2005) para el caso de Suiza, y Turner & Callaghan (2007) para el Reino Unido. Para una panorámica más general de modelos de diseño territorial y una más detallada introducción al tópico, se refiere a Kalcsics et al. (2005).
Ahora bien, el problema una vez modelado se demuestra que pertenece a la clase NP-duro de problemas muy difíciles de resolver (Fernández, Kalcsics, Nickel & Ríos-Mercado, 2010). Esto es que cualquier método que pretende encontrar la solución exacta (óptima global) al problema emplea un tiempo de cómputo que crece exponencialmente con el tamaño del problema en el peor de los casos. Para un tratado más amplio del tema de complejidad computacional, véase Garey & Johnson (1979).
Por tal motivo, las técnicas clásicas para resolver problemas de programación entera como el Método de Ramificación y Acotamiento (Nemhauser & Wolsey, 1988) permiten resolver únicamente problemas con hasta 20 - 30 unidades básicas, lo cual es inoperante para la escala que pretendemos.
En este estudio, el interés consiste en resolver instancias de 100 unidades a 300 unidades básicas, por ende, es necesario desarrollar algoritmos de solución aproximada o heurísticas, los cuales son métodos que si bien renuncian a la optimalidad global, son capaces de obtener soluciones de muy buena calidad en tiempos de cómputo razonables. La calidad y factibilidad de estas soluciones dependen fuertemente de qué tan bien se explote la estructura matemática del problema en su diseño. En este trabajo se aplica una metaheurística basada en un marco de Procedimientos de Búsqueda Ávida Aleatorizada y Adaptativa (Greedy Randomized Adaptive Search Procedures [GRASP]), la cual es una de las más avanzadas en el campo. Los resultados son excelentes. La evaluación numérica muestra el óptimo desempeño de cada uno de los componentes de la heurística y más aún, que proveen soluciones de muy alta calidad encontrando siempre diseños factibles (que cumplen con todos los requerimientos de planificación) lo cual era prácticamente imposible de obtener por los actuales métodos de la empresa, resultando en una gran aportación tanto científica como práctica.
Descripción del problema
Los bienes electrodomésticos se dividen en dos clases: aquellos que tienen capacidades de enfriamiento y aquellos que no (los cuales denotamos como productos de tipo 1 y 2, respectivamente). Esta distinción viene del hecho de que los productos tipo 1 contienen solventes de enfriamiento tóxicos que por ende requieren de un tratamiento especial en su almacenaje en los puntos de recolección.
Por razones de eficiencia, cerca de 250 compañías que distribuyen aparatos de línea blanca en Alemania, por ejemplo, se reagrupan entre un pequeño grupo de corporaciones que toman la responsabilidad de llevar a cabo la recolección y reciclaje de los aparatos electrodomésticos en desuso. Cada corporación tiene un porcentaje de ventas que es la suma del porcentaje de las compañías que lo conforman. Este porcentaje se específica por separado para cada tipo de producto.
Para facilitar el esquema de diseño territorial, dividimos la zona de estudio (Alemania) en 450 unidades básicas aproximadamante. Esta división está basada principalmente en los distritos administrativos como ciudades o condados. Como no se cuenta con estimados confiables del número de artículos retornados por los usuarios, se supone que la cantidad promedio de artículos en desuso de cada unidad básica es proporcional al número de hogares asociados a la correspondiente unidad básica. En cada unidad básica pueden existir varios sitios de recolección físicos donde se recolectan y almacenan los productos retornados de los hogares. De ahí, las compañías tienen que recogerlos y transportarlos al centro de reciclaje.
Más aún, basado en el esfuerzo logístico empleado para llevar a cabo la recolección y reciclaje (medido mediante indicadores de desempeño apropiados), las unidades básicas se clasifican en tres grupos: buenas, regulares y malas, de acuerdo a la calidad de su infraestructura y accesibilidad. Una unidad básica buena es, por ejemplo, aquella que tiene una extensión geográfica pequeña y posee una buena infraestructura. Una zona geográfiva pequeña involucra una o dos regiones postales y es más atractiva porque toma menor tiempo visitarla cuando se efectúa la recolección. De igual manera, una buena infraestructura es aquella que permite fácil accesibilidad de los camiones para recolectoras los artículos. En contraste, una unidad mala es aquella que tiene una peor infraestructura o dificultades en su accesibilidad. La motivación de esta clasificación, proviene del hecho de que los costos de recolección y reciclaje que eventualmente pagarán las compañías deberían de ser proporcionales a los porcentajes de ventas en el mercado de cada corporación. Tener este tipo de clasificación ayuda a desarrollar en el modelo una desigualdad que tome en cuenta esta razón de equidad.
Como los porcentajes de ventas en el mercado pueden diferir para cada tipo de producto, se permite tener unidades básicas divididas, es decir, unidades cuyas corporaciones que recolectan sus productos tipo 1 y tipo 2 son diferentes.
La tarea es entonces asignar las unidades básicas a las corporaciones de tal forma que:
• Todas las unidades básicas para cada tipo de producto son asignadas a una corporación.
• Para cada corporación, el número total de hogares de todas las unidades básicas que le son asignadas es proporcional a su porcentaje de ventas en el mercado para cada uno de los dos tipos de productos.
• Las unidades básicas buenas, regulares y malas deben ser equitativamente distribuidas entre las corporaciones de acuerdo a su porcentaje de ventas en el mercado.
• El número de unidades básicas divididas, es decir, aquellas que son asignadas a diferentes corporaciones, debe ser relativamente pequeño (típicamente se establece un 20% del total de unidades básicas).
• Para cada corporación, las unidades básicas que le son asignadas (parcial, con un tipo de producto o totalmente, con los dos tipos de producto) deben estar lo más geográficamente dispersas como sea posible. Por dispersas, entiéndase que deben estar lo más alejadas entre sí. Esto se logra incorporando una métrica de dispersión adecuada en la función objetivo del modelo.
El conjunto de todas las unidades básicas asignadas a una corporación para al menos uno de los dos tipos de productos es denominado territorio. Cuando se tomó este trabajo, se sabía que la manera en que se efectuaba la asignación por parte del organismo central de asignación era de una forma en que consideraba satisfacer o buscar que el número de hogares fuera proporcional al porcentaje de ventas de mercado de cada corporación, más esta forma ignoraba de alguna medida el criterio de dispersión territorial y se obtenian muchas zonas monopolizadas por regiones que era precisamente lo que se deseaba evitar de acuerdo a la ley establecida. Sin embargo, era evidente la gran dificultad en satisfacer todos los criterios deseados. Es aquí donde nuestro trabajo, basado en una forma científica pretende encontrar diseños que satisfagan todos los criterios y además minimizando el grado de monopolización ya comentado.
Formulación
Denotemos por al conjunto de Unidades Básicas (UB). Sea el número de hogares de la y . Y por al conjunto de UB buenas, regulares y malas, respectivamente. Se usará como índice para representar estos conjuntos y por el índice logístico de la . Sea la distancia euclídea entre las . Denotemos por al conjunto de corporaciones y al porcentaje de ventas de mercado de la corporación para el producto . Una solución se representa por una colección de subconjuntos con ∈ V, donde representa al subconjunto de UB que definen el territorio de la corporación , donde denota el conjunto de UB asignadas a la corporación para el producto . Si la no está dividida, tenemos , para algún ; de otro modo, existen , con . Cuando la división de UB es prohibida totalmente, se tiene , para todo , de tal suerte que define una partición de . El problema de optimización combinatoria consiste en encontrar la solución que maximice la dispersión territorial sujeta a los requerimientos de planificación mencionados, es decir restricciones de balance de carga con respecto al porcentaje de ventas del mercado, restricciones de balance con respecto a una repartición equitativa de las sitios de recolección de acuerdo a la calidad de su infraestructura y que el número de unidades básicas divididas S sea igual o menor al 20% del total. El modelo matemático en detalle se presenta en Fernández et al. (2010). A este problema le denominamos Problema de Diseño Territorial de Máxima Dispersión (MaxD-TDP). Para algunos de los casos reales (450 UB y 6-7 corporaciones) el modelo contiene más de 600 000 variables de decisión binarias y restricciones, lo cual resulta más que intratable por métodos exactos. MaxD-TDP es NP-duro.
Método de Solución
Como se comentó anteriormente, cuando un problema de optimización del tipo combinatorio es clasificado NP-duro, como el tratado en este estudio, los métodos exactos son inaplicables para intentar resolver instancias grandes del problema. Es por eso que surge la necesidad, desde el punto de vista práctico, de desarrollar métodos aproximados o heurísticas, los cuales son métodos que si bien no garantizan optimalidad global, si brindan soluciones de alta calidad en tiempos de cómputo razonables
En el campo de las heurísticas, GRASP (Feo & Resende, 1995) es una metaheurística (Glover & Kochenberger, 2003) relativamente conocida que captura buenas características tanto de algoritmos voraces (greedy) como de construcciones aleatorias. GRASP se ha utilizado ampliamente en resoluciones exitosas de muchos problemas de optimización combinatoria, incluyendo diseño territorial (Ríos-Mercado, 2016; Ríos-Mercado & Escalante, 2016; Ríos-Mercado & Fernández, 2009; Salazar-Aguilar, Ríos-Mercado & González-Velarde, 2013).
Un GRASP es un proceso iterativo en el que cada iteración global típicamente consta de dos fases: construcción y post-procesado. La fase constructiva intenta obtener una solución factible, mientras que la fase de post-proceso intenta mejorarla. Típicamente, cuando la primera fase consigue encontrar una solución factible, la segunda fase es una búsqueda local en unos entornos adecuados, cuyo objetivo es mejorar el valor de la función objetivo. La figura 1 ilustra una implementación genérica de un GRASP en pseudocódigo. El algoritmo tiene como entrada una instancia de un problema de diseño de territorios, el número máximo de iteraciones GRASP y el parámetro de calidad de la lista restringida de candidatos (RCL, por sus siglas en inglés), y devuelve una solución Xbest.
Pseudocódigo de GRASP para MaxD-TDP.
Fuente: Fernández et al. (2010)
La motivación para utilizar GRASP en esta aplicación concreta se deriva del hecho de que parece apropiado para manejar las restricciones de balanceo (2)-(5). Describimos ahora en detalle cada una de las componentes básicas del GRASP y algunas características avanzadas como el filtrado y la reactividad que hemos incorporado a la heurística.
Fase constructiva
Para la fase de construcción de GRASP, hemos desarrollado tres diferentes procedimientos de construcción de soluciones. Dos de ellos (Procedimiento 1 y 1R) tienen como eje motor el tratar de asignar UB que están relativamente cercanas entre sí a diferentes corporaciones. La motivación de esto viene de la naturaleza de la función objetivo. Si dos unidades muy cercanas se asignan al mismo territorio, entonces el valor de la función objetivo será muy bajo, contrario a lo que se busca. El tercero (Procedimiento 2) se basa en la idea complementaria de tratar de asignar a una misma corporación UB que están relativamente alejadas entre sí. Estos procedimientos se describen detalladamente en Fernández et al. (2010).
Búsqueda local
Al término de la fase de construcción se aplica una fase de mejora o búsqueda local. En esta fase se intenta recuperar factibilidad, en caso que la solución construida en la fase anterior sea infactible, así como también mejorar el valor de la función objetivo. Como es muy conocido en el campo, una búsqueda local consta de varios componentes importantes (Aarts & Lenstra, 2003). Uno de estos es la definición de una función de mérito que sirva para evaluar la calidad de cada solución. En este caso particular, las soluciones se evalúan ahora por medio de una función de mérito que pondera tanto la contribución a la función objetivo como la infactibilidad con respecto a las restricciones de balance. La función de mérito empleada en esta fase es muy similar a la función voraz usada anteriormente en la fase de construcción. Sin embargo, se considera ahora que la suma de las infactibilidades relativas toma en cuenta no solamente el límite superior de las restricciones de balance, sino también la violación al límite inferior de estas (2) y (4).
Otro componente importante es la determinación de la o las topologías que definen a los vecindarios, también asociados a los tipos de movimientos que se pueden hacer entre una solución y una adyacente. Los tipos de movimientos que hemos propuesto para definir los vecindarios de búsqueda son los siguientes:
• Vecindario A1: reasignar, para ambos productos, la UB i (actualmente asignada al territorio k), al territorio t (diferente de k). El tamaño de este vecindario es n × m.
• Vecindario A2: reasignar la UB i para el producto p de su territorio actual a uno diferente. Se permite división de unidad básica. El tamaño de este vecindario es 2n × m.
• Vecindario B: intercambiar entre sí los territorios de las UB i y j para uno o ambos productos. El tamaño de este vecindario es 2n2.
El éxito de una buena búsqueda local reside en saber cómo explorar los vecindarios de manera inteligente, balanceando la calidad de la solución con el esfuerzo computacional empleado. En la siguiente sección se proponen y evalúan varias estrategias de búsqueda basadas en estos tres vecindarios propuestos.
EXPERIMENTACIÓN, RESULTADOS Y DISCUSIÓN
Para las pruebas experimentales hemos generado instancias del problema usando datos reales obtenidos a través del SIG ArcView (www.esri.com). Las UB corresponden a áreas postales en Alemania con su respectivo número de hogares asociados. El tamaño de las instancias varía de 100 UB a 300 UB con incrementos de 50 unidades básicas, y de 4 a 7 corporaciones. Las instancias representan regiones rurales, urbanas y mixtas. Para cada combinación de tamaño (n número de unidades básicas y m número de corporaciones), generamos 5 instancias diferentes, excepto para las de 300 unidades básicas donde generamos 4 instancias para cada valor de m, creando un total de 96 instancias de prueba. Las tolerancias para las restricciones de balanceo con respecto a la distribución equitativa de número de hogares y de índice logístico de infraestructura se fijan en τ = 0.05 y β = 0.2, respectivamente. Las distancias entre pares de unidades básicas se calcularon como la distancia euclídea entre las representaciones poligonales de las áreas postales. De este modo, unidades básicas adyacentes tienen distancia internodal igual a cero. Los índices logísticos se eligieron aleatoriamente de tal forma que tenemos aproximadamente el mismo número de unidades básicas buenas, regulares y malas. El límite de unidades divididas S se ha fijado en el 20% del valor de n para cada instancia. Finalmente, los porcentajes de venta de mercado de las corporaciones se han calculado independientemente para cada producto. El valor se genera de la distribución uniforme en el intervalo [0.75/m, 1.25/m]. Al final, estos valores se normalizan para asegurar que la suma sea igual a 1.
Todos los procedimientos heurísticos fueron codificados en lenguaje C++ y compilados con el compilador Workshop 8.0 de Sun bajo el sistema operativo Solaris 9. Las pruebas se ejecutaron en un servidor SunFire V440 con 8 GB of RAM y 4 procesadores UltraSparc III de 1062 MHz, propiedad del Laboratorio de Cómputo de Alto Desempeño del Programa de Posgrado en Ingeniería de Sistemas, Facultad de Ingeniería Mecánica y Eléctrica (FIME), Universidad Autónoma de Nuevo León (UANL).
Como se sabe, el comportamiento de la heurística GRASP depende en gran medida de dos parámetros: el parámetro de umbral de calidad de la RCL y el parámetro λ de peso en la función voraz. En una fase preliminar se hizo una experimentación para calibrar los parámetros, los cuales se usan en el resto de los experimentos. Para el Procedimiento Constructivo 1 usamos α = 0.2 y λ = 0.5, para el Procedimiento 1R usamos α = 0.2 y λ = 1.0, y para el Procedimiento 2 usamos α = 0.8 y λ = 1.0. Los detalles de la calibración pueden encontrarse en Fernández et al. (2010).
Estrategias de búsqueda local
A continuación procedemos a investigar el efecto de la fase de mejora o búsqueda local. Se han propuesto tres diferentes vecindarios para este problema. Como ocurre en el campo de optimización heurística, un concepto importante es el tratar de combinar los diferentes vecindarios de tal forma que al final se produzcan los mejores resultados. Por tal motivo, basado en estos tres vecindarios, hemos diseñado tres diferentes estrategias que los combinan:
• LS1: aplica el vecindario tipo A1 y luego el tipo A2.
• LS2: aplica el vecindario tipo A2 y luego el tipo A1.
• LS3: aplica el vecindario tipo A2, luego el tipo A1 y luego el tipo B.
Como el tamaño de los vecindarios está acotado polinomialmente y no es excesivamente grande, utilizamos una estrategia de búsqueda del tipo “mejor encontrado”, es decir, se examina el vecindario completo y uno se mueve a la mejor solución de todas (si mejora la actual). El límite de iteraciones de GRASP se fijó en 2000. Al GRASP que usa el Procedimiento Constructivo N, con N = {1, 1R, 2}, le denominamos Heurística N.
Los resultados de LS1 y LS2 para las tres heurísticas se muestran en la tabla 1. Nótese que en esta tabla, el intervalo de dispersión relativa (IDR) se calcula con respecto a la mejor solución encontrada por cualquiera de las estrategias LS1 o LS2 para esa heurística en particular. Por ejemplo, el valor 2.7 mostrado para la Heurística 1 para n = 100 bajo la columna LS1, significa que la diferencia entre la solución encontrada bajo LS1 en este grupo de instancias está en promedio a 2.7% de la mejor solución encontrada por la Heurística 1 bajo cualquier esquema de mejora. Por lo tanto, únicamente es válida la comparación entre estrategias de búsqueda local y no entre heurísticas. La comparación entre heurísticas se lleva a cabo en la siguiente sección.
| Tabla 1 | Efecto de las estrategias de búsqueda local. |
| n | Indicador | Heur 1 | Heur 1R | Heur 2 | |||
| LS1 | LS2 | LS1 | LS2 | LS1 | LS2 | ||
| 100 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 2.7 | 0 | 1.5 | 0.5 | 2.8 | 0.8 | |
| IDR peor (%) | 15.9 | 0 | 11.8 | 5.2 | 15.8 | 6.8 | |
| Tiempo de CPU promedio (seg) | 178 | 128 | 157 | 120 | 185 | 178 | |
| 150 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 3.5 | 1.4 | 2.3 | 0 | 4.3 | 0.9 | |
| IDR peor (%) | 14.8 | 21.1 | 11.2 | 0 | 12.6 | 6 | |
| Tiempo de CPU promedio (seg) | 396 | 265 | 361 | 257 | 461 | 440 | |
| 200 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 2.4 | 0 | 4.6 | 0.2 | 5.3 | 0.7 | |
| IDR peor (%) | 15.1 | 0 | 25.3 | 3.6 | 20.7 | 7.9 | |
| Tiempo de CPU promedio (seg) | 676 | 440 | 597 | 411 | 823 | 787 | |
| 150 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 3.5 | 1.4 | 2.3 | 0 | 4.3 | 0.9 | |
| IDR peor (%) | 14.8 | 21.1 | 11.2 | 0 | 12.6 | 6 | |
| Tiempo de CPU promedio (seg) | 396 | 265 | 361 | 257 | 461 | 440 | |
| 250 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 8.4 | 0 | 5.4 | 0.2 | 3.8 | 1.1 | |
| IDR peor (%) | 17.3 | 0 | 12.7 | 3.3 | 13.7 | 9.6 | |
| Tiempo de CPU promedio (seg) | 1178 | 699 | 979 | 671 | 1464 | 1277 | |
| 300 | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 2.6 | 0 | 3.2 | 0 | 2.8 | 1.6 | |
| IDR peor (%) | 18.8 | 0 | 26.6 | 0 | 12.3 | 19 | |
| Tiempo de CPU promedio (seg) | 1728 | 1056 | 1645 | 1067 | 2883 | 2064 | |
| Total | No. De soluciones infactibles | 0 | 0 | 0 | 0 | 0 | 0 |
| IDR promedio (%) | 4 | 0.3 | 3.4 | 0.2 | 3.9 | 1 | |
| IDR peor (%) | 18.8 | 21.1 | 26.6 | 5.2 | 20.7 | 19 | |
Fuente: Fernández et al. (2010) Descargar Tabla
Los resultados en la tabla 1 indican primeramente que, independientemente del procedimiento de construcción, ambas estrategias LS1 y LS2 fueron capaces de obtener siempre soluciones factibles al problema. Esto representa una mejora impactante con respecto a la fase de construcción ya que en los experimentos preliminares se encontró que las heurísticas constructivas obtuvieron soluciones infactibles en aproximadamente el 95% de los casos. Esto muestra contundentemente la efectividad y gran desempeño de la fase de búsqueda local para reparar este aspecto de infactibilidad. Los resultados también indican que la estrategia LS2 es mejor que la LS1 en términos de las desviaciones relativas del mejor valor conocido de la función objetivo de dispersión (valores más bajos de IDR), es decir, sus soluciones son de mejor calidad. LS2 resultó consistentemente mejor que LS1 para cada valor de n probado. Además, LS2 emplea considerable menos tiempo de cómputo Central Processing Unit (CPU) que LS1 (cerca de 40% menos en promedio). Por tanto, concluimos que resulta mucho más ventajoso explorar primero el vecindario tipo A2 y luego el A1.
Comparación de Heurísticas
La tabla 2 muestra una comparación entre las tres diferentes heurísticas, todas bajo el esquema de búsqueda local LS2. Esta vez, el Intervalo de Dispersión Relativa (IDR) se calcula contra la mejor solución obtenida por cualquier heurística, es decir, la mejor solución de todas.
| Tabla 2 | Comparación entre heurísticas |
| n | Indicador | Heur 1 | Heur 1R | Heur 2 |
| 100 | IDR promedio (% de la mejor conocida) | 0.6 | 1.2 | 21.7 |
| IDR peor (%) | 6.4 | 16.6 | 34.4 | |
| Número de soluciones infactibles | 0 | 0 | 0 | |
| Número de mejores soluciones | 14 | 16 | 0 | |
| Tiempo de CPU promedio (seg) | 128 | 120 | 173 | |
| 150 | IDR promedio (% de la mejor conocida) | 0.4 | 1.3 | 19.4 |
| IDR peor (%) | 4.2 | 8.8 | 28.5 | |
| Número de soluciones infactibles | 0 | 0 | 0 | |
| Número de mejores soluciones | 17 | 15 | 0 | |
| Tiempo de CPU promedio (seg) | 265 | 257 | 440 | |
| 200 | IDR promedio (% de la mejor conocida) | 1.5 | 0.2 | 24.1 |
| IDR peor (%) | 13.3 | 3.6 | 44.6 | |
| Número de soluciones infactibles | 0 | 0 | 0 | |
| Número de mejores soluciones | 15 | 18 | 1 | |
| Tiempo de CPU promedio (seg) | 440 | 411 | 787 | |
| 250 | IDR promedio (% de la mejor conocida) | 0.7 | 0.7 | 28.4 |
| IDR peor (%) | 3.2 | 6.2 | 45.6 | |
| Número de soluciones infactibles | 0 | 0 | 0 | |
| Número de mejores soluciones | 14 | 15 | 0 | |
| Tiempo de CPU promedio (seg) | 699 | 671 | 1277 |
Fuente: Fernández et al. (2010) Descargar Tabla
Se observa que en términos de calidad de la solución, la Heurística 2 exhibe pobre desempeño comparada con las otras dos. Las Heurísticas 1 y 1R se desempeñan muy similarmente con respecto a ambos indicadores: función objetivo y tiempo de cómputo, aunque la Heurística 1 se muestra ligeramente mejor que la 1R en términos del objetivo de dispersión. En particular, para los problemas de mayor tamaño (n = 300), ambas heurísticas encuentran la misma solución en el 75% de las instancias probadas. Para las instancias de tamaño menor a 300, la Heurística 1 encuentra las mejores soluciones. En total, las Heurísticas 1 y 1R encuentran cada una un total de 76 de 96 mejores soluciones. Es importante destacar el tremendo e impactante beneficio reportado por la fase de búsqueda local en cada caso. En experimentación preliminar se encontró que la gran mayoría de las soluciones encontradas en la fase de construcción (sin la búsqueda local) fueron infactibles (el porcentaje de éxito fue del 5% con grandes valores de infactibilidad en varios casos). La implementación de los vecindarios A1 y A2 en el esquema de búsqueda local ayudó a elevar este indicador de éxito a 100%, lo cual es muy significativo. Esto sugiere también que la investigación de más sofisticados esquemas de búsqueda local podría merecer la pena como trabajo de investigación futura.
También probamos la estrategia LS3 en las instancias de 300 nodos con la Heurística 1. Para 11 de las 16 instancias, ya no hubo mejora. Más aún, mientras que la mejora relativa promedio de usar LS3 sobre LS2 es menor al 1.5%, el esfuerzo computacional promedio de LS3 es de 19 778.9 s, lo cual representa, comparado con los 1056.5 s empleados por LS2, un incremento bastante grande. La recomendación es usar LS2 como primera opción y, en situaciones donde se requiera con mayor importancia encontrar mejores diseños sin importar el tiempo, aplicar LS3.
CONCLUSIONES
En este trabajo se ha presentado el Problema de Diseño Territorial de Máxima Dispersión motivado por una adaptación de la Ley de Reciclaje WEEE impuesta en 2003 por la Unión Europea. El problema consiste en diseñar territorios para las compañías involucradas en recolectar y reciclar aparatos eléctricos y electrónicos en desuso. Para evitar una concentración monopólica, las estaciones de recolección deben estar dispersamente distribuidas entre las compañías en todo el territorio de estudio. Más aún, la asignación de las estaciones a las corporaciones debe efectuarse de tal manera que la cantidad promedio de artículos retornados sea proporcional al porcentaje de ventas del mercado de cada compañía.
La contribución destacada de este trabajo es que, hasta donde se tiene conocimiento, esta es la primera aplicación de este problema en el campo de recolección y reciclaje desde una perspectiva de optimización, es decir, no había sido tratado con anterioridad. Una contribución de mayor envergadura es que este es también el primer modelo, en todo el campo de diseño territorial, que plantea la maximización de una función de dispersión. Todos los demás modelos consideran la minimización de la dispersión. La consecuencia directa es que este trabajo es pionero en estos dos campos y se espera que sea un referente importante en el futuro y que las ideas aquí desarrolladas puedan ser usadas en otros trabajos de investigación.
Como metodología de solución, dado su inherente complejidad computacional, se ha presentado la aplicación de una metaheurística basada en GRASP, la cual incorpora el desarrollo de varios componentes (como tres diferentes procedimientos para la fase de construcción y tres diferentes tipos de vecindarios para la fase de búsqueda local) que explotan favorablemente la estructura matemática del problema. Los resultados computacionales han sido excelentes, evidenciando el gran desempeño y valía de los mismos, resultando en soluciones de altísima calidad, en varios casos probadas muy cercanas al óptimo global, y en todo caso mucho mejores que las soluciones reportadas por la empresa responsable. Esta metodología constituye por ende otra significativa contribución científica y práctica, avanzando el estado del arte en esta rama del conocimiento y convirtiéndose en una gran innovación tecnológica en un problema altamente complejo. Una consecuencia importante es que las medidas de planificación basadas de forma científica con ayuda de este trabajo, reditúan en un beneficio de impacto ambiental por la naturaleza misma del problema.
Sin embargo, hay algunas avenidas de oportunidad de mayor reto para investigación futura. Se destaca principalmente el desarrollo de heurísticas aún más sofisticadas, que puedan tener mecanismos de utilizar la memoria para tratar de escapar de óptimos locales, y el estudio profundo del poliedro del modelo matemático que permita desarrollar formulaciones aún más fuertes desde la perspectiva de optimización exacta, esto es, desarrollar desigualdades válidas que puedan redituar en menores tiempos de cómputo, aún para el método exacto. Finalmente, en un mediano plazo, sería un gran avance el poder combinar estas decisiones de diseño territorial con las de planificación de las rutas de recolección. Eso representa desde luego un reto aún mayor, mas este trabajo será sin duda una base de apoyo importante para poder atacar tal problemática.
AGRADECIMIENTOS
Se agradecen los comentarios de los revisores anónimos, cuya crítica ayudo a mejorar la presentación del artículo. Este trabajo de investigación ha sido apoyado por el Consejo Nacional de Ciencia y Tecnología (apoyo SEP-Conacyt CB-2005-01-485499-Y), la Universidad Autónoma de Nuevo León a través de su Programa de Apoyo a la Investigación Científica y Tecnológica (apoyo PAICYT CA-1478-07), y el Plan Nacional de Investigación Científica de España, Desarrollo e Innovación Tecnológica (apoyo MTM2006-14961-C05-01), lo cual es gratamente agradecido por los autores.
REFERENCIAS
Glover, F., & Kochenberger, G. (2003). Handbook of Metaheuristics. EUA: Springer.