Changes between Version 3 and Version 4 of Documentation/Howto/ImplementANewVRPEvaluator


Ignore:
Timestamp:
01/28/14 14:50:29 (7 years ago)
Author:
pfleck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPEvaluator

    v3 v4  
    4646In order to implement a new VRP variant by extending a {{{VRPEvaluator}}} you need a basic understanding of how a {{{VRPEvaluator}}} works and how it is used.
    4747
    48 [[Image(1-PRP_EvaluatorEvaluation.png)]]
     48[[Image(1-PRP_EvaluatorEvaluation.png, 400px)]]
    4949
    5050The {{{VRPEvaluator}}} evaluates a VRP solution by calling the {{{Evaluate()}}} Method. A VRP solution contains multiple tours for a given problem instance. In the evaluation process a {{{VRPEvaluation}}} object is created. In the {{{VRPEvaluation}}} object the quality, penalty and other values of the solution candidate are stored.
     
    5858In order to enable incremental evaluation, additional information is created in the original evaluation process, namely the {{{InsertionInfo}}}. The {{{InsertionInfo}}} itself contains a list of {{{TourInsertionInfo}}}, which itself contains a list of {{{StopInsertionInfo}}}. These correspond to the solution candidate itself, one tour and one stop in a tour.
    5959
    60 [[Image(2-InsertionInfoSample.png)]]
    61 
    62 [[Image(3-PRP_EvaluatorEvaluationInfo.png)]]
     60[[Image(2-InsertionInfoSample.png, 600px)]]
     61
     62[[Image(3-PRP_EvaluatorEvaluationInfo.png, 1000px)]]
    6363
    6464In the {{{VRPEvaluator}}} the {{{EvaluateTourInsertionCosts()}}} method determine the change in quality (the costs) by inserting an additional stop between two existing stops of a tour. This is usually done by calculating the difference of the distance between the new three stops and the original two stops.
    6565
     66= Extending an existing VRPEvaluator =
     67
     68In order to implement the ''Pollution-Routing Problem (PRP)'' we need to derive from an existing {{{VRPEvaluator}}}. We derive from the existing ''Capaciated-VRP (CVRP)'' solution because we need a capacity for each stop and vehicle. The new class {{{CPRPEvaluator}}} (Capacitated-PRP) derives from {{{CVRPEvaluator}}}. In addition we need a new {{{CPRPEvaluation}}} class, based on {{{CVRPEvaluation}}} and a new {{{CPRPInsertionInfo}}} class, based on {{{CVRPInsertionInfo}}}.
     69
     70[[Image(4-PRP_EvaluatorEvaluationInfo_Hierarchy.png, 1000px)]]
     71
     72== New CPRPEvaluation and CPRPInsertionInfo classes ==
     73
     74The new {{{CPRPEvaluation}}} additionally stores the ''energy consumption'' of a solution candidate. For the energy consumption not only the driven distance is considered, but also the load of the vehicle.
     75
     76{{{
     77#!cs
     78public class CPRPEvaluation : CVRPEvaluation {
     79  public double EnergyConsumption { get; set; }
     80}
     81}}}
     82
     83In the {{{CPRPInsertionInfo}}} we additionally need to store the load and the driven distance of a vehicle after a stop. This information is used to implement the {{{GetTourInsertionCosts()}}} method for incremental evaluation later in the tutorial.
     84
     85{{{
     86#!cs
     87public class CPRPInsertionInfo : CVRPInsertionInfo {
     88  private readonly double load;
     89 
     90  public double Load {
     91    get { return load; }
     92  }
     93 
     94  private readonly double drivenDistance;
     95 
     96  public double DrivenDistance {
     97    get { return drivenDistance; }
     98  }
     99 
     100  public CPRPInsertionInfo(int start, int end, double spareCapacity, double load, double drivenDistance)
     101    : base(start, end, spareCapacity) {
     102    this.load = load;
     103    this.drivenDistance = drivenDistance;
     104  }
     105}
     106}}}
     107
     108== New CPRPEvaluator class ==
     109
     110Now, we can start creating a new {{{CPRPEvaluator}}} class which overrides the {{{EvaluateTour()}}} and {{{GetTourInsertionCosts()}}} method. In addition it stores the {{{EnergyConsumptionParameter}}} and override a method for setting the default value for the parameter as well as override a method for set the parameter based on an evaluation. We also have to implement methods for creating a new evaluation object. Furthermore, the {{{CPRPEvaluator}}} has to implement a few HeuristicLab specific functionalities for cloning and persistence. For simplicity we left {{{EvaluateTour()}}} and {{{GetTourInsertionCosts()}}} blank for now and deal with them later.
     111
     112{{{
     113#!cs
     114[Item("CPRPEvaluator", "Represents a single depot CPRP evaluator.")]
     115[StorableClass]
     116public class CPRPEvaluator : CVRPEvaluator {
     117  public ILookupParameter<DoubleValue> EnergyConsumptionParameter {
     118    get { return (ILookupParameter<DoubleValue>)Parameters["EnergyConsumption"]; }
     119  }
     120 
     121  [StorableConstructor]
     122  protected CPRPEvaluator(bool deserializing) : base(deserializing) { }
     123 
     124  public CPRPEvaluator() {
     125    Parameters.Add(new LookupParameter<DoubleValue>("EnergyConsumption", "The energy consumption."));
     126  }
     127 
     128  public override IDeepCloneable Clone(Cloner cloner) {
     129    return new CPRPEvaluator(this, cloner);
     130  }
     131 
     132  protected CPRPEvaluator(CPRPEvaluator original, Cloner cloner)
     133    : base(original, cloner) {
     134  }
     135 
     136  protected override VRPEvaluation CreateTourEvaluation() {
     137    return new CPRPEvaluation();
     138  }
     139 
     140  protected override void InitResultParameters() {
     141    base.InitResultParameters();
     142 
     143    EnergyConsumptionParameter.ActualValue = new DoubleValue(0);
     144  }
     145 
     146  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
     147    base.SetResultParameters(tourEvaluation);
     148 
     149    EnergyConsumptionParameter.ActualValue.Value = (tourEvaluation as CPRPEvaluation).EnergyConsumption;
     150  }
     151 
     152  protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
     153    //TODO
     154  }
     155 
     156  protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
     157    out bool feasible) {
     158    //TODO
     159    feasible = false;
     160    return 0.0;
     161  }
     162}
     163}}}
     164
     165== Implementing EvaluateTour ==
     166
     167In order to implement {{{EvaluateTour()}}} for the {{{CPRPEvaluator}}} we copy the existing implementation from the {{{CVRPEvaluator}}} and modify it. This procedure, of copying an existing implementation instead of using proper extensible architecture, is done due to performance reasons. Because the evaluation process is triggered very often, a fast implementation is critical. The existing VRP variants are also based on copying existing solutions.
     168
     169In the beginning we rename the {{{delivered}}} variable to {{{load}}} due to more appropriate meaning of the variable (do not forget to modify it in the subsequent code). In addition we need to store the {{{energy}}} consumption of a tour. Then we use the existing code to calculate the load and check if for overweight already on this position, because we will modify the {{{load}}} variable later. The first lines should look like following:
     170{{{
     171#!cs
     172TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));
     173eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     174double originalQuality = eval.Quality;
     175 
     176IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
     177DoubleArray demand = instance.Demand;
     178 
     179double load = 0.0;
     180double overweight = 0.0;
     181double distance = 0.0;
     182double energy = 0.0;
     183 
     184double capacity = cvrpInstance.Capacity.Value;
     185for (int i = 0; i <= tour.Stops.Count; i++) {
     186  int end = 0;
     187  if (i < tour.Stops.Count)
     188    end = tour.Stops[i];
     189 
     190  load += demand[end];
     191}
     192 
     193double spareCapacity = capacity - load;
     194if (load > capacity) {
     195  overweight = load - capacity;
     196}
     197}}}
     198
     199Now we can simulate a tour. In addition to the existing implementation we also calculate the used {{{energy}}} by multiplying the {{{currentDistance}}} with the current {{{load}}}. Afterwards we decrease the {{{load}}} by the {{{demand}}} of the current {{{stop}}}. Instead of the {{{CVRPInsertionInfo}}} we create a {{{CPRPInsertionInfo}}} and additionally add the current {{{load}}} and the summarized {{{distance}}}.
     200
     201{{{
     202#!cs
     203//simulate a tour, start and end at depot
     204for (int i = 0; i <= tour.Stops.Count; i++) {
     205  int start = 0;
     206  if (i > 0)
     207    start = tour.Stops[i - 1];
     208  int end = 0;
     209  if (i < tour.Stops.Count)
     210    end = tour.Stops[i];
     211 
     212  //drive there
     213  double currentDistace = instance.GetDistance(start, end, solution);
     214  distance += currentDistace;
     215  energy += currentDistace * load;
     216 
     217  load -= instance.GetDemand(end);
     218 
     219  CPRPInsertionInfo stopInfo = new CPRPInsertionInfo(start, end, spareCapacity, load, distance);
     220  tourInfo.AddStopInsertionInfo(stopInfo);
     221}
     222}}}
     223
     224Finally, we must set the {{{EnergyConsumption}}} property of our {{{CPRPEvaluation}}} and add the used energy to the quality.
     225
     226{{{
     227#!cs
     228eval.Quality += instance.FleetUsageFactor.Value;
     229eval.Quality += instance.DistanceFactor.Value * distance;
     230eval.Quality += energy;
     231 
     232eval.Distance += distance;
     233eval.VehicleUtilization += 1;
     234(eval as CPRPEvaluation).EnergyConsumption += energy;
     235 
     236(eval as CVRPEvaluation).Overload += overweight;
     237double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
     238eval.Penalty += penalty;
     239eval.Quality += penalty;
     240tourInfo.Penalty = penalty;
     241tourInfo.Quality = eval.Quality - originalQuality;
     242}}}
     243
     244== Implementing GetTourInsertionCosts ==
     245
     246In order to implement {{{GetTourInsertionCosts()}}} we copy the implementation from the {{{CVRPEvaluator}}} again. Instead of a {{{CVRPInsertionInfo}}} we want to use a {{{CPRPInsertionInfo}}}, therefore we change the types in the first line.
     247
     248To determine the insertion costs we have to consider the change of the load for the whole tour. In addition to the increased distance we have to consider following factors:
     249 - The weight for {{{End}}} has to be carried the additional distance ({{{newDistance-distance}}}).
     250 - The weight of the new {{{customer}}} has to be carried to the new {{{customer}}}.
     251   - To {{{Start}}} ({{{drivenDistance-distance}}})
     252   - plus distance between {{{Start}}} and new {{{comstumer}}}.
     253
     254[[Image(5-TourInsertion.png, 500px)]]
     255
     256{{{
     257#!cs
     258CPRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CPRPInsertionInfo;
     259 
     260double costs = 0;
     261feasible = tourInsertionInfo.Penalty < double.Epsilon;
     262 
     263ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
     264double overloadPenalty = cvrp.OverloadPenalty.Value;
     265 
     266double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
     267double newDistance =
     268  instance.GetDistance(insertionInfo.Start, customer, solution) +
     269  instance.GetDistance(customer, insertionInfo.End, solution);
     270costs += instance.DistanceFactor.Value * (newDistance - distance);
     271costs += (newDistance - distance) * (insertionInfo.Load + instance.GetDemand(insertionInfo.End));
     272costs += (insertionInfo.DrivenDistance - distance) * instance.GetDemand(customer);
     273costs += instance.GetDistance(insertionInfo.Start, customer, solution) * instance.GetDemand(customer);
     274 
     275double demand = instance.Demand[customer];
     276if (demand > insertionInfo.SpareCapacity) {
     277  feasible = false;
     278 
     279  if (insertionInfo.SpareCapacity >= 0)
     280    costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
     281  else
     282    costs += demand * overloadPenalty;
     283}
     284 
     285return costs;
     286}}}
     287