1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022010 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using System.Text;


26  using HeuristicLab.Problems.VehicleRouting.Interfaces;


27  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


28  using HeuristicLab.Core;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Data;


31  using HeuristicLab.Optimization;


32  using HeuristicLab.PluginInfrastructure;


33  using HeuristicLab.Problems.VehicleRouting.Variants;


34  using HeuristicLab.Problems.VehicleRouting.Encodings;


35  using HeuristicLab.Common;


36 


37  namespace 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) {


54  TourInsertionInfo tourInfo = new TourInsertionInfo();


55  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);


56 


57  IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;


58  DoubleArray demand = instance.Demand;


59 


60  ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;


61  DoubleArray dueTime = vrptw.DueTime;


62  DoubleArray readyTime = vrptw.ReadyTime;


63  DoubleArray serviceTimes = vrptw.ServiceTime;


64 


65  double time = 0.0;


66  double waitingTime = 0.0;


67  double serviceTime = 0.0;


68  double tardiness = 0.0;


69  double delivered = 0.0;


70  double overweight = 0.0;


71  double distance = 0.0;


72 


73  double capacity = cvrpInstance.Capacity.Value;


74  for (int i = 0; i <= tour.Stops.Count; i++) {


75  int end = 0;


76  if (i < tour.Stops.Count)


77  end = tour.Stops[i];


78 


79  delivered += demand[end];


80  }


81 


82  double spareCapacity = capacity  delivered;


83 


84  //simulate a tour, start and end at depot


85  for (int i = 0; i <= tour.Stops.Count; i++) {


86  int start = 0;


87  if (i > 0)


88  start = tour.Stops[i  1];


89  int end = 0;


90  if (i < tour.Stops.Count)


91  end = tour.Stops[i];


92 


93  //drive there


94  double currentDistace = vrptw.GetDistance(start, end);


95  time += currentDistace;


96  distance += currentDistace;


97 


98  double arrivalTime = time;


99 


100  //check if it was serviced on time


101  if (time > dueTime[end])


102  tardiness += time  dueTime[end];


103 


104  //wait


105  double currentWaitingTime = 0.0;


106  if (time < readyTime[end])


107  currentWaitingTime = readyTime[end]  time;


108 


109  double waitTime = readyTime[end]time;


110 


111  waitingTime += currentWaitingTime;


112  time += currentWaitingTime;


113 


114  double spareTime = dueTime[end]  time;


115 


116  //service


117  double currentServiceTime = serviceTimes[end];


118  serviceTime += currentServiceTime;


119  time += currentServiceTime;


120 


121  CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime);


122  tourInfo.AddStopInsertionInfo(stopInfo);


123  }


124 


125  eval.Quality += instance.FleetUsageFactor.Value;


126  eval.Quality += instance.DistanceFactor.Value * distance;


127  eval.Distance += distance;


128  eval.VehicleUtilization += 1;


129 


130  if (delivered > capacity) {


131  overweight = delivered  capacity;


132  }


133 


134  (eval as CVRPEvaluation).Overload += overweight;


135  double tourPenalty = 0;


136  double penalty = overweight * cvrpInstance.OverloadPenalty.Value;


137  eval.Penalty += penalty;


138  eval.Quality += penalty;


139  tourPenalty += penalty;


140 


141  (eval as CVRPTWEvaluation).Tardiness += tardiness;


142  (eval as CVRPTWEvaluation).TravelTime += time;


143 


144  penalty = tardiness * vrptw.TardinessPenalty.Value;


145  eval.Penalty += penalty;


146  eval.Quality += penalty;


147  tourPenalty += penalty;


148  eval.Quality += time * vrptw.TimeFactor.Value;


149  tourInfo.Penalty = tourPenalty;


150  }


151 


152  protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,


153  out bool feasible) {


154  CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;


155 


156  double costs = 0;


157  feasible = tourInsertionInfo.Penalty < double.Epsilon;


158 


159  ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;


160  double overloadPenalty = cvrp.OverloadPenalty.Value;


161 


162  ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;


163  DoubleArray dueTime = vrptw.DueTime;


164  DoubleArray readyTime = vrptw.ReadyTime;


165  DoubleArray serviceTimes = vrptw.ServiceTime;


166  double tardinessPenalty = vrptw.TardinessPenalty.Value;


167 


168  double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);


169  double newDistance =


170  instance.GetDistance(insertionInfo.Start, customer) +


171  instance.GetDistance(customer, insertionInfo.End);


172  costs += instance.DistanceFactor.Value * (newDistance  distance);


173 


174  double demand = instance.Demand[customer];


175  if (demand > insertionInfo.SpareCapacity) {


176  feasible = false;


177  if (insertionInfo.SpareCapacity >= 0)


178  costs += (demand  insertionInfo.SpareCapacity) * overloadPenalty;


179  else


180  costs += demand * overloadPenalty;


181  }


182 


183  double time = 0;


184  double tardiness = 0;


185 


186  if (index > 0)


187  time = (tourInsertionInfo.GetStopInsertionInfo(index  1) as CVRPTWInsertionInfo).LeaveTime;


188  time += instance.GetDistance(insertionInfo.Start, customer);


189  if (time > dueTime[customer]) {


190  tardiness += time  dueTime[customer];


191  }


192  if (time < readyTime[customer])


193  time += readyTime[customer]  time;


194  time += serviceTimes[customer];


195  time += instance.GetDistance(customer, insertionInfo.End);


196 


197  double additionalTime = time  (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;


198  for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {


199  CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;


200 


201  if (additionalTime < 0) {


202  //arrive earlier than before


203  //wait probably


204  if (nextStop.WaitingTime < 0) {


205  double wait = nextStop.WaitingTime  additionalTime;


206  if (wait > 0)


207  additionalTime += wait;


208  } else {


209  additionalTime = 0;


210  }


211 


212  //check due date, decrease tardiness


213  if (nextStop.SpareTime < 0) {


214  costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;


215  }


216  } else {


217  //arrive later than before, probably don't have to wait


218  if (nextStop.WaitingTime > 0) {


219  additionalTime = Math.Min(additionalTime, nextStop.WaitingTime);


220  }


221 


222  //check due date


223  if (nextStop.SpareTime > 0) {


224  double spare = nextStop.SpareTime  additionalTime;


225  if (spare < 0)


226  tardiness += spare;


227  } else {


228  tardiness += additionalTime;


229  }


230  }


231  }


232 


233  costs += additionalTime * vrptw.TimeFactor.Value;


234 


235  if (tardiness > 0) {


236  feasible = false;


237  }


238 


239  costs += tardiness * tardinessPenalty;


240 


241  return costs;


242  }


243 


244  protected override void InitResultParameters() {


245  base.InitResultParameters();


246 


247  TardinessParameter.ActualValue = new DoubleValue(0);


248  TravelTimeParameter.ActualValue = new DoubleValue(0);


249  }


250 


251  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {


252  base.SetResultParameters(tourEvaluation);


253 


254  TardinessParameter.ActualValue.Value = (tourEvaluation as CVRPTWEvaluation).Tardiness;


255  TravelTimeParameter.ActualValue.Value = (tourEvaluation as CVRPTWEvaluation).TravelTime;


256  }


257 


258  [StorableConstructor]


259  protected CVRPTWEvaluator(bool deserializing) : base(deserializing) { }


260 


261  public CVRPTWEvaluator() {


262  Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness."));


263  Parameters.Add(new LookupParameter<DoubleValue>("TravelTime", "The travel time."));


264  }


265 


266  public override IDeepCloneable Clone(Cloner cloner) {


267  return new CVRPTWEvaluator(this, cloner);


268  }


269 


270  protected CVRPTWEvaluator(CVRPTWEvaluator original, Cloner cloner)


271  : base(original, cloner) {


272  }


273  }


274  } 
