Multiple Origins - Multiple Destinations
-
21-09-2019 - |
문제
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.
다른 팁
Not necessarily the optimal solution, but maybe a good start:
- Find the point A such that the sum of distances from the origins to A is minimal.
- Find the point B such that the sum of distances from B to the destinations is minimal.
- 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.
You will want to try the full scan algorithm before finding more complex and faster ones.
- Find an algorithm that permute one collection all the ways possible
- Use this algorithm over the destinations collection
- 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;
}