Changeset 7822 for branches/ScatterSearch (trunk integration)

Timestamp:

05/15/12 12:14:47 (12 years ago)

Author:

svonolfe

Message:

Worked on VRP path relinking (#1331)

Location:

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

Files:

• Encodings/Potvin/Crossovers/PotvinCrossover.cs (modified) (1 diff)
• Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs (modified) (3 diffs)
• Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs (modified) (3 diffs)
• PathRelinkers/VRPPathRelinker.cs (modified) (2 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs

@@ -74 +74 @@
     }
 
-    protected Tour FindRoute(PotvinEncoding solution, int city) {
+    protected static Tour FindRoute(PotvinEncoding solution, int city) {
       Tour found = null;
 

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

@@ -40 +40 @@
       : base() { }
 
-    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
-      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
-      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
-      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
-      DoubleArray dueTime = DueTimeParameter.ActualValue;
-      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
-      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
-      DoubleArray demand = DemandParameter.ActualValue;
-      DoubleValue capacity = CapacityParameter.ActualValue;
+    public static PotvinEncoding Apply(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2, bool allowInfeasible,
+      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
+      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
 
-      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
-
-      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
+      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
 
       int tourParent1 = random.Next(parent1.Tours.Count);
@@ -67 +60 @@
           child.Unrouted.Add(city);
 
-      if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible)
+      if (Repair(random, child, replacing, distMatrix, dueTimeArray, readyTimeArray, serviceTimeArray, 
+        demandArray, capacity, allowInfeasible) || allowInfeasible)
         return child;
       else {
@@ -73 +67 @@
           return parent1.Clone() as PotvinEncoding;
         else
-          return parent2.Clone() as PotvinEncoding;   
+          return parent2.Clone() as PotvinEncoding;
       }
+    }
+
+    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      DoubleArray dueTime = DueTimeParameter.ActualValue;
+      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
+      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
+      DoubleArray demand = DemandParameter.ActualValue;
+      DoubleValue capacity = CapacityParameter.ActualValue;
+
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
+      return Apply(random, parent1, parent2,
+        allowInfeasible, dueTime, serviceTime, readyTime,
+        demand, capacity, coordinates, DistanceMatrixParameter, useDistanceMatrix); 
     }
   }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

@@ -41 +41 @@
       : base() { }
 
-    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
-      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
-      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
-      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
-      DoubleArray dueTime = DueTimeParameter.ActualValue;
-      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
-      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
-      DoubleArray demand = DemandParameter.ActualValue;
-      DoubleValue capacity = CapacityParameter.ActualValue;
+    public static PotvinEncoding Apply(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2, bool allowInfeasible,
+      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
+      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
 
-      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
+      int cities = coordinates.Rows - 1;
 
-      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
       Tour newTour = new Tour();
 
-      int breakPoint1 = random.Next(1, Cities + 1);
+      int breakPoint1 = random.Next(1, cities + 1);
       Tour tour1 = FindRoute(child, breakPoint1);
       breakPoint1 = tour1.Cities.IndexOf(breakPoint1);
@@ -63 +58 @@
         newTour.Cities.Add(tour1.Cities[i]);
 
-      int breakPoint2 = random.Next(1, Cities + 1);
+      int breakPoint2 = random.Next(1, cities + 1);
       Tour tour2 = FindRoute(parent2, breakPoint2);
       breakPoint2 = tour2.Cities.IndexOf(breakPoint2);
@@ -81 +76 @@
           child.Unrouted.Add(city);
 
-      if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible) {
+      if (Repair(random, child, newTour, distMatrix, dueTimeArray, readyTimeArray, serviceTimeArray, 
+        demandArray, capacity, allowInfeasible) || allowInfeasible) {
         return child;
       } else {
-         if (random.NextDouble() < 0.5)
+        if (random.NextDouble() < 0.5)
           return parent1.Clone() as PotvinEncoding;
         else
-          return parent2.Clone() as PotvinEncoding;   
-      }
+          return parent2.Clone() as PotvinEncoding;
+      } 
+    }
+
+    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
+      DoubleArray dueTime = DueTimeParameter.ActualValue;
+      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
+      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
+      DoubleArray demand = DemandParameter.ActualValue;
+      DoubleValue capacity = CapacityParameter.ActualValue;
+
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
+      return Apply(random, parent1, parent2,
+        allowInfeasible, dueTime, serviceTime, readyTime,
+        demand, capacity, coordinates, DistanceMatrixParameter, useDistanceMatrix); 
     }
   }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

@@ -208 +208 @@
 
     #region moves
+    public static PotvinEncoding RouteBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random,
+      IntValue vehicles, DoubleArray dueTimeArray,
+      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
+        return PotvinRouteBasedCrossover.Apply(random, initiator, guide, false,
+          dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
+          capacity, coordinates, distanceMatrix, useDistanceMatrix);
+    }
+
+    public static PotvinEncoding SequenceBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random,
+     IntValue vehicles, DoubleArray dueTimeArray,
+     DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+     DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
+      return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, false,
+        dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
+        capacity, coordinates, distanceMatrix, useDistanceMatrix);
+    }
+
+
     public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
       List<int> cities = new List<int>();
@@ -468 +487 @@
             PotvinEncoding next = current.Clone() as PotvinEncoding;
 
-            int neighborhood = rand.Next(2);
+            int neighborhood = rand.Next(4);
             switch (neighborhood) {
-              case 0: GuidedRelocateMove(next, guide, rand);
+              case 0: next = RouteBasedXOver(next, guide, rand, 
+                vehicles, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, 
+                capacity, coordinates, distanceMatrix, useDistanceMatrix);
                 break;
-              case 1: TwoOptMove(next, rand);
+              case 1: next = SequenceBasedXOver(next, guide, rand,
+                vehicles, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
+                capacity, coordinates, distanceMatrix, useDistanceMatrix);
+                  break;
+              case 2: TwoOptMove(next, rand);
                 break;
-              case 2: TwoOptStarMove(next, rand);
-                break;
-              case 3: OrOptMove(next, rand);
-                break;
-              case 4: ExchangeMove(next, rand);
+              case 3: GuidedRelocateMove(next, guide, rand);
                 break;
             }