Changeset 14424 for branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting

Timestamp:

11/28/16 16:41:36 (8 years ago)

Author:

jzenisek

Message:

#2707 adapted clustering leading to more generic usage

Location:

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Encodings/Potvin/Creators/Cluster.cs (added)
• Encodings/Potvin/Creators/ClusterCreator.cs (modified) (3 diffs)
• Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs (added)
• HeuristicLab.Problems.VehicleRouting-3.4.csproj (modified) (2 diffs)

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

@@ -37 +37 @@
   [Item("ClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm and building tours afterwards alternatevly in a random or a greedy fashion.")]
   [StorableClass]
-  public sealed class ClusterCreator : PotvinCreator, IStochasticOperator {
+  public abstract class ClusterCreator : PotvinCreator, IStochasticOperator {
 
     public ILookupParameter<IRandom> RandomParameter {
@@ -69 +69 @@
     }
 
-    private ClusterCreator(ClusterCreator original, Cloner cloner)
+    protected ClusterCreator(ClusterCreator original, Cloner cloner)
       : base(original, cloner) {
     }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new ClusterCreator(this, cloner);
-    }
-
-    public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
-      PotvinEncoding result = new PotvinEncoding(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);
-      }
-
-      // cluster by spatial distribution
-
-      // (1) wrap stops in ClusterObject
-      List<ClusterObject> clusterObjects = new List<ClusterObject>();
-      foreach (int customer in customers) {
-        clusterObjects.Add(new ClusterObject(customer, instance.GetCoordinates(customer)));
-      }
-
-      // (2) cluster
-      int k = random.Next(minK, maxK);
-      List<Cluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
-
-      // (3) build tours
-      // (a) shuffle
-      // (b) greedy
-      foreach (Cluster c in clusters) {
-        Tour newTour = new Tour();
-        result.Tours.Add(newTour);
-
-        if (creationOption == 0) {
-          // (a) shuffle
-          c.Objects.Shuffle(random);
-          foreach (ClusterObject o in c.Objects) {
-            newTour.Stops.Add(o.Id);
-          }
-        } else {
-          // (b) greedy
-          foreach (ClusterObject o in c.Objects) {
-            newTour.Stops.Add(o.Id);
-          }
-          GreedyTourCreation(instance, result, newTour, false);
-        }
-      }
-      return result;
-    }
-
-    public override IOperation InstrumentedApply() {
-      IRandom random = RandomParameter.ActualValue;
-
-      int minK = (MinK.Value.Value > 0) ? MinK.Value.Value : 1;
-      int maxK = (MaxK.Value != null) ? MaxK.Value.Value : ProblemInstance.Vehicles.Value;
-      double clusterChangeThreshold = (ClusterChangeThreshold.Value.Value >= 0.0 &&
-                                       ClusterChangeThreshold.Value.Value <= 1.0)
-        ? ClusterChangeThreshold.Value.Value
-        : 0.0;
-
-      // normalize probabilities
-      double max = TourCreationProbabilities.Value.Max();
-      double[] probabilites = new double[2];
-      for (int i = 0; i < TourCreationProbabilities.Value.Length; i++) {
-        probabilites[i] = TourCreationProbabilities.Value[i] / max;
-      }
-
-      List<int> creationOptions = new List<int>() {0, 1};
-      int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
-
-      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, random, minK, maxK, clusterChangeThreshold, creationOption);
-      return base.InstrumentedApply();
-    }
-
-    private static List<Cluster> KMeans(IVRPProblemInstance instance, IRandom random, List<ClusterObject> objects, int k, double changeTreshold) {
-
-      List<Cluster> clusters = new List<Cluster>();
-      HashSet<int> initMeans = new HashSet<int>();
-      int nextMean = -1;
-
-      // (1) initialize each cluster with a random first object (i.e. mean)
-      for (int i = 0; i < k && i < objects.Count; i++) {
-        Cluster cluster = new Cluster(instance, i);
-
-        do {
-          nextMean = random.Next(0, objects.Count);
-        } while (initMeans.Contains(nextMean));
-        initMeans.Add(nextMean);
-        cluster.SetMean(objects[nextMean]);
-        clusters.Add(cluster);
-      }
-
-      // (2) repeat clustering until change rate is below threshold
-      int changes = 0;
-      double changeRate = 1.0;
-
-      do {
-        changes = KMeansRun(clusters, objects);
-        changeRate = changes / objects.Count;
-
-      } while (changeRate > changeTreshold);
-
-      // remove empty clusters
-      clusters.RemoveAll(c => c.Objects.Count.Equals(0));
-
-      return clusters;
-    }
-
-    private static int KMeansRun(List<Cluster> clusters, List<ClusterObject> objects) {
-      int changes = 0;
-
-      foreach (Cluster c in clusters) {
-        c.Objects.Clear();
-      }
-
-      foreach (ClusterObject o in objects) {
-        int bestClusterIdx = -1;
-        double minImpact = double.MaxValue;
-        for(int i = 0; i < clusters.Count; i++) {
-          double impact = clusters[i].CalculateVarianceIncrease(o);
-          if (impact < minImpact) {
-            minImpact = impact;
-            bestClusterIdx = i;
-          }
-        }
-        clusters[bestClusterIdx].AddObject(o);
-      }
-
-      foreach (Cluster c in clusters) {
-        c.CalculateMean();
-      }
-
-      return changes;
-    }
-
-    class Cluster {
-      public int Id;
-      public List<ClusterObject> Objects { get; private set; }
-      public double Variance { get; private set; }
-      public ClusterObject Mean { get; set; }
-
-      private readonly IVRPProblemInstance instance;
-
-      public Cluster(IVRPProblemInstance instance, int id) {
-        this.instance = instance;
-        Id = id;
-        Objects = new List<ClusterObject>();
-      }
-
-      public bool IsEqual(Cluster cluster) {
-        bool equal = (cluster != null) && (cluster.Objects.Count == Objects.Count);
-        int index = 0;
-
-        while (equal && index < Objects.Count) {
-          equal = cluster.Objects.Contains(Objects[index]);
-          index++;
-        }
-        return equal;
-      }
-
-      public bool AddObject(ClusterObject o) {
-        Objects.Add(o);
-
-        bool clusterChanged = o.ClusterId != Id;
-        o.ClusterId = Id;
-        return clusterChanged;
-      }
-
-      public void SetMean(ClusterObject o) {
-        Mean = o;
-        Mean.ClusterId = Id;
-      }
-
-      public ClusterObject CalculateMean() {
-        int dimensions = instance.Coordinates.Columns;
-        ClusterObject mean = new ClusterObject(-1, Id, dimensions);
-        foreach (ClusterObject o in Objects) {
-          double[] coordinates = instance.GetCoordinates(o.Id);
-          for (int i = 0; i < coordinates.Length; i++) {
-            mean.Coordinates[i] += (coordinates[i] / Objects.Count);
-          }
-        }
-        Mean = mean;
-        return Mean;
-      }
-
-      public double CalculateVariance() {
-        Variance = 0.0;
-
-        if (Mean == null)
-          CalculateMean();
-
-        foreach (ClusterObject o in Objects) {
-          double[] coordinates = instance.GetCoordinates(o.Id);
-          Variance += Math.Pow(Mean.GetDistance(o.Coordinates), 2);
-        }
-        return Variance /= Objects.Count;
-      }
-
-      public double CalculateVarianceIncrease(ClusterObject o) {
-        if(Mean == null)
-          CalculateMean();
-
-        return Math.Pow(Mean.GetDistance(o.Coordinates), 2) / ((Objects.Count > 0) ? Objects.Count : 1);
-      }
-    }
-
-    class ClusterObject {
-      
-      public int Id { get; private set; }
-
-      public int ClusterId { get; set; }
-
-      public double[] Coordinates { get; set; }
-
-      public ClusterObject() { }
-
-      public ClusterObject(int id, int clusterId = -1) {
-        Id = id;
-        ClusterId = clusterId;
-      }
-
-      public ClusterObject(int id, double[] coordinates) {
-        Id = id;
-        Coordinates = coordinates;
-      }
-
-      public ClusterObject(int id, int clusterId, int dimensions) {
-        Id = id;
-        ClusterId = clusterId;
-        Coordinates = new double[dimensions];
-      }
-
-      public double GetDistance(double[] otherCoordinates) {
-        double distance = 0.0;
-
-        for (int i = 0; i < otherCoordinates.Length; i++) {
-          distance += Math.Pow(Coordinates[i] - otherCoordinates[i], 2);
-        }
-        return Math.Sqrt(distance);
-      }
-    }
-
-    private static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
+    protected static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
       double dx = instance.GetCoordinates(0)[0];
       double dy = instance.GetCoordinates(0)[1];
@@ -336 +91 @@
     }
 
-    private static void GreedyTourCreation(IVRPProblemInstance instance, PotvinEncoding individual, Tour tour, bool includeCosts) {
+    protected static void GreedyTourCreation(IVRPProblemInstance instance, PotvinEncoding individual, Tour tour, bool includeCosts) {
       Tour unrouted = tour.Clone() as Tour;
       tour.Stops.Clear();

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

@@ -48 +48 @@
     <CodeAnalysisRuleSet>AllRules.ruleset</CodeAnalysisRuleSet>
     <Prefer32Bit>false</Prefer32Bit>
+    <LangVersion>5</LangVersion>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
@@ -195 +196 @@
     <Compile Include="Analyzer\ConstraintRelaxation\TimeWindowed\TimeWindowRelaxationVRPAnalyzer.cs" />
     <Compile Include="Analyzer\VRPSolution.cs" />
+    <Compile Include="Encodings\Potvin\Creators\Cluster.cs" />
     <Compile Include="Encodings\Potvin\Creators\ClusterCreator.cs" />
+    <Compile Include="Encodings\Potvin\Creators\GeographicDistanceClusterCreator.cs" />
     <Compile Include="Encodings\Potvin\Crossovers\PotvinEdgePreservingSequenceBasedCrossover.cs" />
     <Compile Include="Encodings\Potvin\Manipulators\PotvinGreedyTourCreationManipulator.cs" />