Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 3947 was 3947, checked in by svonolfe, 14 years ago

Fixed some problems in the VRP implementation (#1039)
File size: 13.4 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.Linq;
25using System.Text;
26using HeuristicLab.Operators;
27using HeuristicLab.Data;
28using HeuristicLab.Core;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.VehicleRouting.Encodings;
32
33namespace HeuristicLab.Problems.VehicleRouting {
34  public struct TourEvaluation {
35    public double Quality { get; set; }
36    public double VehcilesUtilized { get; set; }
37    public double TravelTime { get; set; }
38    public double Distance { get; set; }
39    public double Overload { get; set; }
40    public double Tardiness { get; set; }
41  }
42 
43  [Item("VRPEvaluator", "Evaluates solutions for the VRP problem.")]
44  [StorableClass]
45  public sealed class VRPEvaluator : SingleSuccessorOperator, IVRPEvaluator {
46    #region ISingleObjectiveEvaluator Members
47    public ILookupParameter<DoubleValue> QualityParameter {
48      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
49    }
50    #endregion
51
52    public ILookupParameter<DoubleValue> VehcilesUtilizedParameter {
53      get { return (ILookupParameter<DoubleValue>)Parameters["VehiclesUtilized"]; }
54    }
55    public ILookupParameter<DoubleValue> TravelTimeParameter {
56      get { return (ILookupParameter<DoubleValue>)Parameters["TravelTime"]; }
57    }
58    public ILookupParameter<DoubleValue> DistanceParameter {
59      get { return (ILookupParameter<DoubleValue>)Parameters["Distance"]; }
60    }
61    public ILookupParameter<DoubleValue> OverloadParameter {
62      get { return (ILookupParameter<DoubleValue>)Parameters["Overload"]; }
63    }
64    public ILookupParameter<DoubleValue> TardinessParameter {
65      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
66    }
67
68    public ILookupParameter<IVRPEncoding> VRPSolutionParameter {
69      get { return (ILookupParameter<IVRPEncoding>)Parameters["VRPSolution"]; }
70    }
71    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
72      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
73    }
74    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
75      get { return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
76    }
77    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
78      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
79    }
80    public ILookupParameter<IntValue> VehiclesParameter {
81      get { return (ILookupParameter<IntValue>)Parameters["Vehicles"]; }
82    }
83    public ILookupParameter<DoubleValue> CapacityParameter {
84      get { return (ILookupParameter<DoubleValue>)Parameters["Capacity"]; }
85    }
86    public ILookupParameter<DoubleArray> DemandParameter {
87      get { return (ILookupParameter<DoubleArray>)Parameters["Demand"]; }
88    }
89    public ILookupParameter<DoubleArray> ReadyTimeParameter {
90      get { return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"]; }
91    }
92    public ILookupParameter<DoubleArray> DueTimeParameter {
93      get { return (ILookupParameter<DoubleArray>)Parameters["DueTime"]; }
94    }
95    public ILookupParameter<DoubleArray> ServiceTimeParameter {
96      get { return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"]; }
97    }
98    public ILookupParameter<DoubleValue> FleetUsageFactor {
99      get { return (ILookupParameter<DoubleValue>)Parameters["FleetUsageFactor"]; }
100    }
101    public ILookupParameter<DoubleValue> TimeFactor {
102      get { return (ILookupParameter<DoubleValue>)Parameters["TimeFactor"]; }
103    }
104    public ILookupParameter<DoubleValue> DistanceFactor {
105      get { return (ILookupParameter<DoubleValue>)Parameters["DistanceFactor"]; }
106    }
107    public ILookupParameter<DoubleValue> OverloadPenalty {
108      get { return (ILookupParameter<DoubleValue>)Parameters["OverloadPenalty"]; }
109    }
110    public ILookupParameter<DoubleValue> TardinessPenalty {
111      get { return (ILookupParameter<DoubleValue>)Parameters["TardinessPenalty"]; }
112    }
113
114    public VRPEvaluator()
115      : base() {
116      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the VRP solution."));
117      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
118      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The total travel time."));
119      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
120      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
121      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
122      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPSolution", "The VRP solution which should be evaluated."));
123      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
124      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
125      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
126      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
127      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
128      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
129      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
130      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
131      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
132      Parameters.Add(new LookupParameter<DoubleValue>("FleetUsageFactor", "The fleet usage factor considered in the evaluation."));
133      Parameters.Add(new LookupParameter<DoubleValue>("TimeFactor", "The time factor considered in the evaluation."));
134      Parameters.Add(new LookupParameter<DoubleValue>("DistanceFactor", "The distance factor considered in the evaluation."));
135      Parameters.Add(new LookupParameter<DoubleValue>("OverloadPenalty", "The overload penalty considered in the evaluation."));
136      Parameters.Add(new LookupParameter<DoubleValue>("TardinessPenalty", "The tardiness penalty considered in the evaluation."));
137    }
138
139    private double CalculateFleetUsage() {
140      IVRPEncoding vrpSolution = VRPSolutionParameter.ActualValue;
141
142      return vrpSolution.Tours.Count;
143    }
144
145    private static double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
146      double distance = 0.0;
147
148      distance =
149          Math.Sqrt(
150            Math.Pow(coordinates[start, 0] - coordinates[end, 0], 2) +
151            Math.Pow(coordinates[start, 1] - coordinates[end, 1], 2));
152
153      return distance;
154    }
155
156    private static DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates)
157    {
158      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
159
160      for (int i = 0; i < distanceMatrix.Rows; i++) {
161        for (int j = i; j < distanceMatrix.Columns; j++) {
162          double distance = CalculateDistance(i, j, coordinates);
163
164          distanceMatrix[i, j] = distance;
165          distanceMatrix[j, i] = distance;
166        }
167      }
168
169      return distanceMatrix;
170    }
171
172    private static double GetDistance(int start, int end,
173      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
174      double distance = 0.0;
175
176      if (useDistanceMatrix.Value) {
177        if (distanceMatrix.ActualValue == null) {
178          distanceMatrix.ActualValue = CreateDistanceMatrix(coordinates);
179        }
180
181        distance = distanceMatrix.ActualValue[start, end];
182      } else {
183        distance = CalculateDistance(start, end, coordinates);
184      }
185
186      return distance;
187    }
188
189    private static TourEvaluation EvaluateTour(Tour tour, 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 eval = new TourEvaluation();
194
195      double quality = 0.0;
196      double time = 0.0;
197
198      double distance = 0.0;
199      double waitingTime = 0.0;
200      double serviceTime = 0.0;
201      double delivered = 0.0;
202
203      double overweight = 0.0;
204      double tardiness = 0.0;
205
206      //simulate a tour, start and end at depot
207      for (int i = 1; i < tour.Count; i++) {
208        int start = tour[i - 1].Value;
209        int end = tour[i].Value;
210
211        //drive there
212        double currentDistace = GetDistance(start, end, coordinates, distanceMatrix, useDistanceMatrix);
213        distance += currentDistace;
214        time += currentDistace;
215
216        //check if it was serviced on time
217        if (time > dueTimeArray[end])
218          tardiness += time - dueTimeArray[end];
219
220        //wait
221        double currentWaitingTime = 0.0;
222        if (time < readyTimeArray[end])
223          currentWaitingTime = readyTimeArray[end] - time;
224        waitingTime += currentWaitingTime;
225        time += currentWaitingTime;
226
227        //service
228        delivered += demandArray[end];
229        double currentServiceTime = serviceTimeArray[end];
230        serviceTime += currentServiceTime;
231        time += currentServiceTime;
232      }
233
234      if (delivered > capacity.Value) {
235        overweight = delivered - capacity.Value;
236      }
237
238      //Fleet usage
239      quality += fleetUsageFactor.Value;
240      //Travel time
241      quality += timeFactor.Value * time;
242      //Distance
243      quality += distanceFactor.Value * distance;
244
245      //Penalties
246      quality += overloadPenalty.Value * overweight;
247      quality += tardinessPenalty.Value * tardiness;
248
249      eval.Distance = distance;
250      eval.TravelTime = time;
251      eval.VehcilesUtilized = 1;
252      eval.Overload = overweight;
253      eval.Tardiness = tardiness;
254      eval.Quality = quality;
255
256      return eval;
257    }
258
259    public static TourEvaluation Evaluate(IVRPEncoding solution, DoubleArray dueTimeArray,
260      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
261      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
262      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
263      TourEvaluation sumEval = new TourEvaluation();
264      sumEval.Distance = 0;
265      sumEval.Quality = 0;
266      sumEval.TravelTime = 0;
267      sumEval.VehcilesUtilized = 0;
268      sumEval.Overload = 0;
269      sumEval.Tardiness = 0;
270
271      foreach (Tour tour in solution.Tours) {
272        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
273          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
274          coordinates, distanceMatrix, useDistanceMatrix);
275        sumEval.Quality += eval.Quality;
276        sumEval.Distance += eval.Distance;
277        sumEval.TravelTime += eval.TravelTime;
278        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
279        sumEval.Overload += eval.Overload;
280        sumEval.Tardiness += eval.Tardiness;
281      }
282
283      return sumEval;
284    }
285
286    public sealed override IOperation Apply() {
287      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
288
289      TourEvaluation sumEval = Evaluate(solution, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
290        DemandParameter.ActualValue, CapacityParameter.ActualValue,
291        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
292        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
293
294      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
295      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
296      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
297      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
298      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
299      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
300
301      return base.Apply();
302    }
303  }
304}
Note: See TracBrowser for help on using the repository browser.