Changeset 11192 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs
- Timestamp:
- 07/16/14 10:02:10 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs
r11191 r11192 94 94 let distance = distances[startPoint, i] + distances[i, endPoint] + fixedPenalty 95 95 where distance <= maxDistance && i != startPoint && i != endPoint 96 select new { Distance = distance, Index = i, Score = scores[i]};96 select new { Index = i, Score = scores[i], Distance = distance }; 97 97 98 98 var orderedFeasiblePoints = feasiblePoints.OrderByDescending(p => p.Score).ToList(); … … 103 103 endPoint 104 104 }; 105 double length = distances[startPoint, endPoint]; 105 106 106 107 // Add points in a greedy way … … 109 110 insertionPerformed = false; 110 111 111 for (int i = 0; i < orderedFeasiblePoints.Count; i++) {112 for (int position = 1; position < tour.Count; position++) {112 for (int candidatePoint = 0; candidatePoint < orderedFeasiblePoints.Count; candidatePoint++) { 113 for (int insertPosition = 1; insertPosition < tour.Count; insertPosition++) { 113 114 // Create the candidate tour 114 var candidateTour = new List<int>(tour); 115 candidateTour.Insert(position, orderedFeasiblePoints[i].Index); 116 double length = CalculateTourLength(candidateTour); 115 double detour = distances.CalculateInsertionCost(tour, orderedFeasiblePoints[candidatePoint].Index, insertPosition, fixedPenalty); 117 116 118 117 // If the insertion would be feasible, perform it 119 if (length <= maxDistance) { 120 tour = candidateTour; 121 orderedFeasiblePoints.RemoveAt(i); 118 if (length + detour <= maxDistance) { 119 tour.Insert(insertPosition, orderedFeasiblePoints[candidatePoint].Index); 120 length += detour; 121 orderedFeasiblePoints.RemoveAt(candidatePoint); 122 122 insertionPerformed = true; 123 123 break; … … 130 130 return new IntegerVector(tour.ToArray()); 131 131 } 132 133 134 private double CalculateTourLength(IList<int> path) {135 var distances = DistanceMatrixParameter.ActualValue;136 var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;137 138 double length = 0.0;139 140 for (int i = 1; i < path.Count; i++) {141 length += distances[i - 1, i];142 }143 // Add the fixed penalty for every vertex except for the starting and ending vertex144 if (path.Count > 1) {145 if (path[path.Count - 1] == TerminusPointParameter.ActualValue.Value) length += ((path.Count - 2.0) * fixedPenalty);146 else length += ((path.Count - 1.0) * fixedPenalty);147 }148 149 return length;150 }151 132 } 152 133 }
Note: See TracChangeset
for help on using the changeset viewer.