I have an optimization question. It is only somewhat traveling-salesman-ish.
Lets say I have a set of destinations and another corresponding set of origins. I need to link each destination with one origin so that the variation between the routes is as small as possible.
I am not interested in forming pairs of coordinates with a total shortest distance. I am after minimising the variation between the routes.
Obviously, there are many possible combinations of creating origin-destination pairs, it's just a matter of finding the optimal one where all routes are more-less equal.
Ideas on a way to tackle that?
If you take a simple view that "variance" in your problem is measured by the difference between the least and greatest distance in the solution, then you can use the following algorithm. Select a minimum distance and a maximum distance. Then erase those routes in your structure which are outside this band; then perform standard bipartite matching. If (min,max) is your band and (min<min'<max'<max), then obviously (min',max') can be solved only if (min,max) can be solved; this leads to an algorithm where you then start with wider bands and search for a narrowest possible band that still admits a bipartite matching. Bipartite matching is a low-complexity algorithmic problem so the whole solution should be fast; for bipartite matching, see http://en.wikipedia.org/wiki/Matching_%28graph_theory%29.