Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Operators/DynPDPEvaluator.cs @ 8812

Last change on this file since 8812 was 8670, checked in by svonolfe, 12 years ago

Added first version of the dynamic vehicle routing addon (#1955)

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.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;
36using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
37using HeuristicLab.Problems.VehicleRouting;
38using HeuristicLab.Problems.VehicleRouting.Encodings.General;
39using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
40
41namespace HeuristicLab.PDPSimulation.Operators {
42  public class DynPDPInsertionInfo : CVRPPDTWInsertionInfo {
43    private double commitmentTime;
44
45    public double CommitmentTime {
46      get { return commitmentTime; }
47    }
48
49
50    public DynPDPInsertionInfo(int start, int end, double spareCapacity, double tourStartTime,
51      double arrivalTime, double leaveTime, double spareTime, double waitingTime, double commitmentTime,
52      List<int> visited, double arrivalSpareCapacity)
53      : base(start, end, spareCapacity, tourStartTime, arrivalTime, leaveTime, spareTime, waitingTime, visited, arrivalSpareCapacity) {
54        this.commitmentTime = commitmentTime;
55    }
56  }
57 
58  public class DynPDPEvaluation : CVRPPDTWEvaluation {
59    //public List<List<double>> WaitingTimes { get; private set; }
60
61    public DynPDPEvaluation() {
62      //WaitingTimes = new List<List<double>>();
63    }
64  }
65 
66  [Item("DynPDPEvaluator", "Represents a dynamic multi depot CVRPPDTW evaluator.")]
67  [StorableClass]
68  public class DynPDPEvaluator: MDCVRPTWEvaluator {
69    public ILookupParameter<IntValue> PickupViolationsParameter {
70      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
71    }
72
73    protected override VRPEvaluation CreateTourEvaluation() {
74      return new DynPDPEvaluation();
75    }
76
77    public static List<double> GetWaitingTimes(DynPDPProblemInstance instance, Tour tour, IVRPEncoding solution) {
78      DoubleArray dueTime = instance.DueTime;
79      DoubleArray readyTime = instance.ReadyTime;
80      DoubleArray serviceTimes = instance.ServiceTime;
81
82      IntArray vehicleAssignment = instance.VehicleDepotAssignment;
83      int depots = instance.Depots.Value;
84     
85      int tourIndex = solution.GetTourIndex(tour);
86      int vehicle = solution.GetVehicleAssignment(tourIndex);
87      int depot = vehicleAssignment[vehicle];
88
89      List<double> waitingTimes = new List<double>();
90      WaitingStrategy waitingStrategy = (instance as DynPDPProblemInstance).WaitingStrategy;
91
92      double time = readyTime[depot];
93      int count = tour.Stops.Count;
94      if (!(instance as DynPDPProblemInstance).RelocateBackToDepot)
95        count -= 1;
96      for (int i = 0; i <= count; i++) {
97        int start = 0;
98        if (i > 0)
99          start = tour.Stops[i - 1];
100        int end = 0;
101        if (i < tour.Stops.Count)
102          end = tour.Stops[i];
103
104        //Waiting strategy...
105        if (end != 0) {
106          double waitAction = waitingStrategy.GetWaitingTime(time, instance as DynPDPProblemInstance, solution, tour, i);
107          waitingTimes.Add(waitAction);
108          time += waitAction;
109        }
110
111        //drive there
112        time += instance.GetDistance(start, end, solution);
113
114        int endIndex;
115        if (end == 0)
116          endIndex = depot;
117        else
118          endIndex = end + depots - 1;
119
120        //wait
121        if (time < readyTime[endIndex])
122          time = readyTime[endIndex];
123
124        if (end > 0) {
125          //service
126          time += serviceTimes[end - 1];
127        }
128      }
129
130      return waitingTimes;
131    }
132
133    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
134      TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));
135      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
136      double originalQuality = eval.Quality;
137
138      IHeterogenousCapacitatedProblemInstance cvrpInstance = instance as IHeterogenousCapacitatedProblemInstance;
139      DoubleArray demand = instance.Demand;
140
141      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
142      DoubleArray dueTime = vrptw.DueTime;
143      DoubleArray readyTime = vrptw.ReadyTime;
144      DoubleArray serviceTimes = vrptw.ServiceTime;
145
146      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
147      IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation;
148
149      IMultiDepotProblemInstance mdp = instance as IMultiDepotProblemInstance;
150      IntArray vehicleAssignment = mdp.VehicleDepotAssignment;
151      int depots = mdp.Depots.Value;
152
153      double time = 0.0;
154      double waitingTime = 0.0;
155      double serviceTime = 0.0;
156      double tardiness = 0.0;
157      double overweight = 0.0;
158      double distance = 0.0;
159
160      int tourIndex = solution.GetTourIndex(tour);
161      int vehicle = solution.GetVehicleAssignment(tourIndex);
162      int depot = vehicleAssignment[vehicle];
163
164      double capacity = cvrpInstance.Capacity[vehicle];
165
166      double currentLoad = 0.0;
167      Dictionary<int, bool> stops = new Dictionary<int, bool>();
168      int pickupViolations = 0;
169
170      double tourStartTime = readyTime[depot];
171      time = tourStartTime;
172
173      WaitingStrategy waitingStrategy = (instance as DynPDPProblemInstance).WaitingStrategy;
174
175      //simulate a tour
176      int count = tour.Stops.Count;
177      if (!(instance as DynPDPProblemInstance).RelocateBackToDepot)
178        count -= 1;
179      for (int i = 0; i <= count; i++) {
180        int start = 0;
181        if (i > 0)
182          start = tour.Stops[i - 1];
183        int end = 0;
184        if (i < tour.Stops.Count)
185          end = tour.Stops[i];
186
187        //Waiting strategy...
188        if (end != 0) {
189          double waitAction = waitingStrategy.GetBufferTime(time, instance as DynPDPProblemInstance, solution, tour, i);
190          time += waitAction;
191        }
192
193        double commitmentTime = time;
194       
195        //drive there
196        double currentDistace = vrptw.GetDistance(start, end, solution);
197
198        time += currentDistace;
199        distance += currentDistace;
200
201        double arrivalTime = time;
202
203        int endIndex;
204        if (end == 0)
205          endIndex = depot;
206        else
207          endIndex = end + depots - 1;
208
209        //check if it was serviced on time
210        if (time > dueTime[endIndex])
211          tardiness += time - dueTime[endIndex];
212
213        //wait
214        double currentWaitingTime = 0.0;
215        if (time < readyTime[endIndex])
216          currentWaitingTime = readyTime[endIndex] - time;
217
218        double waitTime = readyTime[endIndex] - time;
219
220        waitingTime += currentWaitingTime;
221        time += currentWaitingTime;
222
223        double spareTime = dueTime[endIndex] - time;
224        double arrivalSpareCapacity = capacity - currentLoad;
225
226        if (end > 0) {
227          //service
228          double currentServiceTime = serviceTimes[end - 1];
229          serviceTime += currentServiceTime;
230          time += currentServiceTime;
231
232          //Pickup / deliver
233          int location = pickupDeliveryLocation[end - 1];
234          bool validPickupDelivery =
235            validPickupDelivery =
236            ((demand[end - 1] >= 0) ||
237             (end == location) ||
238             (location <= 0 && vehicle == -location) ||
239             (stops.ContainsKey(location)));
240
241          if (validPickupDelivery) {
242            currentLoad += demand[end - 1];
243          } else {
244            pickupViolations++;
245          }
246
247          if (currentLoad > capacity)
248            overweight += currentLoad - capacity;
249        }
250
251        double spareCapacity = capacity - currentLoad;
252        CVRPPDTWInsertionInfo stopInfo = new DynPDPInsertionInfo(start, end, spareCapacity, tourStartTime,
253          arrivalTime, time, spareTime, waitTime, commitmentTime, new List<int>(stops.Keys), arrivalSpareCapacity);
254        tourInfo.AddStopInsertionInfo(stopInfo);
255
256        stops.Add(end, true);
257      }
258
259      if(!(instance as DynPDPProblemInstance).VehicleUsed[vehicle])
260        eval.Quality += instance.FleetUsageFactor.Value;
261
262      eval.Quality += instance.DistanceFactor.Value * distance;
263      eval.Distance += distance;
264      eval.VehicleUtilization += 1;
265
266      (eval as CVRPEvaluation).Overload += overweight;
267      double tourPenalty = 0;
268      double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
269      eval.Penalty += penalty;
270      eval.Quality += penalty;
271      tourPenalty += penalty;
272
273      (eval as CVRPTWEvaluation).Tardiness += tardiness;
274      (eval as CVRPTWEvaluation).TravelTime += time;
275
276      penalty = tardiness * vrptw.TardinessPenalty.Value;
277      eval.Penalty += penalty;
278      eval.Quality += penalty;
279      tourPenalty += penalty;
280
281      (eval as CVRPPDTWEvaluation).PickupViolations += pickupViolations;
282      penalty = pickupViolations * pdp.PickupViolationPenalty.Value;
283      eval.Penalty += penalty;
284      tourPenalty += penalty;
285
286      eval.Quality += penalty;
287      eval.Quality += time * vrptw.TimeFactor.Value;
288      tourInfo.Penalty = tourPenalty;
289      tourInfo.Quality = eval.Quality - originalQuality;
290    }
291
292    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
293      out bool feasible) {
294        TourEncoding individual = null;
295        if (solution is TourEncoding)
296          individual = solution as TourEncoding;
297        else {
298          individual = new PotvinEncoding(instance);
299          individual.Tours.AddRange(solution.GetTours());
300        }
301
302        int tourIdx = -1;
303        for (int i = 0; i < individual.Tours.Count; i++) {
304          if (solution.GetVehicleAssignment(i) == tourInsertionInfo.Vehicle)
305            tourIdx = i;
306        }
307        Tour tour = individual.Tours[tourIdx];
308
309        tour.Stops.Insert(index, customer);
310        VRPEvaluation newEval = instance.EvaluateTour(tour, individual);
311        tour.Stops.RemoveAt(index);
312
313        feasible = instance.Feasible(newEval);
314        return newEval.Quality - tourInsertionInfo.Quality;
315    }
316
317    protected override void InitResultParameters() {
318      base.InitResultParameters();
319
320      PickupViolationsParameter.ActualValue = new IntValue(0);
321    }
322
323    protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
324      base.SetResultParameters(tourEvaluation);
325
326      PickupViolationsParameter.ActualValue.Value = (tourEvaluation as CVRPPDTWEvaluation).PickupViolations;
327    }
328   
329    [StorableConstructor]
330    protected DynPDPEvaluator(bool deserializing) : base(deserializing) { }
331
332    public DynPDPEvaluator() {
333      Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
334    }
335
336    public override IDeepCloneable Clone(Cloner cloner) {
337      return new DynPDPEvaluator(this, cloner);
338    }
339
340    protected DynPDPEvaluator(DynPDPEvaluator original, Cloner cloner)
341      : base(original, cloner) {
342    }
343  }
344}
Note: See TracBrowser for help on using the repository browser.