Changeset 6760 for branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers

Timestamp:

09/14/11 13:59:25 (13 years ago)

Author:

epitzer

Message:

#1530 integrate changes from trunk

Location:

branches/PersistenceSpeedUp

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.VehicleRouting (modified) (1 prop)
• HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs (modified) (5 diffs)
• HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs)
• HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs (modified) (4 diffs)
• HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs (modified) (3 diffs)

branches/PersistenceSpeedUp

@@ -12 +12 @@
 *.psess
 *.vsp
+*.docstates

@@ -12 +12 @@
 *.psess
 *.vsp
+*.docstates

branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs

@@ -26 +26 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -33 +34 @@
     public ILookupParameter<IRandom> RandomParameter {
       get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
+    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
+      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code (remove with 3.4)
+      if (!Parameters.ContainsKey("AllowInfeasibleSolutions")) {
+        Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
+      }
+      #endregion
     }
 
@@ -43 +58 @@
     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)));
     }
 
     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, 
+      DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand,
+      DoubleValue capacity, DistanceMatrix distMatrix, bool allowInfeasible,
+      out int route, out int place) {
       return individual.FindInsertionPlace(
-        DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
-        DemandParameter.ActualValue, CapacityParameter.ActualValue, CoordinatesParameter.ActualValue,
-        DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue,
-        city, -1, out route, out place);
+        dueTime, serviceTime, readyTime,
+        demand, capacity, distMatrix,
+        city, -1, allowInfeasible,
+        out route, out place);
     }
 
@@ -68 +87 @@
     }
 
-    protected bool Repair(IRandom random, PotvinEncoding solution, Tour newTour) {
+    protected static bool RouteUnrouted(PotvinEncoding solution, DistanceMatrix distMatrix,
+      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity, 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,
+          dueTime, serviceTime, readyTime, demand, capacity,
+          distMatrix, allowInfeasible,
+          out route, out place)) {
+          solution.Tours[route].Cities.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, DistanceMatrix distmatrix,
+      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity, 
+      bool allowInfeasible) {
       bool success = true;
 
@@ -104 +151 @@
       }
 
+      if (!allowInfeasible && !newTour.Feasible(
+        dueTime, serviceTime, readyTime, demand, capacity, distmatrix))
+        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].Cities.Insert(place, unrouted);
-        } else {
-          success = false;
-        }
-
-        index++;
-      }
-
-      for (int i = 0; i < index; i++)
-        solution.Unrouted.RemoveAt(0);
+      success = RouteUnrouted(solution, distmatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible);
 
       return success;

branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -40 +41 @@
 
     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;
+
       PotvinEncoding child = parent2.Clone() as PotvinEncoding;
 
@@ -55 +67 @@
           child.Unrouted.Add(city);
 
-      if (Repair(random, child, replacing))
+      if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible)
         return child;
       else {
@@ -61 +73 @@
           return parent1.Clone() as PotvinEncoding;
         else
-          return parent2.Clone() as PotvinEncoding;
+          return parent2.Clone() as PotvinEncoding;   
       }
     }

branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -41 +42 @@
 
     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;
+
       PotvinEncoding child = parent1.Clone() as PotvinEncoding;
       Tour newTour = new Tour();
@@ -69 +81 @@
           child.Unrouted.Add(city);
 
-      if (Feasible(newTour) &&
-          Repair(random, child, newTour)) {
+      if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, 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;   
       }
     }

@@ -12 +12 @@
 *.psess
 *.vsp
+*.docstates