work in progres ...

How to … implement a new VRP ProblemInstance

Goals

One way to implement a new VRP variant is by implementing a new VRPProblemInstance. This is a suitable possibility if the VRP variant requires additional model data. A VRPProblemInstance is responsible for storing all information about a VRP instance like coordinates, distances, demands, etc. By extending a VRPProblemInstance it is possible to add additional data as additional constraints or flexibility to a VRP variant. It is also necessary to implement a new VRPEvaluator (see How to ... implement a new VRP Evaluator?) to interpret the new data.

In addition to the new VRPProblemInstance a new parser for reading the additional data from a file is required. In order to integrate the new parser into HeuristicLab a VRPInstanceProvider and other components are also required.

After this tutorial you will be able to implement you own VRP variants that require additional model data. You will also have a basic understanding of the concepts and architecture concerning the VRPProblemInstance, the VRPInstanceProvider and related components.

The Time Dependent Vehicle Routing Problem

To show the procedure of implementing a new VRPProblemInstance, the implementation of the ​Time Dependent Travel Time Vehicle Routing Problem (TDVRP) is demonstrated. The TDVPR considers the travel time variation during a day.

In this tutorial, the TDVRP is based on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The additional data are the travel times, which associate a travel time factor for a specific time. There are multiple ways to assign the travel time to the VRP. One way is to specify a global function which maps a time of a day to a travel time for all connections, as shown the following figure (​source).

In this tutorial we use travel-times matrices. Each matrix stores a travel time factor for every connection. Every travel time matrix also specifies a unique timestamp. Between the timestamp of a matrix and the subsequent matrix the travel times of the first matrix is used, resulting in hard steps of the travel time during the day.

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)?.

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

[Plugin("HeuristicLab.TimeDependentVRP", "1.0.0.0")]
[PluginFile("HeuristicLab.TimeDependentVRP.dll", PluginFileType.Assembly)]
[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
[PluginDependency("HeuristicLab.Problems.Instances.VehicleRouting", "3.4")]
public class TimeDependentVRPPlugin : 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
• HeuristicLab.Problems.Instances
• HeuristicLab.Problems.Instances.VehicleRouting

ProblemInstance

Foundations

A VRPProblemInstance contains all data for a specific VRP problem, for example the number of cities, their coordinates and demands. In addition the VRPProblemInstance provides methods for calculate the distance between two cities. Internally a distance matrix is created beforehand for a fast calculation.

A VRPEvaluator uses the VRPProblemInstance and a solution candidate for the VRPProblemInstance to evaluate the solution candidate.

HeuristicLab implements several common VRP variants like the Capaciated VRP (CVRP) and VRP with Time Windows (VRPTW). Every VRP variant extends an existing VRPProblemInstance and adds the new data, for example the capacity for the vehicles in the CVRP. In order to interpret the new data a new VRPEvaluator for each VRPProblemInstance is also necessary.

Extending ProblemInstance and Evaluator

To implement a new VRP variant with additional model data you have to extend an existing VRPProblemInstance and VRPEvaluator. For this tutorial we extend the available CVRPTW.

Implement new ProblemInstance

The new TimeDependentProblemInstance derives from the existing TimeWindowedProblemInstance. In addition we store the travel times as dictionary of a timestamp and the travel time matrix. We also specify a method for determining the travel time between two cities for a specific time.

public interface ITimeDependentProblemInstance : IVRPProblemInstance {
  ItemDictionary<IntValue, DoubleMatrix> TravelTimes { get; }
  double GetTravelTime(double time, int x, int y);
}

To implement the TimeDependentProblemInstance in HeuristicLab you have to add specific code for cloning and persistence.

[Item("TimeDependentProblemInstance", "Represents a time dependant CVRPTW instance.")]
[StorableClass]
public class TimeDependentProblemInstance
  : CVRPTWProblemInstance, ITimeDependentProblemInstance {
   
  [StorableConstructor]
  protected TimeDependentProblemInstance(bool deserializing) : base(deserializing) { }
 
  public override IDeepCloneable Clone(Cloner cloner) {
    return new TimeDependentProblemInstance(this, cloner);
  }
 
  protected TimeDependentProblemInstance(TimeDependentProblemInstance original, Cloner cloner)
    : base(original, cloner) {
    AttachEventHandlers();
  }
 
  [StorableHook(HookType.AfterDeserialization)]
  private void AfterDeserialization() {
    AttachEventHandlers();
  }
}

To store the dictionary of timestamps and travel time matrices we use a ValueParameter. Furthermore we need to register an event handler to the parameter. If the travel times change we have to re-evaluate our known solution. To link the new VRPProblemInstance to a new VRPEvaluator we have to override the Evaluator property and return our new TimeDependentVRPEvaluator.

public class TimeDependentProblemInstance
  : CVRPTWProblemInstance, ITimeDependentProblemInstance {

  protected IValueParameter<ItemDictionary<IntValue, DoubleMatrix>> TravelTimesParameter {
    get { return (IValueParameter<ItemDictionary<IntValue, DoubleMatrix>>)Parameters["TravelTimes"]; }
  }

  public ItemDictionary<IntValue, DoubleMatrix> TravelTimes {
    get { return TravelTimesParameter.Value; }
    set { TravelTimesParameter.Value = value; }
  }

  public TimeDependentProblemInstance() {
    Parameters.Add(new ValueParameter<ItemDictionary<IntValue, DoubleMatrix>>("TravelTimes", "The time dependent travel times.",
      new ItemDictionary<IntValue, DoubleMatrix>()));

    AttachEventHandlers();
  }

  private void AttachEventHandlers() {
    TravelTimesParameter.ValueChanged += TravelTimesParameterOnValueChanged;
  }

  private void TravelTimesParameterOnValueChanged(object sender, EventArgs eventArgs) {
    EvalBestKnownSolution();
  }

  protected override IVRPEvaluator Evaluator {
    get { return new TimeDependentVRPEvaluator(); }
  }
}

The GetTravelTime method is used for determining the travel time between two cities for a given time by first determining the timestamp key for the dictionary. This is done by finding the highest timestamp in the keys that is smaller than the given time.

public double GetTravelTime(double time, int x, int y) {
  double travelTime = 1;
 
  if (TravelTimes != null) {
    var sortedKeys = TravelTimes.Keys.OrderBy(k => k.Value).ToList();
    int i = 0;
    IntValue key = null;
 
    while (i < sortedKeys.Count && sortedKeys[i].Value <= time) {
      key = sortedKeys[i];
      i++;
    }
 
    if (key != null)
      travelTime = TravelTimes[key][x, y];
  }
 
  return travelTime;
}

Implement new Evaluator

EvaluateTour

GetTourInsertionCosts

Read, provide and interpret Data

Parser

InstanceProvider

Interpreter

Result