#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 .
*/
#endregion
using System;
using System.IO;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.Instances.Types;
namespace HeuristicLab.Problems.Orienteering {
[Item("Orienteering Problem", "Represents a single objective Orienteering Problem.")]
[Creatable("Problems")]
[StorableClass]
public class OrienteeringProblem
: SingleObjectiveHeuristicOptimizationProblem,
IStorableContent, IProblemInstanceConsumer, IProblemInstanceConsumer {
public string Filename { get; set; }
#region Parameter Properties
public ValueParameter CoordinatesParameter {
get { return (ValueParameter)Parameters["Coordinates"]; }
}
public ValueParameter DistanceMatrixParameter {
get { return (ValueParameter)Parameters["DistanceMatrix"]; }
}
public ValueParameter StartingPointParameter {
get { return (ValueParameter)Parameters["StartingPoint"]; }
}
public ValueParameter TerminusPointParameter {
get { return (ValueParameter)Parameters["TerminusPoint"]; }
}
public ValueParameter MaximumDistanceParameter {
get { return (ValueParameter)Parameters["MaximumDistance"]; }
}
public ValueParameter ScoresParameter {
get { return (ValueParameter)Parameters["Scores"]; }
}
public ValueParameter FixedPenaltyParameter {
get { return (ValueParameter)Parameters["FixedPenalty"]; }
}
public OptionalValueParameter BestKnownSolutionParameter {
get { return (OptionalValueParameter)Parameters["BestKnownSolution"]; }
}
#endregion
#region Properties
public DoubleMatrix Coordinates {
get { return CoordinatesParameter.Value; }
set { CoordinatesParameter.Value = value; }
}
public DistanceMatrix DistanceMatrix {
get { return DistanceMatrixParameter.Value; }
set { DistanceMatrixParameter.Value = value; }
}
public IntValue StartingPoint {
get { return StartingPointParameter.Value; }
set { StartingPointParameter.Value = value; }
}
public IntValue TerminusPoint {
get { return TerminusPointParameter.Value; }
set { TerminusPointParameter.Value = value; }
}
public DoubleValue MaximumDistance {
get { return MaximumDistanceParameter.Value; }
set { MaximumDistanceParameter.Value = value; }
}
public DoubleArray Scores {
get { return ScoresParameter.Value; }
set { ScoresParameter.Value = value; }
}
public DoubleValue FixedPenalty {
get { return FixedPenaltyParameter.Value; }
set { FixedPenaltyParameter.Value = value; }
}
public IntegerVector BestKnownSolution {
get { return BestKnownSolutionParameter.Value; }
set { BestKnownSolutionParameter.Value = value; }
}
private BestOrienteeringSolutionAnalyser BestOrienteeringSolutionAnalyser {
get { return Operators.OfType().SingleOrDefault(); }
}
#endregion
[StorableConstructor]
private OrienteeringProblem(bool deserializing)
: base(deserializing) {
}
private OrienteeringProblem(OrienteeringProblem original, Cloner cloner)
: base(original, cloner) {
RegisterEventHandlers();
}
public override IDeepCloneable Clone(Cloner cloner) {
return new OrienteeringProblem(this, cloner);
}
public OrienteeringProblem()
: base(new OrienteeringEvaluator(), new GreedyOrienteeringTourCreator()) {
Parameters.Add(new ValueParameter("Coordinates", "The x- and y-Coordinates of the points."));
Parameters.Add(new ValueParameter("DistanceMatrix", "The matrix which contains the distances between the points."));
Parameters.Add(new ValueParameter("StartingPoint", "Index of the starting point.", new IntValue(0)));
Parameters.Add(new ValueParameter("TerminusPoint", "Index of the ending point.", new IntValue(0)));
Parameters.Add(new ValueParameter("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
Parameters.Add(new ValueParameter("Scores", "The scores of the points."));
Parameters.Add(new ValueParameter("FixedPenalty", "The penalty for each visited vertex."));
Parameters.Add(new OptionalValueParameter("BestKnownSolution", "The best known solution of this Orienteering instance."));
Maximization.Value = true;
MaximizationParameter.Hidden = true;
SolutionCreator.IntegerVectorParameter.ActualName = "OrienteeringSolution";
InitializeInitialOrienteeringInstance();
ParameterizeSolutionCreator();
ParameterizeEvaluator();
InitializeOperators();
RegisterEventHandlers();
}
#region Events
protected override void OnSolutionCreatorChanged() {
base.OnSolutionCreatorChanged();
SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
ParameterizeSolutionCreator();
ParameterizeEvaluator();
ParameterizeAnalyzer();
ParameterizeOperators();
}
protected override void OnEvaluatorChanged() {
base.OnEvaluatorChanged();
ParameterizeEvaluator();
ParameterizeAnalyzer();
}
private void SolutionCreator_IntegerVectorParameter_ActualNameChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
ParameterizeOperators();
}
private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
if (Coordinates != null) {
Coordinates.ItemChanged += new EventHandler>(CoordinatesValue_ItemChanged);
Coordinates.Reset += new EventHandler(CoordinatesValue_Reset);
}
ParameterizeSolutionCreator();
UpdateDistanceMatrix();
}
private void CoordinatesValue_ItemChanged(object sender, EventArgs e) {
UpdateDistanceMatrix();
}
private void CoordinatesValue_Reset(object sender, EventArgs e) {
ParameterizeSolutionCreator();
UpdateDistanceMatrix();
}
private void StartingPointParameter_ValueChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
}
private void TerminusPointParameter_ValueChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
}
private void MaximumDistanceParameter_ValueChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
}
private void ScoresParameter_ValueChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
ParameterizeSolutionCreator();
ScoresParameter.Value.Reset += new EventHandler(ScoresValue_Reset);
}
private void ScoresValue_Reset(object sender, EventArgs e) {
ParameterizeSolutionCreator();
}
private void FixedPenaltyParameter_ValueChanged(object sender, EventArgs e) {
ParameterizeEvaluator();
ParameterizeAnalyzer();
}
#endregion
#region Helpers
[StorableHook(HookType.AfterDeserialization)]
private void AfterDeserialization() {
RegisterEventHandlers();
}
private void RegisterEventHandlers() {
SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
if (CoordinatesParameter.Value != null) {
CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
}
StartingPointParameter.ValueChanged += StartingPointParameter_ValueChanged;
TerminusPointParameter.ValueChanged += TerminusPointParameter_ValueChanged;
MaximumDistanceParameter.ValueChanged += MaximumDistanceParameter_ValueChanged;
ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
ScoresParameter.Value.Reset += ScoresValue_Reset;
FixedPenaltyParameter.ValueChanged += FixedPenaltyParameter_ValueChanged;
}
private void ParameterizeSolutionCreator() {
if (SolutionCreator is GreedyOrienteeringTourCreator) {
var creator = (GreedyOrienteeringTourCreator)SolutionCreator;
creator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
creator.ScoresParameter.ActualName = ScoresParameter.Name;
creator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
creator.StartingPointParameter.ActualName = StartingPointParameter.Name;
creator.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
creator.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
}
}
private void ParameterizeEvaluator() {
if (Evaluator is OrienteeringEvaluator) {
var evaluator = (OrienteeringEvaluator)Evaluator;
evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
}
}
private void ParameterizeAnalyzer() {
if (BestOrienteeringSolutionAnalyser != null) {
BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
}
}
private void InitializeOperators() {
Operators.Add(new BestOrienteeringSolutionAnalyser());
ParameterizeAnalyzer();
Operators.Add(new OrienteeringLocalImprovementOperator());
Operators.Add(new OrienteeringShakingOperator());
ParameterizeOperators();
}
private void ParameterizeOperators() {
foreach (var op in Operators.OfType()) {
op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
op.ScoresParameter.ActualName = ScoresParameter.Name;
op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
op.StartingPointParameter.ActualName = StartingPointParameter.Name;
op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
}
foreach (var op in Operators.OfType()) {
op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
op.ScoresParameter.ActualName = ScoresParameter.Name;
op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
op.StartingPointParameter.ActualName = StartingPointParameter.Name;
op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
}
}
#endregion
private DistanceMatrix CalculateDistanceMatrix(double[,] coordinates) {
var distances = DistanceHelper.GetDistanceMatrix(DistanceMeasure.Euclidean, coordinates, null, coordinates.GetLength(0));
return new DistanceMatrix(distances);
}
private void UpdateDistanceMatrix() {
var coordinates = Coordinates;
int dimension = coordinates.Rows;
var distances = DistanceMatrix;
for (int i = 0; i < dimension - 1; i++) {
for (int j = i + 1; j < dimension; j++) {
double x1 = coordinates[i, 0];
double y1 = coordinates[i, 1];
double x2 = coordinates[j, 0];
double y2 = coordinates[j, 1];
distances[i, j] = Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
distances[j, i] = distances[i, j];
}
}
}
private void InitializeInitialOrienteeringInstance() {
var coordinates = new double[21, 2] {
{ 4.60, 7.10 }, { 5.70, 11.40 }, { 4.40, 12.30 }, { 2.80, 14.30 }, { 3.20, 10.30 },
{ 3.50, 9.80 }, { 4.40, 8.40 }, { 7.80, 11.00 }, { 8.80, 9.80 }, { 7.70, 8.20 },
{ 6.30, 7.90 }, { 5.40, 8.20 }, { 5.80, 6.80 }, { 6.70, 5.80 }, { 13.80, 13.10 },
{ 14.10, 14.20 }, { 11.20, 13.60 }, { 9.70, 16.40 }, { 9.50, 18.80 }, { 4.70, 16.80 },
{ 5.00, 5.60 }
};
Coordinates = new DoubleMatrix(coordinates);
DistanceMatrix = CalculateDistanceMatrix(coordinates);
StartingPoint.Value = 0;
TerminusPoint.Value = 20;
MaximumDistance.Value = 30;
Scores = new DoubleArray(new double[21] { 0, 20, 20, 30, 15, 15, 10, 20, 20, 20, 15, 10, 10, 25, 40, 40, 30, 30, 50, 30, 0 });
}
public void Load(CVRPData data) {
if (data.Coordinates == null)
throw new InvalidDataException("The given instance specifies no coordinates!");
if (data.Coordinates.GetLength(1) != 2)
throw new InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
// Clear old solutions
BestKnownQuality = null;
BestKnownSolution = null;
Name = data.Name;
Description = data.Description;
Coordinates = new DoubleMatrix(data.Coordinates);
DistanceMatrix = data.Distances != null
? new DistanceMatrix(data.Distances)
: CalculateDistanceMatrix(data.Coordinates);
StartingPoint = new IntValue(0); // Depot is interpreted as start point
TerminusPoint = new IntValue(0); // Last city is interpreted als end point
MaximumDistance = new DoubleValue(data.Capacity * 2); // capacity is interpreted as max distance
Scores = new DoubleArray(data.Demands); // demands are interpreted as scores
OnReset();
}
public void Load(OPData data) {
if (data.Coordinates == null)
throw new InvalidDataException("The given instance specifies no coordinates!");
if (data.Coordinates.GetLength(1) != 2)
throw new InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
// Clear old solutions
BestKnownQuality = null;
BestKnownSolution = null;
Name = data.Name;
Description = data.Description;
Coordinates = new DoubleMatrix(data.Coordinates);
if (data.Distances != null)
DistanceMatrix = new DistanceMatrix(data.Distances);
else
data.GetDistanceMatrix();
StartingPoint = new IntValue(data.StartingPoint);
TerminusPoint = new IntValue(data.TerminusPoint);
MaximumDistance = new DoubleValue(data.MaximumDistance);
Scores = new DoubleArray(data.Scores);
}
}
}