work in progress ...

= How to ... implement a new VRP Evaluator =

== Goals ==

One way to implement a new VPR variant is by extending the {{{VRPEvaluator}}}. This is a suitable possibility if the VRP variant does not require additional model data or decision variables. A {{{VRPEvaluator}}} is responsible for evaluating a solution candidate which contains a set of tours. By extending the {{{VRPEvaluator}}}, it is possible to interpret the available information of a specific problem instance differently.

After this tutorial you will be able to implement your own VRP variants that only require extending the {{{VRPEvaluator}}}. You will also have a basic understanding of the concepts and architecture concerning the {{{VRPEvaluator}}} and related components.

== The Pollution-Routing Problem ==

To demonstrate the procedure of extending a {{{VRPEvaluator}}}, the implementation of the [http://www.sciencedirect.com/science/article/pii/S019126151100018X Pollution-Routing Problem] is demonstrated. The ''Pollution-Routing Problem (PRP)'' considers the environmental impact of transport logistic by taking the energy consumption of a vehicle into account. Depending on the PRP model, different factors like vehicle mass, speed and environment related factors are considered.

In this tutorial the PRP is based on the ''Capacitated Vehicle Routing Problem (CVRP)''. To keep the tutorial as simple as possible only the current mass of a vehicle is considered. The current mass of a vehicle is computable by its current position in a tour. Therefore no additional model data is required and the implementation of the PRP is possible by only extending the {{{VRPEvaluator}}}.

== Prerequisites ==

Before you start, make sure you have the latest version of the HeuristicLab source code ready. Then create a new plugin called {{{HeuristicLab.PollutionRoutingProblem}}}. For additional help for creating a new plugin, see [wiki:UsersHowtosImplementPluginsStepByStep How to ... create HeuristicLab plugins (step by step)].

The plugin need an additional dependency onto the {{{HeuristicLab.Problems.VehicleRouting}}} plugin. Finally, the plugin should look like this:
{{{
#!cs
[Plugin("HeuristicLab.PollutionRoutingProblem", "1.0.0.0")]
[PluginFile("HeuristicLab.PollutionRoutingProblem.dll", PluginFileType.Assembly)]
[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
public class PollutionRoutingProblemPlugin : PluginBase {
}
}}}

In addition you will need references onto following HeuristicLab assemblies:
 - HeuristicLab.Collections
 - HeuristicLab.Common
 - HeuristicLab.Core
 - HeuristicLab.Data
 - HeuristicLab.Operators
 - HeuristicLab.Optimization
 - HeuristicLab.Parameters
 - HeuristicLab.Persistence
 - '''HeuristicLab.Problems.VehicleRouting'''

= Foundations =

== VRPEvaluator ==

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, 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.

In order to evaluate an entire solution candidate, each tour is evaluated separately. To accomplish this, the abstract method {{{EvaluateTour()}}} is called for each tour. The quality and other values of each tour are summarized into the {{{VRPEvaluation}}}. This is usually done by calculating the distance of each stop and multiplies it with a factor to obtain the quality. If constraints are violated, the penalty value is increased analogously. 

== Incremental Evaluation ==

Some algorithms, like the ''Tabu Search'', work incremental and therefore require a ''move-based evaluation''. A ''move'' corresponds to the insertion of an additional stop into an existing tour. Then, the change of quality is used to determine the further proceeding of the algorithm.

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, 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;
}}}

= Set the new Evaluator in HeuristicLab =

After we finished implementing the insertion infos and the evaluator, compile the plugin and start HeuristicLab.

1. Open a VRP sample (e.g. Tabu Search – VRP)
   a. Choose a CVPR instance (e.g. Augerat A-n36-k5)
2. Show hidden parameters in problem
   a. Select the Evaluator parameter and set the value to the new PRPEvaluator
3. In the ProblemInstance set following parameter
   a. Limit the number of Vehicles (e.g. 5) (depends on problem; compare the number of vehicles for best known quality)
   b. Set DistanceFactor to 0 (distance is already considered in energy consumption)
4. Set parameter of the algorithm
   a. Increase number of Iterations (e.g. 20000)
5. Start the algorithm

Now the algorithm tries to find routs where the stops with high demands are delivered first to avoid carrying around heavy loads.
To demonstrate the effect cities with greater demands are displayed bigger. To modify the view for capacity dependent city sizes use the patch in the attachments.

||= with PRP =||
|| [[Image(6-PRP_result.png, 600px)]] ||


Compared to the standard CVRP evaluator, the solution for PRP can differentiate significantly.

||= with CVRP =||
|| [[Image(7-CVRP_result.png, 600px)]] ||