A metaheuristic proposal using Java for the quadratic assignment problem

Abstract

One of the classic combinatorial optimization problems belonging to the NP-hard class is the quadratic assignment problem. The interest in solving the problem lies in its high computational complexity, as well as its applications in: logistics, electronic circuits, gate assignment in airports, among others. In this work, the Greedy Random Adaptive Search Procedure metaheuristic was implemented to find its solutions. The main contribution of this work is the adaptation of a neighborhood structure contained in k-exchanges in the post-processing phase. The tests were performed for 29 large-scale instances whose dimensions range from 64 to 254 taken from the QAPLIB. The approximate solutions were found through a metaheuristic that bases its search on neighborhoods and local search algorithms. Java was the programming language used for the implementation of metaheuristics; its execution allowed balancing the parameters to obtain competitive results with respect to the values ​​known in the literature. The results reported and presented in this work achieved the proposed objectives.