Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Evaluators/VRPEvaluator.cs @ 4174

Last change on this file since 4174 was 4174, checked in by svonolfe, 12 years ago

Refactored VRP, added some Potvin operators (WIP) (#1039)

File size: 9.8 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 HeuristicLab.Core;
23using HeuristicLab.Data;
24using HeuristicLab.Operators;
25using HeuristicLab.Parameters;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27using HeuristicLab.Problems.VehicleRouting.Encodings;
28
29namespace HeuristicLab.Problems.VehicleRouting {
30  public struct TourEvaluation {
31    public double Quality { get; set; }
32    public double VehcilesUtilized { get; set; }
33    public double TravelTime { get; set; }
34    public double Distance { get; set; }
35    public double Overload { get; set; }
36    public double Tardiness { get; set; }
37  }
38
39  [Item("VRPEvaluator", "Evaluates solutions for the VRP problem.")]
40  [StorableClass]
41  public sealed class VRPEvaluator : VRPOperator, IVRPEvaluator {
42    #region ISingleObjectiveEvaluator Members
43    public ILookupParameter<DoubleValue> QualityParameter {
44      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
45    }
46    #endregion
47
48    public ILookupParameter<DoubleValue> VehcilesUtilizedParameter {
49      get { return (ILookupParameter<DoubleValue>)Parameters["VehiclesUtilized"]; }
50    }
51    public ILookupParameter<DoubleValue> TravelTimeParameter {
52      get { return (ILookupParameter<DoubleValue>)Parameters["TravelTime"]; }
53    }
54    public ILookupParameter<DoubleValue> DistanceParameter {
55      get { return (ILookupParameter<DoubleValue>)Parameters["Distance"]; }
56    }
57    public ILookupParameter<DoubleValue> OverloadParameter {
58      get { return (ILookupParameter<DoubleValue>)Parameters["Overload"]; }
59    }
60    public ILookupParameter<DoubleValue> TardinessParameter {
61      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
62    }
63
64    public ILookupParameter<IVRPEncoding> VRPSolutionParameter {
65      get { return (ILookupParameter<IVRPEncoding>)Parameters["VRPSolution"]; }
66    }
67   
68    public ILookupParameter<DoubleValue> FleetUsageFactor {
69      get { return (ILookupParameter<DoubleValue>)Parameters["FleetUsageFactor"]; }
70    }
71    public ILookupParameter<DoubleValue> TimeFactor {
72      get { return (ILookupParameter<DoubleValue>)Parameters["TimeFactor"]; }
73    }
74    public ILookupParameter<DoubleValue> DistanceFactor {
75      get { return (ILookupParameter<DoubleValue>)Parameters["DistanceFactor"]; }
76    }
77    public ILookupParameter<DoubleValue> OverloadPenalty {
78      get { return (ILookupParameter<DoubleValue>)Parameters["OverloadPenalty"]; }
79    }
80    public ILookupParameter<DoubleValue> TardinessPenalty {
81      get { return (ILookupParameter<DoubleValue>)Parameters["TardinessPenalty"]; }
82    }
83
84    public VRPEvaluator()
85      : base() {
86      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the VRP solution."));
87      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
88      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The total travel time."));
89      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
90      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
91      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
92      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPSolution", "The VRP solution which should be evaluated."));
93      Parameters.Add(new LookupParameter<DoubleValue>("FleetUsageFactor", "The fleet usage factor considered in the evaluation."));
94      Parameters.Add(new LookupParameter<DoubleValue>("TimeFactor", "The time factor considered in the evaluation."));
95      Parameters.Add(new LookupParameter<DoubleValue>("DistanceFactor", "The distance factor considered in the evaluation."));
96      Parameters.Add(new LookupParameter<DoubleValue>("OverloadPenalty", "The overload penalty considered in the evaluation."));
97      Parameters.Add(new LookupParameter<DoubleValue>("TardinessPenalty", "The tardiness penalty considered in the evaluation."));
98    }
99
100    private double CalculateFleetUsage() {
101      IVRPEncoding vrpSolution = VRPSolutionParameter.ActualValue;
102
103      return vrpSolution.Tours.Count;
104    }
105
106    internal static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
107      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
108      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
109      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
110      TourEvaluation eval = new TourEvaluation();
111
112      double quality = 0.0;
113      double time = 0.0;
114
115      double distance = 0.0;
116      double waitingTime = 0.0;
117      double serviceTime = 0.0;
118      double delivered = 0.0;
119
120      double overweight = 0.0;
121      double tardiness = 0.0;
122
123      //simulate a tour, start and end at depot
124      for (int i = 0; i <= tour.Cities.Count; i++) {
125        int start = 0;
126        if(i > 0)
127          start = tour.Cities[i - 1];
128        int end = 0;
129        if (i < tour.Cities.Count)
130          end = tour.Cities[i];
131
132        //drive there
133        double currentDistace = VRPUtilities.GetDistance(start, end, coordinates, distanceMatrix, useDistanceMatrix);
134        distance += currentDistace;
135        time += currentDistace;
136
137        //check if it was serviced on time
138        if (time > dueTimeArray[end])
139          tardiness += time - dueTimeArray[end];
140
141        //wait
142        double currentWaitingTime = 0.0;
143        if (time < readyTimeArray[end])
144          currentWaitingTime = readyTimeArray[end] - time;
145        waitingTime += currentWaitingTime;
146        time += currentWaitingTime;
147
148        //service
149        delivered += demandArray[end];
150        double currentServiceTime = serviceTimeArray[end];
151        serviceTime += currentServiceTime;
152        time += currentServiceTime;
153      }
154
155      if (delivered > capacity.Value) {
156        overweight = delivered - capacity.Value;
157      }
158
159      //Fleet usage
160      quality += fleetUsageFactor.Value;
161      //Travel time
162      quality += timeFactor.Value * time;
163      //Distance
164      quality += distanceFactor.Value * distance;
165
166      //Penalties
167      quality += overloadPenalty.Value * overweight;
168      quality += tardinessPenalty.Value * tardiness;
169
170      eval.Distance = distance;
171      eval.TravelTime = time;
172      eval.VehcilesUtilized = 1;
173      eval.Overload = overweight;
174      eval.Tardiness = tardiness;
175      eval.Quality = quality;
176
177      return eval;
178    }
179
180    public static TourEvaluation Evaluate(IVRPEncoding solution, DoubleArray dueTimeArray,
181      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
182      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
183      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
184      TourEvaluation sumEval = new TourEvaluation();
185      sumEval.Distance = 0;
186      sumEval.Quality = 0;
187      sumEval.TravelTime = 0;
188      sumEval.VehcilesUtilized = 0;
189      sumEval.Overload = 0;
190      sumEval.Tardiness = 0;
191
192      foreach (Tour tour in solution.Tours) {
193        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
194          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
195          coordinates, distanceMatrix, useDistanceMatrix);
196        sumEval.Quality += eval.Quality;
197        sumEval.Distance += eval.Distance;
198        sumEval.TravelTime += eval.TravelTime;
199        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
200        sumEval.Overload += eval.Overload;
201        sumEval.Tardiness += eval.Tardiness;
202      }
203
204      return sumEval;
205    }
206
207    public sealed override IOperation Apply() {
208      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
209
210      TourEvaluation sumEval = Evaluate(solution, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
211        DemandParameter.ActualValue, CapacityParameter.ActualValue,
212        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
213        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
214
215      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
216      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
217      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
218      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
219      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
220      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
221
222      return base.Apply();
223    }
224  }
225}
Note: See TracBrowser for help on using the repository browser.