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

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 3, May-June 2025


Page(s)		1569 - 1586
DOI		https://doi.org/10.1051/ro/2025055
Published online		20 June 2025

H.R. Lourenço, O.C. Martin, T. Stützle, F. Glover and G.A. Kochenberger, Iterated Local Search. Springer US, Boston, MA (2003) 320–353. [Google Scholar]
S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680. [Google Scholar]
F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA (1997). [Google Scholar]
P. Hansen, N. Mladenović, E.K. Burke and G. Kendall, Variable Neighborhood Search. Springer US, Boston, MA (2005) 211–238. [Google Scholar]
K.P. Bennett and E. Parrado-Hernández, The interplay of optimization and machine learning research. J. Mach. Learn. Res. 7 (2006) 1265–1281. [MathSciNet] [Google Scholar]
H. Mittelmann and D. Salvagnin, On solving a hard quadratic 3-dimensional assignment problem. Math. Program. Comput. 7 (2015) 219–234. [CrossRef] [MathSciNet] [Google Scholar]
P.M. Hahn, B.-J. Kim, T. Stuetzle, S. Kanthak, W.L. Hightower, H. Samra, Z. Ding and M. Guignard, The quadratic three-dimensional assignment problem: exact and approximate solution methods. Eur. J. Oper. Res. 184 (2008) 416–428. [CrossRef] [Google Scholar]
L. Loukil, M. Mehdi, N. Melab, E.-G. Talbi and P. Bouvry, Parallel hybrid genetic algorithms for solving Q3AP on computational grid. Int. J. Found. Comput. Sci. 23 (2012) 483–500. [CrossRef] [Google Scholar]
D. Delahaye, S. Chaimatanan, M. Mongeau, M. Gendreau and J.-Y. Potvin, Simulated Annealing: From Basics to Applications. Springer International Publishing, Cham (2019) 1–35. [Google Scholar]
C. Koulamas, S.R. Antony and R. Jaen, A survey of simulated annealing applications to operations research problems. Omega 22 (1994) 41–56. [CrossRef] [Google Scholar]
S. Lan, W. Fan, S. Yang, P.M. Pardalos and N. Mladenovic, A survey on the applications of variable neighborhood search algorithm in healthcare management. Ann. Math. Artif. Intell. 89 (2021) 741–775. [CrossRef] [MathSciNet] [Google Scholar]
P. Hansen and N. Mladenović, Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130 (2001) 449–467. [Google Scholar]
M. Karimi-Mamaghan, M. Mohammadi, P. Meyer, A.M. Karimi-Mamaghan and E.-G. Talbi, Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art. Eur. J. Oper. Res. 296 (2022) 393–422. [CrossRef] [Google Scholar]
S. Szénási and G. Légrádi, Machine learning aided metaheuristics: a comprehensive review of hybrid local search methods. Expert Syst. App. 258 (2024) 125192. [CrossRef] [Google Scholar]
J. Barrera-García, F. Cisternas-Caneo, B. Crawford, M. Gómez Sánchez and R. Soto, Feature selection problem and metaheuristics: a systematic literature review about its formulation, evaluation and applications. Biomimetics 9 (2024) 9. [Google Scholar]
B. Bischl, P. Kerschke, L. Kotthoff, M. Lindauer, Y. Malitsky, A. Fréchette, H. Hoos, F. Hutter, K. Leyton-Brown, K. Tierney and J. Vanschoren, Aslib: a benchmark library for algorithm selection. Artif. Intell. 237 (2016) 41–58. [CrossRef] [Google Scholar]
C.P. Gomes and B. Selman, Algorithm portfolio design: theory vs. practice. Preprint arXiv:1302.1541 (2013). [Google Scholar]
V.-A. Darvariu, S. Hailes and M. Musolesi, Graph reinforcement learning for combinatorial optimization: a survey and unifying perspective. Preprint arXiv:2404.06492 (2024). [Google Scholar]
Q. Lan, A.R. Mahmood, S. Yan and Z. Xu, Learning to optimize for reinforcement learning. Preprint arXiv:2302.01470 (2024). [Google Scholar]
N. Mazyavkina, S. Sviridov, S. Ivanov and E. Burnaev, Reinforcement learning for combinatorial optimization: a survey. Comput. Oper. Res. 134 (2021) 105400. [CrossRef] [Google Scholar]
J. Schulman, F. Wolski, P. Dhariwal, A. Radford and O. Klimov, Proximal policy optimization algorithms. Preprint arXiv:1707.06347 (2017). [Google Scholar]
I. Bello, H. Pham, Q.V. Le, M. Norouzi and S. Bengio, Neural combinatorial optimization with reinforcement learning. Preprint arXiv:1611.09940 (2016). [Google Scholar]
A. Garmendia, Q. Cappart, J. Ceberio and A. Mendiburu, Marco: a memory-augmented reinforcement framework for combinatorial optimization. Preprint arXiv:2408.02207 (2024). [Google Scholar]
H. Yang and M. Gu, A new baseline of policy gradient for traveling salesman problem, in 2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA) (2022) 1–7. [Google Scholar]
T. Mustakhov, Y. Akhmetbek and A. Bogyrbayeva, Deep reinforcement learning for stochastic dynamic vehicle routing problem, in 2023 17th International Conference on Electronics Computer and Computation (ICECCO) (2023) 1–5. [Google Scholar]
J. Holder, N. Jaques and M. Mesbahi, Multi agent reinforcement learning for sequential satellite assignment problems, in Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. (2025) 26516–26524. [Google Scholar]
X. Kong, Y. Zhou, Z. Li and S. Wang, Multi-UAV simultaneous target assignment and path planning based on deep reinforcement learning in dynamic multiple obstacles environments. Front. Neurorobot. 17 (2024) 1302898. [CrossRef] [Google Scholar]
I. Ait Abderrahim and L. Loukil, Hybrid approach for solving the Q3AP. Int. J. Swarm Intell. Res. (IJSIR) 12 (2021) 98–114. [CrossRef] [Google Scholar]
P.S. Bagga and A. Delarue, Solving the quadratic assignment problem using deep reinforcement learning. Preprint arXiv:2310.01604 (2023). [Google Scholar]
J.E.R. Staddon, The dynamics of behavior: review of Sutton and Barto: reinforcement learning: an introduction. J. Exper. Anal. Behav. 113 (2020) 485–491. [CrossRef] [Google Scholar]
W.P. Pierskalla, The multi-dimensional assignment problem. Technical Memorandum No. 93, Operations Research Department, CASE Institute of Technology (1967). [Google Scholar]
R.E. Burkard, E. Çela, S.E. Karisch and F. Rendl, Quadratic assignment problem library. https://coral.ise.lehigh.edu/data-sets/qaplib/. Accessed: 01/01/2024. [Google Scholar]
V. Černỳ, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory App. 45 (1985) 41–51. [CrossRef] [Google Scholar]
N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. [Google Scholar]
C.E. Nugent, T.E. Vollmann and J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res. 16 (1968) 150–173. [CrossRef] [Google Scholar]
S.W. Hadley, F. Rendl and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem. Math. Oper. Res. 17 (1992) 727–739. [CrossRef] [MathSciNet] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.