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


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

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPProblemInstance

    v2 v3  
    1717In 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]).
    1818
    19 [[Image(1_TDVRP_travel_time, 700px)]]
     19[[Image(1_TDVRP_travel_time.png, 600px)]]
    2020
    2121In 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.
     
    5757A {{{VRPEvaluator}}} uses the {{{VRPProblemInstance}}} and a ''solution candidate'' for the {{{VRPProblemInstance}}} to evaluate the ''solution candidate''.
    5858
    59 [[Image(2_TDVRP_ProblemInstance_simple, 700px)]]
     59[[Image(2_TDVRP_ProblemInstance_simple.png, 700px)]]
    6060
    6161HeuristicLab 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.
     
    6565To 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.
    6666
    67 [[Image(3_TDVRP_ProblemInstance_full, 800px)]]
     67[[Image(3_TDVRP_ProblemInstance_full.png, 800px)]]
    6868
    6969== Implement new ProblemInstance ==
     
    171171== Implement new Evaluator ==
    172172
     173In order to make use of the travel time a new {{{VRPEvaluator}}} is necessary. For detailed information about how to implement a new VRP Evaluator, see [wiki:UsersHowtosImplementANewVRPEvaluator How to ... implement a new VRP Evaluator]. As we derived from {{{CVRPTWProblemInstance}}} for the new {{{TimeDependentProblemIntance}}}, we now derive the {{{TimeDependentVRPEvaluator}}} from the existing {{{CVRPTWEvaluator}}}.
     174
     175{{{
     176#!cs
     177[Item("TimeDependentVRPEvaluator", "Represents a time dependent VRP evaluator.")]
     178[StorableClass]
     179public class TimeDependentVRPEvaluator
     180  : CVRPTWEvaluator {
     181
     182  [StorableConstructor]
     183  protected TimeDependentVRPEvaluator(bool deserializing) : base(deserializing) { }
     184 
     185  public TimeDependentVRPEvaluator() {
     186  }
     187 
     188  public override IDeepCloneable Clone(Cloner cloner) {
     189    return new TimeDependentVRPEvaluator(this, cloner);
     190  }
     191 
     192  protected TimeDependentVRPEvaluator(TimeDependentVRPEvaluator original, Cloner cloner)
     193    : base(original, cloner) {
     194  }
     195}
     196}}}
     197
    173198=== EvaluateTour ===
     199Note: Because the evaluator is called very frequently in the optimization progress, the performance is critical. Therefore the design favors speed over proper architecture and code duplication is accepted.
     200
     201For the {{{EvaluateTour}}} method we copy the existing implementation from the base class. The only thing we need to do is to multiply the driven distance with the ''travel time''. This is done by following changes in the method. First get the {{{TimeDependentProblemInstance}}} in the beginning of the method by casting the available problem instance.
     202{{{
     203#!cs
     204ITimeDependentProblemInstance ttvrp = instance as ITimeDependentProblemInstance;
     205}}}
     206In the center of the method change the line
     207{{{
     208#!cs
     209double currentDistace = vrptw.GetDistance(start, end, solution);
     210}}}
     211to
     212{{{
     213#!cs
     214double currentDistace = vrptw.GetDistance(start, end, solution) * ttvrp.GetTravelTime(time, start, end);
     215}}}
     216
     217After these changes the travel time is applied to every driven distance.
    174218
    175219=== GetTourInsertionCosts ===
    176220
     221Unfortunately the increment based evaluation is trickier than the evaluation of a whole tour. Because the insertion of a stop can cause different travel times for the following stops the existing implementation cannot be used directly.
     222
     223For simplicity and reducing the scope of this tutorial we evaluate the whole tour and calculate the quality difference. Of course this is increases the runtime drastically, but we want to focus on other topics in this tutorial.
     224
     225{{{
     226#!cs
     227protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible) {
     228  TourEncoding individual = null;
     229  if (solution is TourEncoding)
     230    individual = solution as TourEncoding;
     231  else {
     232    individual = PotvinEncoding.ConvertFrom(solution, instance);
     233  }
     234 
     235  int tourIdx = -1;
     236  for (int i = 0; i < individual.Tours.Count; i++) {
     237    if (solution.GetVehicleAssignment(i) == tourInsertionInfo.Vehicle)
     238      tourIdx = i;
     239  }
     240  Tour tour = individual.Tours[tourIdx];
     241 
     242  tour.Stops.Insert(index, customer);
     243  VRPEvaluation newEval = instance.EvaluateTour(tour, individual);
     244  tour.Stops.RemoveAt(index);
     245 
     246  feasible = instance.Feasible(newEval);
     247  return newEval.Quality - tourInsertionInfo.Quality;
     248}
     249}}}
     250
    177251= Read, provide and interpret Data =
    178252
     253After the previous section we can use the new problem instances of the {{{Time Dependent VRP}}} variant and evaluate them. However, we need to create the problem instances first. For a brief overview the following sequence diagram shows how the data flows between the different components in the creation process. For simplicity more complex HeuristicLab components are abstracted.
     254
     255[[Image(4_TDVRP_DataFlow.png, 600px)]]
     256
    179257== Parser ==
    180258
     259The first step is to read all relevant data from a file. Our parser is based on the existing {{{SolomonParser}}}. Unfortunately the parser is not designed for reusability, therefore we have to copy the implementation and modify it.
     260
     261First, we create a new class {{{TimeDependentParser}}} and copy the fields and methods from the {{{SolomonParser}}}. Then we add our new data, the '' travel times'', to the class.
     262
     263{{{
     264#!cs
     265//new data
     266private Dictionary<int, double[,]> travelTimes;
     267public Dictionary<int, double[,]> TravelTimes {
     268  get {
     269    return travelTimes;
     270  }
     271}
     272}}}
     273
     274{{{
     275#!cs
     276public TimeDependentParser() {
     277  ...
     278 
     279  travelTimes = new Dictionary<int, double[,]>();
     280}
     281}}}
     282
     283In the parse method we additionally have to read all values from the travel time matrices and store them in the dictionary.
     284
     285{{{
     286#!cs
     287public void Parse() {
     288    ...
     289
     290    // read matrices
     291    while (line != null) {
     292      if (line == "TIME MATRIX") {
     293        line = reader.ReadLine();
     294        int time = int.Parse(line);
     295        travelTimes[time] = new double[cities, cities];
     296        for (int i = 0; i < cities; i++) {
     297          line = reader.ReadLine();
     298          string[] tokens = line.Split('\t');
     299          for (int j = 0; j < cities; j++) {
     300            travelTimes[time][i, j] = double.Parse(tokens[j], CultureInfo.InvariantCulture);
     301          }
     302        }
     303      }
     304 
     305      line = reader.ReadLine();
     306    }
     307  }
     308}
     309}}}
     310
    181311== InstanceProvider ==
    182312
     313To provide a problem with a problem instance, HeuristicLab uses a {{{ProblemInstanceProvider}}}. A {{{ProblemInstanceProvider}}} specifies methods for loading the problem instance data from a source (a {{{Stream}}} or {{{File}}}) or provides problem instances by itself (from a preconfigured data store). The loading procedure from a file is handled by our {{{TimeDependentParser}}} from the previous section; we simply have to call it.
     314
     315The {{{InstanceProvider}}} returns problem unspecific data because some data can be imported from different problems. For example the traveling salesman data can be imported by the ''traveling salesman problem'' and the ''quadratic assignment problem''. For the problem unspecific data we create a {{{TimeDependentData}}} which derives from the existing {{{CVRPTWData}}} and add the dictionary with the timestamps and travel times.
     316
     317{{{
     318#!
     319public class TimeDependentData : CVRPTWData {
     320  public Dictionary<int, double[,]> TravelTimes { get; set; }
     321}
     322}}}
     323
     324An abstract implementation of the {{{ProblemInstanceProvider}}} for VRP is the {{{VRPInstanceProvider}}. We only have to override certain methods for the data import. The {{{ImportData}}} and {{{LoadData}}} method both use the {{{TimeDependentParser}}} to parse the file. First we create a new {{{TimeDependentInstanceProvider}}} class which derives from the existing {{{VRPInstanceProvider}}} and override a few methods. In the {{{LoadInstance}}} method we call the parser and copy the loaded values from the parser to the {{{TimeDependentData}}} object.
     325
     326{{{
     327#!cs
     328public class TimeDependentInstanceProvider
     329  : VRPInstanceProvider {
     330
     331  public override string Name {
     332    get { return "Time Dependent VRP"; }
     333  }
     334 
     335  public override string Description {
     336    get { return "Benchmark test set"; }
     337  }
     338 
     339  public override Uri WebLink {
     340    get { return null; }
     341  }
     342 
     343  public override string ReferencePublication {
     344    get { return string.Empty; }
     345  }
     346 
     347  protected override string FileName {
     348    get { return "TDVRP"; }
     349  }
     350 
     351  public override bool CanImportData {
     352    get { return true; }
     353  }
     354 
     355  public override VRPData ImportData(string path) {
     356    return LoadInstance(new TimeDependentParser(path));
     357  }
     358 
     359 
     360  protected override VRPData LoadData(Stream stream) {
     361    return LoadInstance(new TimeDependentParser(stream));
     362  }
     363 
     364  private TimeDependentData LoadInstance(TimeDependentParser parser) {
     365    parser.Parse();
     366 
     367    var instance = new TimeDependentData {
     368      Dimension = parser.Cities + 1,
     369      Coordinates = parser.Coordinates,
     370      Capacity = parser.Capacity,
     371      Demands = parser.Demands,
     372      DistanceMeasure = DistanceMeasure.Euclidean,
     373      ReadyTimes = parser.Readytimes,
     374      ServiceTimes = parser.Servicetimes,
     375      DueTimes = parser.Duetimes,
     376      MaximumVehicles = parser.Vehicles,
     377      Name = parser.ProblemName,
     378      TravelTimes = parser.TravelTimes
     379    };
     380 
     381    return instance;
     382  }
     383}
     384}}}
     385
    183386== Interpreter ==
    184387
     388To link the problem neutral data to the problem specific instance a {{{ProblemInstanceConsumer}}} is used. The {{{VehicleRoutingProblem}}} itself is a consumer of {{{VRPData}}} and specifies a {{{Load}}} method. To determine which problem specific instance has to be created, a lookup for a {{{VRPDataInterpreter}}} is performed. The {{{VRPDataInterpreter}}} is then responsible for transferring the problem independent data to the problem specific instance.
     389
     390For the Time Dependent VRP variant we create a {{{TimeDependentInterpreter}}} which derives from the {{{CVRPTWInterpreter}}}. The {{{Interpret}}} method first calls the implementation from the base class to copy the CVRPTW data and copy the travel times to the problem instance itself.
     391
     392{{{
     393#!cs
     394class TimeDependentInterpreter : CVRPTWInterpreter, IVRPDataInterpreter<TimeDependentData> {
     395  protected override IVRPProblemInstance CreateProblemInstance() {
     396    return new TimeDependentProblemInstance();
     397  }
     398 
     399  protected override void Interpret(IVRPData data, IVRPProblemInstance problemInstance) {
     400    base.Interpret(data, problemInstance);
     401 
     402    TimeDependentData ttData = (TimeDependentData)data;
     403    TimeDependentProblemInstance problem = (TimeDependentProblemInstance)problemInstance;
     404 
     405    var travelTimes = new ItemDictionary<IntValue, DoubleMatrix>();
     406 
     407    foreach (var key in ttData.TravelTimes.Keys) {
     408      travelTimes[new IntValue(key)] = new DoubleMatrix(ttData.TravelTimes[key]);
     409    }
     410 
     411    problem.TravelTimes = travelTimes;
     412  }
     413}
     414}}}
     415
    185416= Result =
     417
     418To load and start the time dependent VRP variant in HeuristicLab, we first need a valid file to load the {{{TimeDependentData}}} from. We use the data from the Solomon(CVRPTW) instance C101 and add the travel time matrices (dimension must match number of cities). For the travel times random values between 0.5 and 1.0 has been generated. The file should look like this:
     419
     420{{{
     421C101
     422
     423VEHICLE
     424NUMBER     CAPACITY
     425  25         200
     426
     427CUSTOMER
     428CUST NO.  XCOORD.   YCOORD.    DEMAND   READY TIME  DUE DATE   SERVICE   TIME
     429 
     430    0      40         50          0          0       1236          0   
     431    1      45         68         10        912        967         90   
     432    2      45         70         30        825        870         90   
     433    3      42         66         10         65        146         90   
     434    4      42         68         10        727        782         90   
     435...
     436
     437TIME MATRIX
     4380
     4390.925768957     0.520976414     0.562468007     0.750021875     0.61487113      ...
     4400.969856182     0.953186691     0.793840100     0.849949851     0.722734144     ...
     4410.686240672     0.770091988     0.76052254      0.943715274     0.831277119     ...
     4420.677805486     0.568948045     0.52780747      0.597541347     0.801783863     ...
     4430.890418577     0.827736775     0.596248865     0.900999375     0.913970905     ...
     444...
     445
     446
     447TIME MATRIX
     448200
     4490.705789629     0.57992851      0.567098964     0.607691814     0.726458799     ...
     4500.889918297     0.914455074     0.665679621     0.889941709     0.656366975     ...
     4510.647343773     0.526871001     0.94999237      0.82489978      0.591413065     ...
     4520.899079133     0.971614305     0.612777292     0.740562405     0.773627941     ...
     4530.519786836     0.914662095     0.905892404     0.963831082     0.598044971     ...
     454...
     455}}}
     456
     457We simply load the data by first opening one of the VRP samples, e.g. the ''Tabu Search – VRP'' sample. At the Library we choose our {{{TimeDependent VRP}}} implementation, and open our modified data file (c101_TT.txt from the attachments). In the Tabu Search Parameters tab we set the {{{MoveGenerator}}} to {{{PotvinPDShiftMultiMoveGenerator}}}. Optionally set the {{{SolutionCreator}}} to {{{PushForwardInsertionCreator}}} in the Problem tab. Finally run the algorithm.
     458
     459[[Image(5_TDVRP_Result.png, 500px)]]
     460
     461As you can see, the result differs slightly compared to the original version without time dependent travel times. Apparently the change is favorable because the travel time can be used optimal for the additional stops.