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

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