Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4722 was 4722, checked in by swagner, 13 years ago

Merged cloning refactoring branch back into trunk (#922)

File size: 10.2 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.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      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
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, coordinates, distanceMatrix, useDistanceMatrix);
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, ILookupParameter<DoubleMatrix> 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      foreach (Tour tour in solution.GetTours(distanceMatrix)) {
202        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
203          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
204          coordinates, distanceMatrix, useDistanceMatrix);
205        sumEval.Quality += eval.Quality;
206        sumEval.Distance += eval.Distance;
207        sumEval.TravelTime += eval.TravelTime;
208        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
209        sumEval.Overload += eval.Overload;
210        sumEval.Tardiness += eval.Tardiness;
211      }
212
213      return sumEval;
214    }
215
216    public sealed override IOperation Apply() {
217      IVRPEncoding solution = VRPToursParameter.ActualValue;
218
219      TourEvaluation sumEval = Evaluate(solution, VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
220        DemandParameter.ActualValue, CapacityParameter.ActualValue,
221        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
222        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
223
224      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
225      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
226      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
227      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
228      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
229      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
230
231      return base.Apply();
232    }
233  }
234}
Note: See TracBrowser for help on using the repository browser.