source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs @ 11228

#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.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.Orienteering {
  [Item("GreedyOrienteeringTourCreator", @"The initial solution for P-VNS is generated by means of a greedy algorithm that takes into
account all vertices vi that are located within the cost limit Tmax. These points are sorted
in descending order regarding the sum of their objective values. Afterwards, the algorithm
starts with a tour only including the starting and ending point and successively inserts the
points from this list at the first position in which they can feasibly be inserted. (Schilde et. al. 2009)")]
  [StorableClass]
  public class GreedyOrienteeringTourCreator : IntegerVectorCreator {
    public override bool CanChangeName { get { return false; } }

    #region Parameter Properties
    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"]; }
    }
    #endregion

    [StorableConstructor]
    protected GreedyOrienteeringTourCreator(bool deserializing)
      : base(deserializing) { }
    protected GreedyOrienteeringTourCreator(GreedyOrienteeringTourCreator original, Cloner cloner)
      : base(original, cloner) { }

    public GreedyOrienteeringTourCreator()
      : 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."));
    }

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

    protected override IntegerVector Create(IRandom _, IntValue __, IntMatrix ___) {
      int startPoint = StartingPointParameter.ActualValue.Value;
      int endPoint = TerminusPointParameter.ActualValue.Value;
      int numPoints = ScoresParameter.ActualValue.Length;
      var distances = DistanceMatrixParameter.ActualValue;
      double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
      var scores = ScoresParameter.ActualValue;

      // Find all points within the maximum distance allowed (ellipse)
      var feasiblePoints = (
        from point in Enumerable.Range(0, numPoints)
        let distance = distances[startPoint, point] + distances[point, endPoint] + fixedPenalty
        let score = scores[point]
        where distance <= maxDistance
        where point != startPoint && point != endPoint
        orderby score descending
        select point
      ).ToList();

      // Add the starting and terminus point
      var tour = new List<int> {
        startPoint,
        endPoint
      };
      double length = distances[startPoint, endPoint];

      // Add points in a greedy way
      bool insertionPerformed = true;
      while (insertionPerformed) {
        insertionPerformed = false;

        for (int i = 0; i < feasiblePoints.Count; i++) {
          for (int insertPosition = 1; insertPosition < tour.Count; insertPosition++) {
            // Create the candidate tour
            double detour = distances.CalculateInsertionCosts(tour, insertPosition, feasiblePoints[i], fixedPenalty);

            // If the insertion would be feasible, perform it
            if (length + detour <= maxDistance) {
              tour.Insert(insertPosition, feasiblePoints[i]);
              length += detour;
              feasiblePoints.RemoveAt(i);
              insertionPerformed = true;
              break;
            }
          }
          if (insertionPerformed) break;
        }
      }

      return new IntegerVector(tour.ToArray());
    }
  }
}