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


Ignore:
Timestamp:
02/13/14 13:07:02 (8 years ago)
Author:
pfleck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPProblemInstance

    v1 v2  
    1010
    1111After 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.
     12
     13== The Time Dependent Vehicle Routing Problem ==
     14
     15To 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.
     16
     17In 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]).
     18
     19[[Image(1_TDVRP_travel_time, 700px)]]
     20
     21In 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.
     22
     23== Prerequisites ==
     24
     25Before 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)].
     26
     27Your plugin need an additional dependency onto the {{{HeuristicLab.Problems.VehicleRouting}}} and the {{{HeuristicLab.Problems.Instances.VehicleRouting}}} plugin. The plugin should look like this:
     28{{{
     29#!cs
     30[Plugin("HeuristicLab.TimeDependentVRP", "1.0.0.0")]
     31[PluginFile("HeuristicLab.TimeDependentVRP.dll", PluginFileType.Assembly)]
     32[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
     33[PluginDependency("HeuristicLab.Problems.Instances.VehicleRouting", "3.4")]
     34public class TimeDependentVRPPlugin : PluginBase {
     35}
     36}}}
     37
     38In addition you will need references onto following HeuristicLab assemblies:
     39 - HeuristicLab.Collections
     40 - HeuristicLab.Common
     41 - HeuristicLab.Core
     42 - HeuristicLab.Data
     43 - HeuristicLab.Operators
     44 - HeuristicLab.Optimization
     45 - HeuristicLab.Parameters
     46 - HeuristicLab.Persistence
     47 - '''HeuristicLab.Problems.VehicleRouting'''
     48 - '''HeuristicLab.Problems.Instances'''
     49 - '''HeuristicLab.Problems.Instances.VehicleRouting'''
     50
     51= ProblemInstance =
     52
     53== Foundations ==
     54
     55A {{{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.
     56
     57A {{{VRPEvaluator}}} uses the {{{VRPProblemInstance}}} and a ''solution candidate'' for the {{{VRPProblemInstance}}} to evaluate the ''solution candidate''.
     58
     59[[Image(2_TDVRP_ProblemInstance_simple, 700px)]]
     60
     61HeuristicLab 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.
     62
     63== Extending ProblemInstance and Evaluator ==
     64
     65To 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.
     66
     67[[Image(3_TDVRP_ProblemInstance_full, 800px)]]
     68
     69== Implement new ProblemInstance ==
     70
     71The 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.
     72
     73{{{
     74#!cs
     75public interface ITimeDependentProblemInstance : IVRPProblemInstance {
     76  ItemDictionary<IntValue, DoubleMatrix> TravelTimes { get; }
     77  double GetTravelTime(double time, int x, int y);
     78}
     79}}}
     80
     81To implement the {{{TimeDependentProblemInstance}}} in HeuristicLab you have to add specific code for cloning and persistence.
     82
     83{{{
     84#!cs
     85[Item("TimeDependentProblemInstance", "Represents a time dependant CVRPTW instance.")]
     86[StorableClass]
     87public class TimeDependentProblemInstance
     88  : CVRPTWProblemInstance, ITimeDependentProblemInstance {
     89   
     90  [StorableConstructor]
     91  protected TimeDependentProblemInstance(bool deserializing) : base(deserializing) { }
     92 
     93  public override IDeepCloneable Clone(Cloner cloner) {
     94    return new TimeDependentProblemInstance(this, cloner);
     95  }
     96 
     97  protected TimeDependentProblemInstance(TimeDependentProblemInstance original, Cloner cloner)
     98    : base(original, cloner) {
     99    AttachEventHandlers();
     100  }
     101 
     102  [StorableHook(HookType.AfterDeserialization)]
     103  private void AfterDeserialization() {
     104    AttachEventHandlers();
     105  }
     106}
     107}}}
     108
     109To 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}}}.
     110
     111{{{
     112#!cs
     113public class TimeDependentProblemInstance
     114  : CVRPTWProblemInstance, ITimeDependentProblemInstance {
     115
     116  protected IValueParameter<ItemDictionary<IntValue, DoubleMatrix>> TravelTimesParameter {
     117    get { return (IValueParameter<ItemDictionary<IntValue, DoubleMatrix>>)Parameters["TravelTimes"]; }
     118  }
     119
     120  public ItemDictionary<IntValue, DoubleMatrix> TravelTimes {
     121    get { return TravelTimesParameter.Value; }
     122    set { TravelTimesParameter.Value = value; }
     123  }
     124
     125  public TimeDependentProblemInstance() {
     126    Parameters.Add(new ValueParameter<ItemDictionary<IntValue, DoubleMatrix>>("TravelTimes", "The time dependent travel times.",
     127      new ItemDictionary<IntValue, DoubleMatrix>()));
     128
     129    AttachEventHandlers();
     130  }
     131
     132  private void AttachEventHandlers() {
     133    TravelTimesParameter.ValueChanged += TravelTimesParameterOnValueChanged;
     134  }
     135
     136  private void TravelTimesParameterOnValueChanged(object sender, EventArgs eventArgs) {
     137    EvalBestKnownSolution();
     138  }
     139
     140  protected override IVRPEvaluator Evaluator {
     141    get { return new TimeDependentVRPEvaluator(); }
     142  }
     143}
     144}}}
     145
     146The {{{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.
     147
     148{{{
     149#!cs
     150public double GetTravelTime(double time, int x, int y) {
     151  double travelTime = 1;
     152 
     153  if (TravelTimes != null) {
     154    var sortedKeys = TravelTimes.Keys.OrderBy(k => k.Value).ToList();
     155    int i = 0;
     156    IntValue key = null;
     157 
     158    while (i < sortedKeys.Count && sortedKeys[i].Value <= time) {
     159      key = sortedKeys[i];
     160      i++;
     161    }
     162 
     163    if (key != null)
     164      travelTime = TravelTimes[key][x, y];
     165  }
     166 
     167  return travelTime;
     168}
     169}}}
     170
     171== Implement new Evaluator ==
     172
     173=== EvaluateTour ===
     174
     175=== GetTourInsertionCosts ===
     176
     177= Read, provide and interpret Data =
     178
     179== Parser ==
     180
     181== InstanceProvider ==
     182
     183== Interpreter ==
     184
     185= Result =