source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs @ 11226

Last change on this file since 11226 was 11226, checked in by pfleck, 7 years ago

#2208:

  • Fixed bug in LocalImprovementOperator.
  • Implemented ShakingOperator.
File size: 15.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.Instances;
32
33namespace HeuristicLab.Problems.Orienteering {
34
35  [Item("Orienteering Problem", "Represents a single objective Orienteering Problem.")]
36  [Creatable("Problems")]
37  [StorableClass]
38  public class OrienteeringProblem
39    : SingleObjectiveHeuristicOptimizationProblem<IOrienteeringEvaluator, IIntegerVectorCreator>,
40    IStorableContent, IProblemInstanceConsumer<CVRPData> {
41
42    public string Filename { get; set; }
43
44    #region Parameter Properties
45    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
46      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
47    }
48    public ValueParameter<DistanceMatrix> DistanceMatrixParameter {
49      get { return (ValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
50    }
51
52    public ValueParameter<IntValue> StartingPointParameter {
53      get { return (ValueParameter<IntValue>)Parameters["StartingPoint"]; }
54    }
55    public ValueParameter<IntValue> TerminusPointParameter {
56      get { return (ValueParameter<IntValue>)Parameters["TerminusPoint"]; }
57    }
58    public ValueParameter<DoubleValue> MaximumDistanceParameter {
59      get { return (ValueParameter<DoubleValue>)Parameters["MaximumDistance"]; }
60    }
61    public ValueParameter<DoubleArray> ScoresParameter {
62      get { return (ValueParameter<DoubleArray>)Parameters["Scores"]; }
63    }
64    public ValueParameter<DoubleValue> FixedPenaltyParameter {
65      get { return (ValueParameter<DoubleValue>)Parameters["FixedPenalty"]; }
66    }
67
68    public OptionalValueParameter<IntegerVector> BestKnownSolutionParameter {
69      get { return (OptionalValueParameter<IntegerVector>)Parameters["BestKnownSolution"]; }
70    }
71    #endregion
72
73    #region Properties
74    public DoubleMatrix Coordinates {
75      get { return CoordinatesParameter.Value; }
76      set { CoordinatesParameter.Value = value; }
77    }
78    public DistanceMatrix DistanceMatrix {
79      get { return DistanceMatrixParameter.Value; }
80      set { DistanceMatrixParameter.Value = value; }
81    }
82    public IntValue StartingPoint {
83      get { return StartingPointParameter.Value; }
84      set { StartingPointParameter.Value = value; }
85    }
86    public IntValue TerminusPoint {
87      get { return TerminusPointParameter.Value; }
88      set { TerminusPointParameter.Value = value; }
89    }
90    public DoubleValue MaximumDistance {
91      get { return MaximumDistanceParameter.Value; }
92      set { MaximumDistanceParameter.Value = value; }
93    }
94    public DoubleArray Scores {
95      get { return ScoresParameter.Value; }
96      set { ScoresParameter.Value = value; }
97    }
98    public DoubleValue FixedPenalty {
99      get { return FixedPenaltyParameter.Value; }
100      set { FixedPenaltyParameter.Value = value; }
101    }
102    public IntegerVector BestKnownSolution {
103      get { return BestKnownSolutionParameter.Value; }
104      set { BestKnownSolutionParameter.Value = value; }
105    }
106    private BestOrienteeringSolutionAnalyser BestOrienteeringSolutionAnalyser {
107      get { return Operators.OfType<BestOrienteeringSolutionAnalyser>().SingleOrDefault(); }
108    }
109    #endregion
110
111    [StorableConstructor]
112    private OrienteeringProblem(bool deserializing)
113      : base(deserializing) {
114    }
115    private OrienteeringProblem(OrienteeringProblem original, Cloner cloner)
116      : base(original, cloner) {
117      RegisterEventHandlers();
118    }
119    public override IDeepCloneable Clone(Cloner cloner) {
120      return new OrienteeringProblem(this, cloner);
121    }
122    public OrienteeringProblem()
123      : base(new OrienteeringEvaluator(), new GreedyOrienteeringTourCreator()) {
124      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the points."));
125      Parameters.Add(new ValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
126      Parameters.Add(new ValueParameter<IntValue>("StartingPoint", "Index of the starting point.", new IntValue(0)));
127      Parameters.Add(new ValueParameter<IntValue>("TerminusPoint", "Index of the ending point.", new IntValue(0)));
128      Parameters.Add(new ValueParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
129      Parameters.Add(new ValueParameter<DoubleArray>("Scores", "The scores of the points.", new DoubleArray()));
130      Parameters.Add(new ValueParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
131      Parameters.Add(new OptionalValueParameter<IntegerVector>("BestKnownSolution", "The best known solution of this Orienteering instance."));
132
133      Maximization.Value = true;
134      MaximizationParameter.Hidden = true;
135
136      SolutionCreator.IntegerVectorParameter.ActualName = "OrienteeringSolution";
137
138      InitializeInitialOrienteeringInstance();
139
140      ParameterizeSolutionCreator();
141      ParameterizeEvaluator();
142
143      InitializeOperators();
144      RegisterEventHandlers();
145    }
146
147    #region Events
148    protected override void OnSolutionCreatorChanged() {
149      base.OnSolutionCreatorChanged();
150      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
151      ParameterizeSolutionCreator();
152      ParameterizeEvaluator();
153      ParameterizeAnalyzer();
154      ParameterizeOperators();
155    }
156    protected override void OnEvaluatorChanged() {
157      base.OnEvaluatorChanged();
158      ParameterizeEvaluator();
159      ParameterizeAnalyzer();
160    }
161    private void SolutionCreator_IntegerVectorParameter_ActualNameChanged(object sender, EventArgs e) {
162      ParameterizeEvaluator();
163      ParameterizeAnalyzer();
164      ParameterizeOperators();
165    }
166    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
167      if (Coordinates != null) {
168        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(CoordinatesValue_ItemChanged);
169        Coordinates.Reset += new EventHandler(CoordinatesValue_Reset);
170      }
171      ParameterizeSolutionCreator();
172      CalculateDistanceMatrix();
173    }
174    private void CoordinatesValue_ItemChanged(object sender, EventArgs<int, int> e) {
175      CalculateDistanceMatrix();
176    }
177    private void CoordinatesValue_Reset(object sender, EventArgs e) {
178      ParameterizeSolutionCreator();
179      CalculateDistanceMatrix();
180    }
181    private void StartingPointParameter_ValueChanged(object sender, EventArgs e) {
182      ParameterizeEvaluator();
183      ParameterizeAnalyzer();
184    }
185
186    private void TerminusPointParameter_ValueChanged(object sender, EventArgs e) {
187      ParameterizeEvaluator();
188      ParameterizeAnalyzer();
189    }
190    private void MaximumDistanceParameter_ValueChanged(object sender, EventArgs e) {
191      ParameterizeEvaluator();
192      ParameterizeAnalyzer();
193    }
194    private void ScoresParameter_ValueChanged(object sender, EventArgs e) {
195      ParameterizeEvaluator();
196      ParameterizeAnalyzer();
197      ParameterizeSolutionCreator();
198
199      ScoresParameter.Value.Reset += new EventHandler(ScoresValue_Reset);
200    }
201    private void ScoresValue_Reset(object sender, EventArgs e) {
202      ParameterizeSolutionCreator();
203    }
204    private void FixedPenaltyParameter_ValueChanged(object sender, EventArgs e) {
205      ParameterizeEvaluator();
206      ParameterizeAnalyzer();
207    }
208    #endregion
209
210    #region Helpers
211    [StorableHook(HookType.AfterDeserialization)]
212    private void AfterDeserialization() {
213      RegisterEventHandlers();
214    }
215
216    private void RegisterEventHandlers() {
217      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
218
219      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
220      if (CoordinatesParameter.Value != null) {
221        CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
222        CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
223      }
224
225      StartingPointParameter.ValueChanged += StartingPointParameter_ValueChanged;
226      TerminusPointParameter.ValueChanged += TerminusPointParameter_ValueChanged;
227      MaximumDistanceParameter.ValueChanged += MaximumDistanceParameter_ValueChanged;
228
229      ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
230      ScoresParameter.Value.Reset += ScoresValue_Reset;
231      FixedPenaltyParameter.ValueChanged += FixedPenaltyParameter_ValueChanged;
232    }
233
234    private void ParameterizeSolutionCreator() {
235      if (SolutionCreator is GreedyOrienteeringTourCreator) {
236        var creator = (GreedyOrienteeringTourCreator)SolutionCreator;
237        creator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
238        creator.ScoresParameter.ActualName = ScoresParameter.Name;
239        creator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
240        creator.StartingPointParameter.ActualName = StartingPointParameter.Name;
241        creator.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
242        creator.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
243      }
244    }
245    private void ParameterizeEvaluator() {
246      if (Evaluator is OrienteeringEvaluator) {
247        var evaluator = (OrienteeringEvaluator)Evaluator;
248        evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
249        evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
250      }
251    }
252    private void ParameterizeAnalyzer() {
253      if (BestOrienteeringSolutionAnalyser != null) {
254        BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
255
256        BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
257        BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
258        BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
259
260        BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
261        BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
262        BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
263      }
264    }
265    private void InitializeOperators() {
266      Operators.Add(new BestOrienteeringSolutionAnalyser());
267      ParameterizeAnalyzer();
268
269      Operators.Add(new OrienteeringLocalImprovementOperator());
270      Operators.Add(new OrienteeringShakingOperator());
271      ParameterizeOperators();
272    }
273    private void ParameterizeOperators() {
274      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
275        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
276        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
277        op.ScoresParameter.ActualName = ScoresParameter.Name;
278        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
279        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
280        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
281        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
282      }
283      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
284        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
285        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
286        op.ScoresParameter.ActualName = ScoresParameter.Name;
287        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
288        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
289        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
290        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
291      }
292    }
293    #endregion
294
295    private void CalculateDistanceMatrix() {
296      var distances = new double[Coordinates.Rows, Coordinates.Rows];
297      for (int i = 0; i < Coordinates.Rows; i++) {
298        for (int j = 0; j < Coordinates.Rows; j++) {
299          double distanceX = Math.Abs(Coordinates[i, 0] - Coordinates[j, 0]);
300          double distanceY = Math.Abs(Coordinates[i, 1] - Coordinates[j, 1]);
301          distances[i, j] = Math.Sqrt(Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2));
302        }
303      }
304      DistanceMatrix = new DistanceMatrix(distances);
305    }
306
307    private void InitializeInitialOrienteeringInstance() {
308      Coordinates = new DoubleMatrix(new double[21, 2] {
309        {  4.60,  7.10 }, {  5.70, 11.40 }, {  4.40, 12.30 }, {  2.80, 14.30 }, {  3.20, 10.30 },
310        {  3.50,  9.80 }, {  4.40,  8.40 }, {  7.80, 11.00 }, {  8.80,  9.80 }, {  7.70,  8.20 },
311        {  6.30,  7.90 }, {  5.40,  8.20 }, {  5.80,  6.80 }, {  6.70,  5.80 }, { 13.80, 13.10 },
312        { 14.10, 14.20 }, { 11.20, 13.60 }, {  9.70, 16.40 }, {  9.50, 18.80 }, {  4.70, 16.80 },
313        {  5.00,  5.60 }
314      });
315      CalculateDistanceMatrix();
316
317      StartingPoint.Value = 0;
318      TerminusPoint.Value = 20;
319      MaximumDistance.Value = 30;
320
321      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 });
322    }
323
324    public void Load(CVRPData data) {
325      if (data.Coordinates == null && data.Distances == null)
326        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
327      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
328        throw new System.IO.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.");
329
330      Name = data.Name;
331      Description = data.Description;
332
333      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
334      if (Coordinates == null)
335        DistanceMatrix = new DistanceMatrix(data.Distances);
336      StartingPoint = new IntValue(0);// Depot is interpreted as start and endpoint (default)
337      TerminusPoint = new IntValue(0);
338
339      MaximumDistance = new DoubleValue(data.Capacity); // capacity is interpreted as max distance
340      Scores = new DoubleArray(data.Demands); // demands are interpreted as scores
341
342      BestKnownQuality = null;
343      BestKnownSolution = null;
344    }
345  }
346}
Note: See TracBrowser for help on using the repository browser.