Changeset 7815

Timestamp:

05/14/12 17:55:41 (13 years ago)

Author:

svonolfe

Message:

Added first working version of VRP path relinker (#1331)

Location:

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3

Files:

• PathRelinkers/VRPPathRelinker.cs (modified) (5 diffs)
• SimilarityCalculators/VRPSimilarityCalculator.cs (modified) (5 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

@@ -30 +30 @@
 using HeuristicLab.Problems.VehicleRouting.Encodings;
 using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
+using HeuristicLab.Parameters;
+using HeuristicLab.Optimization;
 
 namespace HeuristicLab.Problems.VehicleRouting {
@@ -37 +39 @@
   [Item("VRPPathRelinker", "An operator that relinks paths between vehicle routing solutions.")]
   [StorableClass]
-  public sealed class VRPPathRelinker : PathRelinker {
+  public sealed class VRPPathRelinker : PathRelinker, IStochasticOperator {
+    #region Parameters
+    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
+      get {
+        if (Parameters.ContainsKey("Coordinates"))
+          return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
+      get {
+        if (Parameters.ContainsKey("DistanceMatrix"))
+          return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
+      get {
+        if (Parameters.ContainsKey("UseDistanceMatrix"))
+          return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<IntValue> VehiclesParameter {
+      get {
+        if (Parameters.ContainsKey("Vehicles"))
+          return (ILookupParameter<IntValue>)Parameters["Vehicles"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleValue> CapacityParameter {
+      get {
+        if (Parameters.ContainsKey("Capacity"))
+          return (ILookupParameter<DoubleValue>)Parameters["Capacity"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleArray> DemandParameter {
+      get {
+        if (Parameters.ContainsKey("Demand"))
+          return (ILookupParameter<DoubleArray>)Parameters["Demand"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleArray> ReadyTimeParameter {
+      get {
+        if (Parameters.ContainsKey("ReadyTime"))
+          return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleArray> DueTimeParameter {
+      get {
+        if (Parameters.ContainsKey("DueTime"))
+          return (ILookupParameter<DoubleArray>)Parameters["DueTime"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleArray> ServiceTimeParameter {
+      get {
+        if (Parameters.ContainsKey("ServiceTime"))
+          return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"];
+        else
+          return null;
+      }
+    }
+    public ILookupParameter<DoubleValue> FleetUsageFactor {
+      get { return (ILookupParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
+    }
+    public ILookupParameter<DoubleValue> TimeFactor {
+      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTimeFactor"]; }
+    }
+    public ILookupParameter<DoubleValue> DistanceFactor {
+      get { return (ILookupParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
+    }
+    public ILookupParameter<DoubleValue> OverloadPenalty {
+      get { return (ILookupParameter<DoubleValue>)Parameters["EvalOverloadPenalty"]; }
+    }
+    public ILookupParameter<DoubleValue> TardinessPenalty {
+      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTardinessPenalty"]; }
+    }
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
+    public IValueParameter<IntValue> SampleSizeParameter {
+      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
+    }
+    public IValueParameter<IntValue> IterationsParameter {
+      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
+    }
+    #endregion
+
     [StorableConstructor]
     private VRPPathRelinker(bool deserializing) : base(deserializing) { }
     private VRPPathRelinker(VRPPathRelinker original, Cloner cloner) : base(original, cloner) { }
-    public VRPPathRelinker() : base() { }
+    public VRPPathRelinker() : base() {
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
+      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
+      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
+      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
+      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
+      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
+      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
+      Parameters.Add(new LookupParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation."));
+      Parameters.Add(new LookupParameter<DoubleValue>("EvalTimeFactor", "The time factor considered in the evaluation."));
+      Parameters.Add(new LookupParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation."));
+      Parameters.Add(new LookupParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation."));
+      Parameters.Add(new LookupParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation."));
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+      Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(250)));
+      Parameters.Add(new ValueParameter<IntValue>("Iterations", new IntValue(50)));
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -47 +167 @@
     }
 
-    public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
-      PotvinEncoding sol1 = initiator.Clone() as PotvinEncoding;
-      PotvinEncoding sol2 = guide.Clone() as PotvinEncoding;
-      PotvinEncoding sol3 = new PotvinEncoding();
-
-      // match tours
-      foreach (Tour tour1 in sol1.Tours) {
-        int highestMatch = -1;
-        Tour bestMatchingTour = null;
-        foreach (Tour tour2 in sol2.Tours) {
-          int matchingCities = MatchingCities(tour1, tour2);
-          if (matchingCities > highestMatch) {
-            bestMatchingTour = tour2;
-            highestMatch = matchingCities;
+    private static int MatchingCities(Tour tour1, Tour tour2) {
+      return tour1.Cities.Intersect(tour2.Cities).Count();
+    }
+
+    private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide) {
+      PotvinEncoding result = new PotvinEncoding();
+
+      List<bool> used = new List<bool>();
+      for (int i = 0; i < initiator.Tours.Count; i++) {
+        used.Add(false);
+      }
+
+      for (int i = 0; i < guide.Tours.Count; i++) {
+        int bestMatch = -1;
+        int bestTour = -1;
+
+        for (int j = 0; j < initiator.Tours.Count; j++) {
+          if (!used[j]) {
+            int match = MatchingCities(guide.Tours[i], initiator.Tours[j]);
+            if (match > bestMatch) {
+              bestMatch = match;
+              bestTour = j;
+            }
           }
         }
-        sol2.Tours.Remove(bestMatchingTour);
-        sol3.Tours.Add(bestMatchingTour);
-      }
-      // add all remaining tours
-      sol3.Tours.AddRange(sol2.Tours);
-
-      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
-      // TODO: add local search
-
+
+        if (bestTour != -1) {
+          result.Tours.Add(initiator.Tours[bestTour]);
+          used[bestTour] = true;
+        }
+      }
+
+      for (int i = 0; i < initiator.Tours.Count; i++) {
+        if (!used[i])
+          result.Tours.Add(initiator.Tours[i]);
+      }
+
+      return result;
+    }
+
+    #region moves
+    public static void RelocateMove(PotvinEncoding individual, IRandom random) {
+      int cities = individual.Cities;
+      int city = 1 + random.Next(cities);
+      Tour originalTour = individual.Tours.Find(t => t.Cities.Contains(city));
+      //consider creating new route
+      individual.Tours.Add(new Tour());
+
+      int position = 1 + random.Next(cities + individual.Tours.Count - 1);
+      if (position >= city) {
+        position++;
+      }
+
+      int originalPosition = originalTour.Cities.IndexOf(city);
+      originalTour.Cities.RemoveAt(originalPosition);
+
+      Tour insertionTour;
+      int insertionPosition;
+      if (position <= cities) {
+        insertionTour = individual.Tours.Find(t => t.Cities.Contains(position));
+        insertionPosition = insertionTour.Cities.IndexOf(position) + 1;
+      } else {
+        insertionTour = individual.Tours[position - cities - 1];
+        insertionPosition = 0;
+      }
+
+      insertionTour.Cities.Insert(insertionPosition, city);
+
+      individual.Tours.RemoveAll(t => t.Cities.Count == 0);
+    }
+
+    public static void ExchangeMove(PotvinEncoding individual, IRandom random) {
+      if (individual.Tours.Count > 1) {
+        int tour1Idx = random.Next(individual.Tours.Count);
+        int tour2Idx = random.Next(individual.Tours.Count - 1);
+        if (tour2Idx >= tour1Idx)
+          tour2Idx++;
+
+        Tour tour1 = individual.Tours[tour1Idx];
+        Tour tour2 = individual.Tours[tour2Idx];
+
+        int index1 = random.Next(tour1.Cities.Count);
+        int city1 = tour1.Cities[index1];
+
+        int index2 = random.Next(tour2.Cities.Count);
+        int city2 = tour2.Cities[index2];
+
+        tour1.Cities.RemoveAt(index1);
+        tour1.Cities.Insert(index1, city2);
+
+        tour2.Cities.RemoveAt(index2);
+        tour2.Cities.Insert(index2, city1);
+      }
+    }
+
+    public static void TwoOptMove(PotvinEncoding individual, IRandom random) {
+      List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 4);
+
+      if (tours.Count > 0) {
+        int tourIdx = random.Next(tours.Count);
+        Tour tour = tours[tourIdx];
+
+        int a;
+        if (tour.Cities.Count == 4) {
+          a = 0;
+        } else if (tour.Cities.Count == 5) {
+          int idx = random.Next(4);
+          if (idx >= 2)
+            idx++;
+          a = idx;
+        } else {
+          a = random.Next(tour.Cities.Count);
+        }
+
+        int b;
+        List<int> indices = new List<int>();
+        for (int i = 0; i < tour.Cities.Count; i++) {
+          if (Math.Abs(i - a) > 2) {
+            indices.Add(i);
+          }
+        }
+        b = indices[random.Next(indices.Count)];
+
+        if (b < a) {
+          int tmp = a;
+          a = b;
+          b = tmp;
+        }
+
+        int index = a + 1;
+        int count = b - a - 1;
+        List<int> segment = tour.Cities.GetRange(index, count);
+        tour.Cities.RemoveRange(index, count);
+        segment.Reverse();
+        tour.Cities.InsertRange(index, segment);
+      }
+    }
+
+    public static void TwoOptStartMove(PotvinEncoding individual, IRandom random) {
+      //consider creating new tour
+      individual.Tours.Add(new Tour());
+
+      int route1Idx = random.Next(individual.Tours.Count);
+      int route2Idx = random.Next(individual.Tours.Count - 1);
+      if (route2Idx >= route1Idx)
+        route2Idx++;
+
+      Tour route1 = individual.Tours[route1Idx];
+      Tour route2 = individual.Tours[route2Idx];
+
+      int x1 = random.Next(route1.Cities.Count + 1);
+      int x2 = random.Next(route2.Cities.Count + 1);
+
+      int count = route1.Cities.Count - x1;
+      List<int> segmentX1 = new List<int>();
+      if (count > 0) {
+        segmentX1 = route1.Cities.GetRange(x1, count);
+        route1.Cities.RemoveRange(x1, count);
+      }
+
+      count = route2.Cities.Count - x2;
+      List<int> segmentX2 = new List<int>();
+      if (count > 0) {
+        segmentX2 = route2.Cities.GetRange(x2, count);
+        route2.Cities.RemoveRange(x2, count);
+      }
+
+      route1.Cities.AddRange(segmentX2);
+      route2.Cities.AddRange(segmentX1);
+
+      individual.Tours.RemoveAll(t => t.Cities.Count == 0);
+    }
+
+    public static void OrOptMove(PotvinEncoding individual, IRandom random) {
+      List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 2);
+
+      if (tours.Count > 0) {
+        int tourIdx = random.Next(tours.Count);
+        Tour tour = tours[tourIdx];
+
+        int segmentStart = random.Next(tour.Cities.Count);
+        int segmentLength;
+        if (segmentStart == 0) {
+          segmentLength = 1 + random.Next(tour.Cities.Count - 1);
+        } else {
+          segmentLength = 1 + random.Next(tour.Cities.Count - segmentStart);
+        }
+
+        List<int> segment = tour.Cities.GetRange(segmentStart, segmentLength);
+        tour.Cities.RemoveRange(segmentStart, segmentLength);
+        int newPos;
+        if (tour.Cities.Count == 1)
+          newPos = 0;
+        else
+          newPos = random.Next(tour.Cities.Count - 1);
+
+        if (newPos >= segmentStart)
+          newPos++;
+        tour.Cities.InsertRange(newPos, segment);
+      }
+    }
+    #endregion
+
+    private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
       IList<IItem> selection = new List<IItem>();
       if (solutions.Count > 0) {
@@ -81 +380 @@
       }
 
-      return new ItemArray<IItem>(selection);
-    }
-
-    private static int MatchingCities(Tour tour1, Tour tour2) {
-      return tour1.Cities.Intersect(tour2.Cities).Count();
+      return selection;
+    }
+
+    public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand,
+      IntValue vehicles, DoubleArray dueTimeArray,
+      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
+      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
+     
+      double sigma = 1.5;
+
+      DoubleValue currentOverloadPenalty = new DoubleValue(overloadPenalty.Value);
+      DoubleValue currentTardinessPenalty = new DoubleValue(tardinessPenalty.Value);
+
+      PotvinEncoding current = MatchTours(initiator, guide);
+      double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
+
+      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
+      int i = 0;
+      while(i < iterations && currentSimilarity != 1.0) {
+        TourEvaluation currentEval = VRPEvaluator.Evaluate(current,
+          vehicles, dueTimeArray, serviceTimeArray, readyTimeArray,
+          demandArray, capacity, fleetUsageFactor, timeFactor, distanceFactor,
+          currentOverloadPenalty, currentTardinessPenalty, 
+          coordinates, distanceMatrix, useDistanceMatrix);
+        currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
+
+        if (currentSimilarity < 1.0) {
+          for (int sample = 0; sample < sampleSize; sample++) {
+            PotvinEncoding next = current.Clone() as PotvinEncoding;
+
+            int neighborhood = rand.Next(5);
+            switch (neighborhood) {
+              case 0: RelocateMove(next, rand);
+                break;
+              case 1: ExchangeMove(next, rand);
+                break;
+              case 2: TwoOptMove(next, rand);
+                break;
+              case 3: TwoOptStartMove(next, rand);
+                break;
+              case 4: OrOptMove(next, rand);
+                break;
+            }
+
+            TourEvaluation nextEval = VRPEvaluator.Evaluate(next,
+              vehicles, dueTimeArray, serviceTimeArray, readyTimeArray,
+              demandArray, capacity, fleetUsageFactor, timeFactor, distanceFactor,
+              currentOverloadPenalty, currentTardinessPenalty,
+              coordinates, distanceMatrix, useDistanceMatrix);
+            double nextSimilarity = VRPSimilarityCalculator.CalculateSimilarity(next, guide);
+
+            if (nextSimilarity > currentSimilarity && nextEval.Quality <= currentEval.Quality) {
+              current = next;
+              solutions.Add(current);
+              break;
+            }
+          }
+
+          if (currentEval.Overload > 0)
+            currentOverloadPenalty.Value *= sigma;
+          else
+            currentOverloadPenalty.Value /= sigma;
+
+          if (currentEval.Tardiness > 0)
+            currentTardinessPenalty.Value *= sigma;
+          else
+            currentTardinessPenalty.Value /= sigma;
+
+          i++;
+        }
+      }
+
+      return new ItemArray<IItem>(ChooseSelection(solutions, n));
     }
 
@@ -91 +459 @@
       if (parents.Length != 2)
         throw new ArgumentException("The number of parents is not equal to 2.");
-      return Apply(parents[0], parents[1], n);
+
+      if(!(parents[0] is PotvinEncoding))
+        parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, DistanceMatrixParameter);
+      if (!(parents[1] is PotvinEncoding))
+        parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, DistanceMatrixParameter);
+
+      return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n, 
+        SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue,
+        VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
+        DemandParameter.ActualValue, CapacityParameter.ActualValue,
+        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
+        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
     }
   }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs

@@ -29 +29 @@
 using HeuristicLab.Problems.VehicleRouting.Encodings;
 using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
 
 namespace HeuristicLab.Problems.VehicleRouting {
@@ -37 +39 @@
   [StorableClass]
   public sealed class VRPSimilarityCalculator : SimilarityCalculator {
+    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
+      get {
+        if (Parameters.ContainsKey("DistanceMatrix"))
+          return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"];
+        else
+          return null;
+      }
+    }
+
     [StorableConstructor]
     private VRPSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private VRPSimilarityCalculator(VRPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
-    public VRPSimilarityCalculator() : base() { }
+    public VRPSimilarityCalculator() : base() {
+      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -46 +59 @@
     }
 
-    protected override double CalculateSimilarity(IScope left, IScope right) {
-      PotvinEncoding e1 = left.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
-      PotvinEncoding e2 = right.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
-
+    public static double CalculateSimilarity(PotvinEncoding e1, PotvinEncoding e2) {
       // extract edges from first solution
       var edges1 = new List<Tuple<int, int>>();
       foreach (Tour tour in e1.Tours) {
         edges1.Add(new Tuple<int, int>(0, tour.Cities[0]));
-        edges1.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
         for (int i = 0; i < tour.Cities.Count - 1; i++)
           edges1.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
+        edges1.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
       }
 
@@ -63 +73 @@
       foreach (Tour tour in e2.Tours) {
         edges2.Add(new Tuple<int, int>(0, tour.Cities[0]));
-        edges2.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
         for (int i = 0; i < tour.Cities.Count - 1; i++)
           edges2.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
+        edges2.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
       }
 
@@ -73 +83 @@
       int identicalEdges = 0;
       foreach (var edge in edges1) {
-        if (edges2.Any(x => x.Equals(edge) || x.Item1 == edge.Item2 && x.Item2 == edge.Item1))
+        if (edges2.Any(x => x.Equals(edge)))
           identicalEdges++;
       }
 
-      return identicalEdges * 2.0 / edges1.Count + edges2.Count;
+      return identicalEdges * 2.0 / (edges1.Count + edges2.Count);
+    }
+
+    protected override double CalculateSimilarity(IScope left, IScope right) {
+      IVRPEncoding e1 = left.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
+      if (!(e1 is PotvinEncoding))
+        e1 = PotvinEncoding.ConvertFrom(e1 as IVRPEncoding, DistanceMatrixParameter);
+
+      IVRPEncoding e2 = right.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
+      if (!(e2 is PotvinEncoding))
+        e2 = PotvinEncoding.ConvertFrom(e2 as IVRPEncoding, DistanceMatrixParameter);
+
+      return CalculateSimilarity(e1 as PotvinEncoding, e2 as PotvinEncoding);
     }
   }