Le problème d'affectation quadratique (QAP), NP-difficile, modélise de nombreuses situa-
tions industrielles. Étant données deux matrices n × n de flux F et de distances D, et une
bijection σ entre installations et emplacements, le coût est
C(σ) =n∑i,k=1Fik Dσ(i)σ(k), (1)
et l'objectif est de trouver σ minimisant C [1]. Les méthodes exactes ne parviennent pas
à trouver de solutions optimales au-delà de quelques dizaines d'installations et les meilleures
performances sur QAPLIB [6] reposent sur des recherches tabou robustes [2]. Les approches
d'optimisation combinatoire neuronale ont montré qu'on peut apprendre, par apprentissage
par renforcement, des politiques neuronales compétitives pour des problèmes de tournée ou de
routage [3], et des modèles RL dédiés au QAP ont récemment été proposés [4, 5].
Notre objectif est de concevoir un agent RL spécifiquement adapté au QAP qui exploite
de manière explicite la structure de la fonction de coût, au-delà des architectures NCO gé-
nériques ou des modèles RL précédents. Nous proposons (i) une formulation séquentielle du
QAP en processus de décision markovien où les récompenses reposent sur des coûts margi-
naux exacts, (ii) une politique modulaire combinant un encodeur edge-aware sur (F, D) et une
composante informée par ces coûts marginaux, et (iii) un protocole d'entraînement Proximal
Policy Optimization (PPO) adapté à un espace d'actions dense de taille O(n2).