Free cookie consent management tool by TermsFeed Policy Generator

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

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

Added CVRP implementation using the Alba encoding (#1039)
File size: 14.1 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<DoubleValue> MaxTravelTimeParameter {
87      get { return (ILookupParameter<DoubleValue>)Parameters["MaxTravelTime"]; }
88    } */
89    public ILookupParameter<DoubleArray> DemandParameter {
90      get { return (ILookupParameter<DoubleArray>)Parameters["Demand"]; }
91    }
92    public ILookupParameter<DoubleArray> ReadyTimeParameter {
93      get { return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"]; }
94    }
95    public ILookupParameter<DoubleArray> DueTimeParameter {
96      get { return (ILookupParameter<DoubleArray>)Parameters["DueTime"]; }
97    }
98    public ILookupParameter<DoubleArray> ServiceTimeParameter {
99      get { return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"]; }
100    }
101    public IValueParameter<DoubleValue> FleetUsageFactor {
102      get { return (IValueParameter<DoubleValue>)Parameters["FleetUsageFactor"]; }
103    }
104    public IValueParameter<DoubleValue> TimeFactor {
105      get { return (IValueParameter<DoubleValue>)Parameters["TimeFactor"]; }
106    }
107    public IValueParameter<DoubleValue> DistanceFactor {
108      get { return (IValueParameter<DoubleValue>)Parameters["DistanceFactor"]; }
109    }
110    /*public IValueParameter<DoubleValue> TimePenalty {
111      get { return (IValueParameter<DoubleValue>)Parameters["TimePenalty"]; }
112    } */
113    public IValueParameter<DoubleValue> OverloadPenalty {
114      get { return (IValueParameter<DoubleValue>)Parameters["OverloadPenalty"]; }
115    }
116    public IValueParameter<DoubleValue> TardinessPenalty {
117      get { return (IValueParameter<DoubleValue>)Parameters["TardinessPenalty"]; }
118    }
119
120    public VRPEvaluator()
121      : base() {
122      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the VRP solution."));
123      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
124      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The total travel time."));
125      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
126      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
127      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
128      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPSolution", "The VRP solution which should be evaluated."));
129      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
130      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
131      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
132      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
133      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
134      //Parameters.Add(new LookupParameter<DoubleValue>("MaxTravelTime", "The maximum travel time of each route."));
135      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
136      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
137      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
138      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
139      Parameters.Add(new ValueParameter<DoubleValue>("FleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
140      Parameters.Add(new ValueParameter<DoubleValue>("TimeFactor", "The time factor considered in the evaluation.", new DoubleValue(0)));
141      Parameters.Add(new ValueParameter<DoubleValue>("DistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
142      //Parameters.Add(new ValueParameter<DoubleValue>("TimePenalty", "The time penalty considered in the evaluation.", new DoubleValue(10)));
143      Parameters.Add(new ValueParameter<DoubleValue>("OverloadPenalty", "The overload penalty considered in the evaluation.", new DoubleValue(50)));
144      Parameters.Add(new ValueParameter<DoubleValue>("TardinessPenalty", "The tardiness penalty considered in the evaluation.", new DoubleValue(50)));
145    }
146
147    private double CalculateFleetUsage() {
148      IVRPEncoding vrpSolution = VRPSolutionParameter.ActualValue;
149
150      return vrpSolution.Tours.Count;
151    }
152
153    private static double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
154      double distance = 0.0;
155
156      distance =
157          Math.Sqrt(
158            Math.Pow(coordinates[start, 0] - coordinates[end, 0], 2) +
159            Math.Pow(coordinates[start, 1] - coordinates[end, 1], 2));
160
161      return distance;
162    }
163
164    private static DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates)
165    {
166      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
167
168      for (int i = 0; i < distanceMatrix.Rows; i++) {
169        for (int j = i; j < distanceMatrix.Columns; j++) {
170          double distance = CalculateDistance(i, j, coordinates);
171
172          distanceMatrix[i, j] = distance;
173          distanceMatrix[j, i] = distance;
174        }
175      }
176
177      return distanceMatrix;
178    }
179
180    private static double GetDistance(int start, int end,
181      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
182      double distance = 0.0;
183
184      if (useDistanceMatrix.Value) {
185        if (distanceMatrix.ActualValue == null) {
186          distanceMatrix.ActualValue = CreateDistanceMatrix(coordinates);
187        }
188
189        distance = distanceMatrix.ActualValue[start, end];
190      } else {
191        distance = CalculateDistance(start, end, coordinates);
192      }
193
194      return distance;
195    }
196
197    private static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
198      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
199      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
200      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
201      TourEvaluation eval = new TourEvaluation();
202
203      double quality = 0.0;
204      double time = 0.0;
205
206      double distance = 0.0;
207      double waitingTime = 0.0;
208      double serviceTime = 0.0;
209      double delivered = 0.0;
210
211      double overweight = 0.0;
212      double tardiness = 0.0;
213
214      //simulate a tour, start and end at depot
215      for (int i = 1; i < tour.Count; i++) {
216        int start = tour[i - 1].Value;
217        int end = tour[i].Value;
218
219        //drive there
220        double currentDistace = GetDistance(start, end, coordinates, distanceMatrix, useDistanceMatrix);
221        distance += currentDistace;
222        time += currentDistace;
223
224        //check if it was serviced on time
225        if (time > dueTimeArray[end])
226          tardiness += time - dueTimeArray[end];
227
228        //wait
229        double currentWaitingTime = 0.0;
230        if (time < readyTimeArray[end])
231          currentWaitingTime = readyTimeArray[end] - time;
232        waitingTime += currentWaitingTime;
233        time += currentWaitingTime;
234
235        //service
236        delivered += demandArray[end];
237        double currentServiceTime = serviceTimeArray[end];
238        serviceTime += currentServiceTime;
239        time += currentServiceTime;
240      }
241
242      if (delivered > capacity.Value) {
243        overweight = delivered - capacity.Value;
244      }
245
246      //Fleet usage
247      quality += fleetUsageFactor.Value;
248      //Travel time
249      quality += timeFactor.Value * time;
250      //Distance
251      quality += distanceFactor.Value * distance;
252
253      //Penalties
254      quality += overloadPenalty.Value * overweight;
255      quality += tardinessPenalty.Value * tardiness;
256
257      eval.Distance = distance;
258      eval.TravelTime = time;
259      eval.VehcilesUtilized = 1;
260      eval.Overload = overweight;
261      eval.Tardiness = tardiness;
262      eval.Quality = quality;
263
264      return eval;
265    }
266
267    public static TourEvaluation Evaluate(IVRPEncoding solution, DoubleArray dueTimeArray,
268      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
269      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
270      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
271      TourEvaluation sumEval = new TourEvaluation();
272      sumEval.Distance = 0;
273      sumEval.Quality = 0;
274      sumEval.TravelTime = 0;
275      sumEval.VehcilesUtilized = 0;
276      sumEval.Overload = 0;
277      sumEval.Tardiness = 0;
278
279      foreach (Tour tour in solution.Tours) {
280        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
281          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
282          coordinates, distanceMatrix, useDistanceMatrix);
283        sumEval.Quality += eval.Quality;
284        sumEval.Distance += eval.Distance;
285        sumEval.TravelTime += eval.TravelTime;
286        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
287        sumEval.Overload += eval.Overload;
288        sumEval.Tardiness += eval.Tardiness;
289      }
290
291      if (sumEval.Quality < sumEval.Distance) {
292      }
293
294      return sumEval;
295    }
296
297    public sealed override IOperation Apply() {
298      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
299
300      TourEvaluation sumEval = Evaluate(solution, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
301        DemandParameter.ActualValue, CapacityParameter.ActualValue,
302        FleetUsageFactor.Value, TimeFactor.Value, DistanceFactor.Value, OverloadPenalty.Value, TardinessPenalty.Value,
303        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
304
305      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
306      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
307      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
308      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
309      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
310      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
311
312      return base.Apply();
313    }
314  }
315}
Note: See TracBrowser for help on using the repository browser.