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

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.

• Autores: Acosta Rodríguez, Diego Alejandro
• Fecha de publicación: 2018
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: eng
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/34947
• Acceso en línea: http://hdl.handle.net/1992/34947
• Palabra clave: Distribución logística; Algoritmos heurísticos; Investigación operacional; Ingeniería
• Rights: openAccess
• License: https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf