Vol. 2 No. 1 (2020): Memorias Institucionales UIS
III congreso Colombiano de Investigación de Operaciones

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

Alejandro Arenas Vasco
Universidad de Medellín, Colombia,
Elena Fernández Aréizaga
Universitat Politecnica de Catalunya, España,
Jessica Rodríguez Pereira
Universitat Politecnica de Catalunya, España,

Published 2019-01-01

Keywords

  • Generación de columnas,
  • Dantzig-Wolfe,
  • VRP

How to Cite

Arenas Vasco, A., Fernández Aréizaga, E., & Rodríguez Pereira, J. (2019). 72- #1013 SOLUCIÓN DE UN PROBLEMA DE RUTEO MULTIDEPÓSITO CON FLOTA HETEROGÉNEA USANDO GENERACIÓN DE COLUMNAS. Memorias Institucionales UIS, 2(1). Retrieved from https://revistas.uis.edu.co/index.php/memoriasuis/article/view/10481

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

Downloads

Download data is not yet available.

References

Choi, E. Tcha, D. (2007). A Column Generation
Approach to the Heterogeneous Fleet Vehicle Routing
Problem. Computers & Operations Research, 34, 20802095.

Desrosiers,
J.
Lübbecke,
M.
(2005).
A
Primer
in
Column

Generation. Column Generation, 1-29.
Desrosiers, J. Lübbecke, M. (2005). Selected Topics in
Column Generation. Operations Reasearch, 53, 10071023.

Feillet,
D.
(2010).
A
Tutorial
on
Column
Generation
and

Branch-and-price

for Vehicle Routing Problems. 4OR,
4, 407-424.
Kallehauge, B. Larsen, J. Madsen, O. Solomon, M.
(2005). Vehicle Routing Problem with Time Windows.
Column Generation, 67-97.
Lübbecke, M. (2010). Column Generation. Wiley
Encyclopedia of Operations Research and
Management Science.
Posada, J. Farbiarz, V. González, C. (2011). Análisis
del “Pico y Placa” como Restricción a la Circulación
Vehicular en Medellín – Basado en Volúmenes
Vehiculares. Revista DYNA, 78, 112-121.
Nazareth, J. (1984). Numerical Behaviour of LP
Algorithms Based Upon the Decomposition Principle.
Linear Algebra Appl, 57, 181-189.
Schrijver, A. (1986). Theory of Linear and Integer
Programming. Jhon Wiley and Sons, Chichester, UK