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

58- #1017 BRANCH-AND-PRICE PARA EL PROBLEMA DE ASIGNACIÓN DE VEHÍCULOS

César Dario Alvarez Cruz
Ingenieria de Producción, Universidad Federal de São Carlos, Brazil
Reinaldo Morabito Neto
Ingenieria de Producción, Universidad Federal de São Carlos, Brazil

Publicado 2019-01-01

Palavras-chave

  • Asignación de Vehículos,
  • Decomposición DantzigWolfe,
  • Generación de Columnas,
  • Transporte de Cargas

Como Citar

Alvarez Cruz, C. D., & Morabito Neto, R. (2019). 58- #1017 BRANCH-AND-PRICE PARA EL PROBLEMA DE ASIGNACIÓN DE VEHÍCULOS. Memorias Institucionales UIS, 2(1). Recuperado de https://revistas.uis.edu.co/index.php/memoriasuis/article/view/10467

Resumo

El problema de asignación dinámica de vehículos
(PAV) consiste en asignar una flota de vehículos para
atender la demanda prevista por transporte de carga
entre terminales, durante un horizonte de tiempo finito
y con múltiples periodos, cuyo objetivo es maximizar el
lucro generado por los servicios completados. Dada la
dispersión geográfica por demanda de servicios de
transporte de carga, es común que se acumulen
vehículos vacíos en lugares donde no son necesarios o
se genere una escasez de vehículos donde son
necesitados a lo largo del horizonte de planeación, por
tanto, es importante balancear el suministro de
vehículos y la demanda por servicios a lo largo del
horizonte de planeación. El tamaño de los problemas
prácticos enfrentados por transportadores logísticos es
considerablemente grande para resolver en tiempos
computacionales razonables, especialmente en
transporte de carga por carretera. Consecuentemente,
se recurre a métodos heurísticos para obtener
soluciones factibles, pese a que no se tiene certificado
de calidad de la solución. En este contexto, el objetivo
de este trabajo es contribuir con métodos de solución
que ofrezcan certificados o garantias de optimalidad
para resolver problemas de gran escala. El método
utilizado es un Branch-and-Price que utiliza generación
de columnas basado en la reformulación Dantzig-Wolfe
del PAV. Dada las caracteristicas del problema, se
utiliza una sucesión de caminos minimos en grafos
direccionados aciclicos para resolver el problema
relajado. Asi mismo, se utiliza un esquema de
ramificación basada en partición de caminos para
prohibir soluciones fraccionarias óptimas del problema
maestro restricto. Los resultados computacionales
muestran que el método es eficiente en encontrar la
solución óptima primal. Sin embargo, otras
ramificaciones tienen que ser exploradas para apretar
el limitante dual.

Downloads

Não há dados estatísticos.

Referências

Powell, W. B. (1986). A stochastic model of the
dynamic vehicle allocation problem. Transportation
Science, 20(2):117–129.
https://doi.org/10.1287/trsc.20.2.117
Vasco, R. A. & Morabito, R. (2016). The dynamic
vehicle allocation problem with application in trucking
companies in brazil. Computers & Operations
Research, 76:118 – 133.
https://doi.org/10.1016/j.cor.2016.04.022
Barnhart, C., Hane, C. A., & Vance, P. H. (2000). Using
branch-and-price-and-cut to solve
origin-destination integer multicommodity flow
problems. Operations Research, 48(2):318–326.
https://doi.org/10.1287/opre.48.2.318.12378
Ahuja, R., Magnanti, T. L., & Orlin, J. B. (1993). Network
flows : theory, algorithms, and applications. Prentice
Hall, Englewood Cliffs, N.J. ISBN-13: 978-0136175490
Gondzio, J., González-Brevis, P., & Munari, P. (2016).
Large-scale optimization with the primal- dual column
generation method. Mathematical Programming
Computation, 8(1):47–82.
https://doi.org/10.1007/s12532-015-0090-6