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

Timestamp:

08/06/10 16:08:46 (14 years ago)

Author:

svonolfe

Message:

Refactored VRP, added some Potvin operators (WIP) (#1039)

Location:

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

Files:

• Crossovers/PotvinCrossover.cs (added)
• Crossovers/PotvinSBXCrossover.cs (added)
• Manipulators/Potvin1MManipulator.cs (added)
• Manipulators/Potvin2MManipulator.cs (added)
• Manipulators/PotvinManipulator.cs (added)
• PotvinEncoding.cs (modified) (7 diffs)

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/PotvinEncoding.cs

@@ -31 +31 @@
   [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions.")]
   [StorableClass]
-  class PotvinEncoding : Item, IVRPEncoding {
+  public class PotvinEncoding : Item, IVRPEncoding {
     public override Image ItemImage {
       get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Class; }
@@ -46 +46 @@
 
         foreach (Tour tour in Tours) {
-          cities += tour.Count;
+          cities += tour.Cities.Count;
         }
 
@@ -55 +55 @@
 
     [Storable]
-    public ItemList<IntValue> Unrouted { get; set; }
+    public List<int> Unrouted { get; set; }
 
     public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
@@ -61 +61 @@
       cloner.RegisterClonedObject(this, clone);
       clone.Tours = (ItemList<Tour>)cloner.Clone(this.Tours);
-      clone.Unrouted = (ItemList<IntValue>)cloner.Clone(this.Unrouted);
+      clone.Unrouted = new List<int>(Unrouted);
       return clone;
     }
@@ -67 +67 @@
     public PotvinEncoding() {
       Tours = new ItemList<Tour>();
-      Unrouted = new ItemList<IntValue>();
+      Unrouted = new List<int>();
     }
     
@@ -85 +85 @@
       for (int i = 0; i < route.Count; i++) {
         if (route[i] == 0) {
-          if (tour.Count > 0) {
+          if (tour.Cities.Count > 0) {
             solution.Tours.Add(tour);
             tour = new Tour();
           }
         } else {
-          tour.Add(new IntValue(route[i]));
+          tour.Cities.Add(route[i]);
         }
       }
@@ -96 +96 @@
       return solution;
     }
+
+    public bool FindInsertionPlace(
+      DoubleArray dueTimeArray,
+      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix,
+      int city, int routeToAvoid, out int route, out int place) {
+      route = -1;
+      place = -1;
+      double minDetour = 0;
+
+      for (int tour = 0; tour < Tours.Count; tour++) {
+        if (tour != routeToAvoid) {
+          for (int i = 0; i <= Tours[tour].Cities.Count; i++) {
+            double length = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
+
+            Tours[tour].Cities.Insert(i, city);
+
+            if (Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, 
+              capacity, coordinates, distanceMatrix, useDistanceMatrix)) {
+              double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
+
+              double detour = newLength - length;
+
+              if (route <= 0 || detour < minDetour) {
+                route = tour;
+                place = i;
+                minDetour = detour;
+              }
+            }
+
+            Tours[tour].Cities.RemoveAt(i);
+          }
+        }
+      }
+
+      return route >= 0 && place >= 0;
+    }
   }
 }