Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs @ 17704

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

#2521: worked on VRP

File size: 11.0 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;
23using System.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using System.Threading;
27using HEAL.Attic;
28using HeuristicLab.Analysis;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Data;
32using HeuristicLab.Optimization;
33using HeuristicLab.Optimization.Operators;
34using HeuristicLab.Parameters;
35using HeuristicLab.PluginInfrastructure;
36using HeuristicLab.Problems.Instances;
37using HeuristicLab.Problems.VehicleRouting.Encodings.Alba;
38using HeuristicLab.Problems.VehicleRouting.Interfaces;
39using HeuristicLab.Problems.VehicleRouting.Interpreters;
40using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
41
42namespace HeuristicLab.Problems.VehicleRouting {
43  [Item("Vehicle Routing Problem (VRP)", "Represents a Vehicle Routing Problem.")]
44  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 110)]
45  [StorableType("95137523-AE3B-4638-958C-E86829D54CE3")]
46  public sealed class VehicleRoutingProblem : SingleObjectiveProblem<IVRPEncoding, IVRPEncodedSolution>, IProblemInstanceConsumer<IVRPData> {
47
48    public static new Image StaticItemImage {
49      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
50    }
51
52    #region Parameter Properties
53    public ValueParameter<IVRPProblemInstance> ProblemInstanceParameter {
54      get { return (ValueParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
55    }
56    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
57      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
58    }
59    #endregion
60
61    #region Properties
62    public IVRPProblemInstance ProblemInstance {
63      get { return ProblemInstanceParameter.Value; }
64      set { ProblemInstanceParameter.Value = value; }
65    }
66
67    public VRPSolution BestKnownSolution {
68      get { return BestKnownSolutionParameter.Value; }
69      set { BestKnownSolutionParameter.Value = value; }
70    }
71    #endregion
72
73    [StorableConstructor]
74    private VehicleRoutingProblem(StorableConstructorFlag _) : base(_) { }
75    public VehicleRoutingProblem()
76      : base(new AlbaEncoding()) {
77      Parameters.Add(new ValueParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
78      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
79
80      InitializeRandomVRPInstance();
81      InitializeOperators();
82
83      AttachEventHandlers();
84      AttachProblemInstanceEventHandlers();
85    }
86
87    public override IDeepCloneable Clone(Cloner cloner) {
88      cloner.Clone(ProblemInstance);
89      return new VehicleRoutingProblem(this, cloner);
90    }
91
92    private VehicleRoutingProblem(VehicleRoutingProblem original, Cloner cloner)
93      : base(original, cloner) {
94      this.AttachEventHandlers();
95      this.AttachProblemInstanceEventHandlers();
96    }
97
98    public override ISingleObjectiveEvaluationResult Evaluate(IVRPEncodedSolution solution, IRandom random, CancellationToken cancellationToken) {
99      return new SingleObjectiveEvaluationResult(ProblemInstance.Evaluate(solution).Quality);
100    }
101
102    #region Helpers
103    [StorableHook(HookType.AfterDeserialization)]
104    private void AfterDeserialization() {
105      AttachEventHandlers();
106      AttachProblemInstanceEventHandlers();
107    }
108
109    [Storable(OldName = "operators")]
110    private List<IOperator> StorableOperators {
111      set { Operators.AddRange(value); }
112    }
113
114    private void AttachEventHandlers() {
115      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
116      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
117    }
118
119    private void AttachProblemInstanceEventHandlers() {
120      if (ProblemInstance != null) {
121        ProblemInstance.EvaluationChanged += new EventHandler(ProblemInstance_EvaluationChanged);
122      }
123    }
124
125    private void EvalBestKnownSolution() {
126      if (BestKnownSolution == null) return;
127      try {
128        //call evaluator
129        BestKnownQuality = ProblemInstance.Evaluate(BestKnownSolution.Solution).Quality;
130        BestKnownSolution.Quality = new DoubleValue(BestKnownQuality);
131      } catch {
132        BestKnownQuality = double.NaN;
133        BestKnownSolution = null;
134      }
135    }
136
137    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
138      EvalBestKnownSolution();
139    }
140
141    void ProblemInstance_EvaluationChanged(object sender, EventArgs e) {
142      BestKnownQuality = double.NaN;
143      if (BestKnownSolution != null) {
144        // the tour is not valid if there are more vehicles in it than allowed
145        if (ProblemInstance.Vehicles.Value < BestKnownSolution.Solution.GetTours().Count) {
146          BestKnownSolution = null;
147        } else EvalBestKnownSolution();
148      }
149    }
150
151    void ProblemInstanceParameter_ValueChanged(object sender, EventArgs e) {
152      //InitializeOperators();
153      AttachProblemInstanceEventHandlers();
154
155      //OnOperatorsChanged();
156    }
157
158    public void SetProblemInstance(IVRPProblemInstance instance) {
159      ProblemInstanceParameter.ValueChanged -= new EventHandler(ProblemInstanceParameter_ValueChanged);
160
161      ProblemInstance = instance;
162      AttachProblemInstanceEventHandlers();
163
164      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
165    }
166
167    private void InitializeOperators() {
168      Operators.Add(new VRPSimilarityCalculator());
169      Operators.Add(new QualitySimilarityCalculator());
170      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
171    }
172
173    protected override void ParameterizeOperators() {
174      base.ParameterizeOperators();
175      Parameterize();
176    }
177
178    private void Parameterize() {
179      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
180        op.SolutionVariableName = Encoding.Name;
181        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
182        var calc = op as VRPSimilarityCalculator;
183        if (calc != null) calc.ProblemInstance = ProblemInstance;
184      }
185    }
186
187    #endregion
188
189    private void InitializeRandomVRPInstance() {
190      System.Random rand = new System.Random();
191
192      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
193      int cities = 100;
194
195      problem.Coordinates = new DoubleMatrix(cities + 1, 2);
196      problem.Demand = new DoubleArray(cities + 1);
197      problem.DueTime = new DoubleArray(cities + 1);
198      problem.ReadyTime = new DoubleArray(cities + 1);
199      problem.ServiceTime = new DoubleArray(cities + 1);
200
201      problem.Vehicles.Value = 100;
202      problem.Capacity.Value = 200;
203
204      for (int i = 0; i <= cities; i++) {
205        problem.Coordinates[i, 0] = rand.Next(0, 100);
206        problem.Coordinates[i, 1] = rand.Next(0, 100);
207
208        if (i == 0) {
209          problem.Demand[i] = 0;
210          problem.DueTime[i] = Int16.MaxValue;
211          problem.ReadyTime[i] = 0;
212          problem.ServiceTime[i] = 0;
213        } else {
214          problem.Demand[i] = rand.Next(10, 50);
215          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
216          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
217          problem.ServiceTime[i] = 90;
218        }
219      }
220
221      this.ProblemInstance = problem;
222    }
223
224    public void ImportSolution(string solutionFileName) {
225      SolutionParser parser = new SolutionParser(solutionFileName);
226      parser.Parse();
227
228      HeuristicLab.Problems.VehicleRouting.Encodings.Potvin.PotvinEncodedSolution encoding = new Encodings.Potvin.PotvinEncodedSolution(ProblemInstance);
229
230      int cities = 0;
231      foreach (List<int> route in parser.Routes) {
232        Tour tour = new Tour();
233        tour.Stops.AddRange(route);
234        cities += tour.Stops.Count;
235
236        encoding.Tours.Add(tour);
237      }
238
239      if (cities != ProblemInstance.Coordinates.Rows - 1)
240        ErrorHandling.ShowErrorDialog(new Exception("The optimal solution does not seem to correspond with the problem data"));
241      else {
242        VRPSolution solution = new VRPSolution(ProblemInstance, encoding, new DoubleValue(0));
243        BestKnownSolutionParameter.Value = solution;
244      }
245    }
246
247    #region Instance Consuming
248    public void Load(IVRPData data, IVRPDataInterpreter interpreter) {
249      VRPInstanceDescription instance = interpreter.Interpret(data);
250
251      Name = instance.Name;
252      Description = instance.Description;
253
254      BestKnownQuality = double.NaN;
255      BestKnownSolution = null;
256
257      if (ProblemInstance != null && instance.ProblemInstance != null &&
258        instance.ProblemInstance.GetType() == ProblemInstance.GetType())
259        SetProblemInstance(instance.ProblemInstance);
260      else
261        ProblemInstance = instance.ProblemInstance;
262
263      OnReset();
264
265      if (instance.BestKnownQuality != null) {
266        BestKnownQuality = instance.BestKnownQuality ?? double.NaN;
267      }
268
269      if (instance.BestKnownSolution != null) {
270        VRPSolution solution = new VRPSolution(ProblemInstance, instance.BestKnownSolution, new DoubleValue(0));
271        BestKnownSolution = solution;
272      }
273    }
274    #endregion
275
276    #region IProblemInstanceConsumer<VRPData> Members
277
278    public void Load(IVRPData data) {
279      var interpreterDataType = data.GetType();
280      var interpreterType = typeof(IVRPDataInterpreter<>).MakeGenericType(interpreterDataType);
281
282      var interpreters = ApplicationManager.Manager.GetTypes(interpreterType);
283
284      var concreteInterpreter = interpreters.Single(t => GetInterpreterDataType(t) == interpreterDataType);
285
286      Load(data, (IVRPDataInterpreter)Activator.CreateInstance(concreteInterpreter));
287    }
288
289    private Type GetInterpreterDataType(Type type) {
290      var parentInterfaces = type.BaseType.GetInterfaces();
291      var interfaces = type.GetInterfaces().Except(parentInterfaces);
292
293      var interpreterInterface = interfaces.Single(i => typeof(IVRPDataInterpreter).IsAssignableFrom(i));
294      return interpreterInterface.GetGenericArguments()[0];
295    }
296    #endregion
297  }
298}
Note: See TracBrowser for help on using the repository browser.