Changeset 14430 for branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs

Timestamp:

11/30/16 09:24:40 (7 years ago)

Author:

jzenisek

Message:

#2707 added temporal distance clustering

File:

• branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs (copied) (copied from branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs) (9 diffs)

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -30 +31 @@
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
-  [Item("GeographicDistanceClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm based on their geographic position and building tours afterwards alternatevly in a random or a greedy fashion.")]
+  [Item("TemporalDistanceClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm based on their geographic position and building tours afterwards alternatevly in a random or a greedy fashion.")]
   [StorableClass]
-  public sealed class GeographicDistanceClusterCreator : ClusterCreator {
+  public sealed class TemporalDistanceClusterCreator : ClusterCreator {
 
     [StorableConstructor]
-    private GeographicDistanceClusterCreator(bool deserializing) : base(deserializing) { }
+    private TemporalDistanceClusterCreator(bool deserializing) : base(deserializing) { }
 
-    public GeographicDistanceClusterCreator() : base() {
+    public TemporalDistanceClusterCreator() : base() {
     }
 
-    private GeographicDistanceClusterCreator(GeographicDistanceClusterCreator original, Cloner cloner)
+    private TemporalDistanceClusterCreator(TemporalDistanceClusterCreator original, Cloner cloner)
       : base(original, cloner) {
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new GeographicDistanceClusterCreator(this, cloner);
+      return new TemporalDistanceClusterCreator(this, cloner);
     }
 
-    public static List<SpatialDistanceClusterElement> CreateClusterObjects(IVRPProblemInstance instance) {
+    public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
@@ -58 +59 @@
       }
 
-      // wrap stops in SpatialDistanceClusterElement
-      List<SpatialDistanceClusterElement> clusterObjects = new List<SpatialDistanceClusterElement>();
+      // wrap stops in TemporalDistanceClusterElement
+      List<TemporalDistanceClusterElement> clusterObjects = new List<TemporalDistanceClusterElement>();
       foreach (int customer in customers) {
-        clusterObjects.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
+        clusterObjects.Add(new TemporalDistanceClusterElement(customer, instance.ReadyTime[customer], instance.DueTime[customer]));
       }
       return clusterObjects;
     }
 
-    public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
+    public static PotvinEncoding CreateSolution(ITimeWindowedProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      List<SpatialDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
+      List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
 
       int k = random.Next(minK, maxK);
-      List<SpatialDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
+      List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
 
       // (3) build tours
@@ -83 +84 @@
         if (creationOption == 0) {
           // (a) shuffle
-          c.Objects.Shuffle(random);
-          foreach (var o in c.Objects) {
+          c.Elements.Shuffle(random);
+          foreach (var o in c.Elements) {
             newTour.Stops.Add(o.Id);
           }
         } else {
           // (b) greedy
-          foreach (var o in c.Objects) {
+          foreach (var o in c.Elements) {
             newTour.Stops.Add(o.Id);
           }
@@ -99 +100 @@
     }
 
-    private static List<SpatialDistanceCluster> KMeans(IVRPProblemInstance instance, IRandom random, List<SpatialDistanceClusterElement> objects, int k, double changeTreshold) {
+    private static List<TemporalDistanceCluster> KMeans(ITimeWindowedProblemInstance instance, IRandom random, List<TemporalDistanceClusterElement> objects, int k, double changeTreshold) {
 
-      List<SpatialDistanceCluster> clusters = new List<SpatialDistanceCluster>();
+      List<TemporalDistanceCluster> clusters = new List<TemporalDistanceCluster>();
       HashSet<int> initMeans = new HashSet<int>();
       int nextMean = -1;
@@ -107 +108 @@
       // (1) initialize each cluster with a random first object (i.e. mean)
       for (int i = 0; i < k && i < objects.Count; i++) {
-        SpatialDistanceCluster cluster = new SpatialDistanceCluster(instance, i);
+        TemporalDistanceCluster cluster = new TemporalDistanceCluster(instance, i);
 
         do {
@@ -128 +129 @@
 
       // remove empty clusters
-      clusters.RemoveAll(c => c.Objects.Count.Equals(0));
+      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
 
       return clusters;
     }
 
-    private static int KMeansRun(List<SpatialDistanceCluster> clusters, List<SpatialDistanceClusterElement> objects) {
+    private static int KMeansRun(List<TemporalDistanceCluster> clusters, List<TemporalDistanceClusterElement> objects) {
       int changes = 0;
 
       foreach (var c in clusters) {
-        c.Objects.Clear();
+        c.Elements.Clear();
       }
 
       foreach (var o in objects) {
-        int bestClusterIdx = -1;
-        double minImpact = double.MaxValue;
-        for (int i = 0; i < clusters.Count; i++) {
+        int bestClusterIdx = 0;
+        double minImpact = clusters[0].CalculateImpact(o);
+        for (int i = 1; i < clusters.Count; i++) {
           double impact = clusters[i].CalculateImpact(o);
-          if (impact < minImpact) {
+          if ((minImpact > 0 && impact < minImpact) || (minImpact < 0 && impact > minImpact)) { // V1: min positive impact
+          //if(impact > minImpact) { // V2: max impact
             minImpact = impact;
             bestClusterIdx = i;
@@ -156 +158 @@
       foreach (var c in clusters) {
         c.CalculateMean();
+        c.CalculateVariance();
       }
 
@@ -181 +184 @@
       int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
 
-      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, random, minK, maxK, clusterChangeThreshold, creationOption);
+      var instance = ProblemInstance as ITimeWindowedProblemInstance;
+      if (instance == null) {
+        throw new ArgumentException(string.Format("Cannot initialize {0} with data from {1}", instance.GetType(), ProblemInstance.GetType()));
+      }
+
+      VRPToursParameter.ActualValue = CreateSolution(instance, random, minK, maxK, clusterChangeThreshold, creationOption);
       return base.InstrumentedApply();
     }