UN ENFOQUE DE ALGORITMO GENÉTICO APLICADO A UN PROBLEMA DE RECOLECCIÓN DE LECHE EN CHILE

Abstract

En este artículo se trata un problema real de recolección de leche en el sur de Chile, donde se trabaja con una empresa procesadora de leche la cual requiere recolectar leche parar poder elaborar sus productos, dicha empresa posee una flota heterogenia de camiones destinados para la recaudación de la leche. La cantidad total de leche diaria a recolectar es designada por la empresa procesadora, recolectar una mayor cantidad a la designada genera un costo sobre demanda. El objetivo de este trabajo es encontrar una solución óptima, es decir, tratar de encontrar las rutas más óptimas para que los camiones realicen la recolección, minimizando el costo total reduciendo la cantidad de kilómetros recorridos por los vehículos y recolectando la menor cantidad posible de leche sobre el mínimo diario. Con este propósito se busca resolver el problema a través de un algoritmo genético, dicho algoritmo fue implementado con distintas herramientas (distintos armados iniciales, búsqueda local y distintos métodos de selección en el cruzamiento), las cuales fueron probadas en distintas configuraciones buscando cual resulta más efectiva para resolver este problema. Todos los experimentos fueron probados en casos del mundo real. Se compararon los rendimientos de todas las configuraciones probadas, en donde se obtuvieron soluciones de buena calidad en la gran mayoría de los casos, para instancias pequeñas el algoritmo converge rápidamente a una única solución, mientras que en instancias grandes las configuraciones mostraron un margen mayor de soluciones, es en estos casos que se puede requerir otros enfoques o rediseños para obtener mejores resultados.

This article deals with a A prize collecting problem applied to a real milk collection problem in Chile, we work with a milk processing company which requires milk to be collected in order to be able to produce its products, said company has a heterogeneous fleet of trucks destined for collection of milk. The total amount of daily milk to be collected is designated by the processing company, collecting a larger amount of the designated couta generates a cost on demand. The goal of this work is to find an optimal solution, that is, to try to find the most optimal routes for the trucks to carry out the collection, minimizing the total cost by reducing the amount of kilometers traveled by the vehicles and collecting as little milk as possible over the daily minimum. For this purpose, the problem is sought through a genetic algorithm, said algorithm was implemented with different tools (different initial assemblies, local search and different selection methods at the crossing), which were tested in different configurations looking for which is more efficient. All experiments were tested in real world cases. The yields of all the tested configurations were compared, where good quality solutions were obtained in the vast majority of cases, for small instances the algorithm quickly converges to a single solution, while in large instances the configurations showed a greater margin of solutions, it is in these cases that other approaches or redesigns may be required to obtain better results.