Free cookie consent management tool by TermsFeed Policy Generator

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

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

Improved VRP solution view (#1039)
File size: 12.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<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 TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
146      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
147      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
148      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
149      TourEvaluation eval = new TourEvaluation();
150
151      double quality = 0.0;
152      double time = 0.0;
153
154      double distance = 0.0;
155      double waitingTime = 0.0;
156      double serviceTime = 0.0;
157      double delivered = 0.0;
158
159      double overweight = 0.0;
160      double tardiness = 0.0;
161
162      //simulate a tour, start and end at depot
163      for (int i = 1; i < tour.Count; i++) {
164        int start = tour[i - 1].Value;
165        int end = tour[i].Value;
166
167        //drive there
168        double currentDistace = VehicleRoutingProblem.GetDistance(start, end, coordinates, distanceMatrix, useDistanceMatrix);
169        distance += currentDistace;
170        time += currentDistace;
171
172        //check if it was serviced on time
173        if (time > dueTimeArray[end])
174          tardiness += time - dueTimeArray[end];
175
176        //wait
177        double currentWaitingTime = 0.0;
178        if (time < readyTimeArray[end])
179          currentWaitingTime = readyTimeArray[end] - time;
180        waitingTime += currentWaitingTime;
181        time += currentWaitingTime;
182
183        //service
184        delivered += demandArray[end];
185        double currentServiceTime = serviceTimeArray[end];
186        serviceTime += currentServiceTime;
187        time += currentServiceTime;
188      }
189
190      if (delivered > capacity.Value) {
191        overweight = delivered - capacity.Value;
192      }
193
194      //Fleet usage
195      quality += fleetUsageFactor.Value;
196      //Travel time
197      quality += timeFactor.Value * time;
198      //Distance
199      quality += distanceFactor.Value * distance;
200
201      //Penalties
202      quality += overloadPenalty.Value * overweight;
203      quality += tardinessPenalty.Value * tardiness;
204
205      eval.Distance = distance;
206      eval.TravelTime = time;
207      eval.VehcilesUtilized = 1;
208      eval.Overload = overweight;
209      eval.Tardiness = tardiness;
210      eval.Quality = quality;
211
212      return eval;
213    }
214
215    public static TourEvaluation Evaluate(IVRPEncoding solution, DoubleArray dueTimeArray,
216      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
217      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
218      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
219      TourEvaluation sumEval = new TourEvaluation();
220      sumEval.Distance = 0;
221      sumEval.Quality = 0;
222      sumEval.TravelTime = 0;
223      sumEval.VehcilesUtilized = 0;
224      sumEval.Overload = 0;
225      sumEval.Tardiness = 0;
226
227      foreach (Tour tour in solution.Tours) {
228        TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
229          fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
230          coordinates, distanceMatrix, useDistanceMatrix);
231        sumEval.Quality += eval.Quality;
232        sumEval.Distance += eval.Distance;
233        sumEval.TravelTime += eval.TravelTime;
234        sumEval.VehcilesUtilized += eval.VehcilesUtilized;
235        sumEval.Overload += eval.Overload;
236        sumEval.Tardiness += eval.Tardiness;
237      }
238
239      return sumEval;
240    }
241
242    public sealed override IOperation Apply() {
243      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
244
245      TourEvaluation sumEval = Evaluate(solution, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
246        DemandParameter.ActualValue, CapacityParameter.ActualValue,
247        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
248        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
249
250      QualityParameter.ActualValue = new DoubleValue(sumEval.Quality);
251      VehcilesUtilizedParameter.ActualValue = new DoubleValue(sumEval.VehcilesUtilized);
252      TravelTimeParameter.ActualValue = new DoubleValue(sumEval.TravelTime);
253      DistanceParameter.ActualValue = new DoubleValue(sumEval.Distance);
254      OverloadParameter.ActualValue = new DoubleValue(sumEval.Overload);
255      TardinessParameter.ActualValue = new DoubleValue(sumEval.Tardiness);
256
257      return base.Apply();
258    }
259  }
260}
Note: See TracBrowser for help on using the repository browser.