In my simplistic mind, the genetic algorithm solution sounds like a more complex method of roughly the same approach. (Although I need to investigate this further, really.)

It is not the same approach at all. The genetic algorthm tests combination for fitness, or in this case how much each schedule "costs" - obviously the less it costs, the better. Once you determine the "fittest" N solutions, you combine them in hopes they will retain the best traits and eliminate the bad traits in the "offspring". Check out blokhead's page - he has some good links to theyse types of approaches. In a nut shell, you are reducing your search space to find the local optima - you are not throwing darts.

For the record, I'm talking of hundreds of sales reps in hundreds of locations, so I don't think the brute force method won't work with the computing power I have available.

I guess that depends on how many are actually changing locations each time. If only a small percentage change locations, then this reduces your problem drastically.

Good luck with things, and if you end up using a genetic algorithm or neural net, let me know! :)