Changeset 6455 for trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers

Timestamp:

06/20/11 16:45:49 (13 years ago)

Author:

svonolfe

Message:

Worked on insertion based crossover (#1561)

Location:

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers

Files:

• PotvinCrossover.cs (modified) (2 diffs)
• PotvinInsertionBasedCrossover.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs

@@ -115 +115 @@
         newTour.Cities.Remove(0);
 
-      if (!newTour.Feasible(
-        dueTime, serviceTime, readyTime, demand, capacity, distmatrix))
-              return false; 
-
       //remove duplicates from old tours
       for (int i = 0; i < newTour.Cities.Count; i++) {
@@ -137 +133 @@
         solution.Tours.Remove(tour);
       }
+
+      if (!newTour.Feasible(
+        dueTime, serviceTime, readyTime, demand, capacity, distmatrix))
+        return false;
 
       //route unrouted vehicles

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs

@@ -26 +26 @@
 using HeuristicLab.Data;
 using System;
+using HeuristicLab.Parameters;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
-  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations.")]
+  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations. It is implemented as described in Berger, J and Solois, M and Begin, R (1998). A hybrid genetic algorithm for the vehicle routing problem with time windows. LNCS 1418. Springer, London 114-127.")]
   [StorableClass]
   public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {
+    public IValueParameter<IntValue> Length {
+      get { return (IValueParameter<IntValue>)Parameters["Length"]; }
+    } 
+
     [StorableConstructor]
     private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }
@@ -40 +45 @@
     }
     public PotvinInsertionBasedCrossover()
-      : base() { }
+      : base() {
+        Parameters.Add(new ValueParameter<IntValue>("Length", "The maximum length of the replaced route.", new IntValue(1)));
+    }
 
     protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
@@ -199 +206 @@
       PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
 
-      int k = 1;//random.Next(1, Math.Min(10, parent1.Tours.Count + 1));
+      int length = Math.Min(Length.Value.Value, parent1.Tours.Count) + 1;
+      int k = random.Next(1, length);
       for (int i = 0; i < k; i++) {
         int index = SelectRandomTourBiasedByLength(random, p1Clone);
@@ -254 +262 @@
         child.Tours.Add(childTour);
         if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
-          //success = false;
-          //break;
+          /*success = false;
+          break;*/
         }
       }
@@ -264 +272 @@
           child.Tours.Add(childTour);
           if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
-            //success = false;
-            //break;
+            /*success = false;
+            break;*/
           }
         }
@@ -285 +293 @@
         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 child;
+          return parent2.Clone() as PotvinEncoding;   
       }
     }