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


Ignore:
Timestamp:
02/20/14 10:45:38 (6 years ago)
Author:
pfleck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPEncoding

    v1 v2  
    4949= Implementing new Encoding =
    5050
     51The first thing to do is to create the new encoding. If you want to implement a whole new encoding, you start by deriving from {{{TourEncoding}}}. Then you have to store the assignments vehicles to tours as well as additional data, like our ''tour delimiters'' for the ''multi trip VRP''. In the case of this tutorial we derive from the existing {{{PotvinEncoding}}} which stores the vehicle assignments already.
     52
     53{{{
     54#!cs
     55[Item("MultiTripEncoding", "Represents a potvin encoding of VRP solutions adapted for multi trip VRPs.")]
     56[StorableClass]
     57public class MultiTripEncoding
     58  : PotvinEncoding {
     59 
     60  [StorableConstructor]
     61  protected MultiTripEncoding(bool serializing)
     62    : base(serializing) {
     63  }
     64 
     65  public override IDeepCloneable Clone(Cloner cloner) {
     66    return new MultiTripEncoding(this, cloner);
     67  }
     68 
     69  [StorableHook(HookType.AfterDeserialization)]
     70  private void AfterDeserialization() {
     71    AttachEventHandlers();
     72  }
     73}
     74}}}
     75
     76To implement the multi trip VRP we need to store when a tour is interrupted and the vehicle drives back to the depot. We store this information in a {{{List<list<bool>>}}} which indicates whether the tour is interrupted after the stop or not. A more compact possibility is to store the delimiters as bit in an integer, but then you are limited by the size of an integer (32 bit).
     77
     78{{{
     79#!cs
     80[Storable]
     81public List<List<bool>> TripDelimiters { get; private set; }
     82 
     83public MultiTripEncoding(IVRPProblemInstance instance)
     84  : base(instance) {
     85  TripDelimiters = new List<List<bool>>();
     86  AttachEventHandlers();
     87}
     88
     89protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
     90  : base(original, cloner) {
     91  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
     92  foreach (var delimiters in original.TripDelimiters) {
     93    TripDelimiters.Add(new List<bool>(delimiters));
     94  }
     95}
     96
     97protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
     98  : base(original, cloner) {
     99  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
     100  foreach (var delimiters in original.TripDelimiters) {
     101    TripDelimiters.Add(new List<bool>(delimiters));
     102  }
     103}
     104}}}
     105
     106In order to keep the delimiters synchronized with the actual tours we need to register event handlers on the {{{Tours}}} collection. When a tour is added or removed we also have to add or remove the delimiters.
     107
     108{{{
     109#!cs
     110private void AttachEventHandlers() {
     111  Tours.ItemsAdded += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsAdded);
     112  Tours.ItemsRemoved += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsRemoved);
     113}
     114 
     115void Tours_ItemsAdded(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
     116  foreach (var added in e.Items.Except(e.OldItems).OrderBy(x => x.Index)) {
     117    TripDelimiters.Insert(added.Index, new List<bool>());
     118  }
     119}
     120 
     121void Tours_ItemsRemoved(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
     122  foreach (var removed in e.OldItems.Except(e.Items).OrderByDescending(x => x.Index)) {
     123    TripDelimiters.RemoveAt(removed.Index);
     124  }
     125}
     126}}}
     127
     128In addition we implement a method for retrieving the delimiters for a tour as array, and to flip a delimiter on specific position in a tour. These methods are used for the {{{VRPOperators}}} and the {{{VRPEvaluator}}} later. We also specify a method for converting an existing {{{PotvinEncoding}}} and new delimiters to a new {{{MultiTripEncoding}}}.
     129
     130{{{
     131#!cs
     132public bool[] GetDelimiters(int tour) {
     133  if (tour < TripDelimiters.Count) {
     134    return TripDelimiters[tour].ToArray();
     135  } else {
     136    return new bool[0];
     137  }
     138}
     139 
     140public void FlipDelimiter(int tour, int index) {
     141  if (tour < TripDelimiters.Count) {
     142    if (TripDelimiters[tour].Count <= index) {
     143      for (int i = TripDelimiters[tour].Count; i <= index; i++) {
     144        TripDelimiters[tour].Add(false);
     145      }
     146    }
     147 
     148    TripDelimiters[tour][index] = !TripDelimiters[tour][index];
     149  }
     150}
     151
     152public static MultiTripEncoding ConvertFrom(IVRPProblemInstance instance, PotvinEncoding orig, List<List<bool>> tripDelimiters = null) {
     153  MultiTripEncoding result = new MultiTripEncoding(instance);
     154 
     155  result.Tours.AddRange(orig.Tours);
     156  for (int i = 0; i < result.Tours.Count; i++) {
     157    result.VehicleAssignment[i] = orig.VehicleAssignment[i];
     158  }
     159 
     160  if (tripDelimiters != null)
     161    result.TripDelimiters = tripDelimiters;
     162 
     163  return result;
     164}
     165}}}
     166
    51167= Sample Foundations =
     168
     169In order to implement the sample we need a new {{{ProblemInstance}}} and a new {{{Evaluator}}} for the '''MultiTrip VRP''' variant. For detailed information about creating new {{{VRPInstances}}} and {{{VRPEvaluators}}} see [wiki:UsersHowtosImplementANewVRPProblemInstance How to ... implement a new VRP ProblemInstance] and [wiki:UsersHowtosImplementANewVRPEvaluator How to ... implement a new VRP Evaluator].
     170
    52171== MultiTripVRPInstance ==
     172
     173The {{{MultiTripVRPInstance}}} only needs to store the additional {{{MaxDistance}}} parameter for the vehicle as well as the penalty for exceeding it.
     174
     175{{{
     176#!cs
     177public interface IMultiTripProblemInstance {
     178  DoubleValue MaxDistance { get; set; }
     179  DoubleValue MaxDistancePenalty { get; set; }
     180}
     181}}}
     182
     183For the implementation the usual HL specific cloning and persistence code is necessary.
     184
     185{{{
     186#!cs
     187[Item("MultiTripVRPInstance", "Represents a single depot multi trip CVRP instance.")]
     188[StorableClass]
     189public class MultiTripVRPInstance : CVRPProblemInstance, IMultiTripProblemInstance {
     190  protected IValueParameter<DoubleValue> MaxDistanceParameter {
     191    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistance"]; }
     192  }
     193 
     194  public DoubleValue MaxDistance {
     195    get { return MaxDistanceParameter.Value; }
     196    set { MaxDistanceParameter.Value = value; }
     197  }
     198 
     199  protected IValueParameter<DoubleValue> MaxDistancePenaltyParameter {
     200    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistancePenalty"]; }
     201  }
     202 
     203  public DoubleValue MaxDistancePenalty {
     204    get { return MaxDistancePenaltyParameter.Value; }
     205    set { MaxDistancePenaltyParameter.Value = value; }
     206  }
     207 
     208  [StorableConstructor]
     209  protected MultiTripVRPInstance(bool deserializing) : base(deserializing) { }
     210 
     211  public MultiTripVRPInstance() {
     212    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistance", "The max distance of each vehicle.", new DoubleValue(100)));
     213    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistancePenalty", "The distance penalty considered in the evaluation.", new DoubleValue(100)));
     214 
     215    AttachEventHandlers();
     216  }
     217 
     218  public override IDeepCloneable Clone(Cloner cloner) {
     219    return new MultiTripVRPInstance(this, cloner);
     220  }
     221 
     222  protected MultiTripVRPInstance(MultiTripVRPInstance original, Cloner cloner)
     223    : base(original, cloner) {
     224    AttachEventHandlers();
     225  }
     226 
     227  [StorableHook(HookType.AfterDeserialization)]
     228  private void AfterDeserialization() {
     229    AttachEventHandlers();
     230  }
     231 
     232  private void AttachEventHandlers() {
     233    MaxDistanceParameter.ValueChanged += new EventHandler(MaxDistanceParameter_ValueChanged);
     234    MaxDistancePenaltyParameter.ValueChanged += new EventHandler(MaxDistancePenaltyParameter_ValueChanged);
     235  }
     236 
     237  void MaxDistancePenaltyParameter_ValueChanged(object sender, EventArgs e) {
     238    MaxDistancePenaltyParameter.Value.ValueChanged += new EventHandler(ValueChanged);
     239    EvalBestKnownSolution();
     240  }
     241 
     242  void MaxDistanceParameter_ValueChanged(object sender, EventArgs e) {
     243    MaxDistanceParameter.Value.ValueChanged += new EventHandler(ValueChanged);
     244    EvalBestKnownSolution();
     245  }
     246 
     247  void ValueChanged(object sender, EventArgs e) {
     248    EvalBestKnownSolution();
     249  }
     250 }
     251}}}
     252
     253We will override more methods in the {{{MultiTripProblemInstance}}} class when we deal with '''operators''' in this tutorial later.
     254
    53255== MultiTripEvaluator ==
     256
     257For the evaluator we copy the {{{CVRPEvaluator}}} and modify it. Now we consider the travel distance after a stopover on the depot and calculate the maximum distance violation.
     258
     259{{{
     260#!cs
     261public class MultiTripEvaluation : CVRPEvaluation {
     262  public double MaxDistanceViolation { get; set; }
     263}
     264 
     265[Item("MultiTripEvaluator", "Represents a single depot CVRP evaluator with multiple trips.")]
     266[StorableClass]
     267public class MultiTripEvaluator : CVRPEvaluator {
     268  public ILookupParameter<DoubleValue> MaxDistanceViolationParameter {
     269    get { return (ILookupParameter<DoubleValue>)Parameters["MaxDistanceViolation"]; }
     270  }
     271 
     272  protected override VRPEvaluation CreateTourEvaluation() {
     273    return new MultiTripEvaluation();
     274  }
     275 
     276  protected override void InitResultParameters() {
     277    base.InitResultParameters();
     278 
     279    MaxDistanceViolationParameter.ActualValue = new DoubleValue(0);
     280  }
     281 
     282  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
     283    base.SetResultParameters(tourEvaluation);
     284 
     285    MaxDistanceViolationParameter.ActualValue.Value = (tourEvaluation as MultiTripEvaluation).MaxDistanceViolation;
     286  }
     287 
     288  [StorableConstructor]
     289  protected MultiTripEvaluator(bool deserializing) : base(deserializing) { }
     290 
     291  public MultiTripEvaluator() {
     292    Parameters.Add(new LookupParameter<DoubleValue>("MaxDistanceViolation", "The distance violation."));
     293  }
     294 
     295  public override IDeepCloneable Clone(Cloner cloner) {
     296    return new MultiTripEvaluator(this, cloner);
     297  }
     298 
     299  protected MultiTripEvaluator(MultiTripEvaluator original, Cloner cloner)
     300    : base(original, cloner) {
     301  }
     302}
     303}}}
     304
     305In the evaluation process we need to consider the additional travel distance after a vehicle drives back to the depot. Therefore we add the distance from the current stop to the depot and the distance between the depot and the next stop instead of the direct distance.
     306
     307After a tour we have to check the maximum driven distance whether it exceeds the maximum driven distance of a vehicle or not. In case of a violation of the limit we increment the penalty.
     308
     309{{{
     310#!cs
     311protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
     312  TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour))); ;
     313  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     314  double originalQuality = eval.Quality;
     315 
     316  IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
     317  MultiTripVRPInstance multiTripInstance = instance as MultiTripVRPInstance;
     318  DoubleArray demand = instance.Demand;
     319 
     320  double overweight = 0.0;
     321  double distance = 0.0;
     322 
     323  double capacity = cvrpInstance.Capacity.Value;
     324  double spareCapacity = capacity;
     325 
     326  var tripDelimiters = new bool[0];
     327  if(solution is MultiTripEncoding)
     328    tripDelimiters = ((MultiTripEncoding)solution).GetDelimiters(solution.GetTourIndex(tour));
     329 
     330  //simulate a tour, start and end at depot
     331  for (int i = 0; i <= tour.Stops.Count; i++) {
     332    int start = 0;
     333    if (i > 0)
     334      start = tour.Stops[i - 1];
     335    int end = 0;
     336    if (i < tour.Stops.Count)
     337      end = tour.Stops[i];
     338 
     339    //drive there
     340    double currentDistace = 0;
     341 
     342    if (i > 0 && tripDelimiters.Length >= i && tripDelimiters[i - 1]) {
     343      currentDistace += instance.GetDistance(start, 0, solution);
     344      currentDistace += instance.GetDistance(0, end, solution);
     345 
     346      spareCapacity = capacity;
     347    } else {
     348      currentDistace += instance.GetDistance(start, end, solution);
     349    }
     350    distance += currentDistace;
     351 
     352    spareCapacity -= demand[end];
     353    if (spareCapacity < 0) {
     354      overweight += -spareCapacity;
     355      spareCapacity = 0;
     356    }
     357 
     358    CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
     359    tourInfo.AddStopInsertionInfo(stopInfo);
     360  }
     361 
     362  eval.Quality += instance.FleetUsageFactor.Value;
     363  eval.Quality += instance.DistanceFactor.Value * distance;
     364 
     365  eval.Distance += distance;
     366  eval.VehicleUtilization += 1;
     367 
     368  (eval as CVRPEvaluation).Overload += overweight;
     369  double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
     370  eval.Penalty += penalty;
     371  eval.Quality += penalty;
     372  tourInfo.Penalty = penalty;
     373  tourInfo.Quality = eval.Quality - originalQuality;
     374 
     375  if (distance > multiTripInstance.MaxDistance.Value) {
     376    double maxDistanceViolation = (distance - (multiTripInstance.MaxDistance.Value));
     377    penalty = maxDistanceViolation * multiTripInstance.MaxDistancePenalty.Value;
     378    eval.Penalty += penalty;
     379    eval.Quality += penalty;
     380    (eval as MultiTripEvaluation).MaxDistanceViolation += maxDistanceViolation;
     381  }
     382}
     383}}}
     384
     385Because the increment based implementation is not trivial and not topic of this tutorial, we evaluate the tour at whole and calculate the distance to the previous solution.
     386
     387{{{
     388#!cs
     389protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
     390  out bool feasible) {
     391    if (!(solution is MultiTripEncoding)) {
     392      return base.GetTourInsertionCosts(instance, solution, tourInsertionInfo, index, customer, out feasible);
     393    } else {
     394      MultiTripEncoding individual = (solution as MultiTripEncoding);
     395 
     396      int tourIdx = -1;
     397      for (int i = 0; i < individual.Tours.Count; i++) {
     398        if (solution.GetVehicleAssignment(i) == tourInsertionInfo.Vehicle)
     399          tourIdx = i;
     400      }
     401      Tour tour = individual.Tours[tourIdx];
     402 
     403      tour.Stops.Insert(index, customer);
     404      VRPEvaluation newEval = instance.EvaluateTour(tour, individual);
     405      tour.Stops.RemoveAt(index);
     406 
     407      feasible = instance.Feasible(newEval);
     408      return newEval.Quality - tourInsertionInfo.Quality;
     409    }
     410}
     411}}}
    54412
    55413= Implementing new Operators =