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

Bounds for the vehicle allocation problem

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.

The Dynamic Vehicle Allocation Problem (DVAP) consists in allocating a fleet of vehicles to attend the expected demand for freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profit generated for the completed services. Given the geographical dispersion of freight transportation demand services, it is common that some vehicles accumulate where they are not needed or they lack where they are indeed needed, thus it is important to balance the supply of vehicles and demand for services along the planning horizon. The size of practical problems encountered by logistic transportation companies are significantly large to solve in reasonable computational times, especially in road freight transportation. Consequently, heuristic methods are used to obtain feasible solutions, however, without a quality certificate of the solution. For this reason, this work applies two decomposition methods, which provides quality certificate of the solution, to obtain bounds in reasonable computational times. The methods used are lagrangean relaxation with subgradient optimization and Dantzig-Wolfe decomposition with column generation. Computational experiments with realistic instances show great potential of the bounds in terms of computational efficiency for the second method