72- #1013 SOLUCIÓN DE UN PROBLEMA DE RUTEO MULTIDEPÓSITO CON FLOTA HETEROGÉNEA USANDO GENERACIÓN DE COLUMNAS
No Thumbnail Available
Date
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
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 losvehículos son del mismo tipo (flota homogénea) y todaslas rutas salen y regresan al mismo depósito. Al agregarla posibilidad de usar distintos depósitos, se da másflexibilidad a la empresa, pero el problema también setorna más complejo ya que la cantidad de posibles rutasaumenta exponencialmente. Por último, se agrega laposibilidad de usar diferentes tipos de vehículos (flotaheterogénea) haciendo el problema aún más complejo. Debido a la complejidad del problema, los métodosestándar para solucionar problemas de optimizaciónson incapaces de proporcionar buenos resultados amedida que aumentan el número de clientes, dedepósitos y el tipo de vehículos. Debido a lo anterior, esnecesario utilizar otro método para obtener buenosresultados. El método que se propone en este trabajoes generación de columnas. Los métodos de generación de columnas inician conuna solución factible a partir de la cual se soluciona unProblema Maestro Restringido. Posteriormente se usanlas variables duales del problema anteriormentedescrito (descompuesto por Dantzig-Wolfe) parabuscar nuevas rutas que permitan mejorar el valor delmismo. Una vez encontradas dichas rutas, estas seincorporan al Problema Maestro Restringido y elproceso se repite. El algoritmo termina cuando noexisten más rutas que puedan mejorar el ProblemaMaestro Restringido. El factor clave en este método esque sólo requiere un subgrupo de variables en lugar detodas ellas Finalmente se aplica el método anteriormente descritoa un problema real de ruteo de una empresa deVending de la ciudad de Medellín y se analizan losresultados a partir de un problema con 48 clientes, trestipos de vehículos y dos depósitos
Keywords
Generación de columnas, Dantzig-Wolfe, VRP