source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs @ 11226

#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.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("OrienteeringShakingOperator", @"The used neighborhood operator is based on a two point exchange move. A move in
the k-th neighborhood consists of removing k consecutive vertices from the tour, starting
at a randomly selected position. Afterwards, a sorted list of all vertices not yet included
in the current tour is built. The vertices are sorted in descending order with respect to the
objective value increase using the current weights. Out of the first three entries with the
highest ranking in this list, one randomly selected vertex is reinserted into the current tour
at the same position as the removed vertices. This way, l new vertices are inserted into the
tour. The largest neighborhood is a complete exchange of all vertices on the tour. 
The shaking procedure does not guarantee that the new tour does not exceed the cost
limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The
vertices are sorted in descending order with respect to costs saved when removing the vertex
from the tour. Vertices are removed as long as the cost limit is violated.
(Schilde et. al. 2009)")]
  [StorableClass]
  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {

    #region Shaking Parameter Properties
    public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
    }

    public ILookupParameter<IntValue> NeighborhoodCountParameter {
      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
    }
    #endregion

    public ILookupParameter<IntegerVector> IntegerVectorParameter {
      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
    }
    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<DistanceMatrix> DistanceMatrixParameter {
      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    }
    public ILookupParameter<DoubleArray> ScoresParameter {
      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
    }
    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
    }

    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    }

    [StorableConstructor]
    private OrienteeringShakingOperator(bool deserializing) : base(deserializing) { }
    private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
      : base(original, cloner) {
      //RegisterEventHandlers();
    }
    public OrienteeringShakingOperator()
      : base() {
      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."));
      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<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>("FixedPenalty", "The penalty for each visited vertex."));

      //RegisterEventHandlers();
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new OrienteeringShakingOperator(this, cloner);
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      //RegisterEventHandlers();
    }

    public override IOperation Apply() {
      var initialTour = IntegerVectorParameter.ActualValue;
      var distances = DistanceMatrixParameter.ActualValue;
      var scores = ScoresParameter.ActualValue;
      var startingPoint = StartingPointParameter.ActualValue.Value;
      var terminusPoint = TerminusPointParameter.ActualValue.Value;
      var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
      int numPoints = scores.Length;

      if (NeighborhoodCountParameter.ActualValue == null)
        NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
      else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;

      var random = RandomParameter.ActualValue;

      // Limit the neighborhood to the tour length
      int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
      int limit = initialTour.Length - 3;
      int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;

      // 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 
      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();

      // Elect the starting index of the part to be replaced
      int tourSize = initialTour.Length;
      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))) {
          // Copy from initial tour when outside shaking range
          actualTour.Add(initialTour[position]);

          // Delete this point from the candidate list
          visitablePoints.Remove(initialTour[position]);
        } else {
          if (visitablePoints.Count > 0) {
            // Add the point with the highest utility from the candidate list
            int randomFactor = random.Next(3);
            int insertionIndex = visitablePoints.Count - 1;
            if (visitablePoints.Count > 4) insertionIndex -= randomFactor;

            actualTour.Add(visitablePoints[insertionIndex]);

            // Delete this point from the candidate list
            visitablePoints.RemoveAt(insertionIndex);
          } else {
            // 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++) {
              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);

              if (!alreadyReinserted)
                visitablePoints.Add(initialTour[reinsertPosition]);
            }

            int randomIndex = random.Next(visitablePoints.Count - 1);
            actualTour.Add(visitablePoints[randomIndex]);
            visitablePoints.Clear();
          }
        }
      }

      // 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;
          }
        }
        if (!inserted) {
          distanceSavingsList.Add(distanceSaving);
          sortedPoints.Add(tourPoint);
        }
      }

      // 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);
      }
    }
  }
}