Changes between Version 1 and Version 2 of Documentation/Howto/ImplementANewVRPProblemInstance

Timestamp:

02/13/14 13:07:02 (11 years ago)

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPProblemInstance

@@ -10 +10 @@
 
 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 =