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 ingles) 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 optimas, 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 ultimo basado en la distribución de 500 granjas lecheras en el sur de Chile.