Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs @ 17529

Last change on this file since 17529 was 17529, checked in by abeham, 4 years ago

#2521: some fixes and reusing handling of distance measure as defined in TSP

File size: 12.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Collections.Generic;
23using System.IO;
24using System.Linq;
25using System.Threading;
26using HEAL.Attic;
27using HeuristicLab.Analysis;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Encodings.IntegerVectorEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Optimization.Operators;
33using HeuristicLab.Parameters;
34using HeuristicLab.Problems.Instances;
35using HeuristicLab.Problems.Instances.Types;
36using HeuristicLab.Problems.TravelingSalesman;
37
38namespace HeuristicLab.Problems.Orienteering {
39  [Item("Orienteering Problem (OP)", "Represents a single-objective Orienteering Problem.")]
40  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 115)]
41  [StorableType("0B8DB4A4-F183-4368-86C6-C51289B183D2")]
42  public sealed class OrienteeringProblem : IntegerVectorProblem,
43      IProblemInstanceConsumer<OPData>, IProblemInstanceConsumer<TSPData>, IProblemInstanceConsumer<CVRPData> {
44
45    [Storable] public ValueParameter<IOrienteeringProblemData> OrienteeringProblemDataParameter { get; private set; }
46    [Storable] public OptionalValueParameter<OrienteeringSolution> BestKnownSolutionParameter { get; private set; }
47    [Storable] private IResultParameter<OrienteeringSolution> BestOrienteeringSolutionParameter { get; set; }
48    public IResultDefinition<OrienteeringSolution> BestOrienteeringSolution => BestOrienteeringSolutionParameter;
49
50    public IOrienteeringProblemData OrienteeringProblemData {
51      get { return OrienteeringProblemDataParameter.Value; }
52      set { OrienteeringProblemDataParameter.Value = value; }
53    }
54    public OrienteeringSolution BestKnownSolution {
55      get { return BestKnownSolutionParameter.Value; }
56      set { BestKnownSolutionParameter.Value = value; }
57    }
58
59    [StorableConstructor]
60    private OrienteeringProblem(StorableConstructorFlag _) : base(_) {
61    }
62    private OrienteeringProblem(OrienteeringProblem original, Cloner cloner)
63      : base(original, cloner) {
64      OrienteeringProblemDataParameter = cloner.Clone(original.OrienteeringProblemDataParameter);
65      BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
66      BestOrienteeringSolutionParameter = cloner.Clone(original.BestOrienteeringSolutionParameter);
67    }
68    public override IDeepCloneable Clone(Cloner cloner) {
69      return new OrienteeringProblem(this, cloner);
70    }
71    public OrienteeringProblem()
72      : base(new IntegerVectorEncoding("Route")) {
73      Parameters.Add(OrienteeringProblemDataParameter = new ValueParameter<IOrienteeringProblemData>("OP Data", "The main parameters for the orienteering problem.", new OrienteeringProblemData()));
74      Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter<OrienteeringSolution>("BestKnownSolution", "The best known solution of this Orienteering instance."));
75      Parameters.Add(BestOrienteeringSolutionParameter = new ResultParameter<OrienteeringSolution>("Best Orienteering Solution", "The best so far solution found."));
76      Maximization = true;
77
78      InitializeOperators();
79    }
80
81    public override ISingleObjectiveEvaluationResult Evaluate(IntegerVector solution, IRandom random, CancellationToken cancellationToken) {
82      var data = OrienteeringProblemData;
83      var score = CalculateScore(data, solution);
84      var travelCosts = CalculateTravelCosts(data, solution);
85      var quality = CalculateQuality(data, score, travelCosts);
86
87      return new SingleObjectiveEvaluationResult(quality);
88    }
89
90    public static double CalculateQuality(IOrienteeringProblemData data, double score, double travelCosts) {
91      if (travelCosts > data.MaximumTravelCosts) return data.MaximumTravelCosts - travelCosts; // negative excessive distance
92      return score;
93    }
94    public static double CalculateScore(IOrienteeringProblemData data, IEnumerable<int> solution) {
95      return solution.Sum(t => data.GetScore(t));
96    }
97    public static double CalculateTravelCosts(IOrienteeringProblemData data, IntegerVector solution) {
98      var distance = data.RoutingData.GetPathDistance(solution, closed: false);
99      distance += (solution.Length - 2) * data.PointVisitingCosts;
100      return distance;
101    }
102    public static double CalculateTravelCosts(IOrienteeringProblemData data, IList<int> solution) {
103      var distance = data.RoutingData.GetPathDistance(solution, closed: false);
104      distance += (solution.Count - 2) * data.PointVisitingCosts;
105      return distance;
106    }
107
108    public override void Analyze(IntegerVector[] vectors, double[] qualities, ResultCollection results, IRandom random) {
109      base.Analyze(vectors, qualities, results, random);
110      var data = OrienteeringProblemData;
111
112      var best = GetBestSolution(vectors, qualities).Item1;
113      var score = CalculateScore(OrienteeringProblemData, best);
114      var travelCosts = CalculateTravelCosts(OrienteeringProblemData, best);
115      var quality = CalculateQuality(OrienteeringProblemData, score, travelCosts);
116
117      if (double.IsNaN(BestKnownQuality) || IsBetter(quality, BestKnownQuality)) {
118        BestKnownQuality = quality;
119        BestKnownSolutionParameter.ActualValue = data.GetSolution((IntegerVector)best.Clone(), quality, score, travelCosts);
120      }
121      var bestSoFar = BestOrienteeringSolutionParameter.ActualValue;
122     
123      if (bestSoFar == null || IsBetter(quality, bestSoFar.Quality.Value)) {
124        bestSoFar = data.GetSolution((IntegerVector)best.Clone(), quality, score, travelCosts);
125        BestOrienteeringSolutionParameter.ActualValue = bestSoFar;
126      }
127    }
128    public static double CalculateInsertionCosts(IOrienteeringProblemData data, IList<int> path, int insertPosition, int point) {
129      double detour = data.RoutingData.GetDistance(path[insertPosition - 1], point) + data.RoutingData.GetDistance(point, path[insertPosition]);
130      detour += data.PointVisitingCosts;
131      detour -= data.RoutingData.GetDistance(path[insertPosition - 1], path[insertPosition]);
132      return detour;
133    }
134    public static double CalculateReplacementCosts(IOrienteeringProblemData data, IList<int> path, int replacePosition, int point) {
135      double detour = data.RoutingData.GetDistance(path[replacePosition - 1], point) + data.RoutingData.GetDistance(point, path[replacePosition + 1]);
136      detour -= data.RoutingData.GetDistance(path[replacePosition - 1], path[replacePosition]) + data.RoutingData.GetDistance(path[replacePosition], path[replacePosition + 1]);
137      return detour;
138    }
139    public static double CalculateRemovementSaving(IOrienteeringProblemData data, IList<int> path, int removePosition) {
140      double saving = data.RoutingData.GetDistance(path[removePosition - 1], path[removePosition]);
141      saving += data.RoutingData.GetDistance(path[removePosition], path[removePosition + 1]);
142      saving -= data.RoutingData.GetDistance(path[removePosition - 1], path[removePosition + 1]);
143      saving += data.PointVisitingCosts;
144      return saving;
145    }
146
147    protected override void OnEncodingChanged() {
148      base.OnEncodingChanged();
149      ParameterizeOperators();
150    }
151
152    protected override void OnEvaluatorChanged() {
153      base.OnEvaluatorChanged();
154      ParameterizeOperators();
155    }
156
157    private void InitializeOperators() {
158      Encoding.SolutionCreator = new GreedyOrienteeringTourCreator() {
159        OrienteeringProblemDataParameter = { ActualName = OrienteeringProblemDataParameter.Name }
160      };
161
162      Operators.Add(new OrienteeringLocalImprovementOperator() {
163        OrienteeringProblemDataParameter = { ActualName = OrienteeringProblemDataParameter.Name }
164      });
165      Operators.Add(new OrienteeringShakingOperator() {
166        OrienteeringProblemDataParameter = { ActualName = OrienteeringProblemDataParameter.Name }
167      });
168      Operators.Add(new QualitySimilarityCalculator());
169      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
170
171      ParameterizeOperators();
172    }
173
174    private void ParameterizeOperators() {
175      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
176        op.IntegerVectorParameter.ActualName = Encoding.Name;
177        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
178      }
179      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
180        op.IntegerVectorParameter.ActualName = Encoding.Name;
181      }
182      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
183        similarityCalculator.SolutionVariableName = Encoding.Name;
184        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
185      }
186    }
187
188    #region Instance consuming
189    public void Load(OPData data) {
190      if (data.Coordinates == null && data.Distances == null)
191        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
192      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
193        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.");
194
195      // Clear old solutions
196      BestKnownSolution = null;
197
198      Name = data.Name;
199      Description = data.Description;
200
201      var tsp = TSP.GetDataFromInstance(data);
202      OrienteeringProblemData = new OrienteeringProblemData(tsp, data.StartingPoint, data.TerminalPoint, data.Scores, data.MaximumDistance, data.PointVisitingCosts);
203    }
204
205    public void Load(TSPData data) {
206      if (data.Coordinates == null && data.Distances == null)
207        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
208      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
209        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.");
210
211      // Clear old solutions
212      BestKnownSolution = null;
213
214      Name = data.Name;
215      Description = data.Description;
216
217
218      var tsp = TSP.GetDataFromInstance(data);
219      var avgDist = 0.0;
220      for (var i = 0; i < data.Dimension - 1; i++)
221        for (var j = i + 1; i < data.Dimension; j++)
222          avgDist += tsp.GetDistance(i, j);
223      avgDist /= (data.Dimension - 1) * data.Dimension / 2.0;
224
225      OrienteeringProblemData = new OrienteeringProblemData(tsp, 0, data.Dimension - 1,
226        Enumerable.Repeat(1.0, data.Dimension).ToArray(), 5 * avgDist, 0);
227    }
228
229    public void Load(CVRPData data) {
230      if (data.Coordinates == null && data.Distances == null)
231        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
232      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
233        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.");
234
235      // Clear old solutions
236      BestKnownSolution = null;
237
238      Name = data.Name;
239      Description = data.Description;
240
241      var tsp = TSP.GetDataFromInstance(data);
242      OrienteeringProblemData = new OrienteeringProblemData(tsp, 0, 0, data.Demands, data.Capacity * 2, 0);
243    }
244    #endregion
245  }
246}
Note: See TracBrowser for help on using the repository browser.