UNIVERSIDAD NACIONAL DE TRUJILLO - … · tercer capítulo se hará un análisis del problema, el análisis del modelo matemático y el diseño de la metaheurística de Busca Tabú,

UNIVERSIDAD NACIONAL DE TRUJILLO

FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS

ESCUELA ACADEMICO PROFESIONAL DE INFORMÁTICA

HEURISTICA PARA LA COLECTA DE RESIDUOS DOMICILIARIOS EN LA CIUDAD DE TRUJILLO BASADO EN EL

RUTEO DE VEHICULOS CON VENTANA DE TIEMPO

Tercer Informe de Trabajo de Graduación

PROPUESTO POR: José A. Rodríguez Melquiades <[email protected]>

ELABORADO POR: Luis Miguel Bardales Guerra <[email protected]>

AREA DEL PROYECTO: <Fundamentos de Programación / Algoritmos y Complejidad>

Trujillo, 11 de Diciembre de 2013

Heurística para la Colecta de Residuos Domiciliarios en la Ciudad de Trujillo basado en el Ruteo de Vehículos con Ventana de Tiempo

Tercer Informe de Trabajo de Graduación Versión 1.0

Bardales Guerra Luis Miguel 2

Contenido

I. RESUMEN ............................................................................................................................. 4

II. INTRODUCCION ................................................................................................................... 4

III. PLANTEAMIENTO DE LA INVESTIGACION ................................................................... 6

3.1 Planteamiento del Problema ......................................................................................... 6

3.2 Marco Teórico ................................................................................................................ 6

3.2.1 Optimización Combinatoria ....................................................................................... 6

3.2.2 Problemas NP – El Problema del Agente Viajero ..................................................... 7

3.2.3 Problema de Ruteo de Vehículos .............................................................................. 9

3.2.4 Problema de Ruteo de Vehículos con Ventanas de Tiempo .................................. 11

3.2.5 Métodos Heurísticos ................................................................................................ 13

3.2.6 Servicio de Gestión Ambiental SEGAT ................................................................... 13

3.2.7 Estudios de Colecta de Residuos alrededor del Mundo ......................................... 14

3.2.8 Búsqueda Tabu ....................................................................................................... 16

3.3 Justificación del Estudio .............................................................................................. 18

3.4 Objetivos ...................................................................................................................... 19

3.4.1 Objetivo Principal ..................................................................................................... 19

3.4.2 Objetivos Específicos .............................................................................................. 19

IV. MATERIALES Y METODOS ........................................................................................... 19

4.1 Población y Muestra .................................................................................................... 19

4.2 Variable de Estudio ..................................................................................................... 19

4.3 Tipo de Investigación .................................................................................................. 20

4.4 Técnicas de Recolección de Datos ............................................................................. 20

4.5 Instrumentos de Recolección de Datos....................................................................... 20

4.6 Procedimiento de la Investigación............................................................................... 20

V. RESULTADOS ................................................................................................................ 21




5.1 Problema ..................................................................................................................... 21

5.1.1 Análisis del Problema .............................................................................................. 21

5.1.2 Modelos Matemáticos.............................................................................................. 23

5.2 Comparaciones entre los Modelos Fuente y Modelo Propuesto ................................ 32

VI. CONCLUSIONES ............................................................................................................ 33

VII. REFERENCIAS BIBLIOGRAFICAS ................................................................................ 33

Lista de Figuras

Figura 1. Problema del Viajero. (a) Grafo que indica los nodos y el valor de los arcos. (b) tabla que muestra la relación entre nodos. (c) posible solución optima ................................................ 7

Figura 2. Explosión Combinatoria en el TSP. ............................................................................... 9

Figura 3. Relación de los VRP y sus variantes. .......................................................................... 10

Figura 4. Número de Publicaciones por Periodo (1971 - 2010) .................................................. 15

Figura 5. Trabajos Realizados en Diferentes partes del Mundo (1971 - 2010) .......................... 15

Figura 6. Diagrama de flujo Búsqueda Tabu .............................................................................. 18

Figura 7. Territorios Vecinales del Distrito de Trujillo.................................................................. 21

Lista de Cuadros

Cuadro 1. Cantidad de Residuos Sólidos recolectados por día en el Distrito de Trujillo. .......... 14

Cuadro 2. Ubicación de Puntos Críticos (Datos de 2007) .......................................................... 22

Cuadro 3. Comparación Nro. Variables Generadas y Tiempo Usado ........................................ 32

Cuadro 4. Comparación Tiempo Usado, Memoria Usada, Costo (Tattoni - Badran) ................. 32

Cuadro 5. Comparación Nro. Vehículos, Tiempo Usado, Memoria Usada, Costo (VRPTW - M. Propuesto) ................................................................................................................................... 32




I. RESUMEN

La gran cantidad de residuos producidos en los domicilios a nivel mundial es un tema que en los últimos años ha tomado mucha importancia, debido a que el deficiente proceso de colecta es uno de los factores que provocan la contaminación ambiental. La investigación empieza con el estudio del problema de ruteo de vehículos y sus variantes, seguido del diseño de un modelo de optimización combinatoria para este problema basado en el uso de ventanas de tiempo. Finalmente, debido a la naturaleza combinatoria del problema, se propone una heurística orientada a solucionar el problema discutido. Como estudio de caso consideramos la Ciudad de Trujillo donde se espera tener como resultado la reducción de recursos, tanto económicos como logísticos.

Palabras clave: Colecta de residuos; Optimización combinatoria; Problema de ruteo de vehículos con ventanas de tiempo;

Residential waste produced around the World is a topic that in the last years it has taken relevancy, because of the deficient process of waste collection is one of the facts that produces pollution. Our research starts with the study of the Vehicle Routing Problem and its variants. Next, we design a combinatorial optimization model for this problem based on time Windows. Finally, due to the combinatorial nature of the problem, we propose a heuristic focus on resolving the discussed problem. The case of study we consider the city of Trujillo and we hope to reduce economical and logistic resources.

Keywords: Waste collection; combinatorial optimization; Vehicle routing problems with time windows;

II. INTRODUCCION

De acuerdo con la ACM, la optimización combinatoria es parte de la Informática Teórica (Theoretical Computer Science). Un problema estudiado es el ruteo de vehículos (Vehicle Routing Problem) que por su naturaleza presenta alta complejidad computacional, es decir no existe algoritmo polinomial que solucione los problemas para grandes instancias.

La colecta de residuos domiciliares es una actividad muy importante dentro de una ciudad. Una variante del ruteo de vehículos, denominado Ruteo de Vehículos con Ventana de Tiempo, permite obtener resultados buenos para el proceso de colecta minimizando os costos logísticos generados, es decir mediante algoritmos heurísticos se obtienen resultados aceptables para grandes instancias. Por su naturaleza combinatoria, el trabajo a desarrollar está ubicado dentro del área de investigación Fundamentos de Programación/Algoritmos y complejidad.

El proceso de colecta de residuos implica también la contaminación de un área geográfica, ya que los vehículos colectores generan emisión de gases y, por tanto, contaminación ambiental. Para minimizar este problema se realizan estudios para optimizar la ruta de los vehículos dentro de las ciudades.

Existen muchos estudios de este tipo de problema, sobretodo en Estados Unidos, Europa y Asia, los cuales están basados en sus realidades. El diseño óptimo de rutas para la colecta de residuos sólidos es uno de los grandes desafíos en los sistemas de colecta de residuos. En (Bautista, 2004) los autores extienden el problema de ruteo de arcos capacitados (Capacitated Arc Routing Problem - CARP) proponiendo un algoritmo de basado en la




colonia de las hormigas, cuyos resultados son obtenidos probando su propuesta con instancias encontrado en la literatura del CARP, así como instancias obtenidas del área metropolitana de Barcelona.

Uno de los primeros modelos para la optimización de gestión de residuos sólidos en Port Said, Egipto es discutido en (Badran, 2006). En esta investigación considerando un conjunto de localidades candidatas para que sean estaciones de coleta, se propone un modelo de programación entera mixta para minimizar el costo de gestión de colecta de residuos municipales. La mejor ubicación para las estaciones de colecta es seleccionada desde las localidades candidatas.

La colecta de residuos basados en el problema del ruteo de vehículos con ventanas de tiempo (Vehicle Routing Problem with Time Windows - VRPTW), desde un punto de vista de la vida real, considerando múltiples viajes para la eliminación de desechos y las pausas para la alimentación de los choferes es discutido en (Kim et al., 2006). La solución del problema se obtiene mediante una extensión del algoritmo de inserción de Solomon, es decir, la propuesta minimiza el número de vehículos y el tiempo de viaje total, también considera la compacidad de la ruta y el balanceo de la carga de trabajo ya que son aspectos muy importantes en aplicaciones prácticas.

Según Tattoni et al. (2010) un modelo multi-enfoque (multi-approach) optimiza la gestión de residuos sólidos urbanos aplicado a una área metropolitana italiana. En este trabajo, se introduce un modelo el cual apoya el proceso de toma de decisiones en la gestión de residuos sólidos urbanos. Específicamente, el modelo apunta a determinar cuáles de los sitios (selección, procesamiento y fábricas de despojo) necesitan ser abiertos, y la cantidad de residuo optimo – por cada alternativa de colección (diversificada o sin diversificar por ejemplo) – que debe ser enviado a través de diferentes sitios, tomando en cuenta los costos de transportación y procesamiento por sobre todos los objetivos impuestos por la legislación italiana. El modelo ha sido validado para el caso de un área metropolitana en Italia y un algoritmo genético fue probado para resolver el problema obteniéndose una solución que garantiza el mismo servicio con una mejora en los costos.

La colecta de residuos basados en el problema de ruteo de vehículos con ventana de tiempo, usando 6 procedimientos diferentes para obtener las soluciones iniciales del problema es propuesto en (Benjamín, 2011). Así, las soluciones iniciales de estos procedimientos son mejorados en términos de distancia recorrida usando sus procedimientos fase 1 y fase 2, en donde se reduce el número de vehículos usados. En un intento por mejorar las soluciones, el autor presenta tres algoritmos Metaheurísticos, llamados Busca Tabú (Tabu Search - TS), Busca Vecino Variable (Variable Neighborhood Search - VNS), y Busca Tabú Vecino Variable (Variable Neighborhood Tabu Search - VNTS). Además muestra la posición o ubicación de los centros de eliminación en cierta área geográfica. Las soluciones obtenidas son comparadas con soluciones de anteriores estudios, mostrando mejoras en términos de distancia recorrida y número de vehículos usados.

Como podemos apreciar, los resultados reportados son alentadores. En América Latina no se presta mucha atención a este problema, ya que en algunas oportunidades la falta de recursos y el poco interés, hacen que la colecta de residuos más que una solución, sea un problema más. Los programas de concientización por parte de los gobiernos centrales para la población aún son deficientes.

El esquema de trabajo está divido en 5 capítulos. El primer capítulo contiene todos los conceptos teóricos del problema y también de la metaheurística Busca Tabú, la cual utilizaremos para desarrollar nuestro trabajo. En el segundo capítulo se describen la población y muestra, así como la metodología a seguir en el desarrollo del trabajo. En el tercer capítulo se hará un análisis del problema, el análisis del modelo matemático y el diseño de la metaheurística de Busca Tabú, así como también la implementación y las




pruebas. En el capítulo 4 se encuentra la discusión de resultados obtenidos en el Capítulo 3 y por último el Capítulo 5 mostrara nuestras conclusiones a las que llegamos al realizar nuestro trabajo.

III. PLANTEAMIENTO DE LA INVESTIGACION

3.1 Planteamiento del Problema

¿Cómo optimizar el proceso de ruteo para la colecta de residuos domiciliarios en la ciudad de Trujillo?

3.2 Marco Teórico

3.2.1 Optimización Combinatoria

Según Martí (2002), optimizar significa mucho más que mejorar: Es el proceso que trata de encontrar la mejor solución posible para un determinado problema para el cual existen diferentes soluciones y un criterio para diferenciar entre ellas. De una manera más precisa, estos problemas son expresados de modo tal que se encuentre el valor de las variables de decisión para los que una determinada función objetivo alcance su valor máximo o mínimo, de acuerdo con ciertas condiciones dadas en el problema. Existe una gran cantidad de problemas de optimización, tanto en la ciencia como en la industria. Desde los clásicos problemas de diseño de redes de comunicaciones u organización de la producción hasta los más actuales problemas de ingeniería y re-ingeniería de software, existe una infinidad de problemas teóricos y prácticos que involucran a la optimización.

La optimización combinatoria tiene como objetivo encontrar el máximo (o mínimo) para una determinada función f(x) sobre un conjunto finito de soluciones D. De acuerdo con Garfinkel (1985), “la optimización combinatoria contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución”. Según Yepes (2008) la optimización combinatoria se puede mostrar de acuerdo a la siguiente fórmula:

( ⃗) ⃗ ( )

Dónde:

- ⃗ ( )

- ( ⃗) -

( )

- ( ) -

Algunas clases de problemas de optimización son relativamente fáciles de resolver. Por ejemplo los problemas de programación lineal, en los que tanto la función objetivo como las restricciones son expresiones lineales, y los podemos resolver con el conocido método Simplex (Martí, 2002). Sin embargo, existen




otros tipos de problemas de optimización que son muy difíciles de resolver, de hecho, la mayor parte de los que podemos encontrar en la práctica entran dentro de esta categoría.

3.2.2 Problemas NP – El Problema del Agente Viajero

La idea intuitiva del problema “difícil de resolver” queda reflejada en el término científico NP-hard utilizado en el contexto de complejidad computacional, para indicar que el problema es complejo y que para su solución es necesario mucho recurso computacional, es decir, un problema de optimización NP-hard es aquel cuya solución no puede ser encontrada en un tiempo razonable. De acuerdo con la Figura 1, consideremos el problema del Agente Viajero (Travelling Salesman Problem - TSP), donde un viajero tiene que visitar n ciudades una sola vez, regresando a la ciudad de origen. Entonces se plantea la pregunta: ¿En qué orden deben de visitarse para que la distancia sea mínima? En este problema, el número de soluciones posible es de (n-1)!/2.

Figura 1. Problema del Viajero. (a) Grafo que indica los nodos y el valor de los arcos. (b) tabla que muestra la relación entre nodos. (c) posible solución optima

Matemáticamente, el TSP se formula del modo siguiente (Daza et al., 2009):

Denotaremos por ( ) y ( ) al conjunto de nodos adyacentes e incidentes al nodo i, es decir:

- ( ) * ( ) + - ( ) * ( ) +

De manera similar, el conjunto de arcos incidentes hacia el exterior e interior del nodo i se definen como ( ) *( ) + y ( ) *( ) +. Entonces, el modelo matemático del TSP seria:

∑ ( )

( )




∑ ( )

( )

∑ ( )

( )

∑ ( )

( )

( )

Dónde:

- -

- -

Como podemos apreciar, la restricción (3) nos dice que se debe llegar a todas las ciudades una sola vez. La restricción (4), nos muestra que se debe de salir de las ciudades una sola vez. La restricción (4) nos permite eliminar subrutas, pero por lo menos una de ellas viola esta regla. Finalmente, la restricción (5) es binaria, ya que:

-

-

Si deseamos resolver este problema de una manera exacta, veremos que el tiempo de resolución aumenta exponencialmente a medida que aumentamos el número de ciudades. Ver Figura 2 según Daza et al. (2009).




Figura 2. Explosión Combinatoria en el TSP.

Para encontrar la mejor ruta en una red con 37 nodos (ciudades), se tendría que buscar de entre soluciones, esto sería como “encontrar una mota de polvo en la Atmósfera”. En el caso para una red con 100 nodos, el número de

soluciones sería de entre soluciones posibles, lo cual sería como encontrar “una mota de polvo en el Universo”. La Figura 2 también nos muestra el caso en que si tuviéramos una computadora que procese 20 billones de soluciones en 1 segundo, para computar las soluciones de 20 nodos tardaríamos 50 minutos; y en el caso de 25 nodos, nos tardaríamos 500 años en poder procesar todas las soluciones (Yepes, 2008).

3.2.3 Problema de Ruteo de Vehículos

Otro problema de alta complejidad computacional es el ruteo de vehículos (Vehicle Routing Problem - VRP) que data del final de los 50’s del último siglo, cuando Dantzig y Ramser, dos matemáticos de ese tiempo, establecieron un enfoque algorítmico y una formulación de programación matemática para resolver el problema de entrega de gasolina a las estaciones de servicio. Desde entonces el interés por el VRP evoluciono desde un pequeño grupo de matemáticos hasta un extenso rango de investigadores y practicantes, de diferentes disciplinas envueltas en este campo hoy en día (Caric y Gold, 2008). La mayoría de los problemas del mundo real son mucho más complejos que el VRP clásico, esto debido a que, en la práctica, el VRP clásico esta argumentado por restricciones, dando origen a las denominadas variantes, tales como el problema de ruteo de vehículos capacitados (Capacitated Vehicle Routing Problem - CVRP), el problema de ruteo de vehículos con ventanas de tiempo (VRPTW) y otras variantes. Ver Figura 3.




Figura 3. Relación de los VRP y sus variantes.

El significado de cada rectángulo se muestra a continuación:

- TSP: Travelling Salesman Problem (Problema del Agente Viajero). - TSPB: Travelling Salesman Problem with Backhauls (Problema del Agente

Viajero con Backhauls).

- TSPTW: Travelling Salesman Problem with Time Windows (Problema del Agente Viajero con Ventanas de Tiempo).

- MTSP: Múltiple Travelling Salesman Problem (Problema del Agente Viajero Múltiple).

- CVRP: Capacitated Vehicle Routing Problem (Problema de Ruteo de Vehículos Capacitado).

- DCVRP: Distance Constrained Vehicle Routing Problem (Problema de Ruteo de Vehículos con Distancia Restringida).

- VRPTW: Vehicle Routing Problems with Time Windows (Problema de Ruteo de Vehículos con Ventanas de Tiempo).

- VRPPD: Vehicle Routing Problems with Pickup and Delivery (Problema de Ruteo de Vehículos con Recojo y Entrega).

- VRPBTW: Vehicle Routing Problems with Backhauls and Time Windows (Problema de Ruteo de Vehículos con Backhauls y Ventanas de Tiempo).

- VRPPDTW: Vehicle Routing Problems with Pickup and Delivery and Time Windows (Problema de Ruteo de Vehículos con Recojo y Entrega y Ventanas de Tiempo).

EL problema de VRP es un tema muy investigado, como nos muestra (Joubert, 2006). Los autores integran 3 variantes de la VRP, VRP con múltiple ventanas de tiempo, VRP con flotas heterogéneas y VRP con doble programación dentro de un algoritmo de solución inicial. El algoritmo de solución inicial propuesta resulta factible para la integración, mientras que el concepto recién introducido compatibilidad ventana de tiempo disminuye la carga computacional utilizando




conjuntos de datos de referencia de la literatura como base para las pruebas de eficiencia.

Como se aprecia en la Figura 3, el CVRP es el tipo de problema de ruteo de vehículos más básico. Matemáticamente, se formula del modo siguiente (Deza et al. 2009):

Sea un grafo completo ( ), donde * + es el conjunto de vértices y

el conjunto de aristas entre cada dos vértices. Se denota por 0 el vértice que corresponde con el depósito de los vehículos y los vértices en * + los distintos clientes. Para una arista , - denotamos por el costo de ir de i a j.

Hay una flota vehículos, cada uno de capacidad . Por último, denotamos con

la demanda del cliente i. Una variable binaria indica si la arista está en la ruta de un vehículo o no. La formulación matemática sería entonces:

∑

( )

( (* +)) * + ( )

( (* +)) ( )

( ( ))

∑

* + ( )

* + ( )

La familia de igualdades de (8) impone que el grado de cada vértice correspondiente a cada cliente es exactamente 2, es decir, que cada cliente debe de ser visitado una vez por un vehículo. La igualdad (9) impone que el grado del depósito sea 2K. Las desigualdades (10) y (11) fuerzan la bi-conexidad de una solución entera y que un conjunto de clientes que supera la capacidad máxima Q no pueda ser visitado por el mismo vehículo. Las soluciones de este problema son todas las K rutas que verifican la restricción de capacidad de los problemas.

3.2.4 Problema de Ruteo de Vehículos con Ventanas de Tiempo

El Problema de Ruteo de Vehículos con Ventanas de Tiempo – Vehicle Routing Problem with Time Windows (VRPTW) – es una extensión del VRP tradicional, y por tanto es un problema combinatorio ya que pertenece a la clase de problemas NP-Completo.

En el VRPTW una llamada ventana de tiempo está asociada con cada cliente, es decir, además de la condición de capacidad del vehículo, cada cliente tiene un tiempo dentro del cual se debe de completar el servicio particular. Un vehículo puede llegar antes del intervalo de tiempo, pero debe de comenzar el inicio del servicio dentro de la ventana.

El objetivo del VRPTW es minimizar la cantidad de vehículos y la distancia total recorrida para atender a los clientes sin violar las condiciones de capacidad y la




ventana de tiempo. La condición de capacidad es violada, si la suma total de la demanda de los clientes en una ruta excede la capacidad del vehículo.

Matemáticamente, el VRPTW está representado por ( ), que es un grafo dirigido, donde es un conjunto de clientes, incluido el deposito 0 y n+1, los depósitos de salida y de retorno; y A un conjunto de arcos que denota las conexiones entre los nodos (incluido el deposito). , que es el costo asociado

con el arco (i, j) de A. es el tiempo de viaje asociado con el arco ( ) . q es

la capacidad de cada vehículo; es la demanda de cada cliente i y , - es la ventana de tiempo de cada cliente i. Los vehículos también deben dejar el depósito dentro de la ventana de tiempo , - y deben retornar antes o en el tiempo . Sea también una variable binaria, en donde es 1 si el vehículo k

va por el arco (i, j), caso contrario asume el valor 0. Además, sea una variable que indica el vehículo k atiende al cliente i.

Así, el modelo matemático es el siguiente:

∑ ( )

( )

∑

( )

∑ ( )

( )

∑ ( )

( )

∑

∑

( )

∑ ( )

( )

( ) ( ) ( )

( )

( )

La restricción (13) nos indica que un arco debe de ser recorrido una sola vez y por un solo vehículo. (14) nos indica que la demanda del cliente i que es recorrido por el vehículo k no debe de exceder a la capacidad de este. (15) y (17)




indica que los vehículos deben de salir del depósito de salida y deben de llegar al depósito de retorno. (16) nos muestra que debe de haber una continuidad de flujo por parte de los vehículos. (18) nos da a entender que el tiempo de atención a un cliente que le toma al vehículo, sumado al tiempo que toma para llegar al siguiente cliente, debe de ser menor al tiempo que es atendido el siguiente cliente. (19) y (20) nos explica que el tiempo que debe de ser atendido un cliente debe de encontrarse en el intervalo , -.

3.2.5 Métodos Heurísticos

La existencia de una gran cantidad y variedad de problemas difíciles que aparecen en la práctica y que necesitan ser resueltos de forma eficiente, impulso el desarrollo de procedimientos eficientes para encontrar buenas soluciones aunque no fueran óptimas. Estos métodos, llamados heurísticos o aproximados, son métodos en los que la rapidez del proceso es tan importante como la calidad de la solución obtenida. Díaz et al. (1996), define hasta de 8 maneras distintas el algoritmo heurístico, entre las cuales podemos destacar el siguiente: “Un método heurístico es un procedimiento para resolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución”.

En contraposición a los métodos exactos que proporcionan una solución óptima del problema, los métodos heurísticos se limitan a proporcionar una buena solución no necesariamente óptima. El tiempo invertido por un método exacto para encontrar la solución óptima de un problema NP-hard (si es que existe), es de una magnitud muy superior al heurístico, pudiendo llegar a ser tan grande que en muchos casos el método es inaplicable. Las heurísticas más conocidas son: Algoritmos genéticos, Busca Tabú, Simulated Annealing, colonia de las hormigas, entre otros.

3.2.6 Servicio de Gestión Ambiental SEGAT

La Municipalidad Provincial de Trujillo, mediante Ordenanza Municipal N° 012-2007-MPT crea al Servicio de Gestión Ambiental de Trujillo – SEGAT, organismo público descentralizado, a través del cual se ha realizado el proceso participativo para concluir el Plan de Gestión Integral de los Residuos Sólidos de la Provincia de Trujillo-PIGARS 2010-2020. Este documento de gestión ambiental marca las pautas a seguir para que en la Provincia de Trujillo se gestione los residuos sólidos de manera técnica y ambientalmente segura, y que esta implementado como parte de la política de mejoramiento ambiental contribuyendo a mejorar la calidad de vida de los ciudadanos. En el punto de recolección, los niveles de colecta son altos, llegando inclusive al 100% de cobertura. De acuerdo con el cuadro 1, se aprecia la cantidad de residuos sólidos que se recolectan en el Distrito de Trujillo de los años 2007, 2008 y primer trimestre del 2009, registrados por el SEGAT.




Cuadro 1. Cantidad de Residuos Sólidos recolectados por día en el Distrito de Trujillo.

TIPO DE RESIDUO ORIGEN KG/DIA

PROMEDIO (%) 2007 2008 2009

MUNICIPALES

DOMICILIARIOS 202 000 149 540 167 600 64.37

MERCADOS / COMERCIOS 60 000 53 000 62 000 21.70

BARRIDO 21 000 17 000 40 600 9.75

ESTABLECIMIENTOS DE SALUD (RESIDUOS COMUNES)

5 000 5 000 5 000 1.86

OTROS 6 347 6 150 2.32

TOTAL MUNICIPALES 288 000 230 887 281 350 100.00

De acuerdo con el (PIGARS, 2009), los valores que se refiere a OTROS, incluyen los residuos comerciales, restos de arreglos de pistas, residuos derivados de actividades industriales como curtiembres, residuos agroindustriales como las productoras de espárragos, avícolas, etc. Los reportes indican que se recoge y transporta al botadero controlado de El Milagro un promedio de 281.35 ton/día de residuos sólidos generados en el Distrito de Trujillo (datos a Julio 2009). Como vemos el proceso de recolección en el Distrito de Trujillo es muy eficaz. Sin embargo, este no cuenta con un sistema que optimice el problema, ya que no se cuenta con un plan de rutas que optimice el servicio. Además, la colecta de residuos en la provincia no tiene un estudio de análisis de costos que el proceso demanda. Esto se debe principalmente a que SEGAT no está utilizando el ruteo de vehículos.

3.2.7 Estudios de Colecta de Residuos alrededor del Mundo

En el pasado, la colecta de residuos sólidos fue tratada sin analizar la demanda y la construcción de rutas fue dejada a la experiencia de los conductores. Sin embargo, las ciudades siguen expandiéndose. Debido a este crecimiento, la importancia de un sistema de colecta eficiente aumenta considerablemente. Óptimamente, debería de haber un método que intente maximizar la aceptación general de una solución. Sin embargo, como esto es difícil de realizar, diferentes métodos han sido desarrollados, en donde se centran en la longitud de la ruta, costos, número de vehículos de colecta, etc. La Figura 4 muestra la evolución en número de artículos orientados a este problema ente 1971 y 2010 (Beliën et al., 2010).




Figura 4. Número de Publicaciones por Periodo (1971 - 2010)

Como podemos observar, los artículos sobre la gestión de residuos basados en el problema de ruteo de vehículos han crecido ampliamente después de 1995, lo cual indica el aumento de interés en este tema.

La mayoría de los casos de estudios han sido realizados en Europa, Norteamérica o Asia. La evolución de las publicaciones a través de la historia, como se muestra en la Figura 5, nos enseña como ejemplos de publicaciones con un caso hipotético de estudio o sin caso de estudio decrecieron considerablemente después del 2000. Aquí en nuestro continente, solo hubo algunos estudios alrededor del año 1990, y de nuevo volvió a tomar fuerza a partir del 2005.

Figura 5. Trabajos Realizados en Diferentes partes del Mundo (1971 - 2010)

0

2

4

6

8

10

12

14

1971 -1975

1976 -1980

1981 -1985

1986 -1990

1991 -1995

1996 -2000

2001 -2005

2006 -2010

Norteamerica

Europa

Sudamerica

Asia

Caso Hipoteticoo No CasoAfrica




3.2.8 Búsqueda Tabu

Fred Glover en el año 1986 propuso un nuevo enfoque, el cual llamo Búsqueda Tabu, para permitir a los métodos de Búsqueda Local superar el óptimo local. El principio básico de la Búsqueda Tabu (Tabu Search - TS) es perseguir la Búsqueda Local (Local Search - LS) cuando sea que encuentre una óptima local permitiendo movimientos no mejorados; para evitar regresar a soluciones visitadas anteriormente, se hace uso de memorias, llamadas listas tabú, que graba la historia reciente de la búsqueda, una idea clave que puede ser enlazada con los conceptos de Inteligencia Artificial (Gendreau, 2003).

3.2.8.1 Espacio de Búsqueda y Estructura de Vecindad

El Espacio de Búsqueda de una heurística TS es simplemente el espacio de todas las posibles soluciones que pueden ser considerados (visitados) durante la búsqueda. Por ejemplo, en un CVRP el espacio de búsqueda podría simplemente ser el conjunto de soluciones feasibles del problema, donde cada punto en el espacio de búsqueda corresponde a un conjunto de rutas de vehículos satisfaciendo todas las restricciones especificadas.

Cercanamente enlazado a la definición del espacio de búsqueda es la Estructura de la vecindad. En cada iteración de TS, las transformaciones locales que pueden ser aplicadas a la solución actual, denotado por , define un conjunto de soluciones vecinas en el espacio de búsqueda, denotado por ( ). Formalmente, ( ) es un subconjunto del espacio de búsqueda definido como:

( ) * +

Las estructuras de la vecindad simples para el caso de CVRP involucran movimientos en cada iteración a un vecino común desde su ruta actual; el vecino seleccionado es insertado en la misma ruta o en otra ruta con suficiente capacidad residual. Una característica importante de estas estructuras de vecindad es la manera en la cual las inserciones son desarrolladas: una podría usar inserción aleatoria o inserción en la mejor posición en la ruta objetivo; alternativamente, otra podría ser usar esquemas de inserción más complejas que involucran una re-optimización de la ruta objetivo, como las inserciones GENI.

Es muy importante tener en cuenta que escoger un espacio de búsqueda y una estructura de vecindad es por mucho el paso más crítico en el diseño de cualquier heurística TS. Este es el paso que uno debe hacer el mejor uso de comprensión y conocimiento que tenemos del problema a tratar.

3.2.8.2 Tabús

Los Tabús son uno de los elementos distintivos de TS cuando se lo compara con LS. Como se mencionó anteriormente, los tabús son usados para prevenir los ciclos cuando se retrocede desde un óptimo local a través de movimientos no mejorados. La realización clave es que cuando esa situación ocurre, algo necesita ser hecho para prevenir que la búsqueda de rastreo no vaya sobre sus propios pasos. Esto es alcanzado declarando movimientos tabú (denegado) que revoca el efecto de los movimientos recientes. Por ejemplo, en un caso de CVRP, si el cliente justo ha sido

movido desde la ruta a la ruta , uno podría declarar un movimiento

tabu de desde a para algún numero de iteraciones (este numero es




llamado tenencia tabú del movimiento). Tabús son también útiles para ayudar el movimiento de rastreo desde las porciones previamente visitadas del espacio de búsqueda y así desarrolla una exploración más extensiva.

Los Tabús son almacenado en una memoria de corto plazo de la búsqueda (la lista tabú) y usualmente solo una limitada cantidad mejorada y creíble de información que es guardada. Uno podría guardar soluciones completas, pero esto requiere mucho almacenamiento y lo hace más caro comprobar si un movimiento potencial es tabú o no; por esto es que se utiliza rara vez. Los tabús usados comúnmente involucra grabar las ultimas pocas transformaciones desarrolladas sobre la solución actual y prohibir transformaciones inversas; otros son basados sobre las características clave de la solución por ellos mismos o de los movimientos.

3.2.8.3 Criterio de Aspiración

Los tabús son algunas veces muy poderosos: podrían prohibir movimientos atractivos, siempre cuando no hay peligro de ciclo, o ellos pueden alcanzar un estancamiento general del proceso de búsqueda. Esto es así necesario para usar dispositivos algorítmicos que permitan uno para cancelar tabús. Estos son llamados criterios de aspiración. El criterio más simple y comúnmente utilizado (encontrado en la mayoría de implementaciones de TS) consiste en permitir un movimiento, incluso si es tabú, si resulta en un valor objetivo mucho mejor que la mejor actual solución conocida (desde que la nueva solución no haya sido previamente visitada).

3.2.8.4 Criterio de Termino

En teoría, la búsqueda podría ir para siempre, a menos que el valor óptimo del problema es conocido de antemano. En la práctica, obviamente, la búsqueda tiene que parar en algún punto. Los más comunes criterios de palabra usados en TS son:

- Después de un número fijo de iteraciones (o una cantidad fija de tiempo de CPU).

- Después de un número de iteraciones son un mejoramiento en el valor de la función objetivo (el más usado en la mayoría de implementaciones).

- Cuando el objetivo alcanza un valor umbral pre-especificado.

En esquemas tabú más complejos, la búsqueda es usualmente detenida después de completar una secuencia de fases, la duración de cada fase es determinada por uno de los criterios mencionados anteriormente.

3.2.8.5 TS Probabilístico y Listas Candidato

En un TS regular, uno debe de evaluar el objetivo para cada elemento de la vecindad ( ) de la solución actual. Esto puede resultar ser muy caro desde el punto de vista computacional. Una alternativa es considerar solo un ejemplo aleatorio ( ) de ( ), asi se reduciría significativamente el costo computacional. Otra característica atractiva de esta alternativa es que la aleatoriedad agregada puede actuar como un mecanismo anti-cíclico; esto permite usar pequeñas listas tabú que sería necesario si es




desarrollada la exploración total de la vecindad. Por el lado negativo, debe ser notado que, en ese caso, uno puede obviar soluciones excelentes. Las probabilidades pueden también ser aplicadas para activar el criterio tabú.

Otra manera de controlar el número de movimientos examinados es a través de estrategias de listas candidatas, la cual proveen maneras más

estratégicas de generar un subconjunto más útil ( ) de ( ). Hay que recalcar que el enfoque probabilístico puede ser considerado ser una instancia de una estragia de lista de candidatos, y puede ser tambien ser usado para modificar esa estrategia. Una de las diferencias más llamativas se produciría si no se abordan adecuadamente las cuestiones implicadas en la creación de listas candidatas efectivas, ya que eso diferenciaría una aplicación ingenua de TS de una más sólida.

3.2.8.6 Diagrama de Flujo de La Búsqueda Tabu

A continuación, presentamos un diagrama de flujo de Búsqueda Tabu, para mayor entendimiento de su proceso.

Figura 6. Diagrama de flujo Búsqueda Tabu

3.3 Justificación del Estudio

Hoy en día el estudio del medio ambiente y las maneras de cómo evitar su deterioro son temas muy importantes y de mucho interés para el mundo moderno. Una de estas maneras es la colecta adecuada de residuos generados en los domicilios diariamente. Un óptimo proceso de colecta de residuos es muy importante pues ayuda a disminuir los efectos que tales residuos impactan negativamente en el medio ambiente.




El proyecto presentado es un trabajo novedoso en el país y dentro del área de la Ciencia de la Computación. El desarrollo de una solución óptima para el problema de ruteo de vehículos dentro de nuestro contexto local, ayudará en gran medida a la reducción de recursos económicos y logísticos, y generará un mejor uso y gestión de los mismos.

3.4 Objetivos

3.4.1 Objetivo Principal

Desarrollar una heurística para la colecta de residuos domiciliarios, basado en el ruteo de vehículos con ventanas de tiempo.

3.4.2 Objetivos Específicos

a. Conocer los conceptos del problema de ruteo de vehículos y sus variantes. b. Desarrollar e implementar un modelo de optimización combinatoria para el

problema de ruteo de vehículos con ventana de tiempo (Vehicle Routing Problem with Time Windows - VRPTW) aplicado a nuestro problema a solucionar.

c. Desarrollar e implementar la heurística basado en los conceptos y en la estructura del problema.

d. Testar la propuesta algorítmica propuesta comparándolo con el modelo de optimización a desarrollar.

e. Conocer el proceso de colecta de residuos domiciliarios en la ciudad de Trujillo y ofrecer una solución basada en ciencia de la computación.

IV. MATERIALES Y METODOS

4.1 Población y Muestra

La población de nuestro trabajo son las Municipalidades distritales de la provincia de Trujillo. La muestra será la Municipalidad Distrital de Trujillo, de la cual se recogerán del Plan de Gestión Integral de los Residuos Sólidos – PIGARS 2010 – 2020, desarrollado por el Servicio de Gestión Ambiental de Trujillo – SEGAT.

4.2 Variable de Estudio

Nuestras variables independientes son la distancia recorrida por vehiculo y el numero de vehículos. Con respecto a nuestra variable dependiente, será el costo que implica la ruta de cada vehiculo.




4.3 Tipo de Investigación

Experimental.

4.4 Técnicas de Recolección de Datos

Para nuestra recolección de datos, se hará un análisis documental, especialmente del Plan de Gestión Ambiental de Residuos Sólidos PIGARS 2010 – 2020. Además, se extraerá información de distintos artículos, datos estadísticos, proceso de colecta), conceptos, teorías, formulas, métodos que ayudaran a la solución al problema que se ha planteado.

4.5 Instrumentos de Recolección de Datos

Para nuestro trabajo, se empleara la recolección de datos a través de la encuesta con los responsables de SEGAT, para así poder tener datos reales y saber la realidad actual de la entidad encargada. A continuación, mostraremos el cuestionario que resolverán los encargados de SEGAT:

ENCUESTA DE OPERATIVIDAD SEGAT 1. ¿Con cuántos vehículos colectores cuenta SEGAT actualmente? 2. ¿Cuántos de estos se encuentran operativos? 3. ¿Cuál es la capacidad máxima de los vehículos colectores operativos? ¿La mínima? 4. ¿Cuáles son sus puntos críticos de colecta? ¿Con que capacidad cuentan? 5. ¿Se cumplen los horarios de los vehículos colectores?

Si NO *Si la respuesta es SI pase a la pregunta 6, si la respuesta es NO pase a la pregunta 7

6. ¿Terminan su trabajo en el horario establecido? 7. ¿Cuál es el tiempo extra promedio que les demora culminar con su trabajo asignado? 8. ¿Cuál es la distancia máxima que puede recorrer un vehículo colector? 9. ¿Cuáles de los costos se consideran fijos? ¿Por qué?

A través de esta encuesta a la persona encargada del área, podremos obtener información de primera mano para poder desarrollar nuestro problema de una manera más real.

4.6 Procedimiento de la Investigación

La metodología para el desarrollo para nuestro trabajo está basado en un enfoque cuantitativo, siendo los métodos a usar el estadístico, experimental y comparativo, además de la técnica de la observación. Nuestro trabajo tendrá las siguientes etapas: a. Estudio estadístico de la cantidad de residuos domiciliarios generados y la

cantidad colectada en la ciudad de Trujillo a través del Servicio de Gestión Ambiental SEGAT.

b. Recopilación bibliográfica del problema de ruteo de vehículos y sus variantes,

además de optimización combinatoria.




c. Modelar el problema a investigar usando los conceptos de la optimización combinatoria.

d. Proponer un algoritmo heurístico orientado a solucionar el problema basado en

el problema de ruteo de vehículos con ventana de tiempo. e. Simulación del modelo heurístico propuesto y comparación con el modelo

diseñado.

V. RESULTADOS

5.1 Problema

Como se planteó en el punto 1.3, el objetivo de nuestro trabajo es optimizar el proceso de ruteo para la colecta de residuos domiciliarios en la ciudad de Trujillo.

5.1.1 Análisis del Problema

En nuestro estudio, lo que tenemos que afrontar es encontrar la ruta óptima que permita una colecta de residuos domiciliarios más eficiente y menos costosa.

De acuerdo a la Figura 7, la ciudad de Trujillo comprende las siguientes zonas, las cuales están divididas en 57 distritos (Fuente del 2007). El distrito cuenta

con 29 contenedores de tres metros cúbicos ( ) cuya ubicación se muestra en el Cuadro 2 y los cuales recogen alrededor de 72.2 ton/día; estas zonas son considerados puntos críticos, debido a que se encuentran dentro de la vía pública y producen focos de contaminación. El recojo de residuos domiciliarios se da diariamente, en donde en los puntos críticos se realiza hasta 3 veces por día.

Figura 7. Territorios Vecinales del Distrito de Trujillo




Cuadro 2. Ubicación de Puntos Críticos (Datos de 2007)

Nº DESCRIPCION CANT ESTADO PESO FRECUENCIA TN

1 MERCADO LA HERMELINDA-PROL AV. F. VILLAREAL 2 2.5 3 1.5

2 MERCADO LA HERMELINDA- AV. LIBERTAD 1 2.5 3 7.5

3 MERCADO LA HERMELINDA- MCDO. DE ANIMALES 1 2.5 3 7.5

4 MERCADO LA HERMELINDA-AV. EL PROGRESO 1 2.5 3 7.5

5 MERCADO HERMELINDA- AV. LOS LAURELES 2 2.5 3 15

6 CUARTEL BIM. 32 1 2.5 0.33 0.825

7 CEMENTERIO CHINO 1 RETIRADO 2.5 0 0

8 MERCADO UNIOIN 1 2.5 0 0

9 URB. SAN ISIDRO III ETAPA 1 2.5 1 2.5

10 MALL AVENTURA PLAZA 2 2.5 2 10

11 HOSPITAL REGIONAL (Para residuos comunes) 2 2.5 1 5

12 FACULTAD MEDICINA UNT (Para residuos comunes) 1 2.5 0.5 1.25

13 UNIVERSIDAD NACIONAL DE TRUJILLO 2 2.5 0.5 2.5

14 UNIVERSIDAD PARTICULAR ANTENOR ORREGO 1 2.5 0.25 0.625

15 EX HACIENDA LA ENCALADA 1 2.5 1 2.5

16 MERCADO DE PAPAS 1 2.5 1 2.5

17 COOPERATIVA SANTA ROSA 1 2.5 0 0

18 MERCADO MAYORISTA EN AV. VALLEJO (AV. LOS INCAS) 1 2.5 5 12.5

19 MERCADO MAYORISTA EN GALVEZ-AV. LOS INCAS 1 2.5 5 12.5

20 MERCADO MAYORISTA AV. SINCHI ROCA 1 2.5 2 5

21 DIRELL 1 2.5 1 0.625

22 SANIDAD DE LA PNP (Para residuos comunes) 2 2.5 1 5

23 HOSPITAL BELEN (Para residuos comunes) 1 2.5 1 2.5

24 MERCADO CENTRAL 1 2.5 3 7.5

25 MERCADO LA RINCONADA 1 DETERIORADO 2.5 1 2.5

26 MERCADO SANTO DOMINGUITO 1 2.5 2 5

27 PROLONGACION AV. VALLEJO (URB. LA RINCONADA) 1 RETIRADO 2.5 0 0

28 HOSPITAL VICTOR LAZARTE ECHEGARAY (Para residuos comunes) 1 2.5 1 2.5

29 PENAL EL MILAGRO (HOMBRES) 2 2.5 0.25 1.25

30 PENAL EL MILAGRO (MUJERES) 2 2.5 0.25 1.25

31 FAMECA (Para residuos comunes) 1 2.5 1 2.5

32 MODASA (Para residuos comunes) 1 NO ENCONTRADO 2.5 0 0

33 COCA-COLA (Para residuos comunes) 1 2.5 0.5 1.25

CAPACIDAD TOTAL CONTENEDORES DISPONIBLES 142.075

De acuerdo a datos de Julio de 2009, se recoge y transporta los residuos sólidos al botadero controlado de El Milagro, un promedio de 281.35 ton/día de residuos sólidos generados en el Distrito de Trujillo. Las unidades de




recolección son los encargados de transportar los residuos hacia el botadero controlado de El Milagro ubicado a 13 km del distrito de Trujillo.

El incumplimiento de los horarios de recojo y la interrupción del servicio es debido principalmente a que las compactadoras antiguas continuamente se malogran, ya sea por fallas de neumáticos, frenos, caja de compactación, etc. Además, otro de los problemas es la dificultad de transito de las compactadoras nuevas por las vías de la ciudad, debido al tamaño de las unidades, su radio de giro y los anchos de vías.

Según el estudio de PIGARS, los niveles de recojo son altos, llegando inclusive al 100% de cobertura. Sin embargo, esta cobertura no se realiza respetando los horarios debido a que las unidades de recolección han concluido con su tiempo de vida, el número que se tienen no es suficiente ni adecuado, por lo que se requiere del equipamiento del área con vehículos apropiados. Así mismo, no se cuenta con un plan de rutas que optimice el servicio.

5.1.2 Modelos Matemáticos

5.1.2.1 Modelos Matemáticos Fuente

5.1.2.1.1 Modelo Matemático Tattoni, 2010

El modelo matemático de Tattoni 2010, sugiere un modelo para diseñar un sistema inverso para la gestión de residuos sólidos domiciliaros e un área metropolitana italiana. En general, el modelo identifica donde y cuanto residuo debe de ser transportado desde un conjunto de colecta origen a las instalaciones de proceso y sitios de despojo, para asegurarse el mayor tratamiento propis de acuerdo a la calidad de residuos, costos de procesamiento y objetivos de la calidad de salida impuestos por las regulaciones.

Las siguientes suposiciones son consideradas:

- Todo el residuo sólido está localizado en los sitios de origen, donde es transportado después de haber sido recolectados en los puntos de producción. Existen dos tipos de colecta: Diversificado, que tiene un proceso de selección más barato; y la Sin Diversificar, que tiene un menor costo de colecta.

- Los centros de colecta son considerados el punto inicial de selección, algunos materiales pueden ser directamente enviados a los puntos de despojo. Entonces, hay una operación de orden y una selección de segundo nivel en los sitios de proceso.

- Existe un costo fijo para abrir los centros de despojo y proceso. Hay un número de sitios que pueden ser abiertos y un número mínimo de sitios abiertos debe de garantizados.




- Es posible transportar desde un sitio de colecta a los sitios de despojo pero obviamente el costo variable será diferente y más alto (para prevenir esa posibilidad, un costo infinito de transporte puede ser simple seteado en el modelo)

La solución indicara cuales sitios necesitan ser abiertos y cuánto cuesta los residuos para ser procesados, por cada clase de calidad. La siguiente notación es usada:

* + ( ) Es aquí donde llegan los residuos desde los puntos domiciliarios, donde puede eventualmente desarrollar una selección de primer nivel.

* + ( ) Reciben material desde los CS los residuos colectados, y después de ordenar y seleccionar, dirigirse al flujo de salida a los sitios de despojo.

* + ( ) Reciben material desde CS y PS. En estas instalaciones los residuos pueden ser dirigidos a: Incineración, Materia Prima Secundaria (SRM) y Despojo hacia los rellenos.

* + ( ) La calidad de residuos puede ser dividido en relación de diferentes operadores (tipo de colecta, fracción de valor, etc.) y en este modelo la clases discretas de calidad. Los residuos son clasificados después de cada proceso de selección considerado. Los residuos que son dirigidos al relleno sanitario pertenecen a la clase de calidad más baja.

Costo variable total unitario desde un CS a través de un PS y

por un DS. Comprende los costos de selección de primer nivel en CS, además los costos de transporte tanto de entradas como de salidas de la entrega desde CS al DS vía PS.

Impuesto dado por la legislación para incrementar la recuperación de residuos con valor. El impuesto es dado para cada clase de calidad, entonces no hay un impuesto para el nivel más bajo de calidad debido a que ese residuo es dirigido hacia el relleno sanitario.

Costo fijo para abrir un PS.

Costo fijo para abrir un DS.

Cantidad de residuos almacenados en el CS pertenecientes a

la clase de calidad respectiva.

Capacidad de procesamiento máximo de un PS.

Capacidad de procesamiento máximo de un DS.

Numero minimo de PS que se pueden abrir.

Numero maximo de PS que se pueden abrir.

Numero minimo de PS que se pueden abrir.




Las variables de decisión son las siguientes:

Porcentaje de residuos pertenecientes a la QS residiendo en

el CS para ser transportado a través del PS por el DS. En caso PS sea cero, esto indicaría que el transporte es dirigido a DS sin pasar a través de PS (en caso de una colecta diversificada).

Variable booleana que asume 1 cuando un PS es abierto, y 0

caso contrario.

Variable booleana que asume 1 cuando un DS es abierto, y 0 caso contrario.

Así, el modelo matemático resulta ser:

∑∑∑∑

∑

∑

∑∑∑

( )

∑∑∑

* + ( )

∑∑∑

( )

∑∑∑

( )

∑

* + ( )

∑

* + ( )

( )

* + ( )

* + ( ) El modelo minimiza la suma de los costos variables para transporte desde un conjunto de CS a través de PS a los DS y los costos fijos para abrir aquellos puntos de entrega. La restricción (21) indica que toda la cantidad de residuos en el punto de colecta debe de ser transportado a las instalaciones destino. En (22) la conformidad del impuesto de regulación es impuesta. Restricciones (23) y (24) tienen un doble efecto: limitar la cantidad de residuos transportados a los PS y DS sin exceder su máxima capacidad y mientras tanto evitar que ese residuo sea enviado a instalaciones cerradas. Desde que los municipios proveen un nivel de servicio homogéneo sobre el territorio, las restricciones (25) y (26) se aseguran que el número de sitios abiertos no sea menos que el mínimo y no sea más que el máximo valor. Restricción (27) se asegura




que asume valores entre 0 y 1 donde las restricciones (28) y (29) se

aseguran que los otros dos variables de decisión son binarias.

5.1.2.1.2 Modelo Matemático de Badran, 2006

Las estaciones de colecta son incluidas en este modelo para el sistema de gestión de residuos sólidos de Port Said. Muchos sitios de estaciones de colecta potenciales en cada distrito de Port Said son evaluados por el modelo para escoger las mejores ubicaciones de acuerdo a minimizar el costo del sistema.

Este modelo esta formulado tomando consideración algunos puntos clave del flujo de residuos en las ciudades de Egipto como: no hay separación de residuos en la fuente y que los residuos industriales, de construcción y demolición son transferidos al gasto de sus generadores hacia la estación de colecta más cercana.

El objetivo de este modelo es seleccionar entre diferentes sitios potenciales para las estaciones de colecta para minimizar el costo total de todo el sistema. El costo total es dividido en dos componentes, uno es dependiente sobre las instalaciones y el otro es dependiente sobre la operación del sistema. El siguiente costo incluirá costos de transportes, costos fijos y variables de las instalaciones. El costo tardío incluirá el costo del sistema de operación, el cual incluye el costo de barriles de basura HDPE estándar 7701, uniformes del grupo de colecta, y costos administrativos. El costo que es dependiente sobre las instalaciones es minimizado por el modelo integral mixto, mientras el otro costo es agregado al costo minimizado por el costo total del sistema.

Se está tomando las siguientes suposiciones:

- La eficiencia de colecta es el 100%

- El costo fijo de la estación de colecta o del relleno sanitario o de la planta de compostaje puede ser descrito como un costo diario, dividiéndolo por la vida económica prevista en días, el cual es depreciación con un valor cero.

- El costo variable de la estación de colecta, planta de compostaje o relleno sanitario está dividido por la capacidad diaria de la estación de colecta.

- Combustible y costos de mantenimiento son proporcionales a la distancia recorrida y la carga transportada.

- Costos vehiculares y de personal son proporcionales a la duración del viaje y a la carga transportada.

- Las distancias son medidas desde los centroides de los distritos o

las instalaciones. Medidas Euclidianas serán usadas así como los mapas de ruta detallados no están disponibles en el municipio de Port Said.




- Velocidad promedio de los vehículos están determinados para los vehículos de colecta en 25 km/h y para los vehículos de transferencia en 35 km/h.

Así, la notación es la que viene a continuación:

Plantas de Compostaje

Rellenos Sanitarios

Estaciones de Colecta

Conjunto de distritos

Capacidad diaria de las plantas de compostaje

Capacidad diaria de las estaciones de colecta

Capacidad diaria de los rellenos sanitarios

Cantidad diaria de residuos generados en un distrito.

Costo fijo de las planta de compostaje representado como un costo fijo diario.

Costo fijo de la estación de colecta representado como un

costo fijo diario.

Costo fijo del relleno sanitario representado como un costo fijo.

Costo variable de la planta de compostaje representado por tonelada procesada.

Costo variable de las estaciones de colecta representado por

tonelada procesada.

Costo variable de los rellenos representado por tonelada procesada.

Costo de transporte de 1 ton de residuos desde la planta de compostaje hasta un relleno sanitario.

Costo de transporte de 1 ton de residuos desde la estación

de colecta a la planta de compostaje.

Costo de transporte de 1 ton de residuos desde la estación

de colecta al relleno sanitario.

Costo de transporte de 1 ton de residuos desde un distrito a

una estación de colecta.

Cantidad diaria de residuos desde hospitales, construcciones y demoliciones.

Numero de estaciones de colecta.




Porcentaje de residuos que fueron rechazados tanto en las actividades de selección y compostaje.

Además, sus variables de decisión son las siguientes:

Cantidad (en ton) de residuo solido diario que va a ser transferido desde la planta de compostaje hacia un relleno sanitario.

Cantidad (en ton) de residuo sólido diario que va a ser

transferido desde una estación de colecta hacia una planta de compostaje.

Cantidad (en ton) de residuo solido diario que va a ser

removido desde una estación de colecta hacia un relleno sanitario.

Cantidad (en ton) de residuo sólido diario que va a ser

removido desde un distrito hacia una estación de colecta.

una variable binaria, la cual es 1 si una estación de colecta esta

siendo colocada en una locación candidata.

El modelo matemático es como se muestra a continuación:

∑ ∑

∑

∑

∑

∑ ∑

∑

∑

∑

∑

∑ ∑

∑ ∑

∑ ∑

∑ ∑

Sujeto a:

∑

( ) ( )

∑

( ) ( )

∑

(∑

∑

) ( ) ( )

∑

(

)∑

( ) ( )

∑

( ) ( )

∑

( ) ( )




∑

∑

( ) ( )

( ) ( ) ( )

∑

( )

* + ( )

La función objetivo es minimizar del costo total del sistema de gestión de residuos sólidos. La restricción (1) implica que todos los residuos generados desde un distrito son iguales a las cantidades desde ese distrito a todas las estaciones de colecta. La restricción (2) se asegura que la cantidad transportada desde las estaciones de colecta hacia el relleno sanitario es menor o igual que la cantidad total de los residuos de hospitales, construcción y demolición. La restricción (3) compara la cantidad de residuo que entra y sale de las estaciones de colecta. El balanceo de la cantidad de residuo que entra y sale de las plantas compostaje se da en la restricción (4). Restricciones (5)-(7) se aseguran que la cantidad de residuo transportado a cada estación de colecta, planta de compostaje y relleno sanitario respectivamente, no exceda su capacidad. La restricción (8) certifica que habrá actividad en una locación potencial solo si una estación de colecta es establecida en esa locación. El parámetro M mantiene un numero significativamente grande, el cual hará la restricción no vinculante cuando sea . La

restriccion (9) asegura que el número permitido de estaciones de colecta no exceda al valor T. La restricción (10) es la restricción de no negatividad de las variables de decisión y la restricción (11) se asegura que debe de tener valor binario.

5.1.2.2 Nuevo Modelo Matemático

A partir de los modelos mostrados anteriormente, y basándose en el modelo clásico Del problema de ruteo de vehículos con ventanas de tiempo (ver parte 3.2.4), se procederá a realizar el modelo matemático para nuestro problema en particular.

De acuerdo a la documentación obtenida, podemos dar los siguientes supuestos:

- Los vehículos colectores tienen diferentes tamaños y cargas. Por lo tanto son vehículos colectores heterogéneos.

- Para ayudar en el mantenimiento de los vehículos colectores, se debe de colocar una distancia máxima de recorrido, ya que no todos los vehículos tienen el mismo tiempo de uso (Chun-Hua, 2009).

- El deposito inicial de los vehículos está ubicado en la av. América, a la altura del Mercado La Hermelinda. Es de este lugar que parten para




hacer sus labores, considerando al botadero de El Milagro el depósito de llegada.

- Los horarios de trabajo son de 8 horas, y existen dos turnos: 6am a 3pm y de 7pm a 3am. Se considera también una hora de almuerzo en el primer turno.

- La eficiencia de colecta llega al 100%

- Todo el residuo sólido está localizado en los puntos críticos y en puntos de colecta dentro del distrito.

- No hay separación de residuos en el momento de la colecta y los residuos industriales, de construcción y demolición no son considerados.

- La velocidad promedio de los vehículos colectores será de 25km/h.

- Las distancias son medidas desde los centroides de las urbanizaciones. Medidas Euclidianas serán usadas.

Una vez considerando estas asunciones, procedemos a realizar la notación de nuestro problema.

Conjunto de puntos críticos y de colecta. Aquí se encuentra incluido tanto el depósito de salida (0) como el de llegada (n+1).

Conjunto de vehículos heterogéneos

Conjunto de arcos que unen los puntos críticos o de colecta

Número de puntos críticos o de colecta.

Capacidad de cada vehiculo

Maxima distancia permitida por vehiculo

Cantidad máxima de residuos dentro de los puntos críticos.

Tiempo que tarda el vehículo en llegar de un punto crítico a otro.

Numero grande

Distancia euclidiana de nodo a nodo

Costo fijo por usar un vehículo.

Limite mínimo permitido para llegar a un nodo.

Limite máximo para dejar un nodo.

Costo que implica recorrer los nodos con un vehículo colector.

A continuación, mostramos las variables de decisión de nuestro modelo:




Variable binaria, cuando tiene el valor 1, el arco (i, j) es recorrido

por el vehículo k, caso contrario, posee un valor de 0.

Variable que indica el tiempo que el vehículo k visita al nodo i.

A continuación, mostramos nuestro modelo matemático:

∑ ∑

( )

∑∑

∑ ∑

( )

∑ ( )

( )

∑ ( )

( )

∑

∑

( )

∑ ( )

( )

∑∑

( )

( ) ( ) ( )

( ) ( ) Nuestra función objetivo minimiza los costos de la ruta, además de los costos de utilizar un vehículo. La restricción (40) nos indica que el arco puede ser recorrido una sola vez y un solo vehículo puede pasar a través de él. La restricción (41) nos indica que la cantidad máxima de residuos que se almacenan en los puntos críticos, no debe de exceder a la capacidad del vehículo que lo recorre. Restricciones (42) y (44) nos muestran que los vehículos deben de salir del depósito de salida, y deben de llegar al depósito de llegada. La restricción (43) es para la conservación de flujo. La restricción (45) nos muestra que la distancia que recorre un vehículo, no debe de sobrepasar la distancia máxima permitida. La restricción (46) nos da a entender que el tiempo de atención a un cliente que le toma al vehículo, sumado al tiempo que toma para llegar al siguiente cliente, debe de ser menor o igual al tiempo que es atendido el siguiente cliente. Las restricciones (47) y (48) nos indica que el vehículo debe de atender al cliente entre el límite inferior LI y el límite superior LS.




5.2 Comparaciones entre los Modelos Fuente y Modelo Propuesto

Las comparaciones fueron realizadas en una Computadora AMD A8-3870 with Radeon(tm) HD Graphics 3.00 GHz. 8.00 GB RAM, 1 TB HD. Los modelos fueron implementados en el programa GLPK de libre licencia (GNU).

Cuadro 3. Comparación Nro. Variables Generadas y Tiempo Usado

Modelo Tattoni (2010) Badran (2006) VRPTW Modelo Propuesto

Escenarios Nro. Variables

Generadas

Tiempo usado

Nro. Variables generadas

Tiempo usado

Nro. Variables

Generadas

Tiempo usado

Nro. Variables

Generadas

Tiempo usado

1 6 0.0 seg 3 0.0 seg 147 0.0 seg. 147 0.0 seg

2 8 0.0 seg 4 0.0 seg 195 0.0 seg. 195 0.0 seg

3 9 0.0 seg 5 0.0 seg 249 0.2 seg. 249 0.1 seg

4 10 0.0 seg 5 0.0 seg 309 0.1 seg. 309 0.5 seg

5 11 0.0 seg 6 0.0 seg 369 0.6 seg. 369 0.6 seg

6 13 0.0 seg 6 0.0 seg 744 1.9 seg. 744 1.6 seg

Cuadro 4. Comparación Tiempo Usado, Memoria Usada, Costo (Tattoni - Badran)

Modelo Tattoni (2010) Badran (2006)

Escenarios Tiempo usado

Memoria usada

Costo(S/.) Tiempo usado

Memoria usada

Costo(S/.)

1 0.325 seg 0.2 Mb 32500 0.214 seg 0.2 Mb 1562930

2 0.429 seg 0.5 Mb 32500 0.219 seg 0.2 Mb 1703000

3 0.531 seg 0.6 Mb 32500 0.215 seg 0.3 Mb 2050600

4 0.657 seg 0.8 Mb 32500 0.220 seg 0.3 Mb 2025800

5 0.761 seg 1.0 Mb 32500 0.217 seg 0.4 Mb 2482770

6 0.955 seg 1.4 Mb 32500 0.217 seg 0.4 Mb 2435750

Cuadro 5. Comparación Nro. Vehículos, Tiempo Usado, Memoria Usada, Costo (VRPTW - M. Propuesto)

Modelo VRPTW Modelo Propuesto

Escenarios Nro. Vehículos

Tiempo usado

Memoria usada

Costo(S/.) Nro. Vehículos

Tiempo usado

Memoria usada

Costo(S/.)




1 3 0.315 seg. 0.5 Mb. 46.6567 3 0.215 seg 0.5 Mb 346.6347

2 3 0.216 seg 0.6 Mb. 70.4045 3 0.216 seg 0.6 Mb 370.4045

3 3 0.426 seg 0.8 Mb 75.9896 3 0.325 seg 0.9 Mb 375.9896

4 3 0.323 seg 0.9 Mb 85.8385 3 0.740 seg 1.2 Mb 385.8385

5 3 0.829 seg 1.4 Mb 104.4395 3 0.828 seg 1.4 Mb 404.4395

6 3 2.168 seg 3.0 Mb 164.1590 3 1.928 seg 1.6 Mb 464.1590

VI. CONCLUSIONES

Como apreciamos en el Cuadro 3, Los modelos matemáticos tanto de Badran como de Tattoni generan pocas variables y el tiempo para generarlas es prácticamente 0. Así mismo, el modelo básico de VRPTW con nuestro modelo propuesto tienen la misma cantidad de variables generadas, pero en tiempos un poco distintos; hay que notar que en nuestro modelo el tiempo usado en los distintos escenarios es ascendente.

En el cuadro 4, podremos apreciar la comparación entre los modelos Tattoni y Badran en factores de tiempo usado, memoria usada y costo. Se puede apreciar una constante del costo en los diferentes escenarios, lo cual nos muestra que el objetivo del modelo es optimizar principalmente la gestión de los residuos a través de las distintas fábricas. En el caso de Badran, existe una similitud en cuanto a los objetivos, pero en este modelo podemos apreciar que si existe una variación en el costo.

En el Cuadro 5 podemos apreciar la comparación en factor de número de vehículos usados, tiempo usado y la memoria usada y el costo, entre el modelo de VRPTW y nuestro modelo propuesto. En lo que respecta al costo, vemos que existe un incremento, esto es debido a que nosotros consideramos el costo fijo para utilizar un vehículo; esto ayuda a que el costo aumente. Por otro lado, el tiempo de procesamiento de ambos es casi el mismo, lo que nos permite calcular los costos de ruteo para la colecta de manera más exacta, sin aumentar en demasía el procesamiento computacional.

Al ser un problema combinatorio, podemos decir que mientras más datos tengamos, más puntos críticos o de colecta (nodos) tengamos que visitar, mayor será el tiempo de procesamiento, inclusive puede tardar años encontrar la solución más óptima. Es por ello que las heurísticas aparecen como una alternativa para encontrar una buena solución en un menor tiempo.

VII. REFERENCIAS BIBLIOGRAFICAS

Badran, M.F., & El-Haggar, S.M. (2006). Optimization of municipal solid waste management in Port-Said-Egypt, Waste Management, 26, 534–545.

Bautista, J., & Pereira, J. (2004). Ant algorithms for urban waste collection routing. Ant Colony

Optimization and Swarm Intelligence, Proceedings, 3172, 302-309. Beliën J. De Boeck L. Van Ackere J. (2010) Municipal Solid Waste Collection and Management

Problems: A Literature Review. Hogeschool-Universiteit Brussels (Brussels, Belgium) & Katholieke Universiteit Leuven (Leuven, Belgium). 46 h.

Benjamin A. (2011) Metaheuristics for the Waste Collection Vehicle Routing Problem with Time

Windows. Tesis (Doctorado en Filosofía) Londres, Inglaterra. Universidad de Brunel, Departamento de Ciencias Matemáticas. 196 h.




Comisión Ambiental Municipal de Trujillo. Plan Integral de Gestión Ambiental de Residuos Sólidos -

PIGARS. Trujillo, Perú. Servicio de Gestión Ambiental de Trujillo, 2009. 96p. Deza J, Montoya J, Narducci F (2009) Resolución del Problema de Enrutamiento de Vehículos con

Limitaciones de Capacidad Utilizando un Procedimiento Metaheurístico de Dos Fases. Revista Escuela de Ingeniería de Antioquia, 12, 1794-1237.

Garfinkel R.S. (1985), Motivation and Modeling, en: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan &

D.B. Shmoys (eds.), The Traveling Salesman Problem, John Wiley & Sons, Chichester, 307-360. Joubert J. Claasen S. (2006). A sequential insertion heuristic for the initial solution to a constrained

vehicle routing problem. Orion, 22, 105 – 116. Kim BI, Kim S, Sahoo S. (2006) Waste collection vehicle routing problem with time windows.

Computers & Operations Research, 33, 3624-3642. Martí, Rafael (2002) Procedimientos Metaheurísticos en Optimización Combinatoria. Departamento

de Estadística e Investigación Operativa. Universidad de Valencia, 60 Tattoni S. D’Avino M. Fumarola A. Schiraldi M. (2010) A multi-approach model to optimize Municipal

Solid Waste Management. An application to an Italian metropolitan area. Conference: Sustainable Development Industrial Practice, Education & Research. Bari, Italia. 14-18 Setiembre del 2010.

Tonci, Carič y Hrvoje, Gold. (2008) Vehicle Routing Problem. 1ra Ed. In-Tech, 152p. Yepes, Víctor (2008) Optimización Combinatoria [en línea] Polimedia – Universidad Politécnica de

Valencia, 17/06/2008 <https://polimedia.upv.es/catalogo/curso.asp?curso=584a7ed6-64bf-5c4a-a113-b4e3b3493521> [consulta: 26/08/ 2013]

Gendreau (2003) An Introduction to Tabu Search. En: Glover, Fred y Kochenberger, Gary (Eds.)

Handbook of Metaheuristics, Kluwer Academic Publishers, 2003, USA, pp. 37 – 54. Chun-Hua, L. Hong, Z. Jian, Z (2009) Vehicle Routing Problem with Time Windows and

Simultaneous Pickups and Deliveries. IEEE, 5.

Documents

UNIVERSIDAD NACIONAL DE TRUJILLO - … · tercer capítulo se hará un análisis del problema, el análisis del modelo matemático y el diseño de la metaheurística de Busca Tabú,