How To Implement New Evaluators for the VRP

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 ​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 the development center.

The plugin need an additional dependency onto the HeuristicLab.Problems.VehicleRouting plugin. Finally, the plugin should look like this:

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

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.

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.

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.

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.

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.

[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:

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.

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

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.

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)
   1. Choose a CVPR instance (e.g. Augerat A-n36-k5)
2. Show hidden parameters in problem
   1. Select the Evaluator parameter and set the value to the new PRPEvaluator
3. In the ProblemInstance set following parameter
   1. Limit the number of Vehicles (e.g. 5) (depends on problem; compare the number of vehicles for best known quality)
   2. Set DistanceFactor to 0 (distance is already considered in energy consumption)
4. Set parameter of the algorithm
   1. 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

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

with CVRP