
My little Turkish empire could save a couple of turns by letting the yellow and the purple settlers switch targets. Time is money! I don't think I'm too far off from being able to do these exchanges. I expect that optimising the routing might be NP-complete (just has that Travelling Salesman "feel"), but I could probably brute-force it as there are unlikely to be more than a handful of settlers active at any one moment.
[1] http://www.cs.northwestern.edu/~forbus/395gai/homework.htm