A real, applied problem in spatial epidemiology crossed my desk last week, and it turns out that it is a super-fun combinatorial optimization challenge, too.
Details here: http://gis.stackexchange.com/questions/126280/group-polygon-features-to-match-a-set-of-specifications
I don’t have time to play around with it a lot now, but I did try a little stochastic search, which makes me think that this will not be trivial to solve:
Healthy Algorithms 