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 [wiki:UsersHowtosImplementANewVRPEvaluator 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 [http://www.sciencedirect.com/science/article/pii/S0305054804000887 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 ([http://www.sciencedirect.com/science/article/pii/S0305054804000887 source]).

[[Image(1_TDVRP_travel_time, 700px)]]

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 [wiki:UsersHowtosImplementPluginsStepByStep 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:
{{{
#!cs
[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''.

[[Image(2_TDVRP_ProblemInstance_simple, 700px)]]

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.

[[Image(3_TDVRP_ProblemInstance_full, 800px)]]

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

{{{
#!cs
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. 

{{{
#!cs
[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}}}.

{{{
#!cs
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.

{{{
#!cs
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 =