How To Implement New Encodings for the VRP

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 on creating a new plugin, visit the Development Center.

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
• HEAL.Attic
• HeuristicLab.Problems.VehicleRouting

Implementing new Encoding

The first thing to do is to create the new encoding. If you want to implement a whole new encoding, you start by deriving from TourEncoding. Then you have to store the assignments vehicles to tours as well as additional data, like our tour delimiters for the multi trip VRP. In the case of this tutorial we derive from the existing PotvinEncoding which stores the vehicle assignments already.

[Item("MultiTripEncoding", "Represents a potvin encoding of VRP solutions adapted for multi trip VRPs.")]
[StorableType("3f543d26-1187-4861-954d-0f98896c11e1")]
public class MultiTripEncoding : PotvinEncoding {
 
  [StorableConstructor]
  protected MultiTripEncoding(StorableConstructorFlag _) : base(_) { }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripEncoding(this, cloner);
  }
 
  [StorableHook(HookType.AfterDeserialization)]
  private void AfterDeserialization() {
    AttachEventHandlers();
  }
}

To implement the multi trip VRP we need to store when a tour is interrupted and the vehicle drives back to the depot. We store this information in a List<list<bool>> which indicates whether the tour is interrupted after the stop or not. A more compact possibility is to store the delimiters as bit in an integer, but then you are limited by the size of an integer (32 bit).

[Storable]
public List<List<bool>> TripDelimiters { get; private set; }
 
public MultiTripEncoding(IVRPProblemInstance instance)
  : base(instance) {
  TripDelimiters = new List<List<bool>>();
  AttachEventHandlers();
}

protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
  : base(original, cloner) {
  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
  foreach (var delimiters in original.TripDelimiters) {
    TripDelimiters.Add(new List<bool>(delimiters));
  }
}

protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
  : base(original, cloner) {
  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
  foreach (var delimiters in original.TripDelimiters) {
    TripDelimiters.Add(new List<bool>(delimiters));
  }
}

In order to keep the delimiters synchronized with the actual tours we need to register event handlers on the Tours collection. When a tour is added or removed we also have to add or remove the delimiters.

private void AttachEventHandlers() {
  Tours.ItemsAdded += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsAdded);
  Tours.ItemsRemoved += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsRemoved);
}
 
void Tours_ItemsAdded(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
  foreach (var added in e.Items.Except(e.OldItems).OrderBy(x => x.Index)) {
    TripDelimiters.Insert(added.Index, new List<bool>());
  }
}
 
void Tours_ItemsRemoved(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
  foreach (var removed in e.OldItems.Except(e.Items).OrderByDescending(x => x.Index)) {
    TripDelimiters.RemoveAt(removed.Index);
  }
}

In addition we implement a method for retrieving the delimiters for a tour as array, and to flip a delimiter on specific position in a tour. These methods are used for the VRPOperators and the VRPEvaluator later. We also specify a method for converting an existing PotvinEncoding and new delimiters to a new MultiTripEncoding.

public bool[] GetDelimiters(int tour) {
  if (tour < TripDelimiters.Count) {
    return TripDelimiters[tour].ToArray();
  } else {
    return new bool[0];
  }
}
 
public void FlipDelimiter(int tour, int index) {
  if (tour < TripDelimiters.Count) {
    if (TripDelimiters[tour].Count <= index) {
      for (int i = TripDelimiters[tour].Count; i <= index; i++) {
        TripDelimiters[tour].Add(false);
      }
    }
 
    TripDelimiters[tour][index] = !TripDelimiters[tour][index];
  }
}

public static MultiTripEncoding ConvertFrom(IVRPProblemInstance instance, PotvinEncoding orig, List<List<bool>> tripDelimiters = null) {
  MultiTripEncoding result = new MultiTripEncoding(instance);
 
  result.Tours.AddRange(orig.Tours);
  for (int i = 0; i < result.Tours.Count; i++) {
    result.VehicleAssignment[i] = orig.VehicleAssignment[i];
  }
 
  if (tripDelimiters != null)
    result.TripDelimiters = tripDelimiters;
 
  return result;
}

Sample Foundations

In order to implement the sample we need a new ProblemInstance and a new Evaluator for the MultiTrip VRP variant. For detailed information about creating new VRPInstances and VRPEvaluators see how to implement a new VRP problem instance and how to implement a new VRP evaluator.

MultiTripVRPInstance

The MultiTripVRPInstance only needs to store the additional MaxDistance parameter for the vehicle as well as the penalty for exceeding it.

[StorableType("12ce8815-d464-4775-a6a5-02bffc7f447d")]
public interface IMultiTripProblemInstance {
  DoubleValue MaxDistance { get; set; }
  DoubleValue MaxDistancePenalty { get; set; }
}

For the implementation the usual HL specific cloning and persistence code is necessary.

[Item("MultiTripVRPInstance", "Represents a single depot multi trip CVRP instance.")]
[StorableType("3051e556-1d88-4527-8925-8020c419b5d3")]
public class MultiTripVRPInstance : CVRPProblemInstance, IMultiTripProblemInstance {
  protected IValueParameter<DoubleValue> MaxDistanceParameter {
    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistance"]; }
  }
 
  public DoubleValue MaxDistance {
    get { return MaxDistanceParameter.Value; }
    set { MaxDistanceParameter.Value = value; }
  }
 
  protected IValueParameter<DoubleValue> MaxDistancePenaltyParameter {
    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistancePenalty"]; }
  }
 
  public DoubleValue MaxDistancePenalty {
    get { return MaxDistancePenaltyParameter.Value; }
    set { MaxDistancePenaltyParameter.Value = value; }
  }
 
  [StorableConstructor]
  protected MultiTripVRPInstance(StorableConstructorFlag _) : base(_) { }
 
  public MultiTripVRPInstance() {
    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistance", "The max distance of each vehicle.", new DoubleValue(100)));
    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistancePenalty", "The distance penalty considered in the evaluation.", new DoubleValue(100)));
 
    AttachEventHandlers();
  }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripVRPInstance(this, cloner);
  }
 
  protected MultiTripVRPInstance(MultiTripVRPInstance original, Cloner cloner)
    : base(original, cloner) {
    AttachEventHandlers();
  }
 
  [StorableHook(HookType.AfterDeserialization)]
  private void AfterDeserialization() {
    AttachEventHandlers();
  }
 
  private void AttachEventHandlers() {
    MaxDistanceParameter.ValueChanged += new EventHandler(MaxDistanceParameter_ValueChanged);
    MaxDistancePenaltyParameter.ValueChanged += new EventHandler(MaxDistancePenaltyParameter_ValueChanged);
  }
 
  void MaxDistancePenaltyParameter_ValueChanged(object sender, EventArgs e) {
    MaxDistancePenaltyParameter.Value.ValueChanged += new EventHandler(ValueChanged);
    EvalBestKnownSolution();
  }
 
  void MaxDistanceParameter_ValueChanged(object sender, EventArgs e) {
    MaxDistanceParameter.Value.ValueChanged += new EventHandler(ValueChanged);
    EvalBestKnownSolution();
  }
 
  void ValueChanged(object sender, EventArgs e) {
    EvalBestKnownSolution();
  }
 }

We will override more methods in the MultiTripProblemInstance class when we deal with operators in this tutorial later.

MultiTripEvaluator

For the evaluator we copy the CVRPEvaluator and modify it. Now we consider the travel distance after a stopover on the depot and calculate the maximum distance violation.

public class MultiTripEvaluation : CVRPEvaluation {
  public double MaxDistanceViolation { get; set; }
}
 
[Item("MultiTripEvaluator", "Represents a single depot CVRP evaluator with multiple trips.")]
[StorableType("557b8938-0e72-440c-ab20-5d2e31f715a0")]
public class MultiTripEvaluator : CVRPEvaluator {
  public ILookupParameter<DoubleValue> MaxDistanceViolationParameter {
    get { return (ILookupParameter<DoubleValue>)Parameters["MaxDistanceViolation"]; }
  }
 
  protected override VRPEvaluation CreateTourEvaluation() {
    return new MultiTripEvaluation();
  }
  
  protected override void InitResultParameters() {
    base.InitResultParameters();
 
    MaxDistanceViolationParameter.ActualValue = new DoubleValue(0);
  }
 
  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
    base.SetResultParameters(tourEvaluation);
 
    MaxDistanceViolationParameter.ActualValue.Value = (tourEvaluation as MultiTripEvaluation).MaxDistanceViolation;
  }
 
  [StorableConstructor]
  protected MultiTripEvaluator(StorableConstructorFlag _) : base(_) { }
 
  public MultiTripEvaluator() {
    Parameters.Add(new LookupParameter<DoubleValue>("MaxDistanceViolation", "The distance violation."));
  }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripEvaluator(this, cloner);
  }
 
  protected MultiTripEvaluator(MultiTripEvaluator original, Cloner cloner)
    : base(original, cloner) {
  }
}

In the evaluation process we need to consider the additional travel distance after a vehicle drives back to the depot. Therefore we add the distance from the current stop to the depot and the distance between the depot and the next stop instead of the direct distance.

After a tour we have to check the maximum driven distance whether it exceeds the maximum driven distance of a vehicle or not. In case of a violation of the limit we increment the penalty.

protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
  TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour))); ;
  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
  double originalQuality = eval.Quality;
 
  IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
  MultiTripVRPInstance multiTripInstance = instance as MultiTripVRPInstance;
  DoubleArray demand = instance.Demand;
 
  double overweight = 0.0;
  double distance = 0.0;
 
  double capacity = cvrpInstance.Capacity.Value;
  double spareCapacity = capacity;
 
  var tripDelimiters = new bool[0];
  if(solution is MultiTripEncoding)
    tripDelimiters = ((MultiTripEncoding)solution).GetDelimiters(solution.GetTourIndex(tour));
 
  //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 = 0;
 
    if (i > 0 && tripDelimiters.Length >= i && tripDelimiters[i - 1]) {
      currentDistace += instance.GetDistance(start, 0, solution);
      currentDistace += instance.GetDistance(0, end, solution);
 
      spareCapacity = capacity;
    } else {
      currentDistace += instance.GetDistance(start, end, solution);
    }
    distance += currentDistace;
 
    spareCapacity -= demand[end];
    if (spareCapacity < 0) {
      overweight += -spareCapacity;
      spareCapacity = 0;
    }
 
    CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
    tourInfo.AddStopInsertionInfo(stopInfo);
  }
 
  eval.Quality += instance.FleetUsageFactor.Value;
  eval.Quality += instance.DistanceFactor.Value * distance;
 
  eval.Distance += distance;
  eval.VehicleUtilization += 1;
 
  (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;
 
  if (distance > multiTripInstance.MaxDistance.Value) {
    double maxDistanceViolation = (distance - (multiTripInstance.MaxDistance.Value));
    penalty = maxDistanceViolation * multiTripInstance.MaxDistancePenalty.Value;
    eval.Penalty += penalty;
    eval.Quality += penalty;
    (eval as MultiTripEvaluation).MaxDistanceViolation += maxDistanceViolation;
  }
}

Because the increment based implementation is not trivial and not topic of this tutorial, we evaluate the tour at whole and calculate the distance to the previous solution.

protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
  out bool feasible) {
    if (!(solution is MultiTripEncoding)) {
      return base.GetTourInsertionCosts(instance, solution, tourInsertionInfo, index, customer, out feasible);
    } else {
      MultiTripEncoding individual = (solution as MultiTripEncoding);
 
      int tourIdx = -1;
      for (int i = 0; i < individual.Tours.Count; i++) {
        if (solution.GetVehicleAssignment(i) == tourInsertionInfo.Vehicle)
          tourIdx = i;
      }
      Tour tour = individual.Tours[tourIdx];
 
      tour.Stops.Insert(index, customer);
      VRPEvaluation newEval = instance.EvaluateTour(tour, individual);
      tour.Stops.RemoveAt(index);
 
      feasible = instance.Feasible(newEval);
      return newEval.Quality - tourInsertionInfo.Quality;
    }
}

Implementing new Operators

Foundations

HeuristicLab defines different operators for different situations and algorithms. In this tutorial we will use the following operators:

• SolutionCreator: Operator responsible for creating a new solution (instancing a specific encoding)
• Crossover: Combines two solutions
• Manipulator: Mutates a solution

Link Encoding/Operators to VRP variants

Because different encodings store different information, encodings are able to handle different VRP variants. Each variant specify a marker interface to indicate its "variant type" (e.g. TimeWindowedOperator). A VRP variant compatible encoding can implement this variant type (e.g. GVROperator implements the TimeWindowedOperator). This way, each encoding can specify compatible variants and implements the operators based on the encodings abilities.

In order to link the compatible operators to a VRP variant, the ProblemInstance have to provide a list of compatible Operators. Because a ProblemInstance usually derives from a base ProblemInstance, it uses the operators from the base implementation and selects only the compatible ones. For instance, the CVRPTWProblemInstance uses the operators from the CVRPProblemInstance and only uses those operators which implement the TimeWindowedOperator.

The following figure shows a small sample and overview:

The SingleDepotOperator, CapcaitatedOperator and TimeWindowedOperator represent VRP variants or parts of VRP variants. The AlbaOperator implements all three of them and therefore can be used for all of them. In comparison, the GVROperator (not show in the diagram) does not implement MultiDepotOperator(also not shown) and therefore is not compatible with variants that use multiple depots.

Specific and VRPProblemInstances then specifies which operators are compatible. For instance the CVRPProblemInstance filters the operators by CapacitatedOperator. The CVRPTWProblemInstance, which derives from CVRPProblemInstances used the prefiltered operators and filters by TimeWindowedOperator:

protected override IEnumerable<IOperator> GetOperators() {
  return base.GetOperators().Where(o => o is ITimeWindowedOperator).Cast<IOperator>();
}

Implementing new MultiTripOperator

The first step in implementing new operators is to create the marker interface for the VRP variant.

[StorableType("1ab590b7-e0a1-4051-b6f4-610f25737f43")]
public interface IMultiTripOperator : IVRPOperator { }

After that, we need to link all our MultiTripOperators implementations to the MultiTripProblemInstance. This is done by overriding the GetOperators method. If you implement a complete new Encoding the method would look like this:

protected override IEnumerable<IOperator> GetOperators() {
  return base.GetOperators().Where(o => o is IMultiTripOperator).Cast<IOperator>();
}

In the case of this tutorial we are extending the PotvinEncoding, which defines multiple Operators already. Therefore we want to reuse the existing Operators for our MultiTripEncoding (e.g. the Manipulators and Crossovers). Because we will derive our MultiTripOperators from the PotvinOperators we could simply use all the Operators specified in the base ProblemInstance.

However, we cannot use all PotvinOperators, we need to rule out the PotvinCreators. If someone accidently configures a PotvinCreator, plain PotvinEncoding instances are created and our own MultiTripOperators, which rely on the additional data, will not work. Therefore if an Operator is a VRPCreator it implies that it is a MultiTripOperator.

For a similar reason we cannot reuse Operators from other Encodings, which is usually possible due to conversion between them. If we convert our MultiTripEncoding to a different Encoding we lose the information about the delimiters. Therefore we can only reuse the PotvinOperators because no conversion is required this way.

protected override IEnumerable<IOperator> GetOperators() {
  return base.GetOperators()
    .Where(o => o is IPotvinOperator)
    // is IVRPCreator  implicates  is IMultiTripOperator 
    .Where(o => !(o is IVRPCreator) || (o is IMultiTripOperator)).Cast<IOperator>();
}

Implementing new Creator

The implementation of the new MultiTripIterativeInsertionCreator is very easy. We use the functionality of the IterativeInsertionCreator of the PotvinEncoding to create a PotvinEncoding and convert it with the method from the previous section of the tutorial.

Note that all initial solution candidates created with no delimiters, because random delimiters would mainly yield infeasible solutions, which are hard to repair afterwards.

[Item("MultiTripIterativeInsertionCreator", "Creates a randomly initialized VRP solution.")]
[StorableType("1bd069bf-f31c-476d-94a7-a1b4fd12864c")]
public sealed class MultiTripIterativeInsertionCreator
  : PotvinCreator, IStochasticOperator, IMultiTripOperator {
 
  #region IStochasticOperator Members
  public ILookupParameter<IRandom> RandomParameter {
    get { return (LookupParameter<IRandom>)Parameters["Random"]; }
  }
  #endregion
 
  [StorableConstructor]
  private MultiTripIterativeInsertionCreator(StorableConstructorFlag _) : base(_) { }
 
  public MultiTripIterativeInsertionCreator()
    : base() {
    Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
  }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripIterativeInsertionCreator(this, cloner);
  }
 
  private MultiTripIterativeInsertionCreator(MultiTripIterativeInsertionCreator original, Cloner cloner)
    : base(original, cloner) {
  }
 
  public override IOperation InstrumentedApply() {
    PotvinEncoding singleTripSolution = IterativeInsertionCreator.CreateSolution(
      ProblemInstanceParameter.ActualValue, RandomParameter.ActualValue, false);
 
    VRPToursParameter.ActualValue = MultiTripEncoding.ConvertFrom(ProblemInstanceParameter.ActualValue, singleTripSolution);
 
    return base.InstrumentedApply();
  }
}

A more intelligent Creator, which implements a heuristic to place reasonable delimiters for initial solutions would be nice and would help the algorithm a lot, but is not part of this tutorial.

Implementing new Manipulator

The MultiTripManipulator randomly flips a delimiter in a random tour. This is a very simple mutation and many more implementations are possible, for example to shift a delimiter within a tour. Also a more intelligent manipulators are possible, for example a manipulator who looks for good delimiter positions in long sub-tours, or one who tries to remove delimiters in short sub-tours.

[Item("MultiTripManipulator", "The manimulation operator which flips a random tour delimiter in a multi trip VRP.")]
[StorableType("8f652e53-bfd1-44d9-a1a8-34e8ba24913a")]
public class MultiTripManipulator
  : PotvinManipulator, IMultiTripOperator {

  [StorableConstructor]
  private MultiTripManipulator(StorableConstructorFlag _) : base(_) { }
 
  public MultiTripManipulator() : base() { }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripManipulator(this, cloner);
  }
 
  private MultiTripManipulator(MultiTripManipulator original, Cloner cloner)
    : base(original, cloner) {
  }
 
  protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    var multiTripIndividual = individual as MultiTripEncoding;
    if (multiTripIndividual != null && multiTripIndividual.Tours.Count > 0) {
      int tour = random.Next(individual.Tours.Count);
 
      if (multiTripIndividual.Tours[tour].Stops.Count > 0) {
        int position = random.Next(multiTripIndividual.Tours[tour].Stops.Count);
 
        multiTripIndividual.FlipDelimiter(tour, position);
      }
    }
  }
}

Implement new Crossover

To implement a new Crossover which only combines two sets of delimiters would not yield good results. Therefore we implement a crossover that first performs a PotvinRouteBasedCrossover and afterwards copy the delimiters from the copied tour into the new replaced tour of the new solution.

Unfortunately, the implementation of the crossover does not return which route was replaced, so we have to look it up first with a small helper method. Then we copy the delimiters from the old tour onto the new, replaced tour.

[Item("MultiTripRBX", "The RBX crossover for multi-trip VRP representations.")]
[StorableType("eed6f653-2a17-4836-be49-f9758e8f72dc")]
public class MultiTripRBX
  : PotvinCrossover, IMultiTripOperator {
 
  [StorableConstructor]
  private MultiTripRBX(StorableConstructorFlag _) : base(_) { }
 
  public MultiTripRBX()
    : base() { }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new MultiTripRBX(this, cloner);
  }
 
  private MultiTripRBX(MultiTripRBX original, Cloner cloner)
    : base(original, cloner) {
  }
 
  private int FindReplacedTour(PotvinEncoding original, PotvinEncoding manipulated) {
    int replacedTour = -1;
    for (int tourIdx = 0; tourIdx < original.Tours.Count; tourIdx++) {
      if (original.Tours[tourIdx].Stops.Count != manipulated.Tours[tourIdx].Stops.Count) {
        replacedTour = tourIdx;
        break;
      }
 
      for (int stopIdx = 0; stopIdx < original.Tours[tourIdx].Stops.Count; stopIdx++) {
        if (original.Tours[tourIdx].Stops[stopIdx] != manipulated.Tours[tourIdx].Stops[stopIdx]) {
          replacedTour = tourIdx;
          break;
        }
      }
 
      if (replacedTour >= 0)
        break;
    }
 
    return replacedTour;
  }
 
  protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
    MultiTripEncoding p1 = parent1 as MultiTripEncoding;
    MultiTripEncoding p2 = parent2 as MultiTripEncoding;
 
    PotvinEncoding child = PotvinRouteBasedCrossover.Apply(random, parent1, parent2, ProblemInstance, AllowInfeasibleSolutions.Value.Value);
    MultiTripEncoding ch = child as MultiTripEncoding;
 
    if (ch != null && p1 != null) {
      int tourIdx = FindReplacedTour(parent2, child);
      if (tourIdx != -1) {
        ch.TripDelimiters[tourIdx] = p1.TripDelimiters[tourIdx];
      }
    }
 
    return child;
  }
}

Result

Configure Algorithm

Before we can run the MultiTrip variant inside an algorithm we need to configure the algorithm beforehand. This tutorial provides step by step instructions on how to setup the algorithm and load the problem instance. To avoid this procedure you could write a new VRPDataInterpreter (see how to implement a new VRP problem instance). In the attachments of this tutorial you also find a configured ready-to-run algorithm.

1. Create a new Genetic Algorithm (you can chose a variant like Offspring Selection GA too, then the configuration changes slightly)
   1. Set a new Vehicle Routing Problem
   2. Set the ProblemInstance to a new MultiTripVRPInstance
2. Configure the Genetic Algorithm
   1. In the Problem set the SolutionCreator to MultiTripIterativeInsertionCreator (if not already set automatically)
   2. In the Algorithm Parameters set the Crossover to MultiTripRBX (if you like, you can use the other PotvinCrossovers as well in a MultiVRPSolutionCrossover)
   3. Set the Mutator to a MultiVRPSolutionManipulator
      1. Enable the MultiTripManipulator, PotvinOneLevelExchange and PotvinTwoLevelExchange manipulator
      2. If you want, increase the propability of the MultiTripManipulator (e.g. to 2)
   4. If you want, activate the CapacityRelaxion in the Analyzers
   5. Set the MutationProbability to 25%
   6. Set the PopulationSize to 20 (or higher for better results)
   7. Set the Generations to 2000 (or higher for better results)
3. Open a separate Vehicle Routing Problem
   1. Open a CVRP problem (your own or from a library) (e.g. Augerat P-n50-k7)
   2. Open the original GA ProblemInstance and the ProblemInstance from the new separate problem side by side
   3. Copy the Coordinates and Demands to the empty MultiTripVRPInstance by drag and drop them
   4. Set the remaining parameters (capacity, vehicles, ...)
   5. Set the MaxDistance (e.g. to 500)
4. Run the Algorithm

Interpretation

To visualize the sub-tours of a vehicle use the visualization-patch from the attachments. You also have to sign the MultiTripVRP plugin with the HL signature key from the HL source folder.

Compared to the original CVRP solution, now the algorithm finds solutions with less vehicles. If you set the MaxDistance high enough, the algorithm will find a solution with only one vehicle. However the algorithm needs very long and needs a bit of luck to find the optimal vehicle usage because our mutation and crossover operators actualy does not perform well. The PotvinCrossovers always treat tours at whole and ignore the tour delimiters. A specialized crossover which merges small sub-tours into other tours and preserves the sub-tours would be a good solution. Still, the solutions yielded by the algorithm use less vehicles than the original CVRP variant.