A Hybrid Mixed-Integer Optimization and Clustering Approach to Selective Collection Services Problem of Domestic Solid Waste

Un Enfoque Híbrido de Agrupamiento y Optimización Entera Mixta para el Problema de Servicios de Recolección Selectiva de Residuos Sólidos Domésticos

  • Johana Andrea Patiño Chirva
  • Yesica Xiomara Daza Cruz
  • Eduyn Ramiro Lopez Santana Universidad Distrital Francisco José de Caldas
Keywords: clustering, optimization model, routing, scheduling, waste collection (en_US)
Keywords: clúster, modelo de optimización, ruteo, programación de tareas, recolección de residuos (es_ES)

Abstract (en_US)

 

Context:  Waste generation is causing profound negative impacts on our natural environment. Because of that, processes related to waste collection, transportation, transformation and final disposal have increased its importance and major efficiencies are is desirable. We propose a Mixed Integer Programming model and clustering approach for waste collection and transportation process.

Method: An optimization model, inspired on Bogotá context is proposed, to maximize the amount of waste collected, considering real-life aspects of this activity in the city. For large instances in which there is a big computational cost, we proposed an alternative solution of two stages, firstly a clustering step and then a routing step. 

Results: In small instances of up to 1453 collection sites grouped in 13 blocks and 51 corners, the model result in an overall collection covering of 100%. For large instances, there are variations between the results of each clustering method. The results suggests that the sweep algorithm is better to clustering the collection sites.

Conclusions:  Our proposed model is able to find a solution the waste collection problem in Bogota case considering the vehicle capacity, maximum workday duration and the planning horizon of two days according with the collection process in Bogota. We test three clustering methods in order to group the collection sites and to reduce the complexity of the problem, and then we solve the model using a commercial solver. For the small instances, our model run very fast but in the large instances the computational time was increased. Future work will focus in the validation and search of solution methods improving the performance with the proposed model.

Abstract (es_ES)

Contexto: La generación de residuos está causando profundos y negativos impactos en nuestro ambiente. Por esto, procesos relacionados con la recolección, el transporte, la transformación  y la disposición final de residuos han ganado importancia y se propende a su eficiencia. Un modelo de programación entera mixta y de agrupación es propuesto para los procesos de recolección  y transporte de residuos.

Método: Se propone un modelo de optimización, inspirado en el contexto de Bogotá, cuyo objetivo es maximizar la cantidad de residuos recolectados teniendo en cuenta las características reales de esta actividad en la ciudad. Para instancias grandes en las que el costo computacional es muy alto, se proponen una alternativa de solución de dos etapas, clusterizar primero y rutear después. ´

Resultados: En pequeñas instancias de hasta 1453 puntos de recolección  agrupados en 13 bloques y 51 esquinas, nuestro modelo logro el cubrimiento total de la recolección. Para grandes instancias,  existen variaciones entre los resultados de cada método de agrupación.

Conclusiones: Nuestro modelo propuesto es capaz de encontrar una solución al problema de recolección de residuos en caso de Bogotá considerando la capacidad de los vehículos, la duración máxima de una jornada de trabajo y el horizonte de planificación de dos días de acuerdo con el proceso de recolección de Bogotá. Probamos tres métodos de agrupación para agrupar los sitios de recolección y para reducir la complejidad del problema, y luego se resuelve el modelo usando un paquete comercial. Para instancias pequeñas, nuestro modelo es rápido, pero en grandes instancias se aumenta el tiempo de cálculo. Los trabajos futuros se centrarán en la búsqueda y validación de métodos con el propósito de encontrar aquel que tenga un mejor desempeño con el modelo propuesto.

Downloads

Download data is not yet available.

Author Biography

Eduyn Ramiro Lopez Santana, Universidad Distrital Francisco José de Caldas

Ingeniería Industrial

Profesor Asistente

References

T. P. B. Brandão Vecchi, L. M. de Matos Jorge, M. A. da Silva Sá Ravagnani, and P. R. Paraíso, “Optimization of planning routes in solid waste collection,” Journal of Chemistry and Chemical Engineering, vol. 8, no. 6, pp. 596–601, Jun. 2014.

R. S. Xavier, A. C. Lisboa, D. A. G. Vieira, and R. R. Saldanha, “Heuristica para modelagem e minimização do consumo de combustível para rotas de coleta de lixo,” Bento Gonçalves, 2010, p. 12.

B.-I. Kim, S. Kim, and S. Sahoo, “Waste collection vehicle routing problem with time windows,” Computers & Operations Research, vol. 33, no. 12, pp. 3624–3642, Dec. 2006.

T. Y. Afonso LLorente, “Optimización de rutas de recogida de residuos en zonas mixtas urbana-rurales y orografía singular,” Trabajo de Fin de Grado, Universidad de la laguna, La Laguna, 2014.

R. K. Pati, P. Vrat, and P. Kumar, “A goal programming model for paper recycling system,” Omega, vol. 36, no. 3, pp. 405–417, Jun. 2008.

F. Beijoco, V. Semiao, and Z. Zsidgraiová, “Optimization of a municipal solid waste collection and transportation system,” Lisboa, Portugal, 2011.

S. Simón, J. Demaldé, J. Hernández, and M. Carnero, “Optimización de Recorridos para la Recolección de Residuos Infeccio-sos,” Información tecnológica, vol. 23, no. 4, pp. 125–132, 2012.

A. Méndez, S. Simón, D. Palumbo, E. Chiachera, and M. Carnero, “Dos Enfoques para la Solución del Problema de Ruteo De Vehículos (CVRP): Aplicación a un Caso Real de Recolección de Residuos,” Mecánica Computacional, vol. XXIX, pp. 9367–9377, Nov. 2010.

Y. T. Chen, F. T. S. Chan, S. H. Chung, and B. Niu, “Closed-Loop Supply Chain Network Optimization For Hong Kong Cartridge Recycling Industry,” Hong Kong Polytechnic University, Department of Industrial and Systems Engineering, Hong Kong, 2013.

D. Aksen, O. Kaya, F. S. Salman, and Y. Akça, “Selective and periodic inventory routing problem for waste vegetable oil collection,” Optim Lett, vol. 6, no. 6, pp. 1063–1080, Jan. 2012.

J. Beliën, L. De Boeck, and J. Van Ackere, “Municipal Solid Waste Collection and Management Problems: A Literature Re-view,” Transportation Science, vol. 48, no. 1, pp. 78–102, Nov. 2012.

K. Buhrkal, A. Larsen, and S. Ropke, “The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context,” Procedia - Social and Behavioral Sciences, vol. 39, pp. 241–254, 2012.

T. Bianchi-Aguiar, M. A. Carravilla, and J. F. Oliveira, “Vehicle routing for mixed solid waste collection - comparing alterna-tive hierarchical formulations,” Strathprints Institutional Repository, p. 137, 2011.

R. J. A. Fortunato, “Problema de determinação de circuitos de recolha de resíduos sólidos urbanos da Câmara Municipal de Oeiras,” Maestria, Universidade de Lisboa. Instituto Superior de Economia e Gestão., Lisboa, Portugal, 2014.

L. Bardales, “Heurística para la colecta de residuos domiciliarios en la ciudad de Trujillo basado en el ruteo de vehículos con ventana de tiempo,” Universidad Nacional de Trujillo, Trujillo, Perú, Informe de Trabajo de Graduación 3, Dec. 2013.

A. M. Benjamin and J. E. Beasley, “Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities,” Computers & Operations Research, vol. 37, no. 12, pp. 2270–2280, Dec. 2010.

I. Markov, S. Varone, and M. Bierlaire, “Vehicle routing for a complex waste collection problem,” presented at the 14th Swiss Transport Research Conference (STRC), 2014.

E. A. V. Toso and D. Alem, “Effective location models for sorting recyclables in public management,” European Journal of Operational Research, vol. 234, no. 3, pp. 839–860, May 2014.

S. Fooladi, H. Fazlollahtabar, and I. Mahdavi, “Waste Collection Vehicle Routing Problem Considering Similarity Pattern of Trashcan,” International Journal of Applied Operational Research - An Open Access Journal, vol. 3, no. 3, pp. 0–0, Jun. 2013.

F. Samanlioglu, “A multi-objective mathematical model for the industrial hazardous waste location-routing problem,” Euro-pean Journal of Operational Research, vol. 226, no. 2, pp. 332–340, Apr. 2013.

C. S. Fatih Rahim, “A location-routing problem in glass recycling,” Annals of Operations Research, vol. 223, no. 1, pp. 329–353, 2014.

E. D. Antmann, X. Shi, N. Celik, and Y. Dai, “Continuous-discrete simulation-based decision making framework for solid waste management and recycling programs,” Computers & Industrial Engineering, vol. 65, no. 3, pp. 438–454, Jul. 2013.

L. B. R. Medina, E. C. G. L. Rotta, and J. A. O. Castro, “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución,” Ingeniería, vol. 16, no. 2, pp. 35–55, Dec. 2011.

S. Pirkwieser and G. R. Raidl, “A column generation approach for the periodic vehicle routing problem with time windows,” in International network optimization conference, Pisa, Italia, 2009, vol. 2009.

F. Baniel, “Prise en compte d’objectifs de stabilité pour l’organisation de collectes de déchets,” Doctorat, Université de Toulouse, 2009.

R. A. J. Pirabán, “Métodos Aproximados para la Solución del Problema de Enrutamiento de Vehículos (Dic 2008).” Univer-sidad Nacional de Colombia, Dec-2018.

Y. X. Daza Cruz, J. A. Patiño Chirva, and E. R. López-Santana, “A mixed integer optimization model to design a selective collection routing problem for domestic solid waste,” in 2015 Workshop on Engineering Applications - International Con-gress on Engineering (WEA), 2015, pp. 1–5.

JICA and UAESP, “Proyecto de Estudio del Plan Maestro para el manejo Integral de Residuos sólidos en Bogotá, D.C.,” Uni-dad Administrativa Especial de Servicios Públicos, Bogotá, Colombia, 3, Nov. 2013.

Corte Constitucional, Auto 275 de 2011. 2011, p. 190.

UAESP, “Esquema de Metas a Cumplir para la Inclusión de la Población Recicladora en la gestión pública de los residuos sólidos en la ciudad de Bogotá D.C.,” Secretaría del Hábitat, Bogotá, Colombia, 2011.

K. Shin and S. Han, “A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem,” Computing and Informatics, vol. 30, no. 4, pp. 721–732, Jan. 2012.

E. R. López-Santana and J. de J. Romero Carvajal, “A hybrid column generation and clustering approach to the school bus routing problem with time windows,” Ingeniería, vol. 20, no. 1, pp. 111–127, Mar. 2015.

A. Olivera, “Heurísticas para Problemas de Ruteo de vehículos,” Universidad de la República de Montevideo, Uruguay, Reporte técnico serie 04 - 08, Aug. 2004.

S. Ropke, “Heuristic and exact algorithms for vehicle routing problems,” Doctorate, University of Copenhagen, Copenhagen, 2005.

How to Cite
Patiño Chirva, J., Daza Cruz, Y., & Lopez Santana, E. (2016). A Hybrid Mixed-Integer Optimization and Clustering Approach to Selective Collection Services Problem of Domestic Solid Waste. Ingeniería, 21(2), 235-247. https://doi.org/10.14483/udistrital.jour.reving.2016.2.a09
Published: 2016-05-26
Section
Special Section: Best Extended Articles - WEA 2015