Localización del punto óptimo de partida en el problema de ruteo vehicular con capacidad restringida (CVRP)

Location of the optimal starting point in the vehicle routing problem with restricted capacity (CVRP)

Palabras clave: algorithm, cluster, heuristics, tabú search, vehicle routing problem (en_US)
Palabras clave: algoritmo, conglomerados, heurística, metaheurísticas, tabú, ruteo de vehículos (es_ES)

Resumen (es_ES)

Contexto: Esta investigación resuelve el problema de encontrar el punto óptimo de localización de una flota de vehículos recolectores de basura y las rutas óptimas para minimizar el costo de su recolección, en 144 barrios del municipio de Dosquebradas, Risaralda (Colombia), utilizando 8 vehículos con capacidad homogénea de 25 toneladas de la empresa Serviciudad.

Métodos: Primero, se utilizó una heurística de barrido (Ospina Toro y Orrego, 2016) para encontrar un buen punto de partida para los vehículos de recolección y generar rutas iniciales de buena calidad. Posteriormente, estas rutas iniciales alimentan el algoritmo genético modificado de Chu-Beasley (Solarte, Castillo y Rodríguez, 2015) teniendo en cuenta la capacidad de carga del vehículo (Rondon et al., 2010). Finalmente, para garantizar un resultado óptimo, el mejor encontrado en la fase anterior es tratado nuevamente con una metaheurística tabú (Bodas, 2017).

Resultados: Se diseñó una nueva metodología, denominada híbrida CSGTR (Clustering, sweep, genetic, tabu routing) que permitió aprovechar las ventajas de la clusterización (Rueda et al., 2017) antes del ruteo de vehículos (Hernández, 2017), incluyendo modelos heurísticos como la técnica de barrido (Ospina Toro y Orrego, 2016) y metaheurísticos como los algoritmos de Chu-Beasley y tabú (Grajales, Hincapié y Montoya, 2017). La aplicación de la metodología CSGTR permitió reducir el tiempo y los costos de los recorridos de los camiones recolectores de basura en el municipio de Dosquebradas, Risaralda (Colombia).

Conclusiones: La metodología hibrida CSGTR para resolver el problema de ubicación de flotas de vehículos y generación de rutas de recolección se presenta como un enfoque alternativo, con mejores resultados que el enfoque previo.

Resumen (en_US)

Context: This research solves the problem of finding the optimal location point for a fleet of garbage collection vehicles, as well as their optimal routes in order to minimize the cost of garbage collection in 144 neighborhoods of the municipality of Dosquebradas, Risaralda, Colombia, using 8 vehicles with homogeneous capacity of 25 tons which belong to the company Serviciudad.

Methods: Firstly, a scanning heuristic (Ospina Toro, Toro Ocampo, & Orrego Cardozo, 2016) was used to find a good point of departure for the group of all the vehicles in order to generate good-quality initial routes. Then, these initial routes feed the modified genetic algorithm of Chu-Beasley (Solarte Martinez, Castillo Gaspar, & Rodriguez, 2015), taking into account the load capacity of the vehicles. Finally, in search of an optimal result, the best result found in the previous step is treated again with a Tabu metaheuristic (Bodas López, 2017).

Results: A new methodology was designed and called hybrid CSGTR (Clustering, sweep, genetic y tabú routing), which allows to take advantage of clustering before vehicle routing (Rueda Bayona, Elles Pérez, Sánchez Cotte, González Ariza, & Rivillas Ospina, 2017) and includs Heuristic models such as Scanning Technique and Metaheuristic models like the Chu-Beasley’s and Tabu Algorithm. The application of the CSGTR methodology allowed to reduce the time and costs of the routes of garbage trucks in the municipality of Dosquebradas, Risaralda, Colombia.

Conclusions: The hybrid methodology CSGTR, to solve the problem of location of vehicle fleets and generation of collection routes, is presented as an alternative approach with better results than the previous approach.

Descargas

La descarga de datos todavía no está disponible.

Biografía del autor/a

Guillermo Roberto Solarte, Universidad Tecnológica de Pereira

Ingeniero de Sistemas, magíster Ingeniería de Sistemas y Computación. Docente programa Ingeniería de Sistemas y Computación, docente asociado de la Universidad Tecnológica de Pereira. Pereira

José Soto Mejía, Universidad Tecnológica de Pereira

Físico matemático, magíster en Física, magíster en Investigación Operativa y Estadística. Doctor en Ciencias de la Computación de la Universidad Estadual de Campinas. Docente titular de la Universidad Tecnológica de Pereira. Pereira

Luis Eduardo Muñoz Guerrero, Universidad Tecnológica de Pereira

Ingeniero de Sistemas, magíster Ingeniería de Sistemas y Computación. Docente programa Ingeniería de Sistemas y Computación. Docente asociado de la Universidad Tecnológica de Pereira. Pereira

Referencias

(T2) Referencias

Becerra, Y.A. y Alvarado, F.E. (2017). Ventajas de la aplicación de las metaheurísticas, algoritmos genéticos y búsqueda tabú en la solución de problemas de Job Shop Scheduling. 22-44). En Congreso Internacional y Nacional de Administración Industrial 2016 (Medellín). DOI: https://doi.org/10.4067/s0718-07642011000100011

Balari, S. (2005). Desarrollo y complejidad computacional ¿dos elementos clave para comprender los orígenes del lenguaje? Ludus Vitalis, XIII(24), 181-198.

Bodas L., R. (2017). La metaheurística de búsqueda tabú aplicada al problema de enrutamiento de vehículos. Valladolid: Universidad de Valladolid. Escuela de Ingenierías Industriales. Recuperado de http://uvadoc.uva.es/handle/10324/26070. DOI: https://doi.org/10.3934/dcdsb.2018338

Chu, P. y Beasley, J. (1997). A genetic algorithm for the generalised assignment problem. Computers & Operations Research, 24(1), 17–23. Recuperado de https://www.sciencedirect.com/science/article/pii/S0305054896000329. DOI: https://doi.org/10.1016/s0305-0548(96)00032-9

Donati, A., Montemanni, R., Casagrande, N., Rizzoli, A. y Gambardella, L. (marzo de 2008.). Time dependent vehicle routing problem with a multi ant colony system. Research European Journal of Operational, 45(5), 1174–1191. Recuperado de https://www.sciencedirect.com/science/article/abs/pii/S0377221706006345#!. DOI: https://doi.org/10.1016/j.ejor.2006.06.047

Glover, F. (1987). Tabu Search Methods in Artificial Intelligence and Operations Research. Vol. 1. ORSA Artificial Intelligence. Boulder, CO: Elsevier Ltd. Center for Applied Artificial Intelligence, Graduate School of Business, University of Colorado. Recuperado de https://pdfs.semanticscholar.org/84e3/eec4f65205c4efffc8013419d25e10ed0d5e.pdf

Grajales, A., Hincapié, R. y Montoya G., O. D. (15 de Junio de 2017). Selección óptima de conductores en sistemas de distribución empleando el algoritmo búsqueda tabú. Ingeniare. Revista chilena de ingeniería, 26(2). Recuperado de https://scielo.conicyt.cl/scielo.php?script=sci_arttext&pid=S0718-33052018000200283#aff1. DOI: https://doi.org/10.4067/s0718-33052018000200283

Guasmayan G., F.A. (2014). Solución del problema de ruteo de vehículos dependientes del tiempo utilizando un algoritmo genético modificado. Scientia et Technica, 23(2), 12-34. DOI: https://doi.org/10.22395/rium.v13n25a6

Jaramillo P., J.R. (23 de julio de 2013). Algoritmo memético para resolver el problema de enrutamiento de vehículos con capacidad limitada. Revista EIA, 10(20), 13-23. Recuperado de http://www.scielo.org.co/pdf/eia/n20/n20a02.pdf. DOI: https://doi.org/10.17230/ingciencia.12.23.2

Hernández A., R.J. (2017). Propuesta de solución al problema de ruteo de vehículos en el operador logístico Opperar S.A. para el transporte y distribución de productos alimenticios secos del grupo Nutresa S.A. Bogotá: Universidad Distrital Francisco José de Caldas. Recuperado de http://repository.udistrital.edu.co/bitstream/11349/5756/1/%C3%81lvarezHern%C3%A1ndezRub%C3%A9nJes%C3%BAs2016.pdf. DOI: https://doi.org/10.33304/revinv.v09n1-2017009

Martínez O., A. y Cruz Ch., M.A. (2011). Método de agrupamiento no supervisado para el problema de ruteo vehicular con restricciones de capacidad en vehículos. En M.A. Cruz-Chávez (ed.), Experiencia en el desarrollo y uso de un software para enseñar algoritmos (pp. 148–166). México: CICos. Recuperado de https://docplayer.es/90020918-Metodo-de-agrupamiento-no-supervisado-para-el-problema-de-ruteo-vehicular-con-restricciones-de-capacidad-en-vehiculos.html. DOI: https://doi.org/10.4995/thesis/10251/1856

Ocampo, E.M., Escobar, A.H. y Gallego R., R.A. (2015). Técnicas heurísticas y metaheurísticas. Vol. 2. Pereira, Risaralda, Colombia: Universidad Tecnológica de Pereira.

Olivera, A. (2004.). Heurísticas para problemas de ruteo de vehículos. Montevideo, Uruguay: Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Montevideo. Recuperado de https://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf. DOI: https://doi.org/10.17535/crorr.2017.0031

Orrego C., J.P., Ospina T., D. y Toro O., E.M. (2013). Problema de ruteo de vehículos con capacidad limitada “CVRP” a través de la heurística de barrido y la implementación del algoritmo genético de Chu-Beasley. Scientia Et Technica, 21(3), 225-233. Recuperado de http://revistas.utp.edu.co/index.php/revistaciencia/article/view/9013. DOI: https://doi.org/10.22517/23447214.9013

Ospina T., D., Toro O., E.M. y Orrego C., J.P. (2016). Solución al Problema de Ruteo de Vehículos con Capacidad Limitada (CVRP) usando una técnica metaheurística. Scientia Et Technica, 21(3), 225-233. DOI: https://doi.org/10.22517/23447214.9013

Rondon Villareal, Delgado Quintero, Mendoza Castellanos, Quintero, & Serna Suarez. (2010). Optimización Ruteo Vehicular con Capacidad. Revistas.udistrital.edu.co, 3(4.15), 3-78.

Rueda B., J.G., Elles P., C.J., Sánchez C., E.H., González A., A.L. y Rivillas O., G.D. (2017). Identificación de patrones de variabilidad climática a partir de análisis de componentes principales, Fourier y clúster k-medias. Revista Tecnura, 20(50), 55-68. DOI: 10.14483/udistrital.jour.tecnura.2016.4. a04

Simon, S., Demaldé, J., Hernández, J. y Carnero, M. (12 de agosto de 2012). Optimización de recorridos para la recolección de infecciosos. Información Tecnológica, 23(4), 125-132. Recuperado de https://scielo.conicyt.cl/scielo.php?script=sci_abstract&pid=S0718-07642012000400014&lng=es&nrm=iso&tlng=es. DOI: https://doi.org/10.4067/s0718-07642012000400014

Solarte M., G.R., Castillo G., S.A. y Rodríguez, G. (2015). Optimización de un ruteo vehicular usando algoritmo genético simple Chu-Beasley. Revista Tecnura, 19(44), 93-108. DOI: https://doi.org/10.14483/udistrital.jour.tecnura.2015.2.a07

Toro, E.M., Ruiz, F. y Salazar, H.I. (2011). Algoritmo genético modificado Chu-Beasley a Aplicado a la identificación de errores en la estimación de estado en sistemas eléctricos. Universidad Tecnológica de Pereira.

Cómo citar
Solarte, G., Soto Mejía, J., & Muñoz Guerrero, L. (2019). Localización del punto óptimo de partida en el problema de ruteo vehicular con capacidad restringida (CVRP). Tecnura, 23(59), 27-46. https://doi.org/10.14483/22487638.13653
Publicado: 2019-01-01
Sección
Investigación