Changeset 6607 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers

Timestamp:

07/28/11 14:16:21 (13 years ago)

Author:

svonolfe

Message:

Merged changes from trunk (#1561) into branch (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers

Files:

• PotvinCrossover.cs (modified) (5 diffs)
• PotvinRouteBasedCrossover.cs (modified) (2 diffs)
• PotvinSequenceBasedCrossover.cs (modified) (2 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs

@@ -39 +39 @@
     }
 
+    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
+      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
+    }
+
     [StorableConstructor]
     protected PotvinCrossover(bool deserializing) : base(deserializing) { }
@@ -44 +48 @@
     public PotvinCrossover() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
     }
 
@@ -52 +57 @@
     protected abstract PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2);
 
-    protected bool FindInsertionPlace(PotvinEncoding individual, int city, out int route, out int place) {
+    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, bool allowInfeasible,
+        out int route, out int place) {
       return individual.FindInsertionPlace(
-        city, -1, out route, out place);
+        city, -1, allowInfeasible,
+        out route, out place);
     }
 
@@ -70 +77 @@
     }
 
-    protected bool Repair(IRandom random, PotvinEncoding solution, Tour newTour) {
+    protected static bool RouteUnrouted(PotvinEncoding solution, bool allowInfeasible) {
       bool success = true;
-      
+      int index = 0;
+      while (index < solution.Unrouted.Count && success) {
+        int unrouted = solution.Unrouted[index];
+
+        int route, place;
+        if (FindInsertionPlace(solution, unrouted, allowInfeasible,
+          out route, out place)) {
+          solution.Tours[route].Stops.Insert(place, unrouted);
+        } else {
+          success = false;
+        }
+
+        index++;
+      }
+
+      for (int i = 0; i < index; i++)
+        solution.Unrouted.RemoveAt(0);
+
+      return success;
+    }
+
+    protected static bool Repair(IRandom random, PotvinEncoding solution, Tour newTour, IVRPProblemInstance instance, bool allowInfeasible) {
+      bool success = true;
+
       //remove duplicates from new tour      
       for (int i = 0; i < newTour.Stops.Count; i++) {
@@ -106 +136 @@
       }
 
+      if (!allowInfeasible && !instance.Feasible(newTour))
+        return false;
+
       //route unrouted vehicles
-      int index = 0;
-      while (index < solution.Unrouted.Count && success) {
-        int unrouted = solution.Unrouted[index];
-
-        int route, place;
-        if(FindInsertionPlace(solution, unrouted, out route, out place)) {
-          solution.Tours[route].Stops.Insert(place, unrouted);
-        } else {
-          success = false;
-        }
-
-        index++;
-      }
-
-      for (int i = 0; i < index; i++)
-        solution.Unrouted.RemoveAt(0);
+      success = RouteUnrouted(solution, allowInfeasible);
 
       return success;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

@@ -46 +46 @@
      
     protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
       PotvinEncoding child = parent2.Clone() as PotvinEncoding;
 
@@ -61 +63 @@
           child.Unrouted.Add(city);
 
-      if (Repair(random, child, replacing))
+      if (Repair(random, child, replacing, ProblemInstance, allowInfeasible) || allowInfeasible)
         return child;
       else {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

@@ -46 +46 @@
         
     protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      
       PotvinEncoding child = parent1.Clone() as PotvinEncoding;
       Tour newTour = new Tour();
@@ -76 +78 @@
           child.Unrouted.Add(city);
 
-      if (ProblemInstance.Feasible(newTour) &&
-          Repair(random, child, newTour)) {
+      if (Repair(random, child, newTour, ProblemInstance, allowInfeasible) || allowInfeasible) {
         return child;
       } else {