ResourceFunction[“MaximizeOverPermutations”] is well suited for this task. It uses a simulated annealing method if memory serves.