Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Evaluators/VRPEvaluator.cs @ 6951

Last change on this file since 6951 was 6760, checked in by epitzer, 13 years ago

#1530 integrate changes from trunk

File size: 10.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
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> VRPToursParameter {
65      get { return (ILookupParameter<IVRPEncoding>)Parameters["VRPTours"]; }
66    }
67   
68    public ILookupParameter<DoubleValue> FleetUsageFactor {
69      get { return (ILookupParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
70    }
71    public ILookupParameter<DoubleValue> TimeFactor {
72      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTimeFactor"]; }
73    }
74    public ILookupParameter<DoubleValue> DistanceFactor {
75      get { return (ILookupParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
76    }
77    public ILookupParameter<DoubleValue> OverloadPenalty {
78      get { return (ILookupParameter<DoubleValue>)Parameters["EvalOverloadPenalty"]; }
79    }
80    public ILookupParameter<DoubleValue> TardinessPenalty {
81      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTardinessPenalty"]; }
82    }
83
84    [StorableConstructor]
85    private VRPEvaluator(bool deserializing) : base(deserializing) { }
86    private VRPEvaluator(VRPEvaluator original, Cloner cloner)
87      : base(original, cloner) {
88    }
89    public VRPEvaluator()
90      : base() {
91      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the VRP solution."));
92      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
93      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The total travel time."));
94      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
95      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
96      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
97      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPTours", "The VRP tours which should be evaluated."));
98      Parameters.Add(new LookupParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation."));
99      Parameters.Add(new LookupParameter<DoubleValue>("EvalTimeFactor", "The time factor considered in the evaluation."));
100      Parameters.Add(new LookupParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation."));
101      Parameters.Add(new LookupParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation."));
102      Parameters.Add(new LookupParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation."));
103    }
104
105    public override IDeepCloneable Clone(Cloner cloner) {
106      return new VRPEvaluator(this, cloner);
107    }
108
109    private double CalculateFleetUsage() {
110      IVRPEncoding vrpSolution = VRPToursParameter.ActualValue;
111
112      return vrpSolution.GetTours(DistanceMatrixParameter, VehiclesParameter.ActualValue.Value).Count;
113    }
114
115    internal static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
116      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
117      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
118      DistanceMatrix distMatrix) {
119      TourEvaluation eval = new TourEvaluation();
120
121      double quality = 0.0;
122      double time = 0.0;
123
124      double distance = 0.0;
125      double waitingTime = 0.0;
126      double serviceTime = 0.0;
127      double delivered = 0.0;
128
129      double overweight = 0.0;
130      double tardiness = 0.0;
131
132      //simulate a tour, start and end at depot
133      for (int i = 0; i <= tour.Cities.Count; i++) {
134        int start = 0;
135        if(i > 0)
136          start = tour.Cities[i - 1];
137        int end = 0;
138        if (i < tour.Cities.Count)
139          end = tour.Cities[i];
140
141        //drive there
142        double currentDistace = VRPUtilities.GetDistance(start, end, distMatrix);
143        distance += currentDistace;
144        time += currentDistace;
145
146        //check if it was serviced on time
147        if (time > dueTimeArray[end])
148          tardiness += time - dueTimeArray[end];
149
150        //wait
151        double currentWaitingTime = 0.0;
152        if (time < readyTimeArray[end])
153          currentWaitingTime = readyTimeArray[end] - time;
154        waitingTime += currentWaitingTime;
155        time += currentWaitingTime;
156
157        //service
158        delivered += demandArray[end];
159        double currentServiceTime = serviceTimeArray[end];
160        serviceTime += currentServiceTime;
161        time += currentServiceTime;
162      }
163
164      if (delivered > capacity.Value) {
165        overweight = delivered - capacity.Value;
166      }
167
168      //Fleet usage
169      quality += fleetUsageFactor.Value;
170      //Travel time
171      quality += timeFactor.Value * time;
172      //Distance
173      quality += distanceFactor.Value * distance;
174
175      //Penalties
176      quality += overloadPenalty.Value * overweight;
177      quality += tardinessPenalty.Value * tardiness;
178
179      eval.Distance = distance;
180      eval.TravelTime = time;
181      eval.VehcilesUtilized = 1;
182      eval.Overload = overweight;
183      eval.Tardiness = tardiness;
184      eval.Quality = quality;
185
186      return eval;
187    }
188
189    public static TourEvaluation Evaluate(IVRPEncoding solution, IntValue vehicles, DoubleArray dueTimeArray,
190      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
191      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
192      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
193      TourEvaluation sumEval = new TourEvaluation();
194      sumEval.Distance = 0;
195      sumEval.Quality = 0;
196      sumEval.TravelTime = 0;
197      sumEval.VehcilesUtilized = 0;
198      sumEval.Overload = 0;
199      sumEval.Tardiness = 0;
200
201      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
202
203      foreach (Tour tour in solution.GetTours(distanceMatrix as ILookupParameter<DoubleMatrix>)) {
204        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
205          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
206          distMatrix);
207        sumEval.Quality += eval.Quality;
208        sumEval.Distance += eval.Distance;
209        sumEval.TravelTime += eval.TravelTime;
210        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
211        sumEval.Overload += eval.Overload;
212        sumEval.Tardiness += eval.Tardiness;
213      }
214
215      return sumEval;
216    }
217
218    public sealed override IOperation Apply() {
219      IVRPEncoding solution = VRPToursParameter.ActualValue;
220
221      TourEvaluation sumEval = Evaluate(solution, VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
222        DemandParameter.ActualValue, CapacityParameter.ActualValue,
223        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
224        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
225
226      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
227      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
228      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
229      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
230      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
231      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
232
233      return base.Apply();
234    }
235  }
236}
Note: See TracBrowser for help on using the repository browser.