Heuristic algorithm based on columns generation for the integrated problem of vehicle routing and container loading

Abstract

This paper proposes a heuristic algorithm with a column generation structure, where the master problem is responsible for managing the selection of best set routes, while the slave problem is responsible for solving a shorter restricted route problem (CSP, Constrained Shortest Path) for the generation of columns (feasible routes). The CSP is not necessarily resolved to optimality. In addition to this, a GRASP algorithm (Greedy Randomized Adaptive Search Procedure) is used to verify packing constraints. The master problem begins with a set of feasible routes found through a multi-start randomized constructive heuristic (MSRCA, Multi-Start Randomized Constructive Algorithm) for the multi-container loading problem (3D-BPP, Three-dimensional Bin Packing Problem). The MSRCA consists in finding a group of valid routes thinking only in the best packing of the costumers (Packing First-Route Second). To validate the performance of the optimization methodology proposed here, a benchmark was made with the best solutions reported in the literature using the classic test sets. The results allow to conclude that the slave problem is too complex and computationally expensive to solve it through a MIP, as future proposals it is proposed the use of a labeling algorithm that allows finding a fast and good quality solution.

"Este trabajo propone un algoritmo heurístico con una estructura de generación de columnas, donde el problema maestro se encarga de gerenciar la selección de las rutas factibles, mientras el problema esclavo se encarga de resolver un problema de ruta más corta restringido (CSP, Constrained Shortest Path) para la generación de columnas. El CSP no necesariamente es resuelto a optimalidad. Además de esto, es utilizado un algoritmo GRASP (Greedy Randomized Adaptive Search Procedure) para verificar las restricciones de empaquetamiento. El problema maestro comienza con un conjunto de rutas factibles encontradas a través de una heurística multi-arranque de tipo constructivo aleatorizado (MSRCA, Multi-Start Randomized Constructive Algorithm) para el problema de carga de vehículos (3D-BPP, Three-dimensional Bin Packing Problem). El MSRCA consiste en encontrar un grupo de rutas validas pensando en primero empacar y después rutear (Packing First-Route Second). Para validar el desempeño de la metodología de optimización aquí propuesta, se realizó un benchmark con las mejores soluciones reportadas en la literatura utilizando los conjuntos de prueba clásicos. Los resultados permiten concluir que el problema esclavo es demasiado complejo y computacionalmente caro para resolverlo a través de un MIP, como propuestas futuras se propone el uso de un algoritmo de etiquetado que permita encontrar una solución rápida y de buena calidad."--Tomado del Formato de Documento de Grado.