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

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.