Reinforcement learning-based local search for solving the quadratic 3-dimensional assignment problem

Faculty of Exact and Applied Sciences, Department of Computer Science, University of Oran 1, Oran, Algeria

^* Corresponding author: benzineb.walid@edu.univ-oran1.dz; benzinebwal@gmail.com

Received: 20 May 2024
Accepted: 23 April 2025

Abstract

Local search methods (LSM) are powerful metaheuristics known for efficiently exploring complex optimization landscapes. However, a key limitation is their “amnesiac” nature – they fail to utilize valuable data from past search iterations. This untapped data contains crucial information that can enhance the efficiency and outcomes of the search process. In this work, we propose a novel reinforcement learning (RL)-based move scoring mechanism to augment LSM, aiming to leverage historical data for improved adaptiveness and intelligence in the search process. We apply this hybrid method to the quadratic 3-dimensional assignment problem (Q3AP), a benchmark in combinatorial optimization that generalizes the quadratic assignment problem (QAP). Notably, few studies have focused on Q3AP, and to our knowledge, no prior work has integrated RL into its solution. Our experimental results demonstrate substantial improvements in both solution quality and execution time, particularly for larger and more complex problem instances. This performance gain is attributed to our unique iterative learning and scoring approach, which effectively guides the search process, balancing exploration and exploitation to escape local optima and find superior solutions.