Changeset 11192

Timestamp:

07/16/14 10:02:10 (10 years ago)

Author:

pfleck

Message:

#2208 improved GreedyTourCreator by using an iterative length calculation instead of re-evaluation.

Location:

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

Files:

• Creators/GreedyOrienteeringTourCreator.cs (modified) (4 diffs)
• DistanceMatrix.cs (modified) (1 diff)

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

@@ -94 +94 @@
         let distance = distances[startPoint, i] + distances[i, endPoint] + fixedPenalty
         where distance <= maxDistance && i != startPoint && i != endPoint
-        select new { Distance = distance, Index = i, Score = scores[i] };
+        select new { Index = i, Score = scores[i], Distance = distance };
 
       var orderedFeasiblePoints = feasiblePoints.OrderByDescending(p => p.Score).ToList();
@@ -103 +103 @@
         endPoint
       };
+      double length = distances[startPoint, endPoint];
 
       // Add points in a greedy way
@@ -109 +110 @@
         insertionPerformed = false;
 
-        for (int i = 0; i < orderedFeasiblePoints.Count; i++) {
-          for (int position = 1; position < tour.Count; position++) {
+        for (int candidatePoint = 0; candidatePoint < orderedFeasiblePoints.Count; candidatePoint++) {
+          for (int insertPosition = 1; insertPosition < tour.Count; insertPosition++) {
             // Create the candidate tour
-            var candidateTour = new List<int>(tour);
-            candidateTour.Insert(position, orderedFeasiblePoints[i].Index);
-            double length = CalculateTourLength(candidateTour);
+            double detour = distances.CalculateInsertionCost(tour, orderedFeasiblePoints[candidatePoint].Index, insertPosition, fixedPenalty);
 
             // If the insertion would be feasible, perform it
-            if (length <= maxDistance) {
-              tour = candidateTour;
-              orderedFeasiblePoints.RemoveAt(i);
+            if (length + detour <= maxDistance) {
+              tour.Insert(insertPosition, orderedFeasiblePoints[candidatePoint].Index);
+              length += detour;
+              orderedFeasiblePoints.RemoveAt(candidatePoint);
               insertionPerformed = true;
               break;
@@ -130 +130 @@
       return new IntegerVector(tour.ToArray());
     }
-
-
-    private double CalculateTourLength(IList<int> path) {
-      var distances = DistanceMatrixParameter.ActualValue;
-      var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
-
-      double length = 0.0;
-
-      for (int i = 1; i < path.Count; i++) {
-        length += distances[i - 1, i];
-      }
-      // Add the fixed penalty for every vertex except for the starting and ending vertex
-      if (path.Count > 1) {
-        if (path[path.Count - 1] == TerminusPointParameter.ActualValue.Value) length += ((path.Count - 2.0) * fixedPenalty);
-        else length += ((path.Count - 1.0) * fixedPenalty);
-      }
-
-      return length;
-    }
   }
 }

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

@@ -52 +52 @@
       return this;
     }
+
+    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];
+      }
+
+      // Add the fixed penalty for every vertex except for the starting and ending vertex
+      length += (path.Count - 2) * fixedPenalty;
+
+      return length;
+    }
+
+    public double CalculateInsertionCost(IList<int> path, int point, int insertPosition, double fixedPenalty) {
+      double detour = this[path[insertPosition - 1], point] + this[point, path[insertPosition]];
+      detour += fixedPenalty;
+      detour -= this[path[insertPosition - 1], path[insertPosition]];
+      return detour;
+    }
   }
 }