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

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

Files:

• Alba/AlbaEncoding.cs (modified) (4 diffs)
• Potvin/Crossovers/PotvinCrossover.cs (added)
• Potvin/Crossovers/PotvinSBXCrossover.cs (added)
• Potvin/Manipulators/Potvin1MManipulator.cs (added)
• Potvin/Manipulators/Potvin2MManipulator.cs (added)
• Potvin/Manipulators/PotvinManipulator.cs (added)
• Potvin/PotvinEncoding.cs (modified) (7 diffs)
• Tour.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/AlbaEncoding.cs

@@ -42 +42 @@
         for (int i = 0; i < this.array.Length; i++) {
           if (this.array[i] >= cities) {
-            if (tour.Count > 0) {
+            if (tour.Cities.Count > 0) {
               result.Add(tour);
 
@@ -48 +48 @@
             }
           } else {
-            tour.Add(new IntValue(this.array[i] + 1));
+            tour.Cities.Add(this.array[i] + 1);
           }
         }
 
-        if (tour.Count > 0) {
+        if (tour.Cities.Count > 0) {
           result.Add(tour);
         }
@@ -97 +97 @@
       int cities = 0;
       foreach (Tour tour in tours) {
-        cities += tour.Count;
+        cities += tour.Cities.Count;
       }
 
@@ -107 +107 @@
 
       foreach (Tour tour in tours) {
-        foreach (IntValue city in tour) {
-            array[arrayIndex] = city.Value - 1;
+        foreach (int city in tour.Cities) {
+            array[arrayIndex] = city - 1;
             arrayIndex++;
         }

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;
+    }
   }
 }

trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Tour.cs

@@ -22 +22 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using System.Collections.Generic;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings {
-  public class Tour : ItemList<IntValue> {
+  [StorableClass]
+  public class Tour : Item {
+    [Storable]
+    public List<int> Cities { get; private set; }
+
+    public Tour() {
+      Cities = new List<int>();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      Tour clone = base.Clone(cloner) as Tour;
+      clone.Cities = new List<int>(Cities);
+
+      return clone;
+    }
+
+    public bool Feasible(DoubleArray dueTimeArray,
+      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
+      TourEvaluation eval = VRPEvaluator.EvaluateTour(this,
+        dueTimeArray,
+        serviceTimeArray,
+        readyTimeArray,
+        demandArray,
+        capacity,
+        new DoubleValue(0),
+        new DoubleValue(0),
+        new DoubleValue(0),
+        new DoubleValue(1),
+        new DoubleValue(1),
+        coordinates,
+        distanceMatrix,
+        useDistanceMatrix);
+
+      return eval.Overload < double.Epsilon && eval.Tardiness < double.Epsilon;
+    }
+    
+    public double GetLength(DoubleMatrix coordinates, 
+      ILookupParameter<DoubleMatrix> distanceMatrix, 
+      BoolValue useDistanceMatrix) {
+      double length = 0;
+
+      if (Cities.Count > 0) {
+        List<int> cities = new List<int>();
+        cities.Add(0);
+        foreach (int city in Cities) {
+          cities.Add(city);
+        }
+        cities.Add(0);
+
+        for (int i = 1; i < cities.Count; i++) {
+          length += VRPUtilities.GetDistance(
+            cities[i - 1], cities[i], coordinates, distanceMatrix, useDistanceMatrix); 
+        }
+      }
+
+      return length;
+    }
   }
 }