Changeset 11228 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering

Timestamp:

07/29/14 15:43:47 (10 years ago)

Author:

pfleck

Message:

#2208:

• Fixed bugs in cost calculation of insertion and replacement
• Rewritten Cleanup of infeasible tours
• Small refactoring

Location:

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3

Files:

• Creators/GreedyOrienteeringTourCreator.cs (modified) (2 diffs)
• DistanceMatrix.cs (modified) (1 diff)
• Improvers/OrienteeringLocalImprovementOperator.cs (modified) (8 diffs)
• Shakers/OrienteeringShakingOperator.cs (modified) (11 diffs)

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs

@@ -90 +90 @@
 
       // Find all points within the maximum distance allowed (ellipse)
-      var feasiblePoints =
-        from i in Enumerable.Range(0, numPoints)
-        let distance = distances[startPoint, i] + distances[i, endPoint] + fixedPenalty
-        where distance <= maxDistance && i != startPoint && i != endPoint
-        select new { Index = i, Score = scores[i], Distance = distance };
-
-      var orderedFeasiblePoints = feasiblePoints.OrderByDescending(p => p.Score).ToList();
+      var feasiblePoints = (
+        from point in Enumerable.Range(0, numPoints)
+        let distance = distances[startPoint, point] + distances[point, endPoint] + fixedPenalty
+        let score = scores[point]
+        where distance <= maxDistance
+        where point != startPoint && point != endPoint
+        orderby score descending
+        select point
+      ).ToList();
 
       // Add the starting and terminus point
@@ -110 +112 @@
         insertionPerformed = false;
 
-        for (int candidatePoint = 0; candidatePoint < orderedFeasiblePoints.Count; candidatePoint++) {
+        for (int i = 0; i < feasiblePoints.Count; i++) {
           for (int insertPosition = 1; insertPosition < tour.Count; insertPosition++) {
             // Create the candidate tour
-            double detour = distances.CalculateInsertionCosts(tour, orderedFeasiblePoints[candidatePoint].Index, insertPosition, fixedPenalty);
+            double detour = distances.CalculateInsertionCosts(tour, insertPosition, feasiblePoints[i], fixedPenalty);
 
             // If the insertion would be feasible, perform it
             if (length + detour <= maxDistance) {
-              tour.Insert(insertPosition, orderedFeasiblePoints[candidatePoint].Index);
+              tour.Insert(insertPosition, feasiblePoints[i]);
               length += detour;
-              orderedFeasiblePoints.RemoveAt(candidatePoint);
+              feasiblePoints.RemoveAt(i);
               insertionPerformed = true;
               break;

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs

@@ -55 +55 @@
     public double CalculateTourLength(IList<int> path, double fixedPenalty) {
       double length = 0.0;
-
-      for (int i = 1; i < path.Count; i++) {
-        length += this[i - 1, i];
-      }
-
+      for (int i = 1; i < path.Count; i++)
+        length += this[path[i - 1], path[i]];
       // Add the fixed penalty for every vertex except for the starting and ending vertex
       length += (path.Count - 2) * fixedPenalty;
-
       return length;
     }
-
-    public double CalculateInsertionCosts(IList<int> path, int pointPosition, int insertPosition, double fixedPenalty) {
-      double detour = this[path[insertPosition - 1], pointPosition] + this[pointPosition, path[insertPosition]];
+    public double CalculateInsertionCosts(IList<int> path, int insertPosition, int point, double fixedPenalty) {
+      double detour = this[path[insertPosition - 1], point] + this[point, path[insertPosition]];
       detour += fixedPenalty;
       detour -= this[path[insertPosition - 1], path[insertPosition]];
       return detour;
     }
-
-    public double CalculateReplacementCosts(List<int> path, int pointPosition, int replacementPosition) {
-      double detour = this[pointPosition - 1, replacementPosition] + this[replacementPosition, pointPosition + 1];
-      detour -= this[pointPosition - 1, pointPosition] + this[pointPosition, pointPosition + 1];
+    public double CalculateReplacementCosts(List<int> path, int replacePosition, int point) {
+      double detour = this[path[replacePosition - 1], point] + this[point, path[replacePosition + 1]];
+      detour -= this[path[replacePosition - 1], path[replacePosition]] + this[path[replacePosition], path[replacePosition + 1]];
       return detour;
+    }
+    public double CalculateRemovementSaving(List<int> path, int removePosition, double fixedPenalty) {
+      double saving = this[path[removePosition - 1], path[removePosition]];
+      saving += this[path[removePosition], path[removePosition + 1]];
+      saving -= this[path[removePosition - 1], path[removePosition + 1]];
+      saving += fixedPenalty;
+      return saving;
     }
   }

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

@@ -51 +51 @@
           if (value != null && !(value is OrienteeringProblem))
             throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
-          //if (problem != null) DeregisterProblemEventHandlers();
           problem = (OrienteeringProblem)value;
-          //if (problem != null) RegisterProblemEventHandlers();
-          //UpdateProblem();
         }
       }
@@ -64 +61 @@
 
     #region Parameter Properties
-
     public ILookupParameter<IntegerVector> IntegerVectorParameter {
       get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }
@@ -104 +100 @@
       : base(original, cloner) {
       this.problem = cloner.Clone(original.problem);
-      //RegisterEventHandlers();
     }
     public OrienteeringLocalImprovementOperator()
@@ -115 +110 @@
       Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
       Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
+
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
-
-      //RegisterEventHandlers();
     }
 
@@ -126 +120 @@
     }
 
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      //RegisterEventHandlers();
-    }
-
     public override IOperation Apply() {
-      // TODO Use LocalImprovementorOperator Parameters
-
       int numPoints = ScoresParameter.ActualValue.Length;
       var distances = DistanceMatrixParameter.ActualValue;
       var scores = ScoresParameter.ActualValue;
       double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
+      double maxLength = MaximumDistanceParameter.ActualValue.Value;
 
       bool optimizationDone = true;
 
-      // Find the maximum distance restriction
-      double maxLength = MaximumDistanceParameter.ActualValue.Value;
-
       var tour = IntegerVectorParameter.ActualValue.ToList();
 
       double tourLength = distances.CalculateTourLength(tour, fixedPenalty);
-      double score = tour.Sum(p => scores[p]);
+      double tourScore = tour.Sum(point => scores[point]);
 
       // Check if the tour can be improved by adding or replacing points
@@ -167 +152 @@
         ReplacePoints(tour, visitablePoints,
           distances, maxLength, scores,
-          ref tourLength, ref score, ref optimizationDone);
-      }
-
+          ref tourLength, ref tourScore, ref optimizationDone);
+      }
+
+      // Set new tour
       IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
 
@@ -193 +179 @@
 
             double newLength = tourLength;
-            for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) {
-              newLength -= distances[tour[counterLength], tour[counterLength + 1]];
-            }
-            for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) {
-              newLength += distances[tour[counterLength], tour[counterLength - 1]];
-            }
+            // Recalculate length of whole swapped part, in case distances are not symmetric
+            for (int index = position - 1; index < position + blockLength; index++) newLength -= distances[tour[index], tour[index + 1]];
+            for (int index = position + blockLength - 1; index > position; index--) newLength += distances[tour[index], tour[index - 1]];
             newLength += distances[tour[position - 1], tour[position + blockLength - 1]];
             newLength += distances[tour[position], tour[position + blockLength]];
 
-
-            if (newLength <= (tourLength - 0.00001)) { // Avoid cycling caused by precision
-              var partPath = tour.GetRange(position, blockLength);
+            if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision
+              var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();
 
               tour.RemoveRange(position, blockLength);
-              tour.InsertRange(position, partPath.AsEnumerable().Reverse());
+              tour.InsertRange(position, reversePart);
 
               tourLength = newLength;
@@ -263 +245 @@
           double newPointScore = scores[visitablePoints[i]];
 
-          if (tourLength + detour <= maxLength && newPointScore > oldPointScore) {
+          if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) {
             // Replace the old point by the new one
             tour[tourPosition] = visitablePoints[i];

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

@@ -52 +52 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
     }
-
     public ILookupParameter<IntValue> NeighborhoodCountParameter {
       get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
@@ -58 +57 @@
     #endregion
 
+    #region Parameter Properties
     public ILookupParameter<IntegerVector> IntegerVectorParameter {
       get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
@@ -83 +83 @@
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
+    #endregion
 
     [StorableConstructor]
@@ -88 +89 @@
     private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
       : base(original, cloner) {
-      //RegisterEventHandlers();
     }
     public OrienteeringShakingOperator()
@@ -94 +94 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
       Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));
-      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
 
       Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
@@ -104 +103 @@
       Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
 
-      //RegisterEventHandlers();
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
       return new OrienteeringShakingOperator(this, cloner);
-    }
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      //RegisterEventHandlers();
     }
 
@@ -138 +132 @@
 
       // Find all points that are not yet included in the tour and are
-      // within the maximum distance allowed (ellipse) and sort them with
-      // regard to their utility 
+      // within the maximum distance allowed (ellipse)
+      // and sort them with regard to their utility 
       var visitablePoints = (
-          from i in Enumerable.Range(0, numPoints)
-          // Calculate the distance when going from the starting point to this point and then to the end point
-          let distance = distances[startingPoint, i] + distances[i, terminusPoint] + fixedPenalty
-          // If this distance is feasible and the point is neither starting nor ending point, check the point
-          where distance < maxDistance && i != startingPoint && i != terminusPoint
-          // The point was not yet visited, so add it to the candidate list
-          where !initialTour.Contains(i)
-          // Calculate the utility of the point at this position
-          let utility = scores[i]
-          orderby utility
-          select i
-        ).ToList();
+        from point in Enumerable.Range(0, numPoints)
+        // Calculate the distance when going from the starting point to this point and then to the end point
+        let distance = distances[startingPoint, point] + distances[point, terminusPoint] + fixedPenalty
+        // If this distance is feasible and the point is neither starting nor ending point, check the point
+        where distance < maxDistance && point != startingPoint && point != terminusPoint
+        // The point was not yet visited, so add it to the candidate list
+        where !initialTour.Contains(point)
+        // Calculate the utility of the point at this position
+        let utility = scores[point]
+        orderby utility
+        select point
+      ).ToList();
+
+      // Initialize the new tour
+      var actualTour = new List<int> { startingPoint };
+
+      // Perform the insertions according to the utility sorting
+      InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
+
+      // Bring the tour back to be feasible 
+      CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
+
+      // Set new Tour
+      IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
+
+      return base.Apply();
+    }
+    private void InsertPoints(List<int> actualTour, IntegerVector initialTour,
+      int neighborhood, List<int> visitablePoints, IRandom random) {
 
       // Elect the starting index of the part to be replaced
@@ -158 +169 @@
       int randomPosition = random.Next(tourSize - neighborhood - 2) + 1;
 
-      // Initialize the new tour
-      var actualTour = new List<int> { startingPoint };
-
-      // Perform the insertions according to the utility sorting
       for (int position = 1; position < tourSize; position++) {
         if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
@@ -170 +177 @@
           visitablePoints.Remove(initialTour[position]);
         } else {
+          // Point from within shaking range
           if (visitablePoints.Count > 0) {
             // Add the point with the highest utility from the candidate list
@@ -183 +191 @@
             // We don't have any points left that could be inserted so we can only re-insert
             // the removed and not already re-inserted points in a random order
-            for (int reinsertPosition = randomPosition;
-              reinsertPosition < (randomPosition + neighborhood);
-              reinsertPosition++) {
+            for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
               bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
 
@@ -198 +204 @@
         }
       }
-
-      // Bring the tour back to be feasible 
-      CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
-
-      // Set new Tour
-      IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
-
-      return base.Apply();
-    }
-
+    }
     private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
-      var distanceSavingsList = new List<double>();
-      var sortedPoints = new List<int>();
-
-      // Sort the points on the tour according to their score
-      int tourPointMax = actualTour.Count - 1;
-      for (int tourPoint = 1; tourPoint < tourPointMax; tourPoint++) {
-        double distanceSaving = distances[actualTour[tourPoint - 1], actualTour[tourPoint]];
-        distanceSaving += distances[actualTour[tourPoint], actualTour[tourPoint + 1]];
-        distanceSaving -= distances[actualTour[tourPoint - 1], actualTour[tourPoint + 1]];
-
-        bool inserted = false;
-        int sortMax = sortedPoints.Count;
-        for (int sortCounter = 0; sortCounter < sortMax; sortCounter++) {
-          if (distanceSaving > distanceSavingsList[sortCounter]) {
-            distanceSavingsList.Insert(sortCounter, distanceSaving);
-            sortedPoints.Insert(sortCounter, tourPoint);
-            inserted = true;
-            break;
+      // Sort the points on the tour according to their costs savings when removed
+      var distanceSavings = (
+        from removePosition in Enumerable.Range(1, actualTour.Count - 2)
+        let saving = distances.CalculateRemovementSaving(actualTour, removePosition, fixedPenalty)
+        orderby saving descending
+        select new SavingInfo { Index = removePosition, Saving = saving }
+      ).ToList();
+
+      double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);
+
+      // As long as the created path is infeasible, remove elements
+      while (tourLength > maxDistance) {
+        // Remove the point that frees the largest distance
+        actualTour.RemoveAt(distanceSavings[0].Index);
+        tourLength -= distanceSavings[0].Saving;
+
+        // Shift indices due to removal of a point in the tour
+        for (int i = 1; i < distanceSavings.Count; i++) {
+          if (distanceSavings[i].Index > distanceSavings[0].Index) {
+            distanceSavings[i].Index--;
+            // Note, distance savings are not updated after removal
           }
         }
-        if (!inserted) {
-          distanceSavingsList.Add(distanceSaving);
-          sortedPoints.Add(tourPoint);
-        }
+        distanceSavings.RemoveAt(0);
       }
-
-      // As long as the created path is infeasible, remove elements
-      while (distances.CalculateTourLength(actualTour, fixedPenalty) > maxDistance) {
-        // Remove the point that frees the largest distance
-        actualTour.RemoveAt(sortedPoints[0]);
-
-        int sortMax = sortedPoints.Count;
-        for (int sortCounter = 1; sortCounter < sortMax; sortCounter++) {
-          if (sortedPoints[sortCounter] > sortedPoints[0]) {
-            sortedPoints[sortCounter]--;
-          }
-        }
-        sortedPoints.RemoveAt(0);
-        distanceSavingsList.RemoveAt(0);
-      }
+    }
+    // 
+    private class SavingInfo {
+      public int Index;
+      public double Saving;
     }
   }