58- #1017 BRANCH-AND-PRICE PARA EL PROBLEMA DE ASIGNACIÓN DE VEHÍCULOS
No Thumbnail Available
Date
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
El problema de asignación dinámica de vehículos(PAV) consiste en asignar una flota de vehículos paraatender la demanda prevista por transporte de cargaentre terminales, durante un horizonte de tiempo finitoy con múltiples periodos, cuyo objetivo es maximizar ellucro generado por los servicios completados. Dada ladispersión geográfica por demanda de servicios detransporte de carga, es común que se acumulenvehículos vacíos en lugares donde no son necesarios ose genere una escasez de vehículos donde sonnecesitados a lo largo del horizonte de planeación, portanto, es importante balancear el suministro devehículos y la demanda por servicios a lo largo delhorizonte de planeación. El tamaño de los problemasprácticos enfrentados por transportadores logísticos esconsiderablemente grande para resolver en tiemposcomputacionales razonables, especialmente entransporte de carga por carretera. Consecuentemente,se recurre a métodos heurísticos para obtenersoluciones factibles, pese a que no se tiene certificadode calidad de la solución. En este contexto, el objetivode 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étodoutilizado es un Branch-and-Price que utiliza generaciónde columnas basado en la reformulación Dantzig-Wolfedel PAV. Dada las caracteristicas del problema, seutiliza una sucesión de caminos minimos en grafosdireccionados aciclicos para resolver el problemarelajado. Asi mismo, se utiliza un esquema deramificación basada en partición de caminos paraprohibir soluciones fraccionarias óptimas del problemamaestro restricto. Los resultados computacionalesmuestran que el método es eficiente en encontrar lasolución óptima primal. Sin embargo, otrasramificaciones tienen que ser exploradas para apretarel limitante dual.
Keywords
Asignación de Vehículos, Decomposición DantzigWolfe, Generación de Columnas, Transporte de Cargas