Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs @ 7203

Last change on this file since 7203 was 7203, checked in by svonolfe, 13 years ago

Added static item image according to #1651

File size: 16.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Problems.VehicleRouting.Interfaces;
35using HeuristicLab.Problems.VehicleRouting.Parsers;
36using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
37using HeuristicLab.Problems.VehicleRouting.Variants;
38
39namespace HeuristicLab.Problems.VehicleRouting {
40  [Item("Vehicle Routing Problem", "Represents a Vehicle Routing Problem.")]
41  [Creatable("Problems")]
42  [StorableClass]
43  public sealed class VehicleRoutingProblem : ParameterizedNamedItem, ISingleObjectiveHeuristicOptimizationProblem, IStorableContent {
44    public string Filename { get; set; }
45
46    public static new Image StaticItemImage {
47      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
48    }
49
50    #region Parameter Properties
51    public ValueParameter<BoolValue> MaximizationParameter {
52      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
53    }
54    IParameter ISingleObjectiveHeuristicOptimizationProblem.MaximizationParameter {
55      get { return MaximizationParameter; }
56    }
57    public ValueParameter<IVRPProblemInstance> ProblemInstanceParameter {
58      get { return (ValueParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
59    }
60    public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
61      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
62    }
63    IParameter ISingleObjectiveHeuristicOptimizationProblem.BestKnownQualityParameter {
64      get { return BestKnownQualityParameter; }
65    }
66    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
67      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
68    }
69    public IValueParameter<IVRPCreator> SolutionCreatorParameter {
70      get { return (IValueParameter<IVRPCreator>)Parameters["SolutionCreator"]; }
71    }
72    IParameter IHeuristicOptimizationProblem.SolutionCreatorParameter {
73      get { return SolutionCreatorParameter; }
74    }
75    public IValueParameter<IVRPEvaluator> EvaluatorParameter {
76      get { return (IValueParameter<IVRPEvaluator>)Parameters["Evaluator"]; }
77    }
78    IParameter IHeuristicOptimizationProblem.EvaluatorParameter {
79      get { return EvaluatorParameter; }
80    }
81    #endregion
82
83    #region Properties
84    public IVRPProblemInstance ProblemInstance {
85      get { return ProblemInstanceParameter.Value; }
86      set { ProblemInstanceParameter.Value = value; }
87    }
88
89    public VRPSolution BestKnownSolution {
90      get { return BestKnownSolutionParameter.Value; }
91      set { BestKnownSolutionParameter.Value = value; }
92    }
93
94    public ISingleObjectiveEvaluator Evaluator {
95      get { return ProblemInstance.EvaluatorParameter.Value; }
96    }
97
98    IEvaluator IHeuristicOptimizationProblem.Evaluator {
99      get { return this.Evaluator; }
100    }
101
102    public ISolutionCreator SolutionCreator {
103      get { return ProblemInstance.SolutionCreatorParameter.Value; }
104    }
105
106    [Storable]
107    private List<IOperator> operators;
108
109    public IEnumerable<IOperator> Operators {
110      get { return operators; }
111    }
112    #endregion
113
114    [StorableConstructor]
115    private VehicleRoutingProblem(bool deserializing) : base(deserializing) { }
116    public VehicleRoutingProblem()
117      : base() {
118      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Vehicle Routing Problem is a minimization problem.", new BoolValue(false)));
119      Parameters.Add(new ValueParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
120      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
121      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
122
123      operators = new List<IOperator>();
124
125      InitializeRandomVRPInstance();
126      InitializeOperators();
127
128      AttachEventHandlers();
129      AttachProblemInstanceEventHandlers();
130    }
131
132    public override IDeepCloneable Clone(Cloner cloner) {
133      return new VehicleRoutingProblem(this, cloner);
134    }
135
136    private VehicleRoutingProblem(VehicleRoutingProblem original, Cloner cloner)
137      : base(original, cloner) {
138      this.operators = original.operators.Select(x => (IOperator)cloner.Clone(x)).ToList();
139      this.AttachEventHandlers();
140    }
141
142    #region Events
143    public event EventHandler SolutionCreatorChanged;
144    private void OnSolutionCreatorChanged() {
145      EventHandler handler = SolutionCreatorChanged;
146      if (handler != null) handler(this, EventArgs.Empty);
147    }
148    public event EventHandler EvaluatorChanged;
149    private void OnEvaluatorChanged() {
150      EventHandler handler = EvaluatorChanged;
151      if (handler != null) handler(this, EventArgs.Empty);
152    }
153    public event EventHandler OperatorsChanged;
154    private void OnOperatorsChanged() {
155      EventHandler handler = OperatorsChanged;
156      if (handler != null) handler(this, EventArgs.Empty);
157    }
158    public event EventHandler Reset;
159    private void OnReset() {
160      EventHandler handler = Reset;
161      if (handler != null) handler(this, EventArgs.Empty);
162    } 
163    #endregion
164
165    #region Helpers
166    [StorableHook(HookType.AfterDeserialization)]
167    private void AfterDeserializationHook() {
168      AttachEventHandlers();
169      AttachProblemInstanceEventHandlers();
170    }
171
172    private void AttachEventHandlers() {
173      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
174    }
175
176    private void AttachProblemInstanceEventHandlers() {
177      if (Parameters.ContainsKey("Evaluator"))
178        Parameters.Remove("Evaluator");
179
180      if (Parameters.ContainsKey("SolutionCreator"))
181        Parameters.Remove("SolutionCreator");
182
183      if (Parameters.ContainsKey("BestKnownSolution"))
184        Parameters.Remove("BestKnownSolution");
185
186      if (Parameters.ContainsKey("BestKnownQuality"))
187        Parameters.Remove("BestKnownQuality");
188
189
190      if (ProblemInstance != null) {
191        ProblemInstance.SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
192        ProblemInstance.EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
193        Parameters.Add(ProblemInstance.EvaluatorParameter);
194        Parameters.Add(ProblemInstance.SolutionCreatorParameter);
195
196        Parameters.Add(ProblemInstance.BestKnownQualityParameter);
197        Parameters.Add(ProblemInstance.BestKnownSolutionParameter);
198      }
199    }
200
201    void ProblemInstanceParameter_ValueChanged(object sender, EventArgs e) {
202      AttachProblemInstanceEventHandlers();
203      InitializeOperators();
204
205      OnSolutionCreatorChanged();
206      OnEvaluatorChanged();
207      OnOperatorsChanged();
208    }
209
210    public void SetProblemInstance(IVRPProblemInstance instance) {
211      ProblemInstanceParameter.ValueChanged -= new EventHandler(ProblemInstanceParameter_ValueChanged);
212
213      ProblemInstance = instance;
214      AttachProblemInstanceEventHandlers();
215
216      OnSolutionCreatorChanged();
217      OnEvaluatorChanged();
218
219      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
220    }
221
222    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
223      ParameterizeSolutionCreator();
224     
225      OnSolutionCreatorChanged();
226    }
227    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
228      OnEvaluatorChanged();
229    }
230
231    private void InitializeOperators() {
232      operators = new List<IOperator>();
233
234      if (ProblemInstance != null) {
235        operators.AddRange(
236        ProblemInstance.Operators.Concat(
237          ApplicationManager.Manager.GetInstances<IGeneralVRPOperator>().Cast<IOperator>()).OrderBy(op => op.Name));
238      }
239
240      ParameterizeOperators();
241    }
242
243    private void ParameterizeSolutionCreator() {
244      if (SolutionCreator is IMultiVRPOperator) {
245        (SolutionCreator as IMultiVRPOperator).SetOperators(Operators);
246      }
247    }
248
249    private void ParameterizeOperators() {
250      foreach (IOperator op in Operators) {
251        if (op is IMultiVRPOperator) {
252          (op as IMultiVRPOperator).SetOperators(Operators);
253        }
254      }
255    }
256    #endregion
257
258    public void ImportFromCordeau(string cordeauFileName) {
259      CordeauParser parser = new CordeauParser(cordeauFileName);
260      parser.Parse();
261
262      MDCVRPTWProblemInstance problem = new MDCVRPTWProblemInstance();
263
264      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
265      problem.Vehicles.Value = parser.Vehicles;
266      problem.Capacity = new DoubleArray(parser.Capacity);
267      problem.Demand = new DoubleArray(parser.Demands);
268      problem.Depots.Value = parser.Depots;
269      problem.VehicleDepotAssignment = new IntArray(parser.Vehicles);
270      problem.ReadyTime = new DoubleArray(parser.Readytimes);
271      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
272      problem.DueTime = new DoubleArray(parser.Duetimes);
273
274      int depot = 0;
275      int i = 0;
276      while(i < parser.Vehicles) {
277        problem.VehicleDepotAssignment[i] = depot;
278
279        i++;
280        if (i % (parser.Vehicles / parser.Depots) == 0)
281          depot++;
282      }
283
284      this.ProblemInstance = problem;
285
286      OnReset();
287    }
288
289    public void ImportFromLiLim(string liLimFileName) {
290      LiLimParser parser = new LiLimParser(liLimFileName);
291      parser.Parse();
292
293      CVRPPDTWProblemInstance problem = new CVRPPDTWProblemInstance();
294
295      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
296      problem.Vehicles.Value = parser.Vehicles;
297      problem.Capacity.Value = parser.Capacity;
298      problem.Demand = new DoubleArray(parser.Demands);
299      problem.ReadyTime = new DoubleArray(parser.Readytimes);
300      problem.DueTime = new DoubleArray(parser.Duetimes);
301      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
302      problem.PickupDeliveryLocation = new IntArray(parser.PickupDeliveryLocations);
303
304      this.ProblemInstance = problem;
305
306      OnReset();
307    }
308
309    public void ImportFromSolomon(string solomonFileName) {
310      SolomonParser parser = new SolomonParser(solomonFileName);
311      parser.Parse();
312
313      this.Name = parser.ProblemName;
314      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
315     
316      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
317      problem.Vehicles.Value = parser.Vehicles;
318      problem.Capacity.Value = parser.Capacity;
319      problem.Demand = new DoubleArray(parser.Demands);
320      problem.ReadyTime = new DoubleArray(parser.Readytimes);
321      problem.DueTime = new DoubleArray(parser.Duetimes);
322      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
323
324      this.ProblemInstance = problem;
325
326      OnReset();
327    }
328
329    public void ImportFromTSPLib(string tspFileName) {
330      TSPLIBParser parser = new TSPLIBParser(tspFileName);
331      parser.Parse();
332
333      this.Name = parser.Name;
334      int problemSize = parser.Demands.Length;
335
336      if (parser.Depot != 1) {
337        ErrorHandling.ShowErrorDialog(new Exception("Invalid depot specification"));
338        return;
339      }
340
341      if (parser.WeightType != TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D)  {
342        ErrorHandling.ShowErrorDialog(new Exception("Invalid weight type"));
343        return;
344      }
345
346      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
347      problem.Coordinates = new DoubleMatrix(parser.Vertices);
348      if (parser.Vehicles != -1)
349        problem.Vehicles.Value = parser.Vehicles;
350      else
351        problem.Vehicles.Value = problemSize - 1;
352      problem.Capacity.Value = parser.Capacity;
353      problem.Demand = new DoubleArray(parser.Demands);
354      problem.ReadyTime = new DoubleArray(problemSize);
355      problem.DueTime = new DoubleArray(problemSize);
356      problem.ServiceTime = new DoubleArray(problemSize);
357
358      for (int i = 0; i < problemSize; i++) {
359        problem.ReadyTime[i] = 0;
360        problem.DueTime[i] = int.MaxValue;
361        problem.ServiceTime[i] = 0;
362      }
363
364      if (parser.Distance != -1) {
365        problem.DueTime[0] = parser.Distance;
366      }
367
368      this.ProblemInstance = problem;
369
370      OnReset();
371    }
372
373    public void ImportFromORLib(string orFileName) {
374      ORLIBParser parser = new ORLIBParser(orFileName);
375      parser.Parse();
376
377      this.Name = parser.Name;
378      int problemSize = parser.Demands.Length;
379
380      CVRPProblemInstance problem = new CVRPProblemInstance();
381
382      problem.Coordinates = new DoubleMatrix(parser.Vertices);
383      problem.Vehicles.Value = problemSize - 1;
384      problem.Capacity.Value = parser.Capacity;
385      problem.Demand = new DoubleArray(parser.Demands);
386
387      this.ProblemInstance = problem;
388
389      OnReset();
390    }
391
392    private void InitializeRandomVRPInstance() {
393      System.Random rand = new System.Random();
394
395      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
396      int cities = 100;
397
398      problem.Coordinates = new DoubleMatrix(cities + 1, 2);
399      problem.Demand = new DoubleArray(cities + 1);
400      problem.DueTime = new DoubleArray(cities + 1);
401      problem.ReadyTime = new DoubleArray(cities + 1);
402      problem.ServiceTime = new DoubleArray(cities + 1);
403
404      problem.Vehicles.Value = 100;
405      problem.Capacity.Value = 200;
406
407      for (int i = 0; i <= cities; i++) {
408        problem.Coordinates[i, 0] = rand.Next(0, 100);
409        problem.Coordinates[i, 1] = rand.Next(0, 100);
410
411        if (i == 0) {
412          problem.Demand[i] = 0;
413          problem.DueTime[i] = Int16.MaxValue;
414          problem.ReadyTime[i] = 0;
415          problem.ServiceTime[i] = 0;
416        } else {
417          problem.Demand[i] = rand.Next(10, 50);
418          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
419          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
420          problem.ServiceTime[i] = 90;
421        }
422      }
423
424      this.ProblemInstance = problem;
425    }
426
427    public void ImportSolution(string solutionFileName) {
428      SolutionParser parser = new SolutionParser(solutionFileName);
429      parser.Parse();
430
431      HeuristicLab.Problems.VehicleRouting.Encodings.Potvin.PotvinEncoding encoding = new Encodings.Potvin.PotvinEncoding(ProblemInstance);
432
433      int cities = 0;
434      foreach (List<int> route in parser.Routes) {
435        Tour tour = new Tour();
436        tour.Stops.AddRange(route);
437        cities += tour.Stops.Count;
438
439        encoding.Tours.Add(tour);
440      }
441
442      if (cities != ProblemInstance.Coordinates.Rows - 1)
443        ErrorHandling.ShowErrorDialog(new Exception("The optimal solution does not seem to correspond with the problem data"));
444      else {
445        VRPSolution solution = new VRPSolution(ProblemInstance, encoding, new DoubleValue(0));
446        ProblemInstance.BestKnownSolutionParameter.Value = solution;
447      }
448    }
449  }
450}
Note: See TracBrowser for help on using the repository browser.