72- #1013 SOLUCIÓN DE UN PROBLEMA DE RUTEO MULTIDEPÓSITO CON FLOTA HETEROGÉNEA USANDO GENERACIÓN DE COLUMNAS

Abstract

Este trabajo se enfoca en tres tipos de problemas
diferentes relacionados con el diseño de las rutas de
vehículos. El primero es aquél en el cual todos los
vehículos son del mismo tipo (flota homogénea) y todas
las rutas salen y regresan al mismo depósito. Al agregar
la posibilidad de usar distintos depósitos, se da más
flexibilidad a la empresa, pero el problema también se
torna más complejo ya que la cantidad de posibles rutas
aumenta exponencialmente. Por último, se agrega la
posibilidad de usar diferentes tipos de vehículos (flota
heterogénea) haciendo el problema aún más complejo.
Debido a la complejidad del problema, los métodos
estándar para solucionar problemas de optimización
son incapaces de proporcionar buenos resultados a
medida que aumentan el número de clientes, de
depósitos y el tipo de vehículos. Debido a lo anterior, es
necesario utilizar otro método para obtener buenos
resultados. El método que se propone en este trabajo
es generación de columnas.
Los métodos de generación de columnas inician con
una solución factible a partir de la cual se soluciona un
Problema Maestro Restringido. Posteriormente se usan
las variables duales del problema anteriormente
descrito (descompuesto por Dantzig-Wolfe) para
buscar nuevas rutas que permitan mejorar el valor del
mismo. Una vez encontradas dichas rutas, estas se
incorporan al Problema Maestro Restringido y el
proceso se repite. El algoritmo termina cuando no
existen más rutas que puedan mejorar el Problema
Maestro Restringido. El factor clave en este método es
que sólo requiere un subgrupo de variables en lugar de
todas ellas
Finalmente se aplica el método anteriormente descrito
a un problema real de ruteo de una empresa de
Vending de la ciudad de Medellín y se analizan los
resultados a partir de un problema con 48 clientes, tres
tipos de vehículos y dos depósitos