source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs @ 17533

#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 HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Parameters;

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

    public ILookupParameter<IOrienteeringProblemData> OrienteeringProblemDataParameter {
      get { return (ILookupParameter<IOrienteeringProblemData>)Parameters["OrienteeringProblemData"]; }
    }

    [StorableConstructor]
    private GreedyOrienteeringTourCreator(StorableConstructorFlag _) : base(_) { }
    private GreedyOrienteeringTourCreator(GreedyOrienteeringTourCreator original, Cloner cloner)
      : base(original, cloner) { }

    public GreedyOrienteeringTourCreator()
      : base() {
      Parameters.Add(new LookupParameter<IOrienteeringProblemData>("OrienteeringProblemData", "The main data that comprises the orienteering problem."));
    }

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

    protected override IntegerVector Create(IRandom random, IntValue length, IntMatrix bounds) {
      var data = OrienteeringProblemDataParameter.ActualValue;

      // Find all points within the maximum distance allowed (ellipse)
      var feasiblePoints = (
        from point in Enumerable.Range(0, data.Cities)
        let travelCosts = data.GetDistance(data.StartingPoint, point)
        + data.GetDistance(point, data.TerminalPoint) + data.PointVisitingCosts
        let score = data.GetScore(point)
        where travelCosts <= data.MaximumTravelCosts
        where point != data.StartingPoint && point != data.TerminalPoint
        orderby score descending
        select point
      ).ToList();

      // Add the starting and terminus point
      var tour = new List<int> {
        data.StartingPoint,
        data.TerminalPoint
      };
      double tourLength = data.GetDistance(data.StartingPoint, data.TerminalPoint);

      // 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 = OrienteeringProblem.CalculateInsertionCosts(data, tour, insertPosition, feasiblePoints[i]);

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

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