#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 .
*/
#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 {
///
/// 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)
///
[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 OrienteeringProblemDataParameter {
get { return (ILookupParameter)Parameters["OrienteeringProblemData"]; }
}
[StorableConstructor]
private GreedyOrienteeringTourCreator(StorableConstructorFlag _) : base(_) { }
private GreedyOrienteeringTourCreator(GreedyOrienteeringTourCreator original, Cloner cloner)
: base(original, cloner) { }
public GreedyOrienteeringTourCreator()
: base() {
Parameters.Add(new LookupParameter("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 {
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());
}
}
}