Changeset 6851 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba

Timestamp:

09/29/11 15:51:56 (13 years ago)

Author:

svonolfe

Message:

Added support for multi depot CVRP instances (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba

Files:

• AlbaEncoding.cs (modified) (8 diffs)
• Creators/AlbaCreator.cs (modified) (1 diff)
• Crossovers/AlbaCrossover.cs (modified) (1 diff)
• IAlbaOperator.cs (modified) (1 diff)
• Manipulators/AlbaManipulator.cs (modified) (1 diff)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

@@ -33 +33 @@
   [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
   [StorableClass]
-  public class AlbaEncoding : PermutationEncoding, IHeterogenousCapacitatedEncoding  {   
+  public class AlbaEncoding : PermutationEncoding  {   
     #region IVRPEncoding Members
     public override List<Tour> GetTours() {
+      Repair();
       List<Tour> result = new List<Tour>();
 
@@ -55 +56 @@
       if (tour.Stops.Count > 0) {
         result.Add(tour);
-      }   
+      }
 
       return result;
     }
-    #endregion
 
-    #region IHeterogenousCapacitatedEncoding Members
-
-    public int GetVehicleAssignment(int tour) {
+    public override int GetVehicleAssignment(int tour) {
       int vehicleAssignment = -1;
       Tour currentTour = GetTours()[tour];
@@ -72 +70 @@
       int lastStopIndex = this.IndexOf(lastStop);
 
-      if (lastStopIndex == this.Length - 1)
-        vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
+      if (lastStopIndex == this.Length - 1) {
+        int i = this.Length - 1;
+
+        while (vehicleAssignment == -1) {
+          if (this.array[i] >= ProblemInstance.Cities.Value) {
+            vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
+          }
+          
+          i--;
+        }
+      }
       else
         vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
@@ -80 +87 @@
     }
     #endregion
+
+    public void Repair() {
+      int cities = ProblemInstance.Cities.Value;
+
+      if (this[this.Length - 1] < cities) {
+        int index = this.Length - 2;
+        while (this[index] < cities) {
+          index--;
+        }
+
+        int vehicle = this[index];
+        for (int i = index; i < this.Length - 1; i++)
+          this[i] = this[i + 1];
+        this[Length - 1] = vehicle;
+      }
+    }
 
     public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance)
@@ -100 +123 @@
     public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) {
       List<int> route = new List<int>(routeParam);
-      route.RemoveAt(routeParam.Count - 1);
       
       int cities = instance.Cities.Value;
@@ -129 +151 @@
       int emptyVehicles = instance.Vehicles.Value - tours.Count;
 
-      int[] array = new int[cities + tours.Count + emptyVehicles - 1];
+      int[] array = new int[cities + tours.Count + emptyVehicles];
       int delimiter = 0;
       int arrayIndex = 0;
@@ -140 +162 @@
 
         if (arrayIndex != array.Length) {
-          if (encoding is IHeterogenousCapacitatedEncoding) {
-            array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
-          } else {
-            array[arrayIndex] = cities + delimiter;
-          }
+          array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
           
           delimiter++;
@@ -151 +169 @@
       }
 
-      for (int i = 0; i < emptyVehicles - 1; i++) {
-        if (encoding is IHeterogenousCapacitatedEncoding) {
-          array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
-        } else {
-          array[arrayIndex] = cities + delimiter;
-        }
+      for (int i = 0; i < emptyVehicles; i++) {
+        array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
 
         delimiter++;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/AlbaCreator.cs

@@ -47 +47 @@
       : base(original, cloner) {
     }
+
+    public override IOperation Apply() {
+      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
+
+      return base.Apply();
+    }
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs

@@ -67 +67 @@
 
       ChildParameter.ActualValue = 
-        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);  
+        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);
+      (ChildParameter.ActualValue as AlbaEncoding).Repair();
 
       return base.Apply();

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/IAlbaOperator.cs

@@ -32 +32 @@
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
-  public interface IAlbaOperator: 
-    ISingleDepotOperator, IHeterogenousCapacitatedOperator, ITimeWindowedOperator {    
+  public interface IAlbaOperator:
+    ISingleDepotOperator, IHeterogenousCapacitatedOperator, IMultiDepotOperator, ITimeWindowedOperator {    
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs

@@ -71 +71 @@
 
       Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as AlbaEncoding);
+      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
 
       return base.Apply();