Plusieurs origines - Destinations multiples

Question

J'ai une question d'optimisation. C'est seulement un peu voyageur-vendeur-ish.

Disons que j'ai un ensemble de destinations et un autre ensemble correspondant d'origines. J'ai besoin de lier chaque destination avec une origine afin que la variation entre les routes soit aussi faible que possible.

Je ne suis pas intéressé à former des paires de coordonnées avec une distance totale la plus courte. Je suis après avoir minimisé la variation entre les routes.

De toute évidence, il existe de nombreuses combinaisons possibles de création de paires origine-destination, il s'agit simplement de trouver la combinaison optimale où toutes les routes sont plus égales.

Des idées pour y remédier?

Answer 1

Si vous prenez une vue simple que "variance" dans votre problème est mesurée par le différenti e entre la plus petite et la plus grande distance dans la solution, alors vous pouvez utiliser l'algorithme suivant. Sélectionnez une distance minimale et une distance maximale. Puis effacez les routes de votre structure qui sont en dehors de cette bande; Ensuite, effectuez une mise en correspondance bipartite standard. Si (min, max) est votre bande et (min < min '< max' < max), alors évidemment (min ', max') ne peut être résolu que si (min, max) peut être résolu; ceci mène à un algorithme où vous commencez alors avec des bandes plus larges et recherchez une bande la plus étroite possible qui admet toujours un appariement bipartite. La correspondance bipartite est un problème algorithmique de faible complexité, donc la solution entière devrait être rapide; Pour une correspondance bipartite, voir http://en.wikipedia.org/wiki/Matching_%28graph_theory%29.

Answer 2

Pas nécessairement la solution optimale, mais peut-être un bon point de départ:

1. Trouver le point A telle que la somme des distances des origines à A est minime.
2. Trouvez le point B de sorte que la somme des distances entre B et les destinations soit minimale.
3. Trouvez le chemin le plus court entre A et B.

les étapes 1 et 2 prise O (V^3) pour appliquer l'algorithme de Floyd-Warshall pour déterminer les distances, puis O (V) pour le point de recherche "linéaire" A et B. L'étape 3 prend O (V^2) pour déterminer le chemin le plus court.

Answer 3

Vous voudrez essayer l'algorithme d'analyse complète avant de trouver des algorithmes plus complexes et plus rapides.

1. Trouver un algorithme qui permute une collection de toutes les façons possibles
2. Utilisez cet algorithme sur la collection destinations
3. Pour chaque permutation calculer la variance

Exemple:

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; 
}