Index: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs
===================================================================
--- branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs	(revision 11192)
+++ branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs	(revision 11193)
@@ -66,10 +66,16 @@
     }
 
-    public double CalculateInsertionCost(IList<int> path, int point, int insertPosition, double fixedPenalty) {
-      double detour = this[path[insertPosition - 1], point] + this[point, path[insertPosition]];
+    public double CalculateInsertionCosts(IList<int> path, int pointPosition, int insertPosition, double fixedPenalty) {
+      double detour = this[path[insertPosition - 1], pointPosition] + this[pointPosition, 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];
+      return detour;
+    }
   }
 }
Index: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/HeuristicLab.Problems.Orienteering-3.3.csproj
===================================================================
--- branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/HeuristicLab.Problems.Orienteering-3.3.csproj	(revision 11192)
+++ branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/HeuristicLab.Problems.Orienteering-3.3.csproj	(revision 11193)
@@ -49,4 +49,5 @@
     <Compile Include="Creators\GreedyOrienteeringTourCreator.cs" />
     <Compile Include="DistanceMatrix.cs" />
+    <Compile Include="Improvers\OrienteeringLocalImprovementOperator.cs" />
     <Compile Include="Interfaces\IOrienteeringEvaluator.cs" />
     <Compile Include="Evaluators\OrienteeringEvaluator.cs" />
Index: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs
===================================================================
--- branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs	(revision 11193)
+++ branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs	(revision 11193)
@@ -0,0 +1,279 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.IntegerVectorEncoding;
+using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.Orienteering {
+  [Item("OrienteeringLocalImprovementOperator", @"Iterative improvement consists of three basic operators: shortening, vertex insert and vertex
+exchange. The shortening operator tries to rearrange the vertices within a tour in order to
+minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009)")]
+  [StorableClass]
+  public class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator, IStochasticOperator {
+    #region IGenericLocalImprovementOperator Properties
+    public Type ProblemType { get { return typeof(OrienteeringProblem); } }
+    public IProblem Problem {
+      get { return problem; }
+      set {
+        if (problem != value) {
+          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();
+        }
+      }
+    }
+    #endregion
+
+    [Storable]
+    private OrienteeringProblem problem;
+
+    #region Parameter Properties
+
+    public ILookupParameter<IntegerVector> IntegerVectorParameter {
+      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
+    }
+    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
+      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ILookupParameter<DoubleArray> ScoresParameter {
+      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
+    }
+    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
+    }
+    public ILookupParameter<IntValue> StartingPointParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
+    }
+    public ILookupParameter<IntValue> TerminusPointParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }
+    }
+    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
+    }
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
+    #region ILocalImprovementOperator Parameters
+    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
+    }
+    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
+    }
+    public ILookupParameter<ResultCollection> ResultsParameter {
+      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
+    }
+    #endregion
+    #endregion
+
+    [StorableConstructor]
+    private OrienteeringLocalImprovementOperator(bool deserializing) : base(deserializing) { }
+    private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner)
+      : base(original, cloner) {
+      this.problem = cloner.Clone(original.problem);
+      //RegisterEventHandlers();
+    }
+    public OrienteeringLocalImprovementOperator()
+      : base() {
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
+      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
+      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
+      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 LookupParameter<IRandom>("Random", "The random number generator to use."));
+      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();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new OrienteeringLocalImprovementOperator(this, cloner);
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      //RegisterEventHandlers();
+    }
+
+    public override IOperation Apply() {
+      int numPoints = ScoresParameter.ActualValue.Length;
+      var distances = DistanceMatrixParameter.ActualValue;
+      var scores = ScoresParameter.ActualValue;
+      double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
+
+      bool optimizationDone = true;
+      bool isFeasible = 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]);
+
+      // Check if the tour can be improved by adding or replacing points
+      while (optimizationDone) {
+        optimizationDone = false;
+
+        // Try to shorten the path
+        ShortenPath(tour, distances, ref tourLength);
+
+        // Determine all points that have not yet been visited by this tour
+        var visitablePoints = Enumerable.Range(0, numPoints).Except(tour).ToList();
+
+        // Determine if any of the visitable points can be included at any position within the tour
+        IncludeNewPoints(tour, visitablePoints,
+          distances, fixedPenalty, maxLength,
+          ref tourLength, ref optimizationDone);
+
+        // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
+        ReplacePoints(tour, visitablePoints,
+          distances, maxLength, scores,
+          ref tourLength, ref score, ref optimizationDone);
+      }
+
+      IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
+
+      return base.Apply();
+    }
+
+    private void ShortenPath(List<int> tour, DistanceMatrix distances, ref double tourLength) {
+      bool optimizationDone = true;
+      int pathSize = tour.Count;
+      int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2);
+
+      // Perform a 2-opt
+      while (optimizationDone) {
+        optimizationDone = false;
+
+        for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) {
+          // If an optimization has been done, start from the beginning
+          if (optimizationDone) break;
+
+          for (int position = 1; position < (pathSize - blockLength); position++) {
+            // If an optimization has been done, start from the beginning
+            if (optimizationDone) break;
+
+            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]];
+            }
+            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);
+
+              tour.RemoveRange(position, blockLength);
+              tour.InsertRange(position, partPath.AsEnumerable().Reverse());
+
+              tourLength = newLength;
+
+              // Re-run the optimization
+              optimizationDone = true;
+            }
+          }
+        }
+      }
+    }
+    private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
+      DistanceMatrix distances, double fixedPenalty, double maxLength,
+      ref double tourLength, ref bool optimizationDone) {
+
+      for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
+        // If an optimization has been done, start from the beginning
+        if (optimizationDone) break;
+
+        for (int i = 0; i < visitablePoints.Count; i++) {
+          // If an optimization has been done, start from the beginning
+          if (optimizationDone) break;
+
+          double detour = distances.CalculateInsertionCost(tour, tourPosition, visitablePoints[i], fixedPenalty);
+
+          // Determine if including the point does not violate any constraint
+          if (tourLength + detour <= maxLength) {
+            // Insert the new point at this position
+            tour.Insert(tourPosition, visitablePoints[i]);
+
+            // Update the overall tour tourLength
+            tourLength += detour;
+
+            // Re-run this optimization
+            optimizationDone = true;
+          }
+        }
+      }
+    }
+    private void ReplacePoints(List<int> tour, List<int> visitablePoints,
+      DistanceMatrix distances, double maxLength, DoubleArray scores,
+      ref double tourLength, ref double tourScore, ref bool optimizationDone) {
+
+      for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) {
+        // If an optimization has been done, start from the beginning
+        if (optimizationDone) break;
+
+        for (int i = 0; i < visitablePoints.Count; i++) {
+          // If an optimization has been done, start from the beginning
+          if (optimizationDone) break;
+
+          double detour = distances.CalculateReplacementCost(tour, tourPosition, visitablePoints[i]);
+
+          double oldPointScore = scores[tour[tourPosition]];
+          double newPointScore = scores[visitablePoints[i]];
+
+          if (tourLength + detour <= maxLength && newPointScore > oldPointScore) {
+            // Replace the old point by the new one
+            tour[tourPosition] = visitablePoints[i];
+
+            // Update the overall tour tourLength
+            tourLength += detour;
+
+            // Update the scores achieved by visiting this point
+            tourScore += newPointScore - oldPointScore;
+
+            // Re-run this optimization
+            optimizationDone = true;
+          }
+        }
+      }
+    }
+  }
+}
