Changeset 10460

Timestamp:

02/18/14 08:57:37 (11 years ago)

Author:

svonolfe

Message:

added static apply methods to VRP operators (#2152)

Location:

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators

Files:

• PotvinLocalSearchManipulator.cs (modified) (6 diffs)
• PotvinManipulator.cs (modified) (3 diffs)
• PotvinOneLevelExchangeManipulator.cs (modified) (3 diffs)
• PotvinPairwiseOneLevelExchangeManipulator.cs (modified) (5 diffs)
• PotvinPairwiseTwoLevelExchangeManipulator.cs (modified) (6 diffs)
• PotvinTwoLevelExchangeManipulator.cs (modified) (4 diffs)

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs

@@ -52 +52 @@
     }
 
-    private bool FindBetterInsertionPlace(
-      PotvinEncoding individual, int tour, int city, int length,
+    private static bool FindBetterInsertionPlace(
+      PotvinEncoding individual, IVRPProblemInstance instance, int tour, int city, int length,
       out int insertionTour, out int insertionPlace) {
       bool insertionFound = false;
@@ -70 +70 @@
           distance = individual.GetTourLength(individual.Tours[currentTour]);
           individual.Tours[currentTour].Stops.InsertRange(currentCity, toBeDeleted);
-          if (ProblemInstance.TourFeasible(individual.Tours[currentTour], individual)) {
+          if (instance.TourFeasible(individual.Tours[currentTour], individual)) {
             double lengthIncrease =
               individual.GetTourLength(individual.Tours[currentTour]) - distance;
@@ -92 +92 @@
     }
 
-    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, int maxIterations) {
       //only apply to feasible individuals
-      if (ProblemInstance.Feasible(individual)) {
+      if (instance.Feasible(individual)) {
         bool insertionFound;
         int iterations = 0;
@@ -107 +107 @@
               while (city <= individual.Tours[tour].Stops.Count - length && !insertionFound) {
                 int insertionTour, insertionPlace;
-                if (FindBetterInsertionPlace(individual, tour, city, length,
+                if (FindBetterInsertionPlace(individual, instance, tour, city, length,
                  out insertionTour, out insertionPlace)) {
                   insertionFound = true;
@@ -126 +126 @@
           iterations++;
         } while (insertionFound &&
-          iterations < Iterations.Value.Value);
+          iterations < maxIterations);
 
         IList<Tour> toBeRemoved = new List<Tour>();
@@ -139 +139 @@
       }
     }
+ 
+
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      ApplyManipulation(random, individual, ProblemInstance, Iterations.Value.Value);     
+    }
   }
 }

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs

@@ -55 +55 @@
     protected abstract void Manipulate(IRandom random, PotvinEncoding individual);
 
-    protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
+    protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance) {
       int tourIndex = -1;
 
@@ -61 +61 @@
       double[] probabilities = new double[individual.Tours.Count];
       for (int i = 0; i < individual.Tours.Count; i++) {
-        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)ProblemInstance.Cities.Value);
+        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)instance.Cities.Value);
         sum += probabilities[i];
       }
@@ -82 +82 @@
     }
 
-    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
+    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
       return individual.FindInsertionPlace(
         city, routeToAvoid, allowInfeasible, out route, out place);

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -41 +42 @@
     }
 
-    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
-      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
-
-      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance);
       if (selectedIndex >= 0) {
         Tour route1 =
@@ -68 +67 @@
       }
     }
+
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      ApplyManipulation(random, individual, ProblemInstance, allowInfeasible);      
+    }
   }
 }

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs

@@ -25 +25 @@
 using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
 using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -43 +44 @@
     }
 
-    public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {
+    public static bool PairwiseMove(PotvinEncoding individual, IVRPProblemInstance instance, int city, bool allowInfeasible) {
       bool success;
 
-      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
+      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
       if (pdp != null) {
@@ -64 +65 @@
 
         int source, target;
-        if (ProblemInstance.GetDemand(city) >= 0) {
+        if (instance.GetDemand(city) >= 0) {
           source = city;
           target = dest;
@@ -80 +81 @@
           if (tourIdx != routeToAvoid) {
             Tour tour = individual.Tours[tourIdx];
-            VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
-            individual.InsertPair(tour, source, target, ProblemInstance);
-            VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
+            VRPEvaluation eval = instance.EvaluateTour(tour, individual);
+            individual.InsertPair(tour, source, target, instance);
+            VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);
 
             double delta = evalNew.Quality - eval.Quality;
 
             if (delta < bestQuality &&
-               (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
+               (instance.Feasible(evalNew) || allowInfeasible)) {
               bestQuality = delta;
               bestTour = tourIdx;
@@ -127 +128 @@
     }
 
+    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
+      if (selectedIndex >= 0) {
+        Tour route1 =
+          individual.Tours[selectedIndex];
+
+        int count = route1.Stops.Count;
+
+        if (count > 0) {
+          int i = random.Next(0, count);
+          int city = route1.Stops[i];
+
+          if (!PairwiseMove(individual, pdp, city, allowInfeasible))
+            i++;
+
+          count = route1.Stops.Count;
+        }
+      }
+    }
+
+
     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
       IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
 
       if (pdp != null) {
-        int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
-        if (selectedIndex >= 0) {
-          Tour route1 =
-            individual.Tours[selectedIndex];
-
-          int count = route1.Stops.Count;
-
-          if (count > 0) {
-            int i = random.Next(0, count);
-            int city = route1.Stops[i];
-
-            if (!PairwiseMove(individual, city, allowInfeasible))
-              i++;
-
-            count = route1.Stops.Count;
-          }
-        }
+        ApplyManipulation(random, individual, pdp, allowInfeasible);
       }
     }

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs

@@ -26 +26 @@
 using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
 using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -44 +45 @@
     }
 
-    private PotvinEncoding ReplacePair(PotvinEncoding individual, int replaced, int replacing, bool allowInfeasible) {
+    private static PotvinEncoding ReplacePair(PotvinEncoding individual, IVRPProblemInstance instance, int replaced, int replacing, bool allowInfeasible) {
       individual = individual.Clone() as PotvinEncoding;
-      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
+      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
       int replacedDest = pdp.GetPickupDeliveryLocation(replaced);
@@ -76 +77 @@
 
       replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource;
-      if (!allowInfeasible && !ProblemInstance.TourFeasible(replacedSourceTour, individual))
+      if (!allowInfeasible && !instance.TourFeasible(replacedSourceTour, individual))
         return null;
 
       replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget;
-      if (!allowInfeasible && !ProblemInstance.TourFeasible(replacedTargetTour, individual))
+      if (!allowInfeasible && !instance.TourFeasible(replacedTargetTour, individual))
         return null;
 
@@ -93 +94 @@
         if (tourIdx != routeToAvoid) {
           Tour tour = individual.Tours[tourIdx];
-          VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
-          individual.InsertPair(tour, replacedSource, replacedTarget, ProblemInstance);
-          VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
+          VRPEvaluation eval = instance.EvaluateTour(tour, individual);
+          individual.InsertPair(tour, replacedSource, replacedTarget, instance);
+          VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);
 
           double delta = evalNew.Quality - eval.Quality;
 
           if (delta < bestQuality &&
-              (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
+              (instance.Feasible(evalNew) || allowInfeasible)) {
             bestQuality = delta;
             bestTour = tourIdx;
@@ -127 +128 @@
     }
 
+    public static PotvinEncoding ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
+      PotvinEncoding result = null;
+      
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
+      if (selectedIndex >= 0) {
+        bool performed = false;
+        Tour route1 = individual.Tours[selectedIndex];
+
+        if (route1.Stops.Count > 0) {
+          //randomize customer selection
+          Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
+          int customer1Position = 0;
+
+          while (customer1Position < route1.Stops.Count) {
+            performed = false;
+
+            int customer1 = route1.Stops[perm[customer1Position]];
+            int customer2 = -1;
+
+            for (int i = 0; i < individual.Tours.Count; i++) {
+              if (i != selectedIndex) {
+                Tour tour = individual.Tours[i];
+                for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
+                  customer2 = tour.Stops[customer2Position];
+
+                  if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
+                    result = ReplacePair(individual, pdp, customer2, customer1, allowInfeasible);
+                    if (result != null) {
+                      individual = result;
+
+                      route1 = individual.Tours[selectedIndex];
+                      performed = true;
+                      break;
+                    }
+                  }
+                }
+              }
+
+              if (performed) {
+                break;
+              }
+            }
+
+            if (!performed)
+              customer1Position++;
+            else
+              break;
+          }
+        }
+      }
+
+      return result;
+    }
+
     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
@@ -132 +187 @@
 
       if (pdp != null) {
-        int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
-        if (selectedIndex >= 0) {
-          bool performed = false;
-          Tour route1 = individual.Tours[selectedIndex];
-
-          if (route1.Stops.Count > 0) {
-            //randomize customer selection
-            Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
-            int customer1Position = 0;
-
-            while (customer1Position < route1.Stops.Count) {
-              performed = false;
-
-              int customer1 = route1.Stops[perm[customer1Position]];
-              int customer2 = -1;
-
-              for (int i = 0; i < individual.Tours.Count; i++) {
-                if (i != selectedIndex) {
-                  Tour tour = individual.Tours[i];
-                  for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
-                    customer2 = tour.Stops[customer2Position];
-
-                    if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
-                      PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible);
-                      if (result != null) {
-                        VRPToursParameter.ActualValue = result;
-                        individual = result;
-
-                        route1 = individual.Tours[selectedIndex];
-                        performed = true;
-                        break;
-                      }
-                    }
-                  }
-                }
-
-                if (performed) {
-                  break;
-                }
-              }
-
-              if (!performed)
-                customer1Position++;
-              else
-                break;
-            }
-          }
-        }
+        PotvinEncoding result = ApplyManipulation(random, individual, pdp, allowInfeasible);
+        if (result != null) {
+          VRPToursParameter.ActualValue = result;
+        }        
       }
     }

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -41 +42 @@
     }
 
-    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
-      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
-
-      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance);
       if (selectedIndex >= 0) {
         Tour route1 = individual.Tours[selectedIndex];
@@ -63 +62 @@
                 route1.Stops.RemoveAt(customer1Position);
 
-                if (ProblemInstance.TourFeasible(tour, individual)) {
+                if (instance.TourFeasible(tour, individual)) {
                   int routeIdx, place;
                   if (FindInsertionPlace(individual,
@@ -92 +91 @@
       }
     }
+      
+
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
+      ApplyManipulation(random, individual, ProblemInstance, allowInfeasible);
+    }
   }
 }