Changeset 4230 for branches/VRP/HeuristicLab.Problems.VehicleRouting

Timestamp:

08/16/10 15:20:29 (14 years ago)

Author:

svonolfe

Message:

Added GVR encoding (#1039)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3

Files:

• Encodings/Alba/AlbaEncoding.cs (modified) (3 diffs)
• Encodings/Alba/Manipulators/IntraRouteInversionManipulator.cs (modified) (1 diff)
• Encodings/Alba/Manipulators/LambdaInterchangeManipulator.cs (modified) (4 diffs)
• Encodings/Alba/Moves/IntraRouteInversion/StochasticIntraRouteInversionSingleMoveGenerator.cs (modified) (1 diff)
• Encodings/Alba/Moves/LambdaInterchange/ExhaustiveLambdaInterchangeMoveGenerator.cs (modified) (1 diff)
• Encodings/Alba/Moves/LambdaInterchange/StochasticLambdaInterchangeSingleMoveGenerator.cs (modified) (1 diff)
• Encodings/GVR (added)
• Encodings/GVR/Crossovers (added)
• Encodings/GVR/Crossovers/GVRCrossover.cs (added)
• Encodings/GVR/GVREncoding.cs (added)
• Encodings/GVR/Manipulators (added)
• Encodings/GVR/Manipulators/GVRDisplacementManipulator.cs (added)
• Encodings/GVR/Manipulators/GVRInsertionManipulator.cs (added)
• Encodings/GVR/Manipulators/GVRInversionManipulator.cs (added)
• Encodings/GVR/Manipulators/GVRManipulator.cs (added)
• Encodings/GVR/Manipulators/GVRSwapManipulator.cs (added)
• Encodings/General/TourEncoding.cs (added)
• Encodings/Potvin/PotvinEncoding.cs (modified) (5 diffs)
• Evaluators/VRPEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Problems.VehicleRouting-3.3.csproj (modified) (1 diff)
• Interfaces/IVRPEncoding.cs (modified) (1 diff)
• VRPOperator.cs (modified) (1 diff)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/AlbaEncoding.cs

@@ -26 +26 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using System.Collections.Generic;
+using HeuristicLab.Problems.VehicleRouting.Encodings.General;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
@@ -35 +36 @@
     
     #region IVRPEncoding Members
-    public ItemList<Tour> Tours {
-      get {
-        ItemList<Tour> result = new ItemList<Tour>();
-        
-        Tour tour = new Tour();
-        for (int i = 0; i < this.array.Length; i++) {
-          if (this.array[i] >= cities) {
-            if (tour.Cities.Count > 0) {
-              result.Add(tour);
+    public List<Tour> GetTours() {
+      List<Tour> result = new List<Tour>();
 
-              tour = new Tour();
-            }
-          } else {
-            tour.Cities.Add(this.array[i] + 1);
+      Tour tour = new Tour();
+      for (int i = 0; i < this.array.Length; i++) {
+        if (this.array[i] >= cities) {
+          if (tour.Cities.Count > 0) {
+            result.Add(tour);
+
+            tour = new Tour();
           }
+        } else {
+          tour.Cities.Add(this.array[i] + 1);
         }
+      }
 
-        if (tour.Cities.Count > 0) {
-          result.Add(tour);
-        }
+      if (tour.Cities.Count > 0) {
+        result.Add(tour);
+      }
 
-        return result;
-      }
+      return result;
     }
 
@@ -93 +92 @@
 
     public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, int vehicles) {
-      ItemList<Tour> tours = encoding.Tours;
+      List<Tour> tours = encoding.GetTours();
 
       int cities = 0;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Manipulators/IntraRouteInversionManipulator.cs

@@ -56 +56 @@
 
       List<Tour> validTours = new List<Tour>();
-      foreach (Tour tour in individual.Tours) {
+      foreach (Tour tour in individual.GetTours()) {
         if (tour.Cities.Count >= 4)
           validTours.Add(tour);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Manipulators/LambdaInterchangeManipulator.cs

@@ -26 +26 @@
 using HeuristicLab.Data;
 using System;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
@@ -45 +46 @@
     public static void Apply(AlbaEncoding individual, int tour1Index, int position1, int length1, 
       int tour2Index, int position2, int length2) {
-      Tour tour1 = individual.Tours[tour1Index];
+      List<Tour> tours = individual.GetTours();
+
+      Tour tour1 = tours[tour1Index];
       int tour1Start = -1;
       for (int i = 0; i < individual.Length; i++) {
@@ -54 +57 @@
       }
 
-      Tour tour2 = individual.Tours[tour2Index];
+      Tour tour2 = tours[tour2Index];
       int tour2Start = -1;
       for (int i = 0; i < individual.Length; i++) {
@@ -96 +99 @@
 
     protected override void Manipulate(IRandom rand, AlbaEncoding individual) {
+      List<Tour> tours = individual.GetTours();
       int lambda = LambdaParameter.Value.Value;
-      
-      int route1Index = rand.Next(individual.Tours.Count);
-      Tour route1 = individual.Tours[route1Index];
 
-      int route2Index = rand.Next(individual.Tours.Count - 1);
+      int route1Index = rand.Next(tours.Count);
+      Tour route1 = tours[route1Index];
+
+      int route2Index = rand.Next(tours.Count - 1);
       if (route2Index >= route1Index)
         route2Index += 1;
-      Tour route2 = individual.Tours[route2Index];
+      Tour route2 = tours[route2Index];
 
       int length1 = rand.Next(Math.Min(lambda + 1, route1.Cities.Count + 1));

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/IntraRouteInversion/StochasticIntraRouteInversionSingleMoveGenerator.cs

@@ -59 +59 @@
 
       List<Tour> validTours = new List<Tour>();
-      foreach (Tour tour in individual.Tours) {
+      foreach (Tour tour in individual.GetTours()) {
         if (tour.Cities.Count >= 4)
           validTours.Add(tour);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/ExhaustiveLambdaInterchangeMoveGenerator.cs

@@ -42 +42 @@
       List<LambdaInterchangeMove> moves = new List<LambdaInterchangeMove>();
 
-      for (int tour1Index = 0; tour1Index < individual.Tours.Count; tour1Index++) {
-        Tour tour1 = individual.Tours[tour1Index];
-        for (int tour2Index = tour1Index + 1; tour2Index < individual.Tours.Count; tour2Index++) {
-          Tour tour2 = individual.Tours[tour2Index];
+      List<Tour> tours = individual.GetTours();
+
+      for (int tour1Index = 0; tour1Index < tours.Count; tour1Index++) {
+        Tour tour1 = tours[tour1Index];
+        for (int tour2Index = tour1Index + 1; tour2Index < tours.Count; tour2Index++) {
+          Tour tour2 = tours[tour2Index];
 
           for (int length1 = 0; length1 <= Math.Min(lambda, tour1.Cities.Count); length1++) {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/StochasticLambdaInterchangeSingleMoveGenerator.cs

@@ -55 +55 @@
 
     public static LambdaInterchangeMove Apply(AlbaEncoding individual, int cities, int lambda, IRandom rand) {
-      int route1Index = rand.Next(individual.Tours.Count);
-      Tour route1 = individual.Tours[route1Index];
+      List<Tour> tours = individual.GetTours();
 
-      int route2Index = rand.Next(individual.Tours.Count - 1);
+      int route1Index = rand.Next(tours.Count);
+      Tour route1 = tours[route1Index];
+
+      int route2Index = rand.Next(tours.Count - 1);
       if (route2Index >= route1Index)
         route2Index += 1;
-      Tour route2 = individual.Tours[route2Index];
+      Tour route2 = tours[route2Index];
 
       int length1 = rand.Next(Math.Min(lambda + 1, route1.Cities.Count + 1));

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/PotvinEncoding.cs

@@ -27 +27 @@
 using System.Drawing;
 using System.Collections.Generic;
+using HeuristicLab.Problems.VehicleRouting.Encodings.General;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
   [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
   [StorableClass]
-  public class PotvinEncoding : Item, IVRPEncoding {
-    public override Image ItemImage {
-      get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Class; }
-    }
-    
-    #region IVRPEncoding Members
-    [Storable]
-    public ItemList<Tour> Tours { get; set; }
-
-    public int Cities {
-      get 
-      {
-        int cities = 0;
-
-        foreach (Tour tour in Tours) {
-          cities += tour.Cities.Count;
-        }
-
-        return cities;
-      }
-    }
-    #endregion
-
+  public class PotvinEncoding : TourEncoding {   
     [Storable]
     public List<int> Unrouted { get; set; }
@@ -65 +44 @@
     }
 
-    public PotvinEncoding() {
-      Tours = new ItemList<Tour>();
+    public PotvinEncoding(): base() {
       Unrouted = new List<int>();
+    }
+
+    [StorableConstructor]
+    private PotvinEncoding(bool serializing)
+      : base() {
     }
     
@@ -73 +56 @@
       PotvinEncoding solution = new PotvinEncoding();
 
-      solution.Tours.AddRange(
-        encoding.Tours);
+      TourEncoding.ConvertFrom(encoding, solution);
 
       return solution;
@@ -82 +64 @@
       PotvinEncoding solution = new PotvinEncoding();
 
-      Tour tour = new Tour();
-      for (int i = 0; i < route.Count; i++) {
-        if (route[i] == 0) {
-          if (tour.Cities.Count > 0) {
-            solution.Tours.Add(tour);
-            tour = new Tour();
-          }
-        } else {
-          tour.Cities.Add(route[i]);
-        }
-      }
+      TourEncoding.ConvertFrom(route, solution);
 
       return solution;
@@ -115 +87 @@
             if (Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, 
               capacity, coordinates, distanceMatrix, useDistanceMatrix)) {
-              double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
+                double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
 
               double detour = newLength - length;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Evaluators/VRPEvaluator.cs

@@ -101 +101 @@
       IVRPEncoding vrpSolution = VRPToursParameter.ActualValue;
 
-      return vrpSolution.Tours.Count;
+      return vrpSolution.GetTours().Count;
     }
 
@@ -190 +190 @@
       sumEval.Tardiness = 0;
 
-      foreach (Tour tour in solution.Tours) {
+      foreach (Tour tour in solution.GetTours()) {
         TourEvaluation eval = EvaluateTour(tour, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
           fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/HeuristicLab.Problems.VehicleRouting-3.3.csproj

@@ -140 +140 @@
     <Compile Include="Encodings\General\Moves\MultiVRPMoveOperator\MultiVRPMoveMaker.cs" />
     <Compile Include="Encodings\General\Moves\MultiVRPMoveOperator\MultiVRPMoveGenerator.cs" />
+    <Compile Include="Encodings\General\TourEncoding.cs" />
+    <Compile Include="Encodings\GVR\Crossovers\GVRCrossover.cs" />
+    <Compile Include="Encodings\GVR\GVREncoding.cs" />
+    <Compile Include="Encodings\GVR\Manipulators\GVRDisplacementManipulator.cs" />
+    <Compile Include="Encodings\GVR\Manipulators\GVRInsertionManipulator.cs" />
+    <Compile Include="Encodings\GVR\Manipulators\GVRInversionManipulator.cs" />
+    <Compile Include="Encodings\GVR\Manipulators\GVRSwapManipulator.cs" />
+    <Compile Include="Encodings\GVR\Manipulators\GVRManipulator.cs" />
     <Compile Include="Encodings\Potvin\Crossovers\RouteBasedCrossover.cs" />
     <Compile Include="Encodings\Potvin\Crossovers\SequenceBasedCrossover.cs" />

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Interfaces/IVRPEncoding.cs

@@ -22 +22 @@
 using HeuristicLab.Core;
 using HeuristicLab.Problems.VehicleRouting.Encodings;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Problems.VehicleRouting {
   public interface IVRPEncoding : IItem {
-    ItemList<Tour> Tours {
-      get;
-    }
+    List<Tour> GetTours();
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/VRPOperator.cs

@@ -140 +140 @@
       bool feasible = true;
 
-      foreach (Tour tour in solution.Tours) {
+      foreach (Tour tour in solution.GetTours()) {
         if (!Feasible(tour)) {
           feasible = false;