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

Timestamp:

01/28/14 14:50:29 (11 years ago)

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPEvaluator

@@ -46 +46 @@
 In 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. 
 
-[[Image(1-PRP_EvaluatorEvaluation.png)]]
+[[Image(1-PRP_EvaluatorEvaluation.png, 400px)]]
 
 The {{{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.
@@ -58 +58 @@
 In 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.
 
-[[Image(2-InsertionInfoSample.png)]]
-
-[[Image(3-PRP_EvaluatorEvaluationInfo.png)]]
+[[Image(2-InsertionInfoSample.png, 600px)]]
+
+[[Image(3-PRP_EvaluatorEvaluationInfo.png, 1000px)]]
 
 In 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.
 
+= Extending an existing VRPEvaluator =
+
+In 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}}}.
+
+[[Image(4-PRP_EvaluatorEvaluationInfo_Hierarchy.png, 1000px)]]
+
+== New CPRPEvaluation and CPRPInsertionInfo classes ==
+
+The 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.
+
+{{{
+#!cs
+public class CPRPEvaluation : CVRPEvaluation {
+  public double EnergyConsumption { get; set; }
+}
+}}}
+
+In 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.
+
+{{{
+#!cs
+public class CPRPInsertionInfo : CVRPInsertionInfo {
+  private readonly double load;
+ 
+  public double Load {
+    get { return load; }
+  }
+ 
+  private readonly double drivenDistance;
+ 
+  public double DrivenDistance {
+    get { return drivenDistance; }
+  }
+ 
+  public CPRPInsertionInfo(int start, int end, double spareCapacity, double load, double drivenDistance)
+    : base(start, end, spareCapacity) {
+    this.load = load;
+    this.drivenDistance = drivenDistance;
+  }
+}
+}}}
+
+== New CPRPEvaluator class ==
+
+Now, 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.
+
+{{{
+#!cs
+[Item("CPRPEvaluator", "Represents a single depot CPRP evaluator.")]
+[StorableClass]
+public class CPRPEvaluator : CVRPEvaluator {
+  public ILookupParameter<DoubleValue> EnergyConsumptionParameter {
+    get { return (ILookupParameter<DoubleValue>)Parameters["EnergyConsumption"]; }
+  }
+ 
+  [StorableConstructor]
+  protected CPRPEvaluator(bool deserializing) : base(deserializing) { }
+ 
+  public CPRPEvaluator() {
+    Parameters.Add(new LookupParameter<DoubleValue>("EnergyConsumption", "The energy consumption."));
+  }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new CPRPEvaluator(this, cloner);
+  }
+ 
+  protected CPRPEvaluator(CPRPEvaluator original, Cloner cloner)
+    : base(original, cloner) {
+  }
+ 
+  protected override VRPEvaluation CreateTourEvaluation() {
+    return new CPRPEvaluation();
+  }
+ 
+  protected override void InitResultParameters() {
+    base.InitResultParameters();
+ 
+    EnergyConsumptionParameter.ActualValue = new DoubleValue(0);
+  }
+ 
+  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
+    base.SetResultParameters(tourEvaluation);
+ 
+    EnergyConsumptionParameter.ActualValue.Value = (tourEvaluation as CPRPEvaluation).EnergyConsumption;
+  }
+ 
+  protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) { 
+    //TODO
+  }
+ 
+  protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
+    out bool feasible) {
+    //TODO 
+    feasible = false;
+    return 0.0;
+  }
+}
+}}}
+
+== Implementing EvaluateTour ==
+
+In 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.
+
+In 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:
+{{{
+#!cs
+TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));
+eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+double originalQuality = eval.Quality;
+ 
+IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
+DoubleArray demand = instance.Demand;
+ 
+double load = 0.0;
+double overweight = 0.0;
+double distance = 0.0;
+double energy = 0.0;
+ 
+double capacity = cvrpInstance.Capacity.Value;
+for (int i = 0; i <= tour.Stops.Count; i++) {
+  int end = 0;
+  if (i < tour.Stops.Count)
+    end = tour.Stops[i];
+ 
+  load += demand[end];
+}
+ 
+double spareCapacity = capacity - load;
+if (load > capacity) {
+  overweight = load - capacity;
+}
+}}}
+
+Now 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}}}.
+
+{{{
+#!cs
+//simulate a tour, start and end at depot
+for (int i = 0; i <= tour.Stops.Count; i++) {
+  int start = 0;
+  if (i > 0)
+    start = tour.Stops[i - 1];
+  int end = 0;
+  if (i < tour.Stops.Count)
+    end = tour.Stops[i];
+ 
+  //drive there
+  double currentDistace = instance.GetDistance(start, end, solution);
+  distance += currentDistace;
+  energy += currentDistace * load;
+ 
+  load -= instance.GetDemand(end);
+ 
+  CPRPInsertionInfo stopInfo = new CPRPInsertionInfo(start, end, spareCapacity, load, distance);
+  tourInfo.AddStopInsertionInfo(stopInfo);
+}
+}}}
+
+Finally, we must set the {{{EnergyConsumption}}} property of our {{{CPRPEvaluation}}} and add the used energy to the quality.
+
+{{{
+#!cs
+eval.Quality += instance.FleetUsageFactor.Value;
+eval.Quality += instance.DistanceFactor.Value * distance;
+eval.Quality += energy;
+ 
+eval.Distance += distance;
+eval.VehicleUtilization += 1;
+(eval as CPRPEvaluation).EnergyConsumption += energy;
+ 
+(eval as CVRPEvaluation).Overload += overweight;
+double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
+eval.Penalty += penalty;
+eval.Quality += penalty;
+tourInfo.Penalty = penalty;
+tourInfo.Quality = eval.Quality - originalQuality;
+}}}
+
+== Implementing GetTourInsertionCosts ==
+
+In 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.
+
+To 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:
+ - The weight for {{{End}}} has to be carried the additional distance ({{{newDistance-distance}}}).
+ - The weight of the new {{{customer}}} has to be carried to the new {{{customer}}}. 
+   - To {{{Start}}} ({{{drivenDistance-distance}}}) 
+   - plus distance between {{{Start}}} and new {{{comstumer}}}.
+
+[[Image(5-TourInsertion.png, 500px)]]
+
+{{{
+#!cs
+CPRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CPRPInsertionInfo;
+ 
+double costs = 0;
+feasible = tourInsertionInfo.Penalty < double.Epsilon;
+ 
+ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
+double overloadPenalty = cvrp.OverloadPenalty.Value;
+ 
+double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
+double newDistance =
+  instance.GetDistance(insertionInfo.Start, customer, solution) +
+  instance.GetDistance(customer, insertionInfo.End, solution);
+costs += instance.DistanceFactor.Value * (newDistance - distance);
+costs += (newDistance - distance) * (insertionInfo.Load + instance.GetDemand(insertionInfo.End));
+costs += (insertionInfo.DrivenDistance - distance) * instance.GetDemand(customer);
+costs += instance.GetDistance(insertionInfo.Start, customer, solution) * instance.GetDemand(customer);
+ 
+double demand = instance.Demand[customer];
+if (demand > insertionInfo.SpareCapacity) {
+  feasible = false;
+ 
+  if (insertionInfo.SpareCapacity >= 0)
+    costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
+  else
+    costs += demand * overloadPenalty;
+}
+ 
+return costs;
+}}}
+