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("CVRPPDTWEvaluator", "Represents a single depot CVRPPDTW evaluator.")]


39  [StorableClass]


40  public class CVRPPDTWEvaluator: CVRPTWEvaluator {


41  public ILookupParameter<IntValue> PickupViolationsParameter {


42  get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }


43  }


44 


45  protected override VRPEvaluation CreateTourEvaluation() {


46  return new CVRPPDTWEvaluation();


47  }


48 


49  protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {


50  TourInsertionInfo tourInfo = new TourInsertionInfo();


51  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);


52 


53  IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;


54  DoubleArray demand = instance.Demand;


55 


56  ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;


57  DoubleArray dueTime = vrptw.DueTime;


58  DoubleArray readyTime = vrptw.ReadyTime;


59  DoubleArray serviceTimes = vrptw.ServiceTime;


60 


61  IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;


62  IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation;


63 


64  double capacity = cvrpInstance.Capacity.Value;


65 


66  double time = 0.0;


67  double waitingTime = 0.0;


68  double serviceTime = 0.0;


69  double tardiness = 0.0;


70  double overweight = 0.0;


71  double distance = 0.0;


72 


73  double currentLoad = 0.0;


74  Dictionary<int, bool> stops = new Dictionary<int, bool>();


75  int pickupViolations = 0;


76 


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


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


79  int start = 0;


80  if (i > 0)


81  start = tour.Stops[i  1];


82  int end = 0;


83  if (i < tour.Stops.Count)


84  end = tour.Stops[i];


85 


86  //drive there


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


88  time += currentDistace;


89  distance += currentDistace;


90 


91  double arrivalTime = time;


92 


93  //check if it was serviced on time


94  if (time > dueTime[end])


95  tardiness += time  dueTime[end];


96 


97  //wait


98  double currentWaitingTime = 0.0;


99  if (time < readyTime[end])


100  currentWaitingTime = readyTime[end]  time;


101 


102  double waitTime = readyTime[end]  time;


103 


104  waitingTime += currentWaitingTime;


105  time += currentWaitingTime;


106 


107  double spareTime = dueTime[end]  time;


108 


109  //service


110  double currentServiceTime = serviceTimes[end];


111  serviceTime += currentServiceTime;


112  time += currentServiceTime;


113 


114  //Pickup / deliver


115  double arrivalSpareCapacity = capacity  currentLoad;


116 


117  bool validPickupDelivery =


118  validPickupDelivery =


119  ((demand[end] >= 0) 


120  (stops.ContainsKey(pickupDeliveryLocation[end])));


121 


122  if (validPickupDelivery) {


123  currentLoad += demand[end];


124  } else {


125  pickupViolations++;


126  }


127 


128  if (currentLoad > capacity)


129  overweight += currentLoad  capacity;


130 


131  double spareCapacity = capacity  currentLoad;


132  CVRPPDTWInsertionInfo stopInfo = new CVRPPDTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime, new List<int>(stops.Keys), arrivalSpareCapacity);


133  tourInfo.AddStopInsertionInfo(stopInfo);


134 


135  stops.Add(end, true);


136  }


137 


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


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


140  eval.Distance += distance;


141  eval.VehicleUtilization += 1;


142 


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


144  double tourPenalty = 0;


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


146  eval.Penalty += penalty;


147  eval.Quality += penalty;


148  tourPenalty += penalty;


149 


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


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


152 


153  penalty = tardiness * vrptw.TardinessPenalty.Value;


154  eval.Penalty += penalty;


155  eval.Quality += penalty;


156  tourPenalty += penalty;


157 


158  (eval as CVRPPDTWEvaluation).PickupViolations += pickupViolations;


159  penalty = pickupViolations * pdp.PickupViolationPenalty.Value;


160  eval.Penalty += penalty;


161  tourPenalty += penalty;


162 


163  eval.Quality += penalty;


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


165  tourInfo.Penalty = tourPenalty;


166  }


167 


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


169  out bool feasible) {


170  CVRPPDTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPPDTWInsertionInfo;


171 


172  double costs = 0;


173  feasible = tourInsertionInfo.Penalty < double.Epsilon;


174  bool tourFeasible = true;


175 


176  ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;


177  double overloadPenalty = cvrp.OverloadPenalty.Value;


178 


179  ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;


180  DoubleArray dueTime = vrptw.DueTime;


181  DoubleArray readyTime = vrptw.ReadyTime;


182  DoubleArray serviceTimes = vrptw.ServiceTime;


183  double tardinessPenalty = vrptw.TardinessPenalty.Value;


184 


185  IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;


186  IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation;


187  double pickupPenalty = pdp.PickupViolationPenalty.Value;


188 


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


190  double newDistance =


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


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


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


194 


195  double demand = instance.Demand[customer];


196  if (demand > insertionInfo.ArrivalSpareCapacity) {


197  tourFeasible = feasible = false;


198  if (insertionInfo.ArrivalSpareCapacity >= 0)


199  costs += (demand  insertionInfo.ArrivalSpareCapacity) * overloadPenalty;


200  else


201  costs += demand * overloadPenalty;


202  }


203  int destination = pickupDeliveryLocation[customer];


204 


205  bool validPickup = true;


206  if (demand < 0 && !insertionInfo.Visited.Contains(destination)) {


207  tourFeasible = feasible = false;


208  validPickup = false;


209  costs += pickupPenalty;


210  }


211 


212  double time = 0;


213  double tardiness = 0;


214 


215  if (index > 0)


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


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


218  if (time > dueTime[customer]) {


219  tardiness += time  dueTime[customer];


220  }


221  if (time < readyTime[customer])


222  time += readyTime[customer]  time;


223  time += serviceTimes[customer];


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


225 


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


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


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


229 


230  if (demand >= 0) {


231  if (nextStop.End == destination) {


232  demand = 0;


233  costs = pickupPenalty;


234  if (tourInsertionInfo.Penalty == pickupPenalty && tourFeasible)


235  feasible = true;


236  } else if (nextStop.SpareCapacity < 0) {


237  costs += demand * overloadPenalty;


238  } else if (nextStop.SpareCapacity < demand) {


239  tourFeasible = feasible = false;


240  costs += (demand  nextStop.SpareCapacity) * overloadPenalty;


241  }


242  } else if (validPickup) {


243  if (nextStop.SpareCapacity < 0) {


244  costs += Math.Max(demand, nextStop.SpareCapacity) * overloadPenalty;


245  }


246  }


247 


248  if (additionalTime < 0) {


249  //arrive earlier than before


250  //wait probably


251  if (nextStop.WaitingTime < 0) {


252  double wait = nextStop.WaitingTime  additionalTime;


253  if (wait > 0)


254  additionalTime += wait;


255  } else {


256  additionalTime = 0;


257  }


258 


259  //check due date, decrease tardiness


260  if (nextStop.SpareTime < 0) {


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


262  }


263  } else {


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


265  if (nextStop.WaitingTime > 0) {


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


267  }


268 


269  //check due date


270  if (nextStop.SpareTime > 0) {


271  double spare = nextStop.SpareTime  additionalTime;


272  if (spare < 0)


273  tardiness += spare;


274  } else {


275  tardiness += additionalTime;


276  }


277  }


278  }


279 


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


281 


282  if (tardiness > 0) {


283  tourFeasible = feasible = false;


284  }


285 


286  costs += tardiness * tardinessPenalty;


287 


288  return costs;


289  }


290 


291  protected override void InitResultParameters() {


292  base.InitResultParameters();


293 


294  PickupViolationsParameter.ActualValue = new IntValue(0);


295  }


296 


297  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {


298  base.SetResultParameters(tourEvaluation);


299 


300  PickupViolationsParameter.ActualValue.Value = (tourEvaluation as CVRPPDTWEvaluation).PickupViolations;


301  }


302 


303  [StorableConstructor]


304  protected CVRPPDTWEvaluator(bool deserializing) : base(deserializing) { }


305 


306  public CVRPPDTWEvaluator() {


307  Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));


308  }


309 


310  public override IDeepCloneable Clone(Cloner cloner) {


311  return new CVRPPDTWEvaluator(this, cloner);


312  }


313 


314  protected CVRPPDTWEvaluator(CVRPPDTWEvaluator original, Cloner cloner)


315  : base(original, cloner) {


316  }


317  }


318  } 
