1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System.Collections.Generic;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.IntegerVectorEncoding;


28  using HeuristicLab.Operators;


29  using HeuristicLab.Optimization;


30  using HeuristicLab.Parameters;


31  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


32 


33  namespace HeuristicLab.Problems.Orienteering {


34  [Item("OrienteeringShakingOperator", @"The used neighborhood operator is based on a two point exchange move. A move in


35  the kth neighborhood consists of removing k consecutive vertices from the tour, starting


36  at a randomly selected position. Afterwards, a sorted list of all vertices not yet included


37  in the current tour is built. The vertices are sorted in descending order with respect to the


38  objective value increase using the current weights. Out of the first three entries with the


39  highest ranking in this list, one randomly selected vertex is reinserted into the current tour


40  at the same position as the removed vertices. This way, l new vertices are inserted into the


41  tour. The largest neighborhood is a complete exchange of all vertices on the tour.


42  The shaking procedure does not guarantee that the new tour does not exceed the cost


43  limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The


44  vertices are sorted in descending order with respect to costs saved when removing the vertex


45  from the tour. Vertices are removed as long as the cost limit is violated.


46  (Schilde et. al. 2009)")]


47  [StorableClass]


48  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {


49 


50  #region Shaking Parameter Properties


51  public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {


52  get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }


53  }


54  public ILookupParameter<IntValue> NeighborhoodCountParameter {


55  get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }


56  }


57  #endregion


58 


59  #region Parameter Properties


60  public ILookupParameter<IntegerVector> IntegerVectorParameter {


61  get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }


62  }


63  public ILookupParameter<DoubleValue> MaximumDistanceParameter {


64  get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }


65  }


66  public ILookupParameter<IntValue> StartingPointParameter {


67  get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }


68  }


69  public ILookupParameter<IntValue> TerminusPointParameter {


70  get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }


71  }


72  public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {


73  get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }


74  }


75  public ILookupParameter<DoubleArray> ScoresParameter {


76  get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }


77  }


78  public ILookupParameter<DoubleValue> FixedPenaltyParameter {


79  get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }


80  }


81 


82  public ILookupParameter<IRandom> RandomParameter {


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


84  }


85  #endregion


86 


87  [StorableConstructor]


88  private OrienteeringShakingOperator(bool deserializing) : base(deserializing) { }


89  private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)


90  : base(original, cloner) {


91  }


92  public OrienteeringShakingOperator()


93  : base() {


94  Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));


95  Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));


96 


97  Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));


98  Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));


99  Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));


100  Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));


101  Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));


102  Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));


103  Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));


104 


105  Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));


106  }


107 


108  public override IDeepCloneable Clone(Cloner cloner) {


109  return new OrienteeringShakingOperator(this, cloner);


110  }


111 


112  public override IOperation Apply() {


113  var initialTour = IntegerVectorParameter.ActualValue;


114  var distances = DistanceMatrixParameter.ActualValue;


115  var scores = ScoresParameter.ActualValue;


116  var startingPoint = StartingPointParameter.ActualValue.Value;


117  var terminusPoint = TerminusPointParameter.ActualValue.Value;


118  var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;


119  double maxDistance = MaximumDistanceParameter.ActualValue.Value;


120  int numPoints = scores.Length;


121 


122  if (NeighborhoodCountParameter.ActualValue == null)


123  NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);


124  else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;


125 


126  var random = RandomParameter.ActualValue;


127 


128  if (initialTour.Length > 2) {


129  // Limit the neighborhood to the tour length


130  int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;


131  int limit = initialTour.Length  2; // neighborhood limit within [0, changable tour length  1)


132  int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;


133 


134  // Find all points that are not yet included in the tour and are


135  // within the maximum distance allowed (ellipse)


136  // and sort them with regard to their utility


137  var visitablePoints = (


138  from point in Enumerable.Range(0, numPoints)


139  // Calculate the distance when going from the starting point to this point and then to the end point


140  let distance = distances[startingPoint, point] + distances[point, terminusPoint] + fixedPenalty


141  // If this distance is feasible and the point is neither starting nor ending point, check the point


142  where distance < maxDistance && point != startingPoint && point != terminusPoint


143  // The point was not yet visited, so add it to the candidate list


144  where !initialTour.Contains(point)


145  // Calculate the utility of the point at this position


146  let utility = scores[point]


147  orderby utility


148  select point


149  ).ToList();


150 


151  // Initialize the new tour


152  var actualTour = new List<int> { startingPoint };


153 


154  // Perform the insertions according to the utility sorting


155  InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);


156 


157  // Bring the tour back to be feasible


158  CleanupTour(actualTour, distances, maxDistance, fixedPenalty);


159 


160  // Set new Tour


161  IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());


162  }


163 


164  return base.Apply();


165  }


166  private void InsertPoints(List<int> actualTour, IntegerVector initialTour,


167  int neighborhood, List<int> visitablePoints, IRandom random) {


168 


169  // Elect the starting index of the part to be replaced


170  int tourSize = initialTour.Length;


171  int randomPosition = random.Next(tourSize  neighborhood  1) + 1;


172 


173  for (int position = 1; position < tourSize; position++) {


174  if ((position < randomPosition)  (position > (randomPosition + neighborhood  1))) {


175  // Copy from initial tour when outside shaking range


176  actualTour.Add(initialTour[position]);


177 


178  // Delete this point from the candidate list


179  visitablePoints.Remove(initialTour[position]);


180  } else {


181  // Point from within shaking range


182  if (visitablePoints.Count > 0) {


183  // Add the point with the highest utility from the candidate list


184  int randomFactor = random.Next(3);


185  int insertionIndex = visitablePoints.Count  1;


186  if (visitablePoints.Count > 4) insertionIndex = randomFactor;


187 


188  actualTour.Add(visitablePoints[insertionIndex]);


189 


190  // Delete this point from the candidate list


191  visitablePoints.RemoveAt(insertionIndex);


192  } else {


193  // We don't have any points left that could be inserted so we can only reinsert


194  // the removed and not already reinserted points in a random order


195  for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {


196  bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);


197 


198  if (!alreadyReinserted)


199  visitablePoints.Add(initialTour[reinsertPosition]);


200  }


201 


202  int randomIndex = random.Next(visitablePoints.Count);


203  actualTour.Add(visitablePoints[randomIndex]);


204  visitablePoints.Clear();


205  }


206  }


207  }


208  }


209  private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {


210  // Sort the points on the tour according to their costs savings when removed


211  var distanceSavings = (


212  from removePosition in Enumerable.Range(1, actualTour.Count  2)


213  let saving = distances.CalculateRemovementSaving(actualTour, removePosition, fixedPenalty)


214  orderby saving descending


215  select new SavingInfo { Index = removePosition, Saving = saving }


216  ).ToList();


217 


218  double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);


219 


220  // As long as the created path is infeasible, remove elements


221  while (tourLength > maxDistance) {


222  // Remove the point that frees the largest distance


223  // Note, distance savings are not updated after removal


224  tourLength = distances.CalculateRemovementSaving(actualTour, distanceSavings[0].Index, fixedPenalty);


225  actualTour.RemoveAt(distanceSavings[0].Index);


226 


227  // Shift indices due to removal of a point in the tour


228  for (int i = 1; i < distanceSavings.Count; i++) {


229  if (distanceSavings[i].Index > distanceSavings[0].Index) {


230  distanceSavings[i].Index;


231  }


232  }


233  distanceSavings.RemoveAt(0);


234  }


235  }


236  //


237  private class SavingInfo {


238  public int Index;


239  public double Saving;


240  }


241  }


242  } 
