Tesis Pre-grado
Un Modelo de Programación Lineal Entera para Resolver el Problema de Ruteo de Vehículos de una Distribuidora de Productos de Consumo Masivo
Un modelo de programación lineal entera para resolver el problema de ruteo de vehículos de una distribuidora de productos de consumo masivo
Autor
Pino-Canales, Fernando
Institución
Resumen
El problema de ruteo de vehículos consiste en encontrar las rutas de costo mínimo de una flota de
vehículos, que comienzan y terminan su recorrido en el depósito sin exceder la capacidad de cada
uno de ellos, para visitar a todos los clientes una sola vez y satisfacer su demanda.
En esta memoria se proponen dos modelos de programación lineal entera para resolver el problema
de ruteo de vehículos en una distribuidora de productos de consumo masivo. Una formulación está
basada en el modelo clásico de ruteo de vehículos con eliminación de subtours y la otra formulación
se basa en flujo multicommodity. Ambos modelos tienen como objetivo minimizar la capacidad
ociosa de los vehículos de reparto, esto es, que los vehículos transporten la mayor cantidad posible
de mercadería en cada viaje.
Los modelos se validan con instancias de prueba obtenidas de la literatura para las cuales se conoce
la solución óptima. Además, con los modelos se resuelven instancias con datos reales de una
empresa que tiene su centro de distribución en la ciudad de Concepción. En ambos modelos se
consideran dos funciones objetivos que minimizan la capacidad ociosa y el costo de transporte
respectivamente. Para la obtención de los resultados se hace uso del lenguaje de programación
AMPL en conjunto con el solver de optimización CPLEX, versión 12.6.0.0. Para la validación de
los modelos se utilizaron instancias de la literatura hasta 50 clientes. FONDECYT FONDECYT