A Comparative Analysis of Heuristics Applied to Collecting Used Lubricant Oils Generated in the City of Pereira, Colombia

Authors: Diana Fajardo, Sebastián Ortiz, Oscar Herrera, Angélica Santis

Abstract:

Currently, in Colombia is arising a problem related to collecting used lubricant oils which are generated by the increment of the vehicle fleet. This situation does not allow a proper disposal of this type of waste, which in turn results in a negative impact on the environment. Therefore, through the comparative analysis of various heuristics, the best solution to the VRP (Vehicle Routing Problem) was selected by comparing costs and times for the collection of used lubricant oils in the city of Pereira, Colombia; since there is no presence of management companies engaged in the direct administration of the collection of this pollutant. To achieve this aim, six proposals of through methods of solution of two phases were discussed. First, the assignment of the group of generator points of the residue was made (previously identified). Proposals one and four of through methods are based on the closeness of points. The proposals two and five are using the scanning method and the proposals three and six are considering the restriction of the capacity of collection vehicle. Subsequently, the routes were developed - in the first three proposals by the Clarke and Wright's savings algorithm and in the following proposals by the Traveling Salesman optimization mathematical model. After applying techniques, a comparative analysis of the results was performed and it was determined which of the proposals presented the most optimal values in terms of the distance, cost and travel time.

Keywords: Heuristics, optimization model, savings algorithm used vehicular oil, VRP.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1127840

References:

[1] F. Lacruz, «La empresa ambientalmente responsable. Una visión de futuro» Revista Economía Universidad de Los Andes de Venezuela, nº 21, pp. 39-58, 2005.
[2] E. Bermeo y J. Calderón, «Diseño de un modelo de optimización de rutas de transporte» El Hombre y la Máquina, pp. 52-67, 2009.
[3] W. Barajas, «Desarrollo de un algoritmo heurístico para establecer las rutas de transporte escolar de la Secretaría de Educación de Bogotá (tesis de maestría)» Universidad Nacional de Colombia, 2009.
[4] J. Quintero, «Propuesta metodológica para la recolección de leche en Colombia, caso de estudio: Provincia de Sugamuxi (tesis de maestría)» Universidad Nacional de Colombia, 2013.
[5] J. Castañeda y J. Cardona, «Implementación del método del ahorro para resolver el VRP aplicado al diseño de una red de logística inversa para la recolección de aceite vehicular usado generado en los puntos de acopio ubicados en Pereira» Universidad Tecnológica de Pereira, 2014.
[6] L. Rocha, E. González y J. Orjuela, «Una revisión del estado del arte del problema de ruteo de vehículos: Evolución histórica y métodos de solución» Revista Ingeniería Universidad Distrital, vol. 16, nº 2, pp. 35-55, 2011.
[7] Wan-Yu Liu, Chun-Cheng Lin, Ching-Ren Chiu, You-Song Tsao y Qunwei Wang, «Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths» Sustainability, pp. 4658-4684, 2014.
[8] Á. Jaque, «Universidad Nacional de Colombia» diciembre 2008. (En línea). Available: https://andresjaquep.files.wordpress.com/2008/12/estado-del-arte-vrp1.pdf. (Último acceso: 10 octubre 2015).
[9] J. Ong y Suprayogi, «Vehicle Routing Problem with Backhaul, Multiple Trips and Time Window» Jurnal Teknik Industri, vol. 13, nº 1, pp. 1-10, 2011.
[10] Nurfahizul Ifwah, Shaiful, Shamsunarnie, Zainuddin y Fuad, «Genetic Algorithm for Vehicle Routing Problem with Backhauls» Journal of Science and Technology, vol. 4, nº 1, pp. 9-15, 2012.
[11] A. Olivera, «Heurísticas para Problemas de Ruteo de Vehículos» Montevideo, Uruguay, 2004.
[12] J. Fuentes, M. Parra, H. Gutiérrez, «Método heurístico para el problema de ruteo de vehículos aplicado a la empresa distribuidora Representaciones Continental» Gestión & Sociedad, 7(1), pp. 171-186, 2014.
[13] J. Daza, J. Montoya y F. Narducci, «Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases» Rev.EIA.Esc.Ing.Antioquia (En línea), nº12, pp.23-38, 2009.
[14] G. Clarke y J. W. Wright, «Scheduling of Vehicles from a Central Depot to a Number of» Operations Research, vol. 12, pp. 568-581, 1964.
[15] R. H. Mole y S. R. Jameson, «A sequential route-building algorithm employing a generalized savings» Operational Research Quarterly, nº 27, p. 503–511, 1976.
[16] M. L. Fisher y R. Jaikumar, «A generalized assignment heuristic for the vehicle routing problem» Networks, nº 11, pp. 109-124, 1981.
[17] H. Taha, Investigación de operaciones, Novena ed., México: Pearson Educación, 2012.
[18] B. Reed, G. McMahon, R. Shaw y K. Chatterton, «Disaster-info» mayo 2009. (En línea). Available: http://www.disaster-info.net/Agua/pdf/12-CamionesCisterna.pdf. (Último acceso: 11 mayo 2016).
[19] Miller, Tucker y Zemlin, «Integer Programming Formulation of Traveling Salesman Problems» Journal of the ACM, vol. 7, pp. 326-329, 1960.