Changeset 4270 for branches

Timestamp:

08/20/10 11:43:31 (14 years ago)

Author:

svonolfe

Message:

Code cleanup (#1039)

Location:

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

Files:

• GVR/GVREncoding.cs (modified) (2 diffs)
• GVR/Manipulators/GVRInsertionManipulator.cs (modified) (1 diff)
• Prins/Manipulators/PrinsLSManipulator.cs (modified) (15 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/GVR/GVREncoding.cs

@@ -40 +40 @@
 
     public override List<Tour> GetTours(ILookupParameter<DoubleMatrix> distanceMatrix = null, int maxVehicles = int.MaxValue) {
-      List<Tour> tours = new List<Tour>();
-      Tour newTour = new Tour();
-      double currentDemand = 0;
+      List<Tour> tours = new List<Tour>();    
 
-      int toursProcessed = 0;
       foreach (Tour tour in base.Tours) {
-        if (maxVehicles > tours.Count) {
-          newTour = new Tour();
-          currentDemand = 0;
-        }
+        Tour newTour = new Tour();
+        double currentDemand = 0;
 
         foreach (int city in tour.Cities) {
           currentDemand += demand[city];
 
-          if (maxVehicles > tours.Count && 
-            currentDemand > capacity.Value) {
+          if (currentDemand > capacity.Value) {
             if(newTour.Cities.Count > 0)
               tours.Add(newTour);
@@ -67 +61 @@
         }
 
-        if (newTour.Cities.Count > 0 &&
-          maxVehicles > tours.Count)
+        if (newTour.Cities.Count > 0)
           tours.Add(newTour);
+      }
 
-        toursProcessed++;
-      }
+      //repair if there are too many vehicles used
+      while (tours.Count > maxVehicles) {
+        Tour tour = tours[tours.Count - 1];
+        tours[tours.Count - 2].Cities.AddRange(tour.Cities);
+
+        tours.Remove(tour);
+      } 
 
       return tours;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/GVR/Manipulators/GVRInsertionManipulator.cs

@@ -55 +55 @@
       } else {
         Tour newTour = individual.Tours[random.Next(individual.Tours.Count)];
-        int newPosition = newTour.Cities.Count;
+        int newPosition = random.Next(newTour.Cities.Count + 1);
 
         newTour.Cities.Insert(newPosition, customer);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Prins/Manipulators/PrinsLSManipulator.cs

@@ -77 +77 @@
     protected const int depot = -1;
 
-    private Tour FindTour(PrinsEncoding individual, int citiy) {
+    private Tour FindTour(PrinsEncoding individual, int city) {
       Tour found = null;
 
@@ -84 +84 @@
 
       while (found == null && i < tours.Count) {
-        if (tours[i].Cities.Contains(citiy + 1))
+        if (tours[i].Cities.Contains(city))
           found = tours[i];
         
@@ -252 +252 @@
       if (u != depot) {
         if (v == depot) {
-          Tour tour = FindTour(child, u);
+          Tour tour = FindTour(child, u + 1);
           v = tour.Cities[0] - 1;
           InsertBefore(u, v, parent, child);
@@ -259 +259 @@
         }
       }
-
-      if(!child.Validate()) {
-      }
     }
 
     private void M2(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot) {
-        Tour tour = FindTour(child, u);
+        Tour tour = FindTour(child, u + 1);
         int iu = tour.Cities.IndexOf(u + 1);
         if (iu < tour.Cities.Count - 1) {
@@ -272 +269 @@
 
           if (v == depot) {
-            tour = FindTour(child, u);
+            tour = FindTour(child, u + 1);
             v = tour.Cities[0] - 1;
             InsertBefore(u, x, v, parent, child);
@@ -280 +277 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M3(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot) {
-        Tour tour = FindTour(child, u);
+        Tour tour = FindTour(child, u + 1);
         int iu = tour.Cities.IndexOf(u + 1);
         if (iu < tour.Cities.Count - 1) {
@@ -293 +287 @@
 
           if (v == depot) {
-            tour = FindTour(child, u);
+            tour = FindTour(child, u + 1);
             v = tour.Cities[0] - 1;
             InsertBefore(x, u, v, parent, child);
@@ -301 +295 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
@@ -310 +301 @@
         Swap(u, v, parent, child);
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M5(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot && v != depot) {
-        Tour tour = FindTour(child, u);
+        Tour tour = FindTour(child, u + 1);
         int iu = tour.Cities.IndexOf(u + 1);
         if (iu < tour.Cities.Count - 1) {
@@ -326 +314 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M6(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot && v != depot) {
-        Tour tour = FindTour(child, u);
+        Tour tour = FindTour(child, u + 1);
         int iu = tour.Cities.IndexOf(u + 1);
         if (iu < tour.Cities.Count - 1) {
           int x = tour.Cities[iu + 1] - 1;
 
-          tour = FindTour(child, v);
+          tour = FindTour(child, v + 1);
           int iv = tour.Cities.IndexOf(v + 1);
           if (iv < tour.Cities.Count - 1) {
@@ -348 +333 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M7(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot && v != depot) {
-        Tour tu = FindTour(child, u);
-        Tour tv = FindTour(child, v);
+        Tour tu = FindTour(child, u + 1);
+        Tour tv = FindTour(child, v + 1);
 
         if (tu.Cities[0] == tv.Cities[0]) {
@@ -373 +355 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M8(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot && v != depot) {
-        Tour tu = FindTour(child, u);
-        Tour tv = FindTour(child, v);
+        Tour tu = FindTour(child, u + 1);
+        Tour tv = FindTour(child, v + 1);
 
         if (tu.Cities[0] != tv.Cities[0]) {
@@ -398 +377 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
     private void M9(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
       if (u != depot && v != depot) {
-        Tour tu = FindTour(child, u);
-        Tour tv = FindTour(child, v);
+        Tour tu = FindTour(child, u + 1);
+        Tour tv = FindTour(child, v + 1);
 
         if (tu.Cities[0] != tv.Cities[0]) {
@@ -423 +399 @@
         }
       }
-
-      if (!child.Validate()) {
-      }
     }
 
@@ -492 +465 @@
         return null;
     }
-
-    protected override void Manipulate(IRandom random, PrinsEncoding individual) {
-      List<Tour> tours = individual.GetTours(DistanceMatrixParameter);
-      bool improvement = false;
-      int iterations = 0;
-
-      do {
-        int u = depot;
-        improvement = false;
-        double originalQuality = GetQuality(individual);
-        PrinsEncoding child = null;
-
-        while (!improvement && u < Cities) {
-          int v = depot;
-          while (!improvement && v < Cities) {
-            if (u != v) {
-              child = Manipulate(individual,
-                originalQuality, u, v);
-
-              improvement = child != null;
-            }
-            v++;
-          }
-          u++;
-        }
-
-        if (improvement) {
-          for (int i = 0; i < child.Length; i++) {
-            individual[i] = child[i];
-          }
-        }
-
-        iterations++;
-      } while (improvement && 
-        iterations < Iterations.Value.Value);
-    }
   }
 }