source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Operators/DialARideEvaluator.cs @ 8782

Last change on this file since 8782 was 8782, checked in by svonolfe, 10 years ago

modified fitness function of dial a ride

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