Cotas para el problema de asignación de vehículos

Abstract

El problema de asignación dinámica de vehículos 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 carre-tera. 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. Por esta razón, en este trabajo se propone estudiar dos métodos de decomposición, que proporcionan certificados de calidad, para obtener cotas para el PADV. Los métodos utilizados son relajación lagranjeana junto con método de subgradiente de optimización y decomposición de Dantzig-Wolfe junto con generación de columnas. Experimentos compu-tacionales son realizados con instancias realistas, y los resultados de las cotas se muestran promisorios en términos de eficiencia computacional para el segundo método.

Keywords

• optimización
• asignación de vehículos
• Dantzig-Wolfe
• generación de columnas
• relajación lagranjeana.