Changeset 14559 for branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

Timestamp:

01/12/17 16:42:50 (7 years ago)

Author:

pfleck

Message:

#2707 Simplified k-means clustering for ClusterCreators.

File:

• branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs (modified) (4 diffs)

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -48 +49 @@
     }
 
-    public static List<SpatialDistanceClusterElement> CreateClusterElements(IVRPProblemInstance instance) {
-      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
-
-      // add all customers
-      List<int> customers = new List<int>();
-      for (int i = 1; i <= instance.Cities.Value; i++) {
-        if (pdp == null || pdp.GetDemand(i) >= 0)
-          customers.Add(i);
-      }
-
-      // wrap stops in SpatialDistanceClusterElement
-      List<SpatialDistanceClusterElement> clusterElements = new List<SpatialDistanceClusterElement>();
-      foreach (int customer in customers) {
-        clusterElements.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
-      }
-      return clusterElements;
-    }
 
     public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      // (1) wrap stops in cluster elements
-      List<SpatialDistanceClusterElement> clusterElements = CreateClusterElements(instance);
+      // (1) init data
+      var coordinates = new List<double[]>(instance.Cities.Value);
+      var pdp = instance as IPickupAndDeliveryProblemInstance;
+      for (int i = 1; i <= instance.Cities.Value; i++) {
+        if (pdp == null || pdp.GetDemand(i) >= 0)
+          coordinates.Add(instance.GetCoordinates(i));
+      }
 
       // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
-        .KMeans(random, clusterElements, k, clusterChangeThreshold);
-      
+      var kMeans = new KMeansAlgorithm<double[]>(CalculateMeanHelper, CalculateDistanceHelper);
+      var clusters = kMeans.Run(coordinates, k, clusterChangeThreshold, random);
+
       // (3) build tours with a (a) shuffling (b) greedy tour creation routine
-      foreach (var c in clusters) {
+      foreach (var cluster in clusters) {
         Tour newTour = new Tour();
         result.Tours.Add(newTour);
@@ -84 +73 @@
         if (creationOption == 0) {
           // (a) shuffle
-          c.Elements.Shuffle(random);
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          cluster.ShuffleInPlace(random);
+          newTour.Stops.AddRange(cluster);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
         } else {
           // (b) greedy
-          foreach (var o in c.Elements) {
-            newTour.Stops.Add(o.Id);
+          foreach (var customer in cluster) {
+            newTour.Stops.Add(customer + 1);
           }
           GreedyTourCreation(instance, result, newTour, false);
@@ -98 +88 @@
 
       return result;
+    }
+
+    private static double[] CalculateMeanHelper(List<double[]> coordinates) {
+      var mean = new double[coordinates[0].Length];
+      foreach (double[] coord in coordinates) {
+        for (int i = 0; i < mean.Length; i++) {
+          mean[i] += coord[i] / coordinates.Count;
+        }
+      }
+      return mean;
+    }
+    private static double CalculateDistanceHelper(double[] coord1, double[] coord2) {
+      double distance = 0.0;
+      for (int i = 0; i < coord1.Length; i++) {
+        distance += Math.Pow(coord1[i] - coord2[i], 2);
+      }
+      return Math.Sqrt(distance);
     }