Entendemos por residuo cualquier producto en estado sólido, líquido o gaseoso que carece de valor para quien lo origina y que es depositado (deseable) en lugares específicos para su posterior reco-gida, tratamiento y reciclado.
Residuos Sólidos Urbanos son los residuos sólidos generados por la actividad doméstica y comer-cial, principalmente en los núcleos urbanos.
Residuos Sólidos Urbanos orgánicos son los residuos sólidos generados en las poblaciones que por su naturaleza es necesario su recogida con la mayor frecuencia posible.
La modelización de los sistemas de recogida se empezó a estudiar en los años setenta, desde el punto de vista de programación lineal y metaheurístico.
El problema que se plantea en este trabajo es la optimización en la recogida de residuos sólidos, si bien es aplicable a cualquier tipo: orgánicos, papel/cartón, envases, vidrio, etc., nos vamos a limitar a los orgánicos que es el tipo, que por la frecuencia de su recogida, provoca mayor complejidad.
En los planteamientos de recogida de residuos en grandes poblaciones, los residuos son deposi-tados en contenedores que se encuentran en diferentes puntos de las calles. El problema que lo estudia puede partir del llamado Capacited Arc Routing Problem (CARP), en el que se consideran arcos (de valor diferente en cada sentido) las calles y nodos, los cruces de estas .
En este caso, los modelos para resolver el problema, que encuentran grandes dificultades para ser resuelto de forma exacta, se plantean con estrategias empíricas. La responsabilidad para optimizar esta recogida de residuos cae de lleno en los propios municipios.
Sin embargo, cuando planteamos la recogida en municipios más pequeños, normalmente en entor-nos rurales, este servicio está tendiendo a mancomunarse, que sería el primer paso para una opti-mización. En estos casos el problema podría partir del llamado Capacited Vehicle Routing Problem (CVRP), donde los núcleos de población los consideramos nodos y estos se unen por las vías de comunicación, que las consideramos arcos que, por lo general, se pueden recorrer en ambos sen-tidos, aunque no tienen por qué tener el mismo coste. En la resolución de este problema se em-plean métodos heurísticos, especialmente si se consideran ventanas de tiempo, pero también pueden ser válidos los métodos exactos, como será nuestro caso.
No hay que olvidar que este tipo de problema está incluido en la clase NP-HARD, es decir, dificultad no polinómica y por tanto el esfuerzo para resolverlo crece de forma exponencial al crecer su tama-ño que , en nuestro caso, será el número de poblaciones. Afortunadamente, este servicio suele estar compartimentado en número de poblaciones no muy numeroso y, en nuestro caso, este nú-mero es inferior a veinte en cualquiera de los planteamientos.
Vamos a plantear dos enfoques principales y algunas de sus variantes. El TSP o problema del viajero que es el caso más sencillo de plantear aunque no por eso deje de ser muy compleja su resolución y el VRP o problema de rutas de vehículos con muchas variantes que se adaptan a diferentes casuísticas.
En este problema disponemos de un solo vehículo y una única estación de donde en un solo viaje debe visitar todas las poblaciones. No existe demanda de cada población. Una variante es que tenga que regresar al mismo punto desde donde partió.
Se trata de minimizar el coste total:
Donde cij es el coste de recorrer el tramo de i a j, xij, una variable binaria que nos indica si se recorre o no dicho tramo y n el número de poblaciones. Estaría sujeto a las siguientes restricciones
o De cada nodo parte uno y solo un arco:
o A cada nodo llega uno y solo un arco:
o Y evitando la formación de sub-ciclos:
En este caso disponemos de varios vehículos que deben visitar varias poblaciones y varias estacio-nes de donde parten y terminan los recorridos. Si consideramos la capacidad (C) de los vehículos (m), que partiendo y volviendo de una única estación deben distribuir o recoger (nuestro caso) una demanda de mercancía (d) entonces estamos en un caso particular llamado Capacited Vehicle Routing Problem (CVRP). La función a minimizar sigue siendo el coste del recorrido y este coste se puede interpretar como tiempo, distancia, coste económico, etc.
Cada población tiene asociada una determinada demanda (d) que debe ser satisfecha por la flota de vehículos. En el sentido más simplista del problema, los vehículos empiezan y terminan su recorrido en un mismo punto con capacidad ilimitada, no obstante, los vehículos tienen capacidades limitadas y pueden ser diferentes así como un coste fijo relacionado con su disponibilidad, de manera que se prime el maximizar cada vehículo al total de su capacidad frente al uso de un número mayor de vehículos.
La formulación del problema, según Toth y Vigo [5] sería:
Minimizar
Siendo n el número de poblaciones y m el número de vehículos.
Sujeto a las siguientes restricciones:
o No pueden salir más vehículos de los que hay:
o El número de vehículos que salen del punto 1 es el mismo que el número que vuelven:
o Tenemos que respetar la capacidad máxima y evitar subciclos:
Siendo ui y uj variables enteras auxiliares y Q la demanda total.
El VRP ha dado lugar a multitud de variantes. Vamos a ver algunas de ellas. Gómez Cámara nos recoge en [2] las más conocidas.
MDVRP : Una variante del VRP (Multi Depot Vehicle Routing Problem) que se diferencia en que exis-te varias estaciones de donde parten y vuelven los vehículos. Una primera formulación de esta va-riante la presenta en 1985 Kulkarni y Bhave [6]
Variantes del MDVRP serían:
- Flotas fijas asociadas a cada estación: Caso muy frecuente y que en nuestro planteamiento lo tenemos continuamente presente en el enfoque aproximado. Los vehículos están previa-mente fijados
- Flotas fijas que parten de una estación y terminan en otra. Caso algo más complicado pero todavía insuficiente para nuestro planteamiento. La restricción de que vuelve el mismo número de vehículos que sale ya no se puede aplicar.
PVRP (Periodic Vehicle Routing Problem): Otra variante al VRP estándar. En este caso existe un hori-zonte temporal de T días y los vehículos pueden visitar la población en cualquier día de este perio-do. Uno de los objetivos de su resolución es determinar la planificación incluyendo el día de la visita. Los primeros trabajos de esta variante lo publica en 1979 Russell e Igo [7]
SDVRP (Split Delivery Vehicle Routing Problem): Se diferencia del estándar en que en este caso en-tran en juego varios vehículos. Fue abordado inicialmente por Dror y Trudeau en 1989 [8] y en 1990 [9], proponiendo un algoritmo para su resolución basado en una búsqueda local. En 1994 proponen un nuevo mocdelo basado en programación lineal [10].
SDP (Skip Delivery Problem): Es realmente un caso particular del SDVRP en el que la capacidad de los vehículos es pequeña y la carga solo puede dividirse entre dos poblaciones. Archetti lo resuelve en tiempo polinomial en [11].
SVRP (Stochastic Vehicle Routing Problem ): Es el VRP con variables aleatorias. Los componentes del problema se comportan según una determinada función probabilidad que normalmente se desco-noce. Los primeros trabajos se publican en 1969 por Tillman [12].
VRPPD (Vehicle Routing Problem with Pick-up and Delivering): En este caso las poblaciones pueden recibir unas mercancías o entregar otras. Los primeros trabajos se atribuyen a Wilson et al en 1971 [13]. Se proponen procedimientos exactos por Kohl et al.[14] y por Du Merle el al. [15].
VRPTW (Vehicle Routing Problem with Time Windows): Cada población tiene asociada, además de una capacidad, una ventana temporal en la que solo está permitido la entrega o la recogida. Existe una variante en la que se permite la violación de la ventana asumiendo un coste determinado. Esta variante se empieza a estudiar en 1967 por Pullen y Webb [16]. Trabajos de Kolen et al.[17] y Desrochers [18] fueron el origen de algoritmos exactos basados en técnicas de Branch and Cut.
Existen tres familias: métodos exactos, heurísticos y metaheurísticos
Solo deberíamos utilizarlos en problemas con pocos puntos. Al ser programación entera mixta se utiliza el método Branch and Bound. Podemos encontrar información en los trabajos de Laporte u Norbert [19] y Laporte [20]. En nuestro estudio no parece que haya problemas, ya que el caso ma-yor no supera los veinte puntos.
Se agruparían en algoritmos constructivos, como por ejemplo el algoritmo de los ahorros de Clarke y Wright [21], algoritmos por fases, como por ejemplo el heurístico de barrido [22] o el algoritmo de Pétalo propuesto por Balinski y Quandt [23] que es una generalización del anterior y algoritmos de inserción, que es un caso particular de los algoritmos constructivos como por ejemplo el de inser-ción secuencial de Mole y Jameson [24] o el procedimiento de Búsqueda Local como el operador λ-Intercambio desarrollado por LIn [25].
Se agrupan en tres categorías: búsqueda tabú, como el algoritmo de Osman [26], algoritmos basa-dos en poblaciones, como el procedimiento de memoria adaptativa desarrollado por Rochat y Taillart [27] y algoritmos basados en mecanismos de aprendizaje, como las redes neuronales y colonias de hormigas utilizados por Ghaziri [28] y Scumann y Retzko [29] para la resolución del VRP.
Laporte [30] menciona que quizá los algoritmos de hormigas como D-ants de Reimann [31] sea uno de los mejores y más prometedores a la hora de aplicarlos al VRP.
El problema permite varios niveles de estudio en función del objetivo a conseguir.
Nivel Estratégico. En este nivel estudiaríamos el número, tipo y ubicación de los Centros de Trata-miento y de las Estaciones de Transferencia. En este caso intervendrían todos los núcleos de pobla-ción, que estaría cerca de la centena y pensamos que los métodos metaheurísticos serían lo más apropiados.
Nivel Táctico. En este nivel partiríamos de las ubicaciones de los Centros de Tratamiento y de las Estaciones de Transferencia y nos centraríamos en definir las Bases de Vehículos, su ubicación, tipo y composición aproximada, así como en relacionar las poblaciones con las Bases y estas con las Es-taciones. Este nivel se podía abordar con métodos metaheurísticos y exactos ya que en el estudio no tendrían que entrar todas las poblaciones de una vez, sino que podríamos filtrar y descartar aquellas que por su lejanía no sería probable su asignación a una Base o Estación determinada.
Nivel operativo. Es el nivel más bajo. Nos quedaría definir los vehículos y optimizar los recorridos que han de realizar estos para optimizar una función de coste u objetivo así como los recorridos dentro de las poblaciones. En este nivel el problema se subdivide en varios problemas similares y menores, en los que intervienen un número relativamente pequeño de puntos (poblaciones, Esta-ciones y Bases). Este nivel es perfectamente asumible con un método exacto para tratar los reco-rridos entre poblaciones y un método metaheurístico para los recorridos internos en las grandes poblaciones.
Nuestro estudio lo vamos a centrar en el Nivel Operativo y vamos a utilizar un modelo de progra-mación lineal entera-mixta basado en técnicas de Branch and Bound .
Capítulo 2: Especificación del problema
Capítulo 3: Modelo MILP básico
Capítulo 4: Refinado del modelo básico
Capítulo 6: Conclusiones y trabajos futuros