source: trunk/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs @ 17607

#region License Information
/* HeuristicLab
 * Copyright (C) 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 HEAL.Attic;

namespace HeuristicLab.Problems.Orienteering {
  /// <summary>
  /// 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)
  /// </summary>
  [Item("GreedyOrienteeringTourCreator", @"Implements the solution creation procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")]
  [StorableType("FB68525D-DD53-4BE7-A6B4-EC54E6FD0E64")]
  public sealed class GreedyOrienteeringTourCreator : IntegerVectorCreator, IOrienteeringSolutionCreator {
    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> TerminalPointParameter {
      get { return (ILookupParameter<IntValue>)Parameters["TerminalPoint"]; }
    }
    public ILookupParameter<DoubleValue> PointVisitingCostsParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["PointVisitingCosts"]; }
    }
    #endregion

    [StorableConstructor]
    private GreedyOrienteeringTourCreator(StorableConstructorFlag _) : base(_) { }
    private 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>("TerminalPoint", "Index of the ending point."));
      Parameters.Add(new LookupParameter<DoubleValue>("PointVisitingCosts", "The costs for visiting a point."));
    }

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

    protected override IntegerVector Create(IRandom random, IntValue length, IntMatrix bounds) {
      int startPoint = StartingPointParameter.ActualValue.Value;
      int endPoint = TerminalPointParameter.ActualValue.Value;
      int numPoints = ScoresParameter.ActualValue.Length;
      var distances = DistanceMatrixParameter.ActualValue;
      double pointVisitingCosts = PointVisitingCostsParameter.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] + pointVisitingCosts
        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 tourLength = 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], pointVisitingCosts);

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

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