Changeset 5201 for branches/VRP

Timestamp:

01/03/11 16:18:37 (13 years ago)

Author:

svonolfe

Message:

Fixed some Problems with the Alba Encoding (#1177)

Location:

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

Files:

• AlbaEncoding.cs (modified) (1 diff)
• Creators/PushForwardInsertionCreator.cs (modified) (7 diffs)
• Moves/LambdaInterchange/AlbaStochasticLambdaInterchangeSingleMoveGenerator.cs (modified) (1 diff)

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

@@ -102 +102 @@
       route.RemoveAt(routeParam.Count - 1);
       
-      int cities = 0;
-      for (int i = 0; i < route.Count; i++) {
-        if (route[i] != 0) {
-          cities++;
-        }
-      }
+      int cities = instance.Cities.Value;
 
       int vehicle = cities;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs

@@ -30 +30 @@
 using HeuristicLab.Problems.VehicleRouting.Variants;
 using HeuristicLab.Common;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
@@ -83 +84 @@
 
     // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
-    private double Gauss(IRandom random) {
+    private static double Gauss(IRandom random) {
       double u = 0.0, v = 0.0, s = 0.0;
       do {
@@ -93 +94 @@
     }
 
-    private double N(double mu, double sigma, IRandom random) {
+    private static double N(double mu, double sigma, IRandom random) {
       return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
     }
 
-    private double Distance(int start, int end) {
-      return ProblemInstance.GetDistance(start, end);
-    }
-
-    private double TravelDistance(List<int> route, int begin) {
+    private static double Distance(IVRPProblemInstance problemInstance, int start, int end) {
+      return problemInstance.GetDistance(start, end);
+    }
+
+    private static double TravelDistance(IVRPProblemInstance problemInstance, List<int> route, int begin) {
       double distance = 0;
       for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
-        distance += Distance(route[i], route[i + 1]);
+        distance += Distance(problemInstance, route[i], route[i + 1]);
       }
       return distance;
     }
 
-    private bool SubrouteConstraintsOK(List<int> route, int begin) {     
-      Tour subroute = new Tour();
-      subroute.Stops.AddRange(route.GetRange(begin,
-          route.Count - begin));
-
-      return ProblemInstance.Feasible(subroute);
-    }
-
-    protected override List<int> CreateSolution() {
+    private static bool SubrouteConstraintsOK(IVRPProblemInstance problemInstance, List<int> route, int begin) {
+      AlbaEncoding solution = AlbaEncoding.ConvertFrom(route, problemInstance);
+
+      return problemInstance.Feasible(solution);
+    }
+
+    public static List<int> CreateSolution(IVRPProblemInstance problemInstance, IRandom random, 
+      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
+      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
       double alpha, beta, gamma;
-      alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
-      beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
-      gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
-
-      double x0 = ProblemInstance.Coordinates[0, 0];
-      double y0 = ProblemInstance.Coordinates[0, 1];
+      alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);
+      beta = N(betaValue, Math.Sqrt(betaVariance), random);
+      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
+
+      double x0 = problemInstance.Coordinates[0, 0];
+      double y0 = problemInstance.Coordinates[0, 1];
       double distance = 0;
       double cost = 0;
@@ -138 +139 @@
        *-----------------------------------------------------------------------------
        */
-      for (int i = 1; i <= ProblemInstance.Cities.Value; i++) {
-        distance = Distance(i, 0);
-        if (ProblemInstance.Coordinates[i, 0] < x0) distance = -distance;
+      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
+        distance = Distance(problemInstance, i, 0);
+        if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
 
         cost = -alpha * distance + // distance 0 <-> City[i]
-               beta * (ProblemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
-               gamma * (Math.Asin((ProblemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
+               beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
+               gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
 
         index = 0;
@@ -161 +162 @@
       int customer = -1;
       int subTourCount = 1;
-      List<int> route = new List<int>(ProblemInstance.Cities.Value + ProblemInstance.Vehicles.Value - 1);
+      List<int> route = new List<int>(problemInstance.Cities.Value + problemInstance.Vehicles.Value - 1);
       minimumCost = double.MaxValue;
       indexOfMinimumCost = -1;
@@ -176 +177 @@
             route.Insert(i, (int)unroutedList[c]);
             if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
-            cost = TravelDistance(route, currentRoute);
-            if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute)) {
+            cost = TravelDistance(problemInstance, route, currentRoute);
+            if (cost < minimumCost && SubrouteConstraintsOK(problemInstance, route, currentRoute)) {
               minimumCost = cost;
               indexOfMinimumCost = i;
@@ -207 +208 @@
         customer = -1;
       } while (unroutedList.Count > 0);
-      while (route.Count < ProblemInstance.Cities.Value + ProblemInstance.Vehicles.Value)
+      while (route.Count < problemInstance.Cities.Value + problemInstance.Vehicles.Value)
         route.Add(0);
 
       return route;
+    }
+
+    protected override List<int> CreateSolution() {
+      return CreateSolution(ProblemInstance, RandomParameter.ActualValue,
+        Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,
+        AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);
     }
   }

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

@@ -67 +67 @@
       List<Tour> tours = individual.GetTours();
 
-      int route1Index = rand.Next(tours.Count);
-      Tour route1 = tours[route1Index];
+      if (tours.Count > 1) {
+        int route1Index = rand.Next(tours.Count);
+        Tour route1 = tours[route1Index];
 
-      int route2Index = rand.Next(tours.Count - 1);
-      if (route2Index >= route1Index)
-        route2Index += 1;
-      Tour route2 = tours[route2Index];
+        int route2Index = rand.Next(tours.Count - 1);
+        if (route2Index >= route1Index)
+          route2Index += 1;
 
-      int length1 = rand.Next(Math.Min(lambda + 1, route1.Stops.Count + 1));
-      int index1 = rand.Next(route1.Stops.Count - length1 + 1);
+        Tour route2 = tours[route2Index];
 
-      int l2Min = 0;
-      if (length1 == 0)
-        l2Min = 1;
-      int length2 = rand.Next(l2Min, Math.Min(lambda + 1, route2.Stops.Count + 1));
-      int index2 = rand.Next(route2.Stops.Count - length2 + 1);
+        int length1 = rand.Next(Math.Min(lambda + 1, route1.Stops.Count + 1));
+        int index1 = rand.Next(route1.Stops.Count - length1 + 1);
 
-      return new AlbaLambdaInterchangeMove(route1Index, index1, length1, route2Index, index2, length2, individual);
+        int l2Min = 0;
+        if (length1 == 0)
+          l2Min = 1;
+        int length2 = rand.Next(l2Min, Math.Min(lambda + 1, route2.Stops.Count + 1));
+        int index2 = rand.Next(route2.Stops.Count - length2 + 1);
+
+        return new AlbaLambdaInterchangeMove(route1Index, index1, length1, route2Index, index2, length2, individual);
+      } else {
+        return new AlbaLambdaInterchangeMove(0, 0, 0, 0, 0, 0, individual);
+      }
     }