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

Timestamp:

02/20/14 10:45:38 (10 years ago)

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPEncoding

@@ -49 +49 @@
 = Implementing new Encoding =
 
+The 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.
+
+{{{
+#!cs
+[Item("MultiTripEncoding", "Represents a potvin encoding of VRP solutions adapted for multi trip VRPs.")]
+[StorableClass]
+public class MultiTripEncoding
+  : PotvinEncoding {
+ 
+  [StorableConstructor]
+  protected MultiTripEncoding(bool serializing)
+    : base(serializing) {
+  }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripEncoding(this, cloner);
+  }
+ 
+  [StorableHook(HookType.AfterDeserialization)]
+  private void AfterDeserialization() {
+    AttachEventHandlers();
+  }
+}
+}}}
+
+To 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). 
+
+{{{
+#!cs
+[Storable]
+public List<List<bool>> TripDelimiters { get; private set; }
+ 
+public MultiTripEncoding(IVRPProblemInstance instance)
+  : base(instance) {
+  TripDelimiters = new List<List<bool>>();
+  AttachEventHandlers();
+}
+
+protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
+  : base(original, cloner) {
+  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
+  foreach (var delimiters in original.TripDelimiters) {
+    TripDelimiters.Add(new List<bool>(delimiters));
+  }
+}
+
+protected MultiTripEncoding(MultiTripEncoding original, Cloner cloner)
+  : base(original, cloner) {
+  TripDelimiters = new List<List<bool>>(original.TripDelimiters.Count);
+  foreach (var delimiters in original.TripDelimiters) {
+    TripDelimiters.Add(new List<bool>(delimiters));
+  }
+}
+}}}
+
+In 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. 
+
+{{{
+#!cs
+private void AttachEventHandlers() {
+  Tours.ItemsAdded += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsAdded);
+  Tours.ItemsRemoved += new CollectionItemsChangedEventHandler<IndexedItem<Tour>>(Tours_ItemsRemoved);
+}
+ 
+void Tours_ItemsAdded(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
+  foreach (var added in e.Items.Except(e.OldItems).OrderBy(x => x.Index)) {
+    TripDelimiters.Insert(added.Index, new List<bool>());
+  }
+}
+ 
+void Tours_ItemsRemoved(object sender, CollectionItemsChangedEventArgs<IndexedItem<Tour>> e) {
+  foreach (var removed in e.OldItems.Except(e.Items).OrderByDescending(x => x.Index)) {
+    TripDelimiters.RemoveAt(removed.Index);
+  }
+}
+}}}
+
+In 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}}}. 
+
+{{{
+#!cs
+public bool[] GetDelimiters(int tour) {
+  if (tour < TripDelimiters.Count) {
+    return TripDelimiters[tour].ToArray();
+  } else {
+    return new bool[0];
+  }
+}
+ 
+public void FlipDelimiter(int tour, int index) {
+  if (tour < TripDelimiters.Count) {
+    if (TripDelimiters[tour].Count <= index) {
+      for (int i = TripDelimiters[tour].Count; i <= index; i++) {
+        TripDelimiters[tour].Add(false);
+      }
+    }
+ 
+    TripDelimiters[tour][index] = !TripDelimiters[tour][index];
+  }
+}
+
+public static MultiTripEncoding ConvertFrom(IVRPProblemInstance instance, PotvinEncoding orig, List<List<bool>> tripDelimiters = null) {
+  MultiTripEncoding result = new MultiTripEncoding(instance);
+ 
+  result.Tours.AddRange(orig.Tours);
+  for (int i = 0; i < result.Tours.Count; i++) {
+    result.VehicleAssignment[i] = orig.VehicleAssignment[i];
+  }
+ 
+  if (tripDelimiters != null)
+    result.TripDelimiters = tripDelimiters;
+ 
+  return result;
+}
+}}}
+
 = Sample Foundations =
+
+In 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].
+
 == MultiTripVRPInstance ==
+
+The {{{MultiTripVRPInstance}}} only needs to store the additional {{{MaxDistance}}} parameter for the vehicle as well as the penalty for exceeding it.
+
+{{{
+#!cs
+public interface IMultiTripProblemInstance {
+  DoubleValue MaxDistance { get; set; }
+  DoubleValue MaxDistancePenalty { get; set; }
+}
+}}}
+
+For the implementation the usual HL specific cloning and persistence code is necessary. 
+
+{{{
+#!cs
+[Item("MultiTripVRPInstance", "Represents a single depot multi trip CVRP instance.")]
+[StorableClass]
+public class MultiTripVRPInstance : CVRPProblemInstance, IMultiTripProblemInstance {
+  protected IValueParameter<DoubleValue> MaxDistanceParameter {
+    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistance"]; }
+  }
+ 
+  public DoubleValue MaxDistance {
+    get { return MaxDistanceParameter.Value; }
+    set { MaxDistanceParameter.Value = value; }
+  }
+ 
+  protected IValueParameter<DoubleValue> MaxDistancePenaltyParameter {
+    get { return (IValueParameter<DoubleValue>)Parameters["MaxDistancePenalty"]; }
+  }
+ 
+  public DoubleValue MaxDistancePenalty {
+    get { return MaxDistancePenaltyParameter.Value; }
+    set { MaxDistancePenaltyParameter.Value = value; }
+  }
+ 
+  [StorableConstructor]
+  protected MultiTripVRPInstance(bool deserializing) : base(deserializing) { }
+ 
+  public MultiTripVRPInstance() {
+    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistance", "The max distance of each vehicle.", new DoubleValue(100)));
+    Parameters.Add(new ValueParameter<DoubleValue>("MaxDistancePenalty", "The distance penalty considered in the evaluation.", new DoubleValue(100)));
+ 
+    AttachEventHandlers();
+  }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripVRPInstance(this, cloner);
+  }
+ 
+  protected MultiTripVRPInstance(MultiTripVRPInstance original, Cloner cloner)
+    : base(original, cloner) {
+    AttachEventHandlers();
+  }
+ 
+  [StorableHook(HookType.AfterDeserialization)]
+  private void AfterDeserialization() {
+    AttachEventHandlers();
+  }
+ 
+  private void AttachEventHandlers() {
+    MaxDistanceParameter.ValueChanged += new EventHandler(MaxDistanceParameter_ValueChanged);
+    MaxDistancePenaltyParameter.ValueChanged += new EventHandler(MaxDistancePenaltyParameter_ValueChanged);
+  }
+ 
+  void MaxDistancePenaltyParameter_ValueChanged(object sender, EventArgs e) {
+    MaxDistancePenaltyParameter.Value.ValueChanged += new EventHandler(ValueChanged);
+    EvalBestKnownSolution();
+  }
+ 
+  void MaxDistanceParameter_ValueChanged(object sender, EventArgs e) {
+    MaxDistanceParameter.Value.ValueChanged += new EventHandler(ValueChanged);
+    EvalBestKnownSolution();
+  }
+ 
+  void ValueChanged(object sender, EventArgs e) {
+    EvalBestKnownSolution();
+  }
+ }
+}}}
+
+We will override more methods in the {{{MultiTripProblemInstance}}} class when we deal with '''operators''' in this tutorial later.
+
 == MultiTripEvaluator ==
+
+For 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.
+
+{{{
+#!cs
+public class MultiTripEvaluation : CVRPEvaluation {
+  public double MaxDistanceViolation { get; set; }
+}
+ 
+[Item("MultiTripEvaluator", "Represents a single depot CVRP evaluator with multiple trips.")]
+[StorableClass]
+public class MultiTripEvaluator : CVRPEvaluator {
+  public ILookupParameter<DoubleValue> MaxDistanceViolationParameter {
+    get { return (ILookupParameter<DoubleValue>)Parameters["MaxDistanceViolation"]; }
+  }
+ 
+  protected override VRPEvaluation CreateTourEvaluation() {
+    return new MultiTripEvaluation();
+  }
+  
+  protected override void InitResultParameters() {
+    base.InitResultParameters();
+ 
+    MaxDistanceViolationParameter.ActualValue = new DoubleValue(0);
+  }
+ 
+  protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
+    base.SetResultParameters(tourEvaluation);
+ 
+    MaxDistanceViolationParameter.ActualValue.Value = (tourEvaluation as MultiTripEvaluation).MaxDistanceViolation;
+  }
+ 
+  [StorableConstructor]
+  protected MultiTripEvaluator(bool deserializing) : base(deserializing) { }
+ 
+  public MultiTripEvaluator() {
+    Parameters.Add(new LookupParameter<DoubleValue>("MaxDistanceViolation", "The distance violation."));
+  }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripEvaluator(this, cloner);
+  }
+ 
+  protected MultiTripEvaluator(MultiTripEvaluator original, Cloner cloner)
+    : base(original, cloner) {
+  }
+}
+}}}
+
+In 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.
+
+After 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.
+
+{{{
+#!cs
+protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
+  TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour))); ;
+  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+  double originalQuality = eval.Quality;
+ 
+  IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
+  MultiTripVRPInstance multiTripInstance = instance as MultiTripVRPInstance;
+  DoubleArray demand = instance.Demand;
+ 
+  double overweight = 0.0;
+  double distance = 0.0;
+ 
+  double capacity = cvrpInstance.Capacity.Value;
+  double spareCapacity = capacity;
+ 
+  var tripDelimiters = new bool[0];
+  if(solution is MultiTripEncoding)
+    tripDelimiters = ((MultiTripEncoding)solution).GetDelimiters(solution.GetTourIndex(tour));
+ 
+  //simulate a tour, start and end at depot
+  for (int i = 0; i <= tour.Stops.Count; i++) {
+    int start = 0;
+    if (i > 0)
+      start = tour.Stops[i - 1];
+    int end = 0;
+    if (i < tour.Stops.Count)
+      end = tour.Stops[i];
+ 
+    //drive there
+    double currentDistace = 0;
+ 
+    if (i > 0 && tripDelimiters.Length >= i && tripDelimiters[i - 1]) {
+      currentDistace += instance.GetDistance(start, 0, solution);
+      currentDistace += instance.GetDistance(0, end, solution);
+ 
+      spareCapacity = capacity;
+    } else {
+      currentDistace += instance.GetDistance(start, end, solution);
+    }
+    distance += currentDistace;
+ 
+    spareCapacity -= demand[end];
+    if (spareCapacity < 0) {
+      overweight += -spareCapacity;
+      spareCapacity = 0;
+    }
+ 
+    CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
+    tourInfo.AddStopInsertionInfo(stopInfo);
+  }
+ 
+  eval.Quality += instance.FleetUsageFactor.Value;
+  eval.Quality += instance.DistanceFactor.Value * distance;
+ 
+  eval.Distance += distance;
+  eval.VehicleUtilization += 1;
+ 
+  (eval as CVRPEvaluation).Overload += overweight;
+  double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
+  eval.Penalty += penalty;
+  eval.Quality += penalty;
+  tourInfo.Penalty = penalty;
+  tourInfo.Quality = eval.Quality - originalQuality;
+ 
+  if (distance > multiTripInstance.MaxDistance.Value) {
+    double maxDistanceViolation = (distance - (multiTripInstance.MaxDistance.Value));
+    penalty = maxDistanceViolation * multiTripInstance.MaxDistancePenalty.Value;
+    eval.Penalty += penalty;
+    eval.Quality += penalty;
+    (eval as MultiTripEvaluation).MaxDistanceViolation += maxDistanceViolation;
+  }
+}
+}}}
+
+Because 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.
+
+{{{
+#!cs
+protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
+  out bool feasible) {
+    if (!(solution is MultiTripEncoding)) {
+      return base.GetTourInsertionCosts(instance, solution, tourInsertionInfo, index, customer, out feasible);
+    } else {
+      MultiTripEncoding individual = (solution as MultiTripEncoding);
+ 
+      int tourIdx = -1;
+      for (int i = 0; i < individual.Tours.Count; i++) {
+        if (solution.GetVehicleAssignment(i) == tourInsertionInfo.Vehicle)
+          tourIdx = i;
+      }
+      Tour tour = individual.Tours[tourIdx];
+ 
+      tour.Stops.Insert(index, customer);
+      VRPEvaluation newEval = instance.EvaluateTour(tour, individual);
+      tour.Stops.RemoveAt(index);
+ 
+      feasible = instance.Feasible(newEval);
+      return newEval.Quality - tourInsertionInfo.Quality;
+    }
+}
+}}}
 
 = Implementing new Operators =