Changeset 7815 for branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators

Timestamp:

05/14/12 17:55:41 (13 years ago)

Author:

svonolfe

Message:

Added first working version of VRP path relinker (#1331)

File:

• branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs (modified) (5 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs

@@ -29 +29 @@
 using HeuristicLab.Problems.VehicleRouting.Encodings;
 using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
 
 namespace HeuristicLab.Problems.VehicleRouting {
@@ -37 +39 @@
   [StorableClass]
   public sealed class VRPSimilarityCalculator : SimilarityCalculator {
+    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
+      get {
+        if (Parameters.ContainsKey("DistanceMatrix"))
+          return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"];
+        else
+          return null;
+      }
+    }
+
     [StorableConstructor]
     private VRPSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private VRPSimilarityCalculator(VRPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
-    public VRPSimilarityCalculator() : base() { }
+    public VRPSimilarityCalculator() : base() {
+      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -46 +59 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      PotvinEncoding e1 = left.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
-      PotvinEncoding e2 = right.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
-
+    public static double CalculateSimilarity(PotvinEncoding e1, PotvinEncoding e2) {
       // extract edges from first solution
       var edges1 = new List<Tuple<int, int>>();
       foreach (Tour tour in e1.Tours) {
         edges1.Add(new Tuple<int, int>(0, tour.Cities[0]));
-        edges1.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
         for (int i = 0; i < tour.Cities.Count - 1; i++)
           edges1.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
+        edges1.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
       }
 
@@ -63 +73 @@
       foreach (Tour tour in e2.Tours) {
         edges2.Add(new Tuple<int, int>(0, tour.Cities[0]));
-        edges2.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
         for (int i = 0; i < tour.Cities.Count - 1; i++)
           edges2.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
+        edges2.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
       }
 
@@ -73 +83 @@
       int identicalEdges = 0;
       foreach (var edge in edges1) {
-        if (edges2.Any(x => x.Equals(edge) || x.Item1 == edge.Item2 && x.Item2 == edge.Item1))
+        if (edges2.Any(x => x.Equals(edge)))
           identicalEdges++;
       }
 
-      return identicalEdges * 2.0 / edges1.Count + edges2.Count;
+      return identicalEdges * 2.0 / (edges1.Count + edges2.Count);
+    }
+
+    protected override double CalculateSimilarity(IScope left, IScope right) {
+      IVRPEncoding e1 = left.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
+      if (!(e1 is PotvinEncoding))
+        e1 = PotvinEncoding.ConvertFrom(e1 as IVRPEncoding, DistanceMatrixParameter);
+
+      IVRPEncoding e2 = right.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
+      if (!(e2 is PotvinEncoding))
+        e2 = PotvinEncoding.ConvertFrom(e2 as IVRPEncoding, DistanceMatrixParameter);
+
+      return CalculateSimilarity(e1 as PotvinEncoding, e2 as PotvinEncoding);
     }
   }