Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs @ 7895

Last change on this file since 7895 was 7276, checked in by svonolfe, 13 years ago

Improved incremental evaluation (#1177)

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