Free cookie consent management tool by TermsFeed Policy Generator

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

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

Refactored VRP, added Potvin encoding (WIP) (#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 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 = 0; i <= tour.Count; i++) {
160        int start = 0;
161        if(i > 0)
162          start = tour[i - 1].Value;
163        int end = 0;
164        if(i < tour.Count)
165          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.