Uncoordinated settlers

My FreeCiv client-side AI (not related to [1]) is sending settlers off to found new cities, but they are still a bit uncoordinated. It may be as obvious as in this composite screenshot where two contemporaneously-existing settlers are on paths crossing each other. I've fudged the image a bit to show one settler's path info in purple and the other's in yellow.


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