Multiple Origins - Multiple Destinations

Question

I either have a blonde moment or am attempting something a bit out of my league, but here it goes ;)

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?

Answer 1

Not necessarily the optimal solution, but maybe a good start:

1. Find the point A such that the sum of distances from the origins to A is minimal.
2. Find the point B such that the sum of distances from B to the destinations is minimal.
3. Find the shortest path from A to B.

Steps 1 and 2 take O(V^3) for applying Floyd-Warshall algorithm to determine the distances, and then O(V) for "linear" searching point A and B. Step 3 take O(V^2) for determining the shortest path.

Answer 2

You will want to try the full scan algorithm before finding more complex and faster ones.

1. Find an algorithm that permute one collection all the ways possible
2. Use this algorithm over the destinations collection
3. For each permutation calculate the variance

Example:

IEnumerable<Point[]> Permute(Point[] points)
{
   if(points.Length > 1)
       foreach(var point in points)
       {
          var remaining = points.Except(point).ToArray();
          foreach(var permutation in Permute(remaining))
               yield return new [] { new [] { point },  permutation}
                  .SelectMany(p => p)
                  .ToArray();
       }
   else
       yield return points;
}

Point[] SortDestinations(
         Point[] origins,
         Point[] destinations)
{
    var minVariance = int.MaxValue;
    Point[] minVariancePermutation;
    foreach(var permutation in Permute(destinations))
    {
        var variance = CalculateVariance(origins, permutation);
        if(variance < minVariance)
        {
            minVariance = variance;
            minVariancePermutation = permutation
        }
    }
    return minVariancePermutation;
}

Answer 3

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.