Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceOverhaul/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPTW/MDCVRPTWEvaluator.cs @ 13368

Last change on this file since 13368 was 13368, checked in by ascheibe, 8 years ago

#2520 added guids to storable classes

File size: 10.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Parameters;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Problems.VehicleRouting.Interfaces;
29using HeuristicLab.Problems.VehicleRouting.Variants;
30
31namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
32  [Item("MDCVRPTWEvaluator", "Represents a multi depot CVRPTW evaluator.")]
33  [StorableClass("FB2D8AA0-9B1A-4976-93B6-FF99268CD13F")]
34  public class MDCVRPTWEvaluator : MDCVRPEvaluator {
35    public ILookupParameter<DoubleValue> TardinessParameter {
36      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
37    }
38
39    public ILookupParameter<DoubleValue> TravelTimeParameter {
40      get { return (ILookupParameter<DoubleValue>)Parameters["TravelTime"]; }
41    }
42
43    protected override VRPEvaluation CreateTourEvaluation() {
44      return new CVRPTWEvaluation();
45    }
46
47    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
48      TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));
49      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
50      double originalQuality = eval.Quality;
51
52      IHeterogenousCapacitatedProblemInstance cvrpInstance = instance as IHeterogenousCapacitatedProblemInstance;
53      DoubleArray demand = instance.Demand;
54
55      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
56      DoubleArray dueTime = vrptw.DueTime;
57      DoubleArray readyTime = vrptw.ReadyTime;
58      DoubleArray serviceTimes = vrptw.ServiceTime;
59
60      IMultiDepotProblemInstance mdp = instance as IMultiDepotProblemInstance;
61      IntArray vehicleAssignment = mdp.VehicleDepotAssignment;
62      int depots = mdp.Depots.Value;
63
64      double time = 0.0;
65      double waitingTime = 0.0;
66      double serviceTime = 0.0;
67      double tardiness = 0.0;
68      double delivered = 0.0;
69      double overweight = 0.0;
70      double distance = 0.0;
71
72      int tourIndex = solution.GetTourIndex(tour);
73      int vehicle = solution.GetVehicleAssignment(tourIndex);
74      int depot = vehicleAssignment[vehicle];
75
76      double capacity = cvrpInstance.Capacity[vehicle];
77      for (int i = 0; i < tour.Stops.Count; i++) {
78        delivered += instance.GetDemand(tour.Stops[i]);
79      }
80
81      double spareCapacity = capacity - delivered;
82
83      double tourStartTime = vrptw.ReadyTime[depot];
84      time = tourStartTime;
85
86      //simulate a tour, start and end at depot
87      for (int i = 0; i <= tour.Stops.Count; i++) {
88        int start = 0;
89        if (i > 0)
90          start = tour.Stops[i - 1];
91        int end = 0;
92        if (i < tour.Stops.Count)
93          end = tour.Stops[i];
94
95        //drive there
96        double currentDistace = vrptw.GetDistance(start, end, solution);
97        time += currentDistace;
98        distance += currentDistace;
99
100        double arrivalTime = time;
101
102        int endIndex;
103        if (end == 0)
104          endIndex = depot;
105        else
106          endIndex = end + depots - 1;
107
108        //check if it was serviced on time
109        if (time > dueTime[endIndex])
110          tardiness += time - dueTime[endIndex];
111
112        //wait
113        double currentWaitingTime = 0.0;
114        if (time < readyTime[endIndex])
115          currentWaitingTime = readyTime[endIndex] - time;
116
117        double waitTime = readyTime[endIndex] - time;
118
119        waitingTime += currentWaitingTime;
120        time += currentWaitingTime;
121
122        double spareTime = dueTime[endIndex] - time;
123
124        //service
125        double currentServiceTime = 0;
126        if (end > 0)
127          currentServiceTime = serviceTimes[end - 1];
128        serviceTime += currentServiceTime;
129        time += currentServiceTime;
130
131        CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, tourStartTime, arrivalTime, time, spareTime, waitTime);
132        tourInfo.AddStopInsertionInfo(stopInfo);
133      }
134
135      eval.Quality += instance.FleetUsageFactor.Value;
136      eval.Quality += instance.DistanceFactor.Value * distance;
137      eval.Distance += distance;
138      eval.VehicleUtilization += 1;
139
140      if (delivered > capacity) {
141        overweight = delivered - capacity;
142      }
143
144      (eval as CVRPEvaluation).Overload += overweight;
145      double tourPenalty = 0;
146      double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
147      eval.Penalty += penalty;
148      eval.Quality += penalty;
149      tourPenalty += penalty;
150
151      (eval as CVRPTWEvaluation).Tardiness += tardiness;
152      (eval as CVRPTWEvaluation).TravelTime += time;
153
154      penalty = tardiness * vrptw.TardinessPenalty.Value;
155      eval.Penalty += penalty;
156      eval.Quality += penalty;
157      tourPenalty += penalty;
158      eval.Quality += time * vrptw.TimeFactor.Value;
159      tourInfo.Penalty = tourPenalty;
160      tourInfo.Quality = eval.Quality - originalQuality;
161    }
162
163    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
164      out bool feasible) {
165      CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;
166
167      double costs = 0;
168      feasible = tourInsertionInfo.Penalty < double.Epsilon;
169
170      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
171      double overloadPenalty = cvrp.OverloadPenalty.Value;
172
173      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
174      DoubleArray dueTime = vrptw.DueTime;
175      DoubleArray readyTime = vrptw.ReadyTime;
176      DoubleArray serviceTimes = vrptw.ServiceTime;
177      double tardinessPenalty = vrptw.TardinessPenalty.Value;
178
179      IMultiDepotProblemInstance mdp = instance as IMultiDepotProblemInstance;
180      int depots = mdp.Depots.Value;
181
182      double startDistance, endDistance;
183      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);
184
185      double demand = instance.GetDemand(customer);
186      if (demand > insertionInfo.SpareCapacity) {
187        feasible = false;
188
189        if (insertionInfo.SpareCapacity >= 0)
190          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
191        else
192          costs += demand * overloadPenalty;
193      }
194
195      double time = 0;
196      double tardiness = 0;
197
198      if (index > 0)
199        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
200      else
201        time = insertionInfo.TourStartTime;
202
203      time += startDistance;
204
205      int customerIndex = customer + depots - 1;
206
207      if (time > dueTime[customerIndex]) {
208        tardiness += time - dueTime[customerIndex];
209      }
210      if (time < readyTime[customerIndex])
211        time += readyTime[customerIndex] - time;
212      time += serviceTimes[customer - 1];
213      time += endDistance;
214
215      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
216      for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {
217        CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;
218
219        if (additionalTime < 0) {
220          //arrive earlier than before
221          //wait probably
222          if (nextStop.WaitingTime < 0) {
223            double wait = nextStop.WaitingTime - additionalTime;
224            if (wait > 0)
225              additionalTime += wait;
226          } else {
227            additionalTime = 0;
228          }
229
230          //check due date, decrease tardiness
231          if (nextStop.SpareTime < 0) {
232            costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;
233          }
234        } else {
235          //arrive later than before, probably don't have to wait
236          if (nextStop.WaitingTime > 0) {
237            additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime);
238          }
239
240          //check due date
241          if (nextStop.SpareTime > 0) {
242            double spare = nextStop.SpareTime - additionalTime;
243            if (spare < 0)
244              tardiness += -spare;
245          } else {
246            tardiness += additionalTime;
247          }
248        }
249      }
250
251      costs += additionalTime * vrptw.TimeFactor.Value;
252
253      if (tardiness > 0) {
254        feasible = false;
255      }
256
257      costs += tardiness * tardinessPenalty;
258
259      return costs;
260    }
261
262    protected override void InitResultParameters() {
263      base.InitResultParameters();
264
265      TardinessParameter.ActualValue = new DoubleValue(0);
266      TravelTimeParameter.ActualValue = new DoubleValue(0);
267    }
268
269    protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
270      base.SetResultParameters(tourEvaluation);
271
272      TardinessParameter.ActualValue.Value = (tourEvaluation as CVRPTWEvaluation).Tardiness;
273      TravelTimeParameter.ActualValue.Value = (tourEvaluation as CVRPTWEvaluation).TravelTime;
274    }
275
276    [StorableConstructor]
277    protected MDCVRPTWEvaluator(bool deserializing) : base(deserializing) { }
278
279    public MDCVRPTWEvaluator() {
280      Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));
281      Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The travel time."));
282    }
283
284    public override IDeepCloneable Clone(Cloner cloner) {
285      return new MDCVRPTWEvaluator(this, cloner);
286    }
287
288    protected MDCVRPTWEvaluator(MDCVRPTWEvaluator original, Cloner cloner)
289      : base(original, cloner) {
290    }
291  }
292}
Note: See TracBrowser for help on using the repository browser.