Changeset 4376 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings

Timestamp:

09/09/10 16:24:09 (14 years ago)

Author:

svonolfe

Message:

Added Potvin encoding (#1177)

Location:

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

Files:

• Alba/AlbaEncoding.cs (modified) (3 diffs)
• Alba/Crossovers/AlbaCrossover.cs (modified) (1 diff)
• Alba/Manipulators/AlbaManipulator.cs (modified) (1 diff)
• Alba/Moves/AlbaMoveGenerator.cs (modified) (1 diff)
• General/TourEncoding.cs (modified) (2 diffs)
• Potvin (added)
• Potvin/Crossovers (added)
• Potvin/Crossovers/PotvinCrossover.cs (added)
• Potvin/Crossovers/PotvinRouteBasedCrossover.cs (added)
• Potvin/Crossovers/PotvinSequenceBasedCrossover.cs (added)
• Potvin/IPotvinOperator.cs (added)
• Potvin/Manipulators (added)
• Potvin/Manipulators/PotvinLocalSearchManipulator.cs (added)
• Potvin/Manipulators/PotvinManipulator.cs (added)
• Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs (added)
• Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs (added)
• Potvin/PotvinEncoding.cs (added)

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

@@ -28 +28 @@
 using HeuristicLab.Problems.VehicleRouting.Encodings.General;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
   [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 {   
+  public class AlbaEncoding : PermutationEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHeterogenousCapacitatedEncoding  {   
     #region IVRPEncoding Members
     public override List<Tour> GetTours() {
@@ -60 +61 @@
     #endregion
 
+    #region IHeterogenousCapacitatedEncoding Members
+
+    public int GetVehicleAssignment(int tour) {
+      int vehicleAssignment = -1;
+      Tour currentTour = GetTours()[tour];
+
+      int lastStop = currentTour.Stops[
+        currentTour.Stops.Count - 1] - 1;
+
+      int lastStopIndex = this.IndexOf(lastStop);
+
+      if (lastStopIndex == this.Length - 1)
+        vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
+      else
+        vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
+
+      return vehicleAssignment;
+    }
+    #endregion
+
     public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
       AlbaEncoding clone = new AlbaEncoding(
-        new Permutation(this.PermutationType, this.array), 
-        (IVRPProblemInstance)cloner.Clone(ProblemInstance));
+        new Permutation(this.PermutationType, this.array), ProblemInstance);
       cloner.RegisterClonedObject(this, clone);
       clone.readOnly = readOnly;
@@ -103 +123 @@
         instance);
     }
+
+    public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {
+      List<Tour> tours = encoding.GetTours();
+
+      int cities = 0;
+      foreach (Tour tour in tours) {
+        cities += tour.Stops.Count;
+      }
+
+      int emptyVehicles = instance.Vehicles.Value - tours.Count;
+
+      int[] array = new int[cities + tours.Count + emptyVehicles - 1];
+      int delimiter = 0;
+      int arrayIndex = 0;
+      
+      foreach (Tour tour in tours) {
+        foreach (int city in tour.Stops) {
+          array[arrayIndex] = city - 1;
+          arrayIndex++;
+        }
+
+        if (arrayIndex != array.Length) {
+          if (encoding is IHeterogenousCapacitatedEncoding) {
+            array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
+          } else {
+            array[arrayIndex] = cities + delimiter;
+          }
+          
+          delimiter++;
+          arrayIndex++;
+        }
+      }
+
+      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;
+        }
+
+        delimiter++;
+        arrayIndex++;
+      }
+
+      AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected, new IntArray(array)), instance);
+
+      return solution;
+    }
   }
 }

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

@@ -53 +53 @@
         IVRPEncoding solution = ParentsParameter.ActualValue[i];
 
-        /*if (!(solution is AlbaEncoding)) {
-          parents[i] = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
-            DistanceMatrixParameter);
-        } else*/ {
+        if (!(solution is AlbaEncoding)) {
+          parents[i] = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
+        } else {
           parents[i] = solution;
         }

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

@@ -62 +62 @@
       IVRPEncoding solution = VRPToursParameter.ActualValue;
       if (!(solution is AlbaEncoding)) {
-        //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value, DistanceMatrixParameter);
+        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
       }
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveGenerator.cs

@@ -43 +43 @@
       IVRPEncoding solution = VRPToursParameter.ActualValue;
       if (!(solution is AlbaEncoding)) {
-        //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
-        //  DistanceMatrixParameter);
+        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
       }
       

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

@@ -71 +71 @@
     protected IVRPProblemInstance ProblemInstance { get; set; }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      TourEncoding clone = (TourEncoding)base.Clone(cloner);
-
-      clone.ProblemInstance = (IVRPProblemInstance)cloner.Clone(ProblemInstance);
-
-      return clone;
-    }
-
     public TourEncoding(IVRPProblemInstance problemInstance) {
       Tours = new ItemList<Tour>();
@@ -87 +79 @@
     [StorableConstructor]
     protected TourEncoding(bool serializing)
-      : base() {
+      : base(serializing) {
+    }
+
+    public static void ConvertFrom(IVRPEncoding encoding, TourEncoding solution, IVRPProblemInstance problemInstance) {
+      solution.Tours = new ItemList<Tour>(encoding.GetTours());
+    }
+
+    public static void ConvertFrom(List<int> route, TourEncoding solution) {
+      solution.Tours = new ItemList<Tour>();
+
+      Tour tour = new Tour();
+      for (int i = 0; i < route.Count; i++) {
+        if (route[i] == 0) {
+          if (tour.Stops.Count > 0) {
+            solution.Tours.Add(tour);
+            tour = new Tour();
+          }
+        } else {
+          tour.Stops.Add(route[i]);
+        }
+      }
     }
   }