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

Resumen

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.