1st one just screams Genetic Algo. Maybe thats just a case of "When you have a hammer..." though. I don't see any CPU/time limit though so maybe there is a proper solution.
You're right about the "when you have a hammer" issue. The biggest problem with genetic algorithms is that there's rarely a good reason for using them for cookie-cutter combinatorial optimization like the problem, when there are hundreds of papers on very good approximation algorithms.
