ACERCAMIENTOS BASADOS EN BÚSQUEDA LOCAL PARA EL PROBLEMA DE RECOLECCIÓN DE LECHE CON MEZCLA

Abstract

Esta memoria aborda el problema del enrutamiento de vehículos para la recolección de leche considerando la posibilidad de mezcla tanto en ruta como en planta. Esta es una variante del problema de enrutamiento de vehículos (VRP por sus siglas en inglés) que modela las rutas que debe seguir una flota de camiones recolectores de leche, desde un conjunto de granjas productoras hacia una planta de procesamiento, teniendo en cuenta que en cada granja se produce leche de distinta calidad y precio. La mezcla de leche durante el transporte permite generar rutas con un menor costo, pero con una disminución del beneficio por parte de la planta. Por su parte, el beneficio aumenta en base a la calidad de cada tipo de leche. El objetivo de este problema es encontrar un conjunto de rutas óptimas, una para cada camión, que permita la recolección de leche de todos los productores a un costo mínimo, satisfaciendo las cuotas por cada tipo de leche que impone la planta, sin sobrepasar la capacidad de cada camión. Para resolver este problema, se plantea un modelo de programación entera mixta y dos técnicas de búsqueda local. Un acercamiento basado en hill-climbing y uno basado en iterated local search. Los acercamientos son evaluados utilizando cuatro conjuntos de instancias. El último basado en la distribución de 500 granjas lecheras en el sur de Chile.

This work addresses the problem of routing vehicles for milk collection considering the possibility of mixing both on the road and in the plant. This is a variant of the vehicle routing problem (VRP) that models the routes that a fleet of milk collection trucks must follow, from a set of producing farms to a processing plant, taking into account that in Each farm produces milk of different quality and price. The mixing of milk during transport allows routes to be generated with a lower cost, but with a decrease in the benefit of the plant. For its part, the benefit increases based on the quality of each type of milk. The objective of this problem is to find a set of optimal routes, one for each truck, which allows the collection of milk from all producers at a minimum cost, satisfying the quotas for each type of milk imposed by the plant, without exceeding the capacity of each truck. To solve this problem, a mixed integer programming model and two local search techniques are proposed. An approach based on hill-climbing and one based on iterated local search. The approaches are evaluated using four sets of instances. The latter based on the distribution of 500 dairy farms in southern Chile.