modelamiento y solución del problema de recolección de
TRANSCRIPT
1
Modelamiento y solución del problema de recolección de residuos reciclables
Daniel A. Ospina1 y David Álvarez-Martínez
Departamento de Ingeniería Industrial
Facultad de Ingeniería
Universidad de los Andes, Bogotá - Colombia
Resumen
En este documento se presenta una metodología de solución para el problema de enrutamiento de
vehículos con demanda fraccionada, inspirada en una aplicación real de recolección de residuos
reutilizables. Este trabajo se divide en dos partes: la primera desarrolla un modelo matemático para
formalizar el problema y exponer su complejidad; en la segunda, se implementa una metaheurística
Iterated Local Search (ILS), que logra resolver instancias de gran porte. El ILS utiliza una fase de
construcción tipo route-first cluster-second, la cual resuelve un TSP y su solución se particiona en
rutas que cumplan con la capacidad de cada vehículo. Posteriormente, son seleccionadas las rutas que
visiten todos los clientes con el menor costo a través de un modelo de set partitioning. El ILS utiliza
cinco operadores clásicos de la literatura. Se han desarrollado casos de prueba tanto para la
formulación como para el ILS, estos fueron generados utilizando las instancias clásicas. Además, se
utilizaron instancias reales basadas en una empresa de recolección de residuos. Los resultados
obtenidos son alcanzados en tiempos razonables, aun para las instancias de mayor tamaño. Como
trabajo futuro se propone comparar esta metodología, de forma tal que permita validar su desempeño
real.
Palabras claves: Recolección de residuos reciclables, Problema de Rutas de Vehículos, Modelación
Matemática, ILS
1Corresponding author: [email protected]
2
1. INTRODUCCIÓN
Existe una preocupación mundial por la acumulación de residuos dado que estos incrementan
exponencialmente y que representan un peligro para la salud de las personas. Por esto, la organización
para la cooperación y el desarrollo económico (OCDE) estableció la primera etapa, entre 1994 y 1995,
sobre los principios básicos de la responsabilidad extendida del producto (REP) y con los cuales
colaboran 36 países a nivel mundial; haciendo necesario el desarrollo de sistemas que permitan el
reciclaje de la mayor parte de estos residuos.
Sin embargo, según una encuesta realizada por la Universidad Andrés Bello de Chile en 2017, las
principales razones por las cuales la gente no recicla son la falta de sistemas disponibles y la falta de
conocimiento. Como ejemplo de esto, en Colombia, a pesar de que se están produciendo más de 10
millones de toneladas de residuos sólidos al año (2017), no se han desarrollado proyectos efectivos
para promover su reciclaje y así contribuir con el medio ambiente. Como consecuencia, los rellenos
sanitarios de las diferentes ciudades están llegando a su capacidad total en menos tiempo, provocando
crisis ambientales. Sin embargo, en Bogotá, ya se están implementando medidas de este tipo; en los
últimos meses, se han instalado aproximadamente 40.000 contenedores de basura especializados en las
calles, con el fin de reciclar y que la recolección de los residuos sea más fácil. (BOGOTÁ, s.f.) Con
soluciones como esta, toma mayor relevancia esta investigación, pues resulta útil realizar una
planeación de las rutas de los vehículos de recolección y el almacenamiento de los residuos durante su
transporte, con el fin de aumentar la eficiencia del sistema de recolección en las ciudades. Como una
posible solución a esta problemática, países como Suecia llegan a reutilizar y a reciclar el 99 % de sus
residuos, y en Corea disponen de una política muy estricta de tratamiento de basuras donde los puntos
con basureros tienen carteles adicionales con información al consumidor, además de una clasificación
de restos de comida, basura general, reciclables y objetos voluminosos.
Por otro lado, en Chile, se adelantan investigaciones de ingeniería que buscan diseñar sistemas de rutas
y frecuencias de recolección de residuos reciclables en puntos limpios con el fin de minimizar los
costos operacionales y establecer estrategias de recolección. Siguiendo la misma corriente de las
investigaciones en Chile, Henke, Speranza y Wäscher (2015) modelan el sistema de recolección de
basura de una ciudad de Alemania, como un problema de enrutamiento de vehículos, los cuales parten
de un único depósito a recolectar diferentes tipos de desechos en cada uno de los puntos de la ciudad,
para luego regresar al depósito. Estos residuos reciclables no pueden mezclarse en el transporte y, por
lo tanto, el vehículo dispone de una capacidad que puede ser fraccionada en distintos compartimientos.
Este problema se conoce como Multi-compartment Vehicle Routing Problem (MCVRP), la
complejidad del MCVRP en la recolección de basuras en NP-Hard, ya que es una generalización del
CVRP. Este modelamiento busca solucionar un aspecto crítico de la administración de residuos y es
aplicable a cualquier ciudad.
En este trabajo se pretende resolver el problema de enrutamiento de un sistema de recolección de
basuras, adicionando restricciones prácticas de la aplicación. Es por esto, que se considera el uso de
3
una flota homogénea con múltiples compartimientos flexibles, además de tener en cuenta múltiples
depósitos que representan los diferentes botaderos de la ciudad o puntos de tratamiento de residuos
reciclables. Por lo tanto, la versión del problema a tratar lo llamaremos como Multi-depot Multi-
compartment Vehicle Routing Problem (MDMCVRP). Se propone entonces formalizar el problema
mediante un modelo de programación lineal entero mixto y presentar una metodología de solución
aproximada mediante un algoritmo metaheuristico tipo ILS. Por consiguiente, las decisiones que este
algoritmo deberá resolver en esta nueva variante de MCVRP son ¿cuál debe ser el tour para cada uno
de los vehículos del sistema?, ¿en cuántos compartimientos se debe fraccionar la capacidad de cada
vehículo?, y ¿en qué ruta o vehículo debe ser recogido cada uno de los tipos de residuos?
La metodología de solución propuesta será validada a través del uso de las instancias clásicas del
problema MDVRP, para esto se han adaptado las instancias al incluir la demanda fraccionada de cada
cliente. También se utilizarán instancias reales de la empresa RECUPAC en Santiago de Chile, se
validarán entonces los resultados obtenidos con la operación actual del sistema. Además de esto, se
presenta una herramienta computacional en versión beta para mejorar los procesos de recolección de
residuos reciclables en Colombia.
El resto del documento tiene la siguiente estructura: en la Sección 2 se realiza una revisión exhaustiva
del estado del arte del problema de recolección de residuos. En la Sección 3 se define formalmente el
problema presentado; en la Sección 4 se presenta la metodología de solución propuesta; en la Sección
5 se valida del desempeño de la metodología propuesta. Finalmente, en la Sección 6 se presentan las
conclusiones y trabajos futuros.
2. REVISIÓN DE LITERATURA
Los principios del problema de enrutamiento comenzaron con el matemático William Rowan
Hamilton, quien se preguntó sobre la existencia de una secuencia consecutiva de arcos de un grafo
visitando cada uno de los vértices una vez y le llamó a esto el problema del Circuito Halmitoniano.
Como extensión de este surge el Problema del Agente Viajero (TSP), definido por Karl Menger en la
década de los 30, el cual se convierte en la base de todas las investigaciones del problema de
enrutamiento de vehículos (VRP) en la época moderna. Dantzig y Ramser (1959) exponen el problema
de despacho de camiones de gasolina desde una terminal hacia diferentes estaciones de servicio. El
objetivo es minimizar el recorrido total de los camiones teniendo en cuenta que la capacidad de cada
uno es limitada y que la demanda de cada una de las estaciones de servicio debe ser satisfecha a
cabalidad (problema de enrutamiento de vehículos con capacidad, CVRP). El problema es solucionado
a través de una formulación de programación lineal, sirviendo como punto de partida para todos los
problemas de enrutamiento que buscan óptimos a través de la modelación matemática.
Después, como una variante del VRP, aparece el problema de enrutamiento de vehículos con múltiples
depósitos (MDVRP). En este caso existen varios puntos de partida posibles para los vehículos, por lo
que a cada cliente se le asigna una ruta que a su vez está asignada a uno de los depósitos. De ahí, el
MDVRP tiene muchas aplicaciones en las cadenas de suministro del mundo real como la entrega de
4
comidas, productos químicos, bebidas gaseosas, entre otros; dejando en claro que la optimización de
los despachos conlleva una disminución de costos y, por lo tanto, un aumento de las ganancias en la
industria que promueven el crecimiento de la economía.
Las primeras heurísticas fueron propuestas por Wren y Holliday (1972), Gillett y Miller (1974),
Golden, Magnanti y Nguyen (1977), y Raft (1982); todas solucionando el MDVRP a través de
algoritmos del VRP. El primero presenta la construcción simultánea de varias rutas desde varios
depósitos teniendo en cuenta restricciones de número de vehículos por cada punto de partida e
introduciendo una regla de prioridad cuando varios clientes requieren el servicio. El segundo desarrolla
el algoritmo de barrido que resuelve problemas medianos y grandes de despacho de vehículos
utilizando coordenadas polares para cada una de las ubicaciones para luego, a través de un proceso
iterativo, mejorar la distancia recorrida total. Este algoritmo tiene la ventaja de que su complejidad
computacional aumenta linealmente con el número de locaciones, haciéndolo uno de los métodos más
utilizados en la academia y obteniendo mejores resultados que el método de ahorros de Gaskell. Por
otra parte, el tercer trabajo se centra en la solución de problemas grandes de enrutamiento (más de 100
puntos de demanda) con la operación y manipulación de grandes bases de datos, haciendo
modificaciones de los algoritmos de Gillett y Miller (1974) y otros más. En cuanto al trabajo de Raft
(1982), se presenta una heurística como solución a una variante del despacho de vehículos con
múltiples depósitos. Dentro de este método se divide el problema en cinco áreas de decisión: la
asignación de rutas, la asignación de depósitos, la asignación de vehículos, el periodo de entrega y el
diseño del enrutamiento. Cada una de estas decisiones se toma por separado y luego son conectadas
dentro de un proceso iterativo. El gran avance de esta investigación es la posibilidad de trabajar con
demandas estocásticas y de posponer entregas a los clientes, incluyendo así más restricciones prácticas
reales.
En paralelo a todas las metodologías antes presentadas en torno al VRP, se han desarrollado también
integraciones de este problema con otros problemas de la ingeniería como el empaquetamiento de
productos. Este problema surge por la necesidad de considerar la mercancía más allá de una restricción
volumétrica en los vehículos, dentro de cualquier sistema logístico. Con esto, aparte de cumplir con las
restricciones de peso, se busca minimizar el espacio utilizado por la mercancía, creando una
herramienta vital para mejorar las operaciones, por ejemplo, en los puertos del mundo al mejorar la
carga de contenedores (Dereli y Dash 2010). Otras aplicaciones del problema se pueden ver en los
trabajos de Lodi, Martello y Monaci (2002), Wäscher, Haußner y Schumann (2007) y Coffman y col.
(2013). Sin embargo, en la integración de este problema con el de enrutamiento, es más común hablar
del problema de entregas con compartimientos múltiples (Multi-compartment Delivery Problem,
MCDP). Esta nueva variante plantea un problema de enrutamiento clásico con vehículos con
capacidad fraccionada en compartimientos en los cuales se empacan diferentes tipos de productos,
dado que los productos no se pueden mezclar entre sí. Coelho y Laporte (2015) presentan cuatro
categorías del MCDP, teniendo en cuenta la posibilidad de dividir un compartimiento entre varios
clientes y la restricción de satisfacer la demanda del cliente en una sola entrega o varias, para luego
solucionarlos a través de programación entera mixta y un algoritmo Branch & Cut. Los resultados
5
computacionales de esta metodología, para los casos de periodos simples y múltiples de tiempo,
arrojan soluciones exactas para 50 y 20 clientes respectivamente. Ahora, como uno de los trabajos más
recientes y de mayor relevancia, Henke, Speranza y Wäscher (2015) presentan una formulación
matemática y un algoritmo de la búsqueda del vecindario variable (Variable Neighborhood Search,
VNS) como solución a un MCDP en un sistema de recolección de basura en Alemania. Sin embargo,
las condiciones en las que deben ser configurados los compartimientos de los vehículos son diferentes
a las encontradas en las aplicaciones clásicas del problema de enrutamiento de vehículos con múltiples
compartimientos (MCVRP). En primer lugar, el tamaño de cada compartimiento no es fijo y puede ser
determinado individualmente para cada vehículo o tour. En segundo lugar, el tamaño de los
compartimientos sólo puede variar discretamente. Esto quiere decir que las paredes de los
compartimientos sólo pueden ser movidas a posiciones predefinidas. Por último, el número de
compartimientos puede ser igual al número de productos o menor.
No obstante, a pesar de la amplia investigación que se ha realizado de los problemas de enrutamiento y
empaquetamiento fraccionado, son pocos los trabajos publicados integrando estos dos problemas; lo
que muestra una gran oportunidad para hacer una contribución a la mejora de las operaciones del
sistema.
3. DEFINICIÓN Y FORMULACIÓN DEL PROBLEMA
El problema de recolección de residuos considerado en este trabajo puede ser modelado como una
variante del problema clásico de enrutamiento de vehículos, donde cada cliente demanda a lo máximo
tres tipos diferentes de productos, los cuales pueden ser o no recogidos en diferentes vehículos.
Además de esto, se considera al momento de elaborar las rutas de recolección los distintos orígenes y
destinos disponibles en la ciudad, para realizar las operaciones de acopio de material reciclable
(botaderos).
En el caso de la recolección de residuos reciclables, se deben considerar los diferentes tipos de
desechos tenidos en cuenta en el proceso de reciclaje por la ciudad. Para este problema, cada camión
tiene una capacidad total y a su vez tiene tres sub-capacidades referentes a los tres tipos de productos
(vidrio, papel y plástico). Cada camión tiene la posibilidad de adecuar estos compartimientos antes de
salir del depósito dependiendo de la ruta que vaya a realizar; los camiones no están obligados a recoger
la demanda total de cada cliente, pero sí deben recoger la totalidad de la demanda de un producto, si
esta ha sido programada. Esto se debe al mecanismo de recolección del vehículo, el cual levantará y
verterá el contenedor seleccionado.
Además de lo descrito anteriormente, el problema tiene en cuenta la posibilidad de realizar las rutas
desde los diferentes botaderos disponibles en la ciudad. Debe entonces, velarse porque las rutas que
comienzan en un botadero regresen al final del día a este mismo. Cabe aclarar que las demandas de
producto a recogerse en cada punto de recolección son valores estimados gracias a los valores
históricos de la empresa que esté operando actualmente el sistema.
6
MODELO MATEMÁTICO
El problema descrito anteriormente puede ser modelado matemáticamente, usando una formulación
basada en redes. Sea 𝑣𝑒 = {0, … , 𝑑, … , 𝑑 + 𝑠} el conjunto de nodos de un grafo no direccionado que
incluye 𝑑 depósitos y 𝑠 clientes (puntos de recolección). Sea C un subconjunto de 𝑣𝑒, 𝐶 = {𝑑 +
1, … , 𝑑 + 𝑐} el conjunto de clientes a atender. Sea D un subconjunto de 𝑣𝑒, 𝐷 = {1, … , 𝑑} el conjunto
de depósitos desde donde pueden partir los vehículos. Sea 𝐾 = {1, … , 𝑘} el conjunto de vehículos. Sea
𝑀𝑘 = {1, … , 𝑚𝑘} el conjunto indexado en 𝑘 que representa los compartimientos por vehículo. Sea 𝑃 =
{0, … , 𝑝} el conjunto de productos demandados por cada cliente. Sea 𝑉 = {0, … , 𝑣} el conjunto de
vehículos del sistema.
Para la construcción del modelo, se tienen en cuenta las siguientes variables de decisión:
𝑥𝑖𝑗𝑘 variable binaria, que toma valor de 1 si va del vértice i al vértice j con el vehículo k, 0 de lo
contrario.
𝑦𝑖𝑗 variable binaria, que toma valor de 1 si se abre el depósito i, 0 de lo contrario.
𝑢𝑗𝑘𝑚variable binaria, que toma valor de 1 si el tamaño 𝑞𝑚 es asignado al vehículo k para el cliente j, 0
de lo contrario.
𝑧𝑖𝑘 variable binaria, que toma valor de 1 si el vértice i es visitado por el vehículo, 0 de lo contrario.
𝑠𝑝𝑘𝑗 variable binaria, que toma valor de 1 si se atiende la demanda del producto p del cliente j con el
vehículo k, 0 de lo contrario.
𝑓𝑖𝑗 variable binaria, que toma valor de 1 si el cliente j es asignado al depósito i, 0 de lo contrario.
𝑔𝑖𝑘 variable real, que representa el número de nodos visitados hasta el nodo i.
El modelo tiene como función objetivo la minimización de los costos asociados al problema, estos son,
el costo de ir de un cliente a otro, el costo de abrir un depósito y el costo de abrir una nueva ruta, como
se ilustran en la Ecuación 1.
𝑚𝑖𝑛 𝑍 = ∑ 𝑦𝑖𝑂𝑖
𝑖 𝜖 𝐷
+ ∑ ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗𝑘
𝑘 𝜖 𝐾𝑗 𝜖 𝑣𝑒𝑖 𝜖 𝑣𝑒
+ ∑ ∑ ∑ 𝐹𝑘 ∗ 𝑥𝑖𝑗𝑘
𝑘 𝜖 𝑉𝑗 𝜖 𝐶𝑖 𝜖 𝐷
(1)
Sujeto a las siguientes restricciones.
7
∑ ∑ 𝑠𝑝𝑗𝑘𝑑𝑝𝑗𝑗 𝜖 𝐶𝑝 𝜖 𝑃 ≤ 𝑄𝑘 ∀ 𝑘 𝜖 𝑉 (2)
∑ 𝑥𝑖𝑗𝑘𝑗 𝜖 𝑣𝑒\𝑖 − ∑ 𝑥𝑗𝑖𝑘𝑗 𝜖 𝑣𝑒\𝑖 = 0 ∀ 𝑖 𝜖 𝑣𝑒, ∀ 𝑘 𝜖 𝑉
(3)
∑ ∑ 𝑓𝑖𝑗𝑑𝑝𝑗𝑗 𝜖 𝐶𝑝 𝜖 𝑃 ≤ 𝑤𝑖𝑦𝑖 ∀ 𝑖 𝜖 𝐷 (4)
∑ ∑ 𝑥𝑖𝑗𝑘𝑗 𝜖 𝐶𝑖 𝜖 𝐷 = 1 ∀ 𝑘 𝜖 𝑉 (5)
∑ ∑ 𝑥𝑗𝑖𝑘𝑗 𝜖 𝐶𝑖 𝜖 𝐷 = 1 ∀ 𝑘 𝜖 𝑉 (6)
∑ ∑ 𝑥𝑖𝑗𝑘𝑘 𝜖 𝑉𝑖 𝜖 𝑣𝑒\𝑗 ≥ 1 ∀ 𝑗 𝜖 𝐶 (7)
∑ 𝑥𝑖𝑢𝑘𝑢 𝜖 𝐶 + ∑ 𝑥𝑢𝑗𝑘𝑢 𝜖 𝑣𝑒\𝑗 ≤ 1 + 𝑓𝑖𝑗 ∀ 𝑖 𝜖 𝐷, ∀ 𝑗 𝜖 𝐶, ∀ 𝑘 𝜖 𝑉 (8)
∑ 𝑥𝑖𝑢𝑘𝑢 𝜖 𝐶 + ∑ 𝑥𝑢𝑗𝑘𝑢 𝜖 𝑣𝑒\𝑗 ≤ 1 + 𝑧𝑗𝑘
∀ 𝑖 𝜖 𝐷, ∀ 𝑗 𝜖 𝐶, ∀ 𝑘 𝜖 𝑉
(9)
∑ 𝑠𝑝𝑗𝑘𝑘 𝜖 𝑉 = 1 ∀ 𝑗 𝜖 𝐶, ∀ 𝑝 𝜖 𝑃 (10)
𝑠𝑝𝑗𝑘 = 𝑧𝑗𝑘 ∀ 𝑗 𝜖 𝐶, ∀ 𝑝 𝜖 𝑃, ∀ 𝑘 𝜖 𝑉 (11)
∑ ∑ 𝑢𝑗𝑘𝑚𝑚 𝜖 𝑀𝑘𝑗 𝜖 𝐶 ≤ �̂�𝑘 ∀ 𝑘 𝜖 𝐾 (12)
∑ 𝑑𝑗𝑠𝑘𝑗
𝑗 𝜖 𝐶
≤ 𝑄𝑘 ∑ ∑ 𝑞𝑚𝑘𝑢𝑗𝑘𝑚
𝑗 𝜖 𝐶𝑚 𝜖 𝑀𝑘
∀ 𝑘 𝜖 𝐾 (13)
𝑔𝑖𝑘 − 𝑔𝑗𝑘 + (𝑐 − 1) ∗ 𝑥𝑖𝑗𝑘 ≤ 𝑐 − 2 ∀ 𝑖, 𝑗 𝜖 𝑣𝑒, 𝑘 𝜖 𝐾 (14)
1 ≤ 𝑔i𝑘 ≤ c − 1 ∀ 𝑖 𝜖 𝑣𝑒, 𝑘 𝜖 𝐾 (15)
𝑥𝑖𝑗𝑘, 𝑦𝑖𝑗, 𝑢𝑗𝑘𝑚, 𝑧𝑖𝑘, 𝑠𝑝𝑘𝑗, 𝑓𝑖𝑗 = {0,1} ∀ 𝑖, 𝑗 𝜖 𝑣𝑒, 𝑘 𝜖 𝐾, 𝑝 𝜖 𝑃, 𝑚 𝜖 𝑀𝑘 (16)
𝑔𝑖𝑘 ≥ 1 ∀ 𝑖 𝜖 𝑣𝑒, 𝑘 𝜖 𝐾 (17)
La Ecuación 2 garantiza que la demanda satisfecha no exceda la capacidad del vehículo. La Ecuación 3
es la restricción de continuidad de flujo. La Ecuación 4 garantiza que la demanda satisfecha por
depósito no exceda la capacidad del mismo. Las Ecuaciones 5 y 6 obligan el uso y la llegada de todos
los vehículos. La Ecuación 7 permite que un cliente pueda ser visitado por más de un vehículo. La
Ecuación 8 asigna un cliente a un depósito si existe una ruta que parta de ese depósito y visite a ese
cliente. La Ecuación 9 asigna un cliente a un vehículo si existe una ruta que recoge un producto de
este. La Ecuación 10 obliga que la recogida de un producto sólo pueda hacerse en un viaje. La
8
Ecuación 11 asigna el cliente al vehículo, si dicho vehículo recoge algún producto del cliente. La
Ecuación 12 la suma de compartimientos configurados en el vehículo debe ser menor o igual al
número de compartimientos máximos. La Ecuación 13 garantiza que la capacidad del vehículo no
puede ser excedida. Por último, las Ecuaciones 14 y 15 eliminan los subtours. Las Ecuaciones 16 y 17
son las restricciones de naturaleza de las variables.
El problema propuesto es entonces formalizado como un problema de programación lineal entero
mixto presentado en las Ecuaciones 1 – 17. En la Sección 5 se evidencia las limitantes del MIP, por
esto se propone una aproximación metaheurística que permita resolver instancias reales del problema.
4. METODOLOGÍA DE SOLUCIÓN
El algoritmo metaheurístico propuesto, está compuesto por dos fases. La primera fase, consiste en
encontrar una solución inicial de buena calidad mediante un proceso de construcción basado en route-
first cluster-second, para esto es necesario resolver un problema de TSP considerando únicamente los
clientes, particionar la solución en rutas que tienen en cuenta la demanda de cada cliente y la capacidad
de los vehículos y, por último, seleccionar las rutas y asignarlas a un depósito, a través de un modelo
de set partitioning, garantizando que todos los clientes y sus respectivas demandas sean recogidas.
Por otro lado, la segunda fase consiste en un proceso de búsqueda local, para esto se propone una
metaheurística tipo ILS, para el cual se han utilizado diferentes vecindarios de búsqueda dados por el
uso de cinco operadores clásicos de la literatura. El algoritmo selecciona entonces aleatoriamente uno
de estos en cada iteración, evalúa únicamente los vecinos factibles y realiza el movimiento de
transición hacia el mejor vecino encontrado.
A continuación, se detallan los elementos de la fase de construcción. El primer paso de esta fase es
solucionar un problema de TSP, utilizando la localización de los clientes, para esto se usó la heurística
LKH (Helsgaun, 2017), la cual obtiene soluciones eficientes junto a un buen desempeño
computacional. Esta heurística devuelve como resultado el orden de atención de los clientes.
Utilizando este orden de atención se crean las rutas, al dividir la secuencia considerando la demanda de
cada cliente y el almacenamiento dentro del vehículo compartimentado, de este proceso se obtiene
como resultado un conjunto de rutas. Este conjunto se genera realizando todas las posibles particiones
(puntos de arranque) del TSP resultante.
9
Figura 1. Ejemplo del TSP resultante para seis clientes.
En la Figura 1 se ilustra el orden resultante obtenido con la heurística LKH para una instancia de
ejemplo de seis clientes. Por otro lado, la Figura 2 ilustra las posibles particiones y rutas factibles
obtenidas dada la capacidad del vehículo de ejemplo.
a b c
Figura 2. Rutas generadas de las posibles particiones del TSP resultando de la Figura 1.
a. Rutas generadas, partiendo la evaluación de las demandas desde el nodo 1. b. Rutas generadas, partiendo la evaluación
de las demandas desde el nodo 2. c. Rutas generadas, partiendo la evaluación de las demandas desde el nodo 3.
Una vez se tienen todas las rutas factibles posibles, se deben generar las copias de estas asignadas a
cada depósito disponible. Se debe buscar entonces, el conjunto de rutas que permita la recolección de
cada uno de los productos demandados buscando minimizar el costo total recorrida por la flota de
vehículos asignada, para esto se genera un modelo de set-partitioning (Toth & Vigo, 2014).
La fase de construcción permite encontrar una solución factible inicial. En la segunda fase, se utiliza
esta solución como punto de partida del Iterated Local Search. Esta metaheurística consiste en
encontrar, en cada iteración, una solución S’ a través de la perturbación de la solución actual, para
luego ser mejorada mediante una búsqueda local. Esta solución mejorada se elige o no bajo un criterio
de aceptación, convirtiéndola así en la solución actual. Dado lo anterior, es evidente que el proceso de
perturbación es muy importante, pues si es muy pequeño, el algoritmo no puede escapar de mínimos
locales y si es muy grande el algoritmo se va a comportar como una búsqueda local con reinicio
aleatorio.
10
Como se mencionó anteriormente, el proceso de perturbación requiere de una buena definición de
operadores de transición que le permita explorar y explotar el espacio de soluciones. Para este trabajo
se definieron cinco vecindarios explicados a continuación y que se basan en la implementación
realizada por (Subramanian, 2012).
Solución Inicial Shift(1,0) Shift(2,0)
Swap(1,1) Swap(2,2) Swap(2,1)
Figura 3. Vecindarios
SHIFT (1,0). Un cliente k es transferido de su posición a otra en cualquier ruta.
SHIFT (2,0). Dos clientes adyacentes, k y l, son transferidos de su posición a otra en cualquier ruta,
este vecindario puede verse también como la transferencia de un arco de una ruta a otra.
SWAP (1,1). Es una permutación entre un cliente k que pertenece una ruta y un cliente l que pertenece
a otra.
SWAP (2,1). Es una permutación entre dos clientes k y l que pertenecen a una ruta y un cliente m que
pertenece a otra.
SWAP (2,2). Es una permutación entre dos clientes adyacentes de una y dos clientes adyacentes de
otra; o lo que es lo mismo, la permutación de un arco de una ruta y un arco de otra.
En la Figura 3, puede verse de manera gráfica el comportamiento de los diferentes vecindarios. Así
mismo, en el Algoritmo 1 puede verse la metaheurística propuesta. En esta puede ver que primero se
ejecuta una heurística LKH sobre el conjunto de clientes, dejando por fuera el conjunto de nodos
referentes a los depósitos. A continuación, utilizando cada cliente como punto de inicio, se particiona
11
la solución generada por el LKH, evaluando si los residuos (cliente) pueden o no agregarse a la ruta
que se está construyendo, según la capacidad acumulada de la misma, este procedimiento puede
observarse en las Líneas 2 a 10. El resultado de la partición permite encontrar un conjunto de
segmentos de rutas, por lo que se debe crear un modelo de set partitioning considerando, ahora sí, los
diferentes depósitos. En este caso, a cada segmento de ruta del pool se le agrega cada depósito
disponible. Resolver el modelo se realiza por medio del optimizador CPLEX ®, obteniendo entonces
una solución inicial factible del problema (Línea 11). Se realiza una búsqueda local sobre la solución
inicial a partir de los vecindarios propuestos, se tienen en cuenta entonces los ahorros obtenidos con
cada operador y nodos involucrados en dicho operador (Línea 12). Mientras se alcanza el máximo de
iteraciones, se perturba aleatoriamente teniendo en cuenta el vecindario que mayor ahorro genera a la
solución (Línea 14). Se ejecuta nuevamente una búsqueda local (Línea 15) y se acepta o no bajo el
criterio de si la solución generada es mejor que la anterior (Línea 16). Por último, a partir de la Línea
18, para cada ruta generada se vuelve a ejecutar la heurística LKH con el fin de reparar daños en las
rutas de la solución final.
Algoritmo 1. Metaheurística para el Multi-Depot Multi-Compartment Vehicle Routing Problem
Input: Depósitos, Clientes, IteracionesMáximas
Output: Incumbente 1 RutaTSP = LKH(Clientes) 2 For i=1 to Clientes 3 For j=i to Clientes 4 If RutaTSP[j].Demanda ≤ RutaActual.Capacidad 5 RutaActual.Add(RutaTSP[j]) 6 Else 7 PoolRutas.Add(RutaActual) 8 End If 9 End For 10 End For 11 Rutas = ResolverSet-Partitioning(PoolRutas, Depósitos) 12 S* = BúsquedaLocal(Rutas) 13 For k = 1 to IteracionesMáximas 14 S’ = Perturbar(S*) 15 S*’= BúsquedaLocal(S’) 16 S* = CriterioAceptación(S*’, S*) 17 End For 18 For i = 1 to S*.NumeroRutas 19 Incumbente.Add(LKH(S*[i])) 20 End For
12
5. EXPERIMENTOS COMPUTACIONALES Y ANÁLISIS DE RESULTADOS
Para probar la formulación y el algoritmo planteado, se adecuaron los conjuntos de instancias clásicas
de la literatura especializada, pues como se mencionó anteriormente, las instancias clásicas no tienen la
demanda fraccionada. Para esto, se desarrolló un algoritmo que lee la instancia tal cual como está y
fracciona la demanda. Primero, se multiplicó la capacidad del camión y la demanda de cada cliente por
mil, esto para mantener las proporciones de la instancia; segundo, se selecciona de manera aleatoria
(uniforme) un número entre cero y uno para multiplicar por el valor de la demanda y generar tres
particiones de la demanda. Por último, se reescribe la instancia en un nuevo archivo para poner a
disposición de la academia y el público en general (Ospina, 2019). En este sentido, las instancias
conservan la información original y el comportamiento de las instancias clásicas, con la característica
que se incluye en este trabajo.
En primer lugar, se probó el desempeño del MIP presentado en la Sección 3, para esto se utilizó el
optimizador Gurobi, llamado desde de Python sobre el ambiente de trabajo Spyder de Anaconda. Fue
ejecutado en un Intel Core i7con 2.2 GHz y 16 GB de RAM, ejecutado bajo un sistema operativo
Windows de 64 bits.
Los resultados obtenidos para el MIP pueden observarse en la Tabla 1. Como se había mencionado, el
problema es NP-Hard y con el MIP planteado se pueden resolver instancias de hasta máximo 15
clientes y 3 depósitos, dónde se obtiene un tiempo de ejecución de 24 segundos, que es un tiempo
aceptable. Sin embargo, para instancias más grandes que estas, el MIP no da solución incluso
dejándolo en ejecución hasta por 24 horas. Como se puede ver, el MIP presenta serias limitaciones
para resolver el problema descrito, por lo que se planteó una metaheurística que permita resolver
instancias de mayor tamaño, como los casos prácticos de la aplicación, en tiempos computacionales
que permitan responder a las solicitudes reales del operador de la recolección.
El algoritmo fue desarrollado en lenguaje C y fue ejecutado en un Intel Core i7con 2.2 GHz y 16 GB
de RAM, compilado y ejecutado bajo un sistema operativo Ubuntu de 64 bits. Cada instancia fue
solucionada una única vez y se calibró el número iteraciones máximo del ILS probando diferentes
valores, hasta llegar a un comportamiento estable del algoritmo. Por lo que se fijó en 10 iteraciones.
13
Figura 4. Rutas generadas con el ILS.
En primer lugar, se comparó el ILS con la formulación, como se ilustra en la Tabla 1. Utilizando el
mismo computador con la misma instancia (15 clientes, 3 depósitos), el resultado obtenido con el ILS,
no logra alcanzar la solución óptima (cómo se ilustra en la Figura 4), requiriendo únicamente un
tiempo de ejecución de 0,11 segundos.
Tabla 1. Comparación MIP-ILS
MIP ILS
Costo 200 204
Tiempo de
cómputo (s) 24 0,11
En segundo lugar, para validar el ILS en instancias de gran porte, se propone comparar el algoritmo
con trabajos previos que no incluyen distintos depósitos (botaderos), debido a que en la literatura no
hay valores de resultados para instancias con las características presentadas en este trabajo. Dado lo
anterior, se realizó una comparación con los trabajos de (Guantibonza, 2019) y (Tapia, 2019). El
primero de estos trabajos presenta un algoritmo constructivo basado en la filosofía de route-first
cluster-second, como el expuesto en la fase constructiva de este trabajo, desarrollado en Visual Basic.
Mientras que (Tapia, 2019) presenta una modificación del algoritmo de ahorros, desarrollada en Java.
Por otro lado, Los resultados obtenidos con el algoritmo propuesto para las diferentes instancias del
MDMCVRP se presentan en la Tabla 2, con el fin de poder comparar con trabajos futuros. Los
resultados presentados en la Tabla 2 muestran que la fase constructiva logra encontrar una solución
factible muy buena, que luego es mejorada por el ILS propuesto, tomando un tiempo total de cómputo
bastante razonable. Además, como se mencionó antes, se puede observar que la fase constructiva es la
que más tiempo aporta al tiempo total, pues se hace un gran esfuerzo por obtener una muy buena
14
solución en esta fase. Dado lo anterior, el ILS encuentra la solución mejorada en muy pocas
iteraciones, lo que supone menor esfuerzo computacional y por lo tanto menor tiempo para esta fase
del algoritmo.
El resultado de la comparación con los otros dos trabajos puede evidenciarse en la Tabla 3. En primer
lugar, está la comparación realizada con el algoritmo route-first cluster-second, el Gap presentado
tiene en cuenta la distancia total. Puede observarse entonces que, en el 75% de las instancias
comparadas los resultados obtenidos con el algoritmo propuesto en este trabajo son mejores en cuanto
a la distancia total. De igual manera, en el 78% de las instancias comparadas, el tiempo computacional
es menor con el algoritmo propuesto.
En segundo lugar, puede verse la comparación realizada con el algoritmo de ahorros. Con respecto a
ese trabajo, tan solo en el 8% de las instancias comparadas el algoritmo aquí propuesto obtiene
mejores resultados en cuanto a la distancia total que el segundo trabajo. Sin embargo, es importante
mencionar dos cosas, la primera es que el promedio de desfase en la distancia total es de 61 metros,
considerando todas las instancias comparadas; la segunda, que en el 100% de las instancias
comparadas, el algoritmo propuesto aquí, supera en tiempo computacional al otro, en promedio, este
tiempo computacional disminuye en 55 segundos. No obstante, es importante mencionar que los
algoritmos mencionados no fueron ejecutados en el mismo computador ni en el mismo lenguaje de
programación, lo que puede cambiar los resultados en cuanto a tiempos computacionales.
Por último, puede observarse que el promedio del Gap para la comparación con el algoritmo de
ahorros es muy bajo, lo que supone un buen comportamiento del algoritmo incluso en esta variación
del problema para la que no fue diseñado.
6. CONCLUSIONES Y TRABAJOS FUTUROS
El problema planteado en este trabajo muestra una contribución a la literatura en cuanto a que no se
había formalizado un problema con la característica de la demanda fraccionada y que a su vez fuera
con múltiples depósitos. La formalización como un problema de programación entero mixto no
permite resolver instancia de gran porte dada la complejidad del problema, ni siquiera en tiempos
computacionales elevados (24 horas).
15
Tabla 2. Comparación entre el modelo constructivo y el modelo ILS propuesto.
Instancia
Constructivo Mejora (ILS)
Tiempo total Costo Tiempo de
cómputo (s) Costo Tiempo de
cómputo (s)
1dimcoordChrist50.dat 762 1.2 595 0.03 1.23 1dimcoordChrist75.dat 1100 2.47 873 0.41 2.89 1dimcoordChrist100.dat 1180 3.72 936 0.36 4.08 1dimcoordGaspelle.dat 528 0.1 427 0.01 0.2 1dimcoordGaspelle2.dat 948 0.18 731 0.03 0.2 1dimcoordGaspelle3.dat 660 0.54 539 0.03 0.58 1dimcoordGaspelle4.dat 656 0.39 526 0.03 0.43 1dimcoordGaspelle5.dat 626 0.4 502 0.04 0.45 1dimcoordGaspelle6.dat 480 0.43 444 0.016 0.44 1dimcoordMin27.dat 4168 0.39 3316 0.04 0.44 1dimcoordMin134.dat 11000 30.57 8406 1.07 31.64 1dimcoordOr117.dat 15194 15.26 12413 0.67 15.93 1dimcoord20-5-1.dat 420 0.14 335 0.01 0.15 1dimcoord20-5-2.dat 342 0.2 259 0.04 0.24 1dimcoord50-5-1.dat 836 0.75 670 0.05 0.8 1dimcoord50-5-2.dat 616 1.32 479 0.06 1.38 1dimcoord50-5-2b.dat 476 1.28 363 0.02 1.3 1dimcoord50-5-2bBIS.dat 404 1.62 327 0.05 1.67 1dimcoord50-5-2BIS.dat 970 2.13 727 0.06 2.19 1dimcoord50-5-3.dat 816 1.06 636 0.07 1.13 1dimcoord50-5-3b.dat 580 1.04 452 0.07 1.12 1dimcoord100-5-1.dat 1842 5.02 1478 0.14 5.16 1dimcoord100-5-1b.dat 1138 4.85 917 0.11 4.96 1dimcoord100-5-2b.dat 626 5.29 497 0.15 5.45 1dimcoord100-5-3.dat 1430 8.67 1102 0.08 8.76 1dimcoord100-5-3b.dat 840 8.49 620 0.18 8.67 1dimcoord200-10-1.dat 1788 38.21 1406 1.78 39.99 1dimcoord200-10-1b.dat 1232 35.67 994 1.48 37.15 1dimcoord200-10-2.dat 1592 37.65 1243 0.57 38.22 1dimcoordP111112.dat 1732 7.54 1341 0.28 7.82 1dimcoordP111212.dat 1592 5.33 1260 0.57 5.91 1dimcoordP112112.dat 1282 8.38 1077 0.12 8.51 1dimcoordP112212.dat 1020 8.88 798 0.5 9.39 1dimcoordP113112.dat 1354 12.16 1096 0.13 12.3 1dimcoordP121112.dat 2340 22 1887 0.87 22.87 1dimcoordP121122.dat 2192 42.48 1748 0.89 43.38 1dimcoordP121212.dat 2686 31.9 2115 1.43 33.33 1dimcoordP121222.dat 2272 58.78 1811 1.54 60.33 1dimcoordP122112.dat 3128 37.42 2388 0.99 38.42 1dimcoordP122122.dat 1684 80.7 1337 1.76 82.47 1dimcoordP122212.dat 1944 65.65 1540 3.49 69.14 1dimcoordP122222.dat 1282 99.11 1035 1.15 100.27 1dimcoordP123112.dat 2162 44.38 1699 2.78 47.16 1dimcoordP123122.dat 1948 39.76 1574 1.12 40.89 1dimcoordP123212.dat 1952 88.38 1559 1.48 89.87 1dimcoordP123222.dat 1592 52.19 1232 1.38 53.57 1dimcoordP131212.dat 2124 15.42 1720 0.47 15.89 1dimcoordP131222.dat 1876 18.88 1458 0.93 19.81 1dimcoordP132112.dat 1446 25.11 1166 0.51 25.63 1dimcoordP132122.dat 1574 27.13 1316 0.54 27.68 1dimcoordP132212.dat 1476 32.37 1204 0.81 33.19 1dimcoordP132222.dat 876 35.55 686 0.65 36.2 1dimcoordP133112.dat 1520 27.77 1210 1.17 28.94 1dimcoordP133122.dat 1360 22.44 1078 1.14 23.59 1dimcoordP133212.dat 1804 23.4 1422 0.33 23.73 1dimcoordP133222.dat 1102 26.78 866 0.8 27.58
PROMEDIO 20.9 0.6 21.5
16
Dado lo anterior, se presenta un algoritmo de solución aproximado que, al probarse con la misma
instancia que el MIP, alcanza un valor muy cercano al óptimo en un tiempo computacional bajo. Se
probó entonces en instancias de mayor tamaño, que fueron adaptadas de instancias clásicas de la
literatura dado que no hay instancias para este problema. En estas instancias se obtuvo una solución en
tiempos computacionales bastante razonables incluso para las instancias más grandes que tienen hasta
200 clientes.
Para probar el desempeño del algoritmo propuesto, se resolvió una versión del problema con un único
depósito para comparar los resultados con dos trabajos de pregrado. En la comparación con el primero,
que presenta un algoritmo constructivo basado en la filosofía de route-first cluster-second, los
resultados obtenidos con la metaheurística propuesta superan en tiempo computacional y en función
objetivo a los alcanzados en dicho trabajo. En cuanto al segundo trabajo, que presenta una
modificación del algoritmo de ahorros, la metaheurística propuesta alcanza mejores resultados en
cuanto a tiempo computacional, pero en función objetivo se alcanzan mejores resultados en sólo 8
instancias de las 36 evaluadas.
Los resultados obtenidos en la comparación son satisfactorios teniendo en cuenta que el algoritmo fue
construido para resolver problemas más grandes y logra comportarse bien para resolver otros
problemas asociados al aquí presentado.
Como trabajo futuro se plantea la generación de instancias de tamaño real para el sistema de
recolección de basuras de la ciudad de Bogotá, es decir, construir instancias con 40.000 clientes o
puntos de recolección y probar el desempeño de la metaheurística con este tamaño de instancia. Así
mismo, se plantea mejorar la herramienta de visualización de los resultados del algoritmo, pues
actualmente permite graficar, pero no hacer cambios rápidos sobre la misma.
REFERENCIAS
[1] BOGOTÁ, A. D. (s.f.). bogota.gov.co. Obtenido de https://bogota.gov.co/mi-ciudad/habitat/como-usar-los-
nuevos-contenedores-de-aseo
[2] C. Coelho, L., & Laporte, G. (2015). Classification, Models and Exact Algorithms for Multi-Compartment
Delivery Problems. European Journal of Operational Research, 854 - 864.
[3] Dantzig, G., & Ramser, J. (1959). The Truck Dispatching Problem. Management Science, 80 - 91.
17
[4] Dereli, T., & Sena , G. (2011). Development of a decision support system for solving container loading
problems. Transport, 138 - 147.
[5] Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid algorithm for the capacitated location-
routing problem. Computers & Operations Research, 79 - 79.
[6] Escobar, J. W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014). A Granular Variable Tabu Neighborhood
Search for the capacitated location-routing problem. Transportation Research Part B, 344 - 356.
[7] Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A Tabu Search Algorithm for a Routing and
Container Loading Problem. Transportation Science, 342 - 350.
[8] Gillet, B., & Miller, L. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research,
240 - 349.
[9] Golden, B., Magnanti, T., & Nguyen, H. (1977). Implementing vehicle routing algorithms. Networks, 113 -
148.
[10] Guatibonza, S. (2019). Enfoque heurístico para el problema integrado de ruteo de vehículos y
empaquetamiento de mercancías aplicado al sistema de recolección de residuos. Bogotá.
[11] Helsgaun, K. (2017). An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling
Salesman and Vehicle Routing Problems. Technical Report.
[12] Henke, T., Speranza, M. G., & Wäscher, G. (2015). The multi-compartment vehicle routing problem with
flexible compartment sizes. European Journal of Operational Research, 730 - 743.
[13] Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European
Journal of Operational Research, 241 - 252.
[14] Ospina, D. (2019). Instancias de prueba del MDMCVRP. Obtenido de
https://www.dropbox.com/sh/p9e6n7pmql8jsiy/AAAuLHY0LJ7q8Aaom1zLJGKLa?dl=0
[15] Raft , O. (1982). A modular algorithm for an extended vehicle scheduling problem. Eur. J. Oper. Res, 67 -
76.
[16] Subramanian, A. (2012). Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.
[17] Tapia, S. (2019). Herramienta para problema de recolección de basura basado en un algoritmo de ahorros
modificado. Bogotá.
[18] Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. Society for Industrial
and Applied Mathematics.
[19] Wäscher , G., Haubner, H., & Schumann, H. (2007). An improved typology of cutting and packing
problems. European Journal of Operational Research, 1109 - 1130.
[20] Wren, A., & Holliday, A. (1972). Computer scheduling of vehicles from one or more deports to a number
of delivery points. Operational Research Quarterly, 333 - 344.
18
Tabla 3. Comparación entre el algoritmo propuesto, el algoritmo route-first cluster-second y el algoritmo de ahorros.
Instancia
CHG C&W ILS
Distancia Tiempo Gap Distancia Tiempo Gap Distancia Tiempo
coordP111112 2021 15 -4% 1877 33 4% 1944 9 coordP111122 1896 14 -6% 1700 33 5% 1789 6 coordP111212 1871 18 -
10%
1651 32 2% 1683 6 coordP111222 1998 18 -1% 1836 33 7% 1972 8 coordP112112 2186 18 -2% 2113 33 2% 2151 9 coordP112122 1799 18 -
13%
1558 32 1% 1570 10 coordP112212 999 19 -3% 937 34 3% 965 10 coordP112222 1255 18 2% 1252 32 2% 1274 22 coordP113112 1767 18 -6% 1649 33 0% 1656 12 coordP113122 1978 18 -1% 1953 33 0% 1956 11 coordP113212 1469 19 0% 1426 33 3% 1475 17 coordP113222 1544 13 -2% 1448 32 4% 1509 15 coordP121112 3328 57 0% 3188 156 4% 3322 24 coordP121122 3887 59 -3% 3587 156 5% 3766 38 coordP121212 3074 57 -3% 2862 156 4% 2989 31 coordP121222 2975 58 -5% 2708 157 4% 2815 48 coordP122112 2475 54 -3% 2338 156 3% 2398 37 coordP122122 2283 57 4% 2285 156 4% 2368 70 coordP122212 2200 60 2% 2251 156 0% 2241 66 coordP122222 2645 64 0% 2576 156 2% 2636 91 coordP123112 3308 58 -7% 3026 156 2% 3081 46 coordP123122 3286 58 -1% 3215 157 1% 3254 28 coordP123212 1951 64 -1% 1912 155 1% 1935 87 coordP123222 2600 58 -1% 2537 155 2% 2577 41 coordP131112 2782 34 0% 2712 61 2% 2778 15 coordP131122 2599 26 -6% 2269 61 8% 2451 18 coordP131212 2176 37 -9% 1914 61 4% 1985 19 coordP131222 2596 31 -2% 2467 61 3% 2531 14 coordP132112 2054 25 1% 2049 61 1% 2074 24 coordP132122 2652 38 2% 2608 60 4% 2714 21 coordP132212 1926 22 -1% 1858 61 3% 1907 31 coordP132222 3032 34 0% 2998 61 1% 3042 30 coordP133112 2632 21 -1% 2514 61 3% 2595 27 coordP133122 1680 28 0% 1660 60 1% 1680 18 coordP133212 1217 33 2% 1181 60 5% 1239 23 coordP133222 2218 27 -1% 2198 61 0% 2190 24
Total 82356
1266
78312
2992
80510
1007
Promedio -2%
3%