Might help, might not: The last time I had to do a closely related chore I ended up using a technique called "simulated annealing" to find good-but-not-absolutely-optimal solutions. The problem is it was decades ago using an all-but-extinct programming language,* so I can't provide more than the name. Googling "simulated annealing" turns up articles that look relevant but wouldn't provide anything like a ready-to-use solution.

* Since someone's bound to ask, it was APL.