Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4068 was 4068, checked in by swagner, 14 years ago

Sorted usings and removed unused usings in entire solution (#1094)
File size: 12.0 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 : SingleSuccessorOperator, 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    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
68      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
69    }
70    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
71      get { return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
72    }
73    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
74      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
75    }
76    public ILookupParameter<IntValue> VehiclesParameter {
77      get { return (ILookupParameter<IntValue>)Parameters["Vehicles"]; }
78    }
79    public ILookupParameter<DoubleValue> CapacityParameter {
80      get { return (ILookupParameter<DoubleValue>)Parameters["Capacity"]; }
81    }
82    public ILookupParameter<DoubleArray> DemandParameter {
83      get { return (ILookupParameter<DoubleArray>)Parameters["Demand"]; }
84    }
85    public ILookupParameter<DoubleArray> ReadyTimeParameter {
86      get { return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"]; }
87    }
88    public ILookupParameter<DoubleArray> DueTimeParameter {
89      get { return (ILookupParameter<DoubleArray>)Parameters["DueTime"]; }
90    }
91    public ILookupParameter<DoubleArray> ServiceTimeParameter {
92      get { return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"]; }
93    }
94    public ILookupParameter<DoubleValue> FleetUsageFactor {
95      get { return (ILookupParameter<DoubleValue>)Parameters["FleetUsageFactor"]; }
96    }
97    public ILookupParameter<DoubleValue> TimeFactor {
98      get { return (ILookupParameter<DoubleValue>)Parameters["TimeFactor"]; }
99    }
100    public ILookupParameter<DoubleValue> DistanceFactor {
101      get { return (ILookupParameter<DoubleValue>)Parameters["DistanceFactor"]; }
102    }
103    public ILookupParameter<DoubleValue> OverloadPenalty {
104      get { return (ILookupParameter<DoubleValue>)Parameters["OverloadPenalty"]; }
105    }
106    public ILookupParameter<DoubleValue> TardinessPenalty {
107      get { return (ILookupParameter<DoubleValue>)Parameters["TardinessPenalty"]; }
108    }
109
110    public VRPEvaluator()
111      : base() {
112      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the VRP solution."));
113      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
114      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The total travel time."));
115      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
116      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
117      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
118      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPSolution", "The VRP solution which should be evaluated."));
119      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
120      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
121      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
122      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
123      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
124      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
125      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
126      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
127      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
128      Parameters.Add(new LookupParameter<DoubleValue>("FleetUsageFactor", "The fleet usage factor considered in the evaluation."));
129      Parameters.Add(new LookupParameter<DoubleValue>("TimeFactor", "The time factor considered in the evaluation."));
130      Parameters.Add(new LookupParameter<DoubleValue>("DistanceFactor", "The distance factor considered in the evaluation."));
131      Parameters.Add(new LookupParameter<DoubleValue>("OverloadPenalty", "The overload penalty considered in the evaluation."));
132      Parameters.Add(new LookupParameter<DoubleValue>("TardinessPenalty", "The tardiness penalty considered in the evaluation."));
133    }
134
135    private double CalculateFleetUsage() {
136      IVRPEncoding vrpSolution = VRPSolutionParameter.ActualValue;
137
138      return vrpSolution.Tours.Count;
139    }
140
141    private static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
142      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
143      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
144      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
145      TourEvaluation eval = new TourEvaluation();
146
147      double quality = 0.0;
148      double time = 0.0;
149
150      double distance = 0.0;
151      double waitingTime = 0.0;
152      double serviceTime = 0.0;
153      double delivered = 0.0;
154
155      double overweight = 0.0;
156      double tardiness = 0.0;
157
158      //simulate a tour, start and end at depot
159      for (int i = 1; i < tour.Count; i++) {
160        int start = tour[i - 1].Value;
161        int end = tour[i].Value;
162
163        //drive there
164        double currentDistace = VehicleRoutingProblem.GetDistance(start, end, coordinates, distanceMatrix, useDistanceMatrix);
165        distance += currentDistace;
166        time += currentDistace;
167
168        //check if it was serviced on time
169        if (time > dueTimeArray[end])
170          tardiness += time - dueTimeArray[end];
171
172        //wait
173        double currentWaitingTime = 0.0;
174        if (time < readyTimeArray[end])
175          currentWaitingTime = readyTimeArray[end] - time;
176        waitingTime += currentWaitingTime;
177        time += currentWaitingTime;
178
179        //service
180        delivered += demandArray[end];
181        double currentServiceTime = serviceTimeArray[end];
182        serviceTime += currentServiceTime;
183        time += currentServiceTime;
184      }
185
186      if (delivered > capacity.Value) {
187        overweight = delivered - capacity.Value;
188      }
189
190      //Fleet usage
191      quality += fleetUsageFactor.Value;
192      //Travel time
193      quality += timeFactor.Value * time;
194      //Distance
195      quality += distanceFactor.Value * distance;
196
197      //Penalties
198      quality += overloadPenalty.Value * overweight;
199      quality += tardinessPenalty.Value * tardiness;
200
201      eval.Distance = distance;
202      eval.TravelTime = time;
203      eval.VehcilesUtilized = 1;
204      eval.Overload = overweight;
205      eval.Tardiness = tardiness;
206      eval.Quality = quality;
207
208      return eval;
209    }
210
211    public static TourEvaluation Evaluate(IVRPEncoding solution, DoubleArray dueTimeArray,
212      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
213      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
214      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
215      TourEvaluation sumEval = new TourEvaluation();
216      sumEval.Distance = 0;
217      sumEval.Quality = 0;
218      sumEval.TravelTime = 0;
219      sumEval.VehcilesUtilized = 0;
220      sumEval.Overload = 0;
221      sumEval.Tardiness = 0;
222
223      foreach (Tour tour in solution.Tours) {
224        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
225          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
226          coordinates, distanceMatrix, useDistanceMatrix);
227        sumEval.Quality += eval.Quality;
228        sumEval.Distance += eval.Distance;
229        sumEval.TravelTime += eval.TravelTime;
230        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
231        sumEval.Overload += eval.Overload;
232        sumEval.Tardiness += eval.Tardiness;
233      }
234
235      return sumEval;
236    }
237
238    public sealed override IOperation Apply() {
239      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
240
241      TourEvaluation sumEval = Evaluate(solution, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
242        DemandParameter.ActualValue, CapacityParameter.ActualValue,
243        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
244        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
245
246      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
247      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
248      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
249      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
250      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
251      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
252
253      return base.Apply();
254    }
255  }
256}
Note: See TracBrowser for help on using the repository browser.