work in progress ...

How to ... implement a new VRPEncoding

Goals

One way to implement a new VRP variant is by implementing a new VRPEncoding and new Operators. This is a suitable possibility if the VRP variant requires additional decision variables to optimize. Based on these new decision variables, new Operators for crossing and mutating solutions in the search process of algorithms (e.g. a Genetic Algorithm) are required.

A VRPEncoding is the representation of a solution candidate for a given ProblemInstance (see How to ... implement a new VRP ProblemInstance?). There are different ways of representing and operating on tours of a VRP solution. (​source) Different Encodings require different Operators to work on. This way of extending the vehicle routing problem allows you to modify the search process and yielding results with additinal decition variables.

After this tutorial you will be able to implement you own VRP variants that require additional decision variables. You will also have a basic understanding of the concepts and architecture concerning the VRPEncoding, the VRPOperator concepts and related components.

The Multi Trip Vehicle Routing Problem

To show the procedure of implementing a new VRPEncoding, the implementation of the Multi Trip Vehicle Routing Problem (MTVRP) (​source) is demonstrated. The MTVRP allows vehicles to return to the depot, refill their cargo and therefore can satisfy multiple tours. In addition the maximum driving distance of each vehicle is limited. Usually MTVRP solutions require much fewer vehicles compared to standard VRP variants because a vehicle can drive multiple tours.

In this tutorial, the MTVRP is based on the Capacitated Vehicle Routing Problem (CVRP). In addition we have to specify the maximum distance a vehicle can drive as well the penalty for exceeding the maximum distance.

To implement the new Encoding we extend the existing PotvingEncoding (​source). In addition, the available operators for the PotvinEncoding will be extended in order to make use of the new data in the encoding. The advantage of extending an existing encoding is that we can reuse the original operators in the algorithm. If you like to implement a complete new encoding you also have to implement all operators yourself.

Prerequisites

Before you start, make sure you have the latest version of the HeuristicLab source code ready. Then create a new plugin called HeuristicLab.MultiTripVRP. For additional help for creating a new plugin, see How to ... create HeuristicLab plugins (step by step)?.

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

[Plugin("HeuristicLab.MultiTripVRP", "1.0.0.0")]
[PluginFile("HeuristicLab.MultiTripVRP.dll", PluginFileType.Assembly)]
[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
public class MultiTripVRPPlugin : PluginBase {
}

In addition you will need references onto following HeuristicLab assemblies:

• HeuristicLab.Collections
• HeuristicLab.Common
• HeuristicLab.Core
• HeuristicLab.Data
• HeuristicLab.Encodings.PermutationEncoding
• HeuristicLab.Operators
• HeuristicLab.Optimization
• HeuristicLab.Parameters
• HeuristicLab.Persistence
• HeuristicLab.Problems.VehicleRouting

Implementing new Encoding

Sample Foundations

MultiTripVRPInstance

MultiTripEvaluator

Implementing new Operators

Foundations

Link Encoding/Operators to VRP variants

Implementing new MultiTripOperator

Implementing new Creator

Implementing new Manipulator

Implement new Crossover

Result

Configure Algorithm

Interpretation