Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6851


Ignore:
Timestamp:
09/29/11 15:51:56 (11 years ago)
Author:
svonolfe
Message:

Added support for multi depot CVRP instances (#1177)

Location:
branches/VRP
Files:
21 added
1 deleted
43 edited
2 moved

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/CVRPPDTWView.cs

    r6789 r6851  
    9595
    9696                  t += Content.GetDistance(
    97                     lastCustomer, location);
     97                    lastCustomer, location, Solution);
    9898
    9999                  if (t < readyTime[location]) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/CVRPTWView.cs

    r4374 r6851  
    7676
    7777                  t += Content.GetDistance(
    78                     lastCustomer, location);
     78                    lastCustomer, location, Solution);
    7979
    8080                  if (t < readyTime[location]) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/HeuristicLab.Problems.VehicleRouting.Views-3.4.csproj

    r6710 r6851  
    112112  </ItemGroup>
    113113  <ItemGroup>
     114    <Compile Include="MultiDepotVRPView.cs">
     115      <SubType>UserControl</SubType>
     116    </Compile>
     117    <Compile Include="MultiDepotVRPView.Designer.cs">
     118      <DependentUpon>MultiDepotVRPView.cs</DependentUpon>
     119    </Compile>
    114120    <Compile Include="CVRPPDTWView.cs">
    115121      <SubType>UserControl</SubType>
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VRPImportDialog.Designer.cs

    r6710 r6851  
    8585      this.openVRPFileDialog.DefaultExt = "vrp";
    8686      this.openVRPFileDialog.FileName = "vrp";
    87       this.openVRPFileDialog.Filter = "TSPLib Format|*.vrp|Solomon Format|*.txt|ORLib Format|*.txt|LiLim Format|*.txt";
    88       this.openVRPFileDialog.Title = "Open TSP File";
     87      this.openVRPFileDialog.Filter = "TSPLib Format|*.vrp|Solomon Format|*.txt|ORLib Format|*.txt|LiLim Format|*.txt|Cordeau Format|*.md";
     88      this.openVRPFileDialog.Title = "Open VRP File";
    8989      //
    9090      // tspFileLabel
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VRPImportDialog.cs

    r6710 r6851  
    2727
    2828namespace HeuristicLab.Problems.VehicleRouting.Views {
    29   public enum VRPFormat { Empty, TSPLib, Solomon, ORLib, LiLim }
     29  public enum VRPFormat { Empty, TSPLib, Solomon, ORLib, LiLim, Cordeau }
    3030
    3131  public sealed partial class VRPImportDialog : Form {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VehicleRoutingProblemView.cs

    r6710 r6851  
    8686              Content.ImportFromLiLim(vrpImportDialog.VRPFileName);
    8787              break;
     88
     89            case VRPFormat.Cordeau:
     90              Content.ImportFromCordeau(vrpImportDialog.VRPFileName);
     91              break;
    8892          }
    8993
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

    r6710 r6851  
    3333  [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
    3434  [StorableClass]
    35   public class AlbaEncoding : PermutationEncoding, IHeterogenousCapacitatedEncoding  {   
     35  public class AlbaEncoding : PermutationEncoding  {   
    3636    #region IVRPEncoding Members
    3737    public override List<Tour> GetTours() {
     38      Repair();
    3839      List<Tour> result = new List<Tour>();
    3940
     
    5556      if (tour.Stops.Count > 0) {
    5657        result.Add(tour);
    57       }   
     58      }
    5859
    5960      return result;
    6061    }
    61     #endregion
    6262
    63     #region IHeterogenousCapacitatedEncoding Members
    64 
    65     public int GetVehicleAssignment(int tour) {
     63    public override int GetVehicleAssignment(int tour) {
    6664      int vehicleAssignment = -1;
    6765      Tour currentTour = GetTours()[tour];
     
    7270      int lastStopIndex = this.IndexOf(lastStop);
    7371
    74       if (lastStopIndex == this.Length - 1)
    75         vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
     72      if (lastStopIndex == this.Length - 1) {
     73        int i = this.Length - 1;
     74
     75        while (vehicleAssignment == -1) {
     76          if (this.array[i] >= ProblemInstance.Cities.Value) {
     77            vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
     78          }
     79         
     80          i--;
     81        }
     82      }
    7683      else
    7784        vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
     
    8087    }
    8188    #endregion
     89
     90    public void Repair() {
     91      int cities = ProblemInstance.Cities.Value;
     92
     93      if (this[this.Length - 1] < cities) {
     94        int index = this.Length - 2;
     95        while (this[index] < cities) {
     96          index--;
     97        }
     98
     99        int vehicle = this[index];
     100        for (int i = index; i < this.Length - 1; i++)
     101          this[i] = this[i + 1];
     102        this[Length - 1] = vehicle;
     103      }
     104    }
    82105
    83106    public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance)
     
    100123    public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) {
    101124      List<int> route = new List<int>(routeParam);
    102       route.RemoveAt(routeParam.Count - 1);
    103125     
    104126      int cities = instance.Cities.Value;
     
    129151      int emptyVehicles = instance.Vehicles.Value - tours.Count;
    130152
    131       int[] array = new int[cities + tours.Count + emptyVehicles - 1];
     153      int[] array = new int[cities + tours.Count + emptyVehicles];
    132154      int delimiter = 0;
    133155      int arrayIndex = 0;
     
    140162
    141163        if (arrayIndex != array.Length) {
    142           if (encoding is IHeterogenousCapacitatedEncoding) {
    143             array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
    144           } else {
    145             array[arrayIndex] = cities + delimiter;
    146           }
     164          array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
    147165         
    148166          delimiter++;
     
    151169      }
    152170
    153       for (int i = 0; i < emptyVehicles - 1; i++) {
    154         if (encoding is IHeterogenousCapacitatedEncoding) {
    155           array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
    156         } else {
    157           array[arrayIndex] = cities + delimiter;
    158         }
     171      for (int i = 0; i < emptyVehicles; i++) {
     172        array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
    159173
    160174        delimiter++;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/AlbaCreator.cs

    r4752 r6851  
    4747      : base(original, cloner) {
    4848    }
     49
     50    public override IOperation Apply() {
     51      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
     52
     53      return base.Apply();
     54    }
    4955  }
    5056}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs

    r4752 r6851  
    6767
    6868      ChildParameter.ActualValue =
    69         Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding); 
     69        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);
     70      (ChildParameter.ActualValue as AlbaEncoding).Repair();
    7071
    7172      return base.Apply();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/IAlbaOperator.cs

    r4369 r6851  
    3232
    3333namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    34   public interface IAlbaOperator: 
    35     ISingleDepotOperator, IHeterogenousCapacitatedOperator, ITimeWindowedOperator {   
     34  public interface IAlbaOperator:
     35    ISingleDepotOperator, IHeterogenousCapacitatedOperator, IMultiDepotOperator, ITimeWindowedOperator {   
    3636  }
    3737}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs

    r4752 r6851  
    7171
    7272      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as AlbaEncoding);
     73      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
    7374
    7475      return base.Apply();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/ExtendedPotvin/Creators/IterativeInsertionCreator.cs

    r6838 r6851  
    3333using HeuristicLab.Problems.VehicleRouting.Variants;
    3434
    35 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     35namespace HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin {
    3636  [Item("IterativeInsertionCreator", "Creates a randomly initialized VRP solution.")]
    3737  [StorableClass]
    38   public sealed class IterativeInsertionCreator : PotvinCreator, IStochasticOperator {
     38  public sealed class IterativeInsertionCreator : ExtendedPotvinCreator, IStochasticOperator {
    3939    #region IStochasticOperator Members
    4040    public ILookupParameter<IRandom> RandomParameter {
     
    6565
    6666    private static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
    67       double dx = instance.Coordinates[0, 0];
    68       double dy = instance.Coordinates[0, 1];
     67      double dx = instance.GetCoordinates(0)[0];
     68      double dy = instance.GetCoordinates(0)[1];
    6969
    70       double cx = instance.Coordinates[city, 0];
    71       double cy = instance.Coordinates[city, 1];
     70      double cx = instance.GetCoordinates(city)[0];
     71      double cy = instance.GetCoordinates(city)[1];
    7272
    7373      double alpha = Math.Atan((cx - dx) / (dy - cy)) * (180.0 / Math.PI);
     
    8282    }
    8383
    84     private static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, bool adhereTimeWindows) {
    85       PotvinEncoding result = new PotvinEncoding(instance);
     84    private static ExtendedPotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, bool adhereTimeWindows) {
     85      ExtendedPotvinEncoding result = new ExtendedPotvinEncoding(instance);
    8686
    8787      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     
    8989      List<int> customers = new List<int>();
    9090      for (int i = 1; i <= instance.Cities.Value; i++)
    91         if(pdp == null || pdp.Demand[i] >= 0)
     91        if(pdp == null || pdp.GetDemand(i) >= 0)
    9292          customers.Add(i);
    9393
     
    107107        int index = (i + j) % customers.Count;
    108108
    109         int stopIdx = result.FindBestInsertionPlace(currentTour, customers[index]);
     109        int stopIdx = 0;
     110        if(currentTour.Stops.Count > 0)
     111          result.FindBestInsertionPlace(currentTour, customers[index]);
    110112        currentTour.Stops.Insert(stopIdx, customers[index]);
    111113
     
    122124              currentTour.Stops.Remove(pdp.PickupDeliveryLocation[customers[index]]);
    123125
    124           if(currentTour.Stops.Count > 0)
    125             result.Tours.Add(currentTour);
     126          if (currentTour.Stops.Count == 0)
     127            result.Tours.Remove(currentTour);
    126128          currentTour = new Tour();
     129          result.Tours.Add(currentTour);
    127130         
    128131          currentTour.Stops.Add(customers[index]);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/ExtendedPotvin/Creators/PushForwardInsertionCreator.cs

    r6839 r6851  
    3333using HeuristicLab.Problems.VehicleRouting.Variants;
    3434
    35 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     35namespace HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin {
    3636  [Item("PushForwardInsertionCreator", "Creates a randomly initialized VRP solution.")]
    3737  [StorableClass]
    38   public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
     38  public sealed class PushForwardInsertionCreator : ExtendedPotvinCreator, IStochasticOperator {
    3939    #region IStochasticOperator Members
    4040    public ILookupParameter<IRandom> RandomParameter {
     
    9999    }
    100100
    101     private static double Distance(IVRPProblemInstance problemInstance, int start, int end) {
    102       return problemInstance.GetDistance(start, end);
    103     }
    104 
    105     private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
     101    private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance) {
     102      double distance = 0.0;
     103
     104      double startX = problemInstance.Coordinates[start, 0];
     105      double startY = problemInstance.Coordinates[start, 1];
     106
     107      double endX = problemInstance.Coordinates[end, 0];
     108      double endY = problemInstance.Coordinates[end, 1];
     109
     110      distance =
     111          Math.Sqrt(
     112            Math.Pow(startX - endX, 2) +
     113            Math.Pow(startY - endY, 2));
     114
     115      return distance;
     116    }
     117
     118    private static ExtendedPotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
    106119      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
    107120      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
    108       PotvinEncoding result = new PotvinEncoding(problemInstance);
     121      ExtendedPotvinEncoding result = new ExtendedPotvinEncoding(problemInstance);
    109122
    110123      double alpha, beta, gamma;
     
    113126      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
    114127
    115       double x0 = problemInstance.Coordinates[0, 0];
    116       double y0 = problemInstance.Coordinates[0, 1];
     128      int totalTours = 0;
     129
    117130      double distance = 0;
    118131      double cost = 0;
     
    121134
    122135      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    123 
    124       /*-----------------------------------------------------------------------------
    125        * generate cost list
    126        *-----------------------------------------------------------------------------
    127        */
    128       for (int i = 1; i <= problemInstance.Cities.Value; i++) {
    129         //only insert sources
    130         if (pdp == null || problemInstance.Demand[i] >= 0) {
    131           distance = Distance(problemInstance, i, 0);
    132           if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
    133 
    134           cost = -alpha * distance + // distance 0 <-> City[i]
    135                  beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
    136                  gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
    137 
    138           int index = 0;
    139           while (index < costList.Count && costList[index] < cost) index++;
    140 
    141           costList.Insert(index, cost);
    142 
    143           unroutedList.Insert(index, i);
    144         }
     136      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
     137
     138      int depots = 1;
     139      if (mdp != null) {
     140        depots = mdp.Depots.Value;
     141        for (int i = 0; i < result.VehicleAssignment.Length; i++)
     142          result.VehicleAssignment[i] = -1;
    145143      }
    146144
    147       double minimumCost = double.MaxValue;
    148       int indexOfMinimumCost = -1;
    149       int indexOfMinimumCost2 = -1;
    150       int indexOfCustomer = -1;
    151 
    152       Tour tour = new Tour();
    153       result.Tours.Add(tour);
    154 
    155       tour.Stops.Add(unroutedList[0]);
    156 
    157       if (pdp != null) {
    158         tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
    159       }
    160 
    161       unroutedList.RemoveAt(0);
    162 
    163       while (unroutedList.Count > 0) {
    164         for (int c = 0; c < unroutedList.Count; c++) {
    165           VRPEvaluation eval =
    166           problemInstance.EvaluateTour(tour, result);
    167           double originalCosts = eval.Quality;
    168           int customer = unroutedList[c];
    169 
    170           for (int i = 0; i <= tour.Stops.Count; i++) {
    171             tour.Stops.Insert(i, customer);
    172             eval = problemInstance.EvaluateTour(tour, result);
    173             double tourCost = eval.Quality - originalCosts;
    174 
    175             if (pdp != null) {
    176               for (int j = i + 1; j <= tour.Stops.Count; j++) {
    177                 bool feasible;
    178                 cost = tourCost +
    179                   problemInstance.GetInsertionCosts(eval, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
     145      List<int> unrouted = new List<int>();
     146      for (int i = 1; i <= problemInstance.Cities.Value; i++)
     147        if (pdp == null || problemInstance.GetDemand(i) >= 0)
     148          unrouted.Add(i);
     149
     150      for (int depot = 0; depot < depots; depot++) {
     151        int vehicleCount = problemInstance.Vehicles.Value;
     152        List<int> vehicles = new List<int>();
     153        if (mdp != null) {
     154          vehicleCount = 0;
     155          for (int i = 0; i < mdp.VehicleDepotAssignment.Length; i++) {
     156            if (mdp.VehicleDepotAssignment[i] == depot) {
     157              vehicleCount++;
     158              vehicles.Add(i);
     159            }
     160          }
     161        } else {
     162          for (int i = 0; i < problemInstance.Vehicles.Value; i++)
     163            vehicles.Add(i);
     164        }
     165
     166        costList.Clear();
     167        unroutedList.Clear();
     168
     169        double x0 = problemInstance.Coordinates[depot, 0];
     170        double y0 = problemInstance.Coordinates[depot, 1];
     171
     172        /*-----------------------------------------------------------------------------
     173        * generate cost list
     174        *-----------------------------------------------------------------------------
     175        */
     176        for (int i = 1; i <= problemInstance.Cities.Value; i++) {
     177          //only insert sources
     178          if (unrouted.Contains(i) && (pdp == null || problemInstance.GetDemand(i) >= 0)) {
     179            distance = GetDistance(i + depots - 1, depot, problemInstance);
     180            if (problemInstance.Coordinates[i + depots - 1, 0] < x0) distance = -distance;
     181
     182            double dueTime = 0;
     183            if (problemInstance is ITimeWindowedProblemInstance)
     184              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i];
     185
     186            cost = -alpha * distance + // distance 0 <-> City[i]
     187                   beta * dueTime + // latest arrival time
     188                   gamma * (Math.Asin((problemInstance.Coordinates[i + depots - 1, 0] - y0) / distance) / 360 * distance); // polar angle
     189
     190            int index = 0;
     191            while (index < costList.Count && costList[index] < cost) index++;
     192
     193            costList.Insert(index, cost);
     194
     195            unroutedList.Insert(index, i);
     196          }
     197        }
     198
     199        int tours = 0;
     200        double minimumCost = double.MaxValue;
     201        int indexOfMinimumCost = -1;
     202        int indexOfMinimumCost2 = -1;
     203        int indexOfCustomer = -1;
     204
     205        Tour tour = new Tour();
     206        result.Tours.Add(tour);
     207        result.VehicleAssignment[totalTours] = vehicles[0];
     208        vehicles.RemoveAt(0);
     209        tours++;
     210        totalTours++;
     211
     212        tour.Stops.Add(unroutedList[0]);
     213
     214        if (pdp != null) {
     215          tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
     216        }
     217
     218        unrouted.Remove(unroutedList[0]);
     219        unroutedList.RemoveAt(0);
     220
     221        while (unroutedList.Count > 0 && (tours < vehicleCount || depot == depots - 1)) {
     222          for (int c = 0; c < unroutedList.Count; c++) {
     223            VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
     224            double originalCosts = eval.Quality;
     225            int customer = unroutedList[c];
     226
     227            for (int i = 0; i <= tour.Stops.Count; i++) {
     228              tour.Stops.Insert(i, customer);
     229              eval = problemInstance.EvaluateTour(tour, result);
     230              double tourCost = eval.Quality - originalCosts;
     231
     232              if (pdp != null) {
     233                for (int j = i + 1; j <= tour.Stops.Count; j++) {
     234                  bool feasible;
     235                  cost = tourCost +
     236                    problemInstance.GetInsertionCosts(eval, result, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
     237                  if (cost < minimumCost && feasible) {
     238                    minimumCost = cost;
     239                    indexOfMinimumCost = i;
     240                    indexOfMinimumCost2 = j;
     241                    indexOfCustomer = c;
     242                  }
     243                }
     244              } else {
     245                cost = tourCost;
     246                bool feasible = problemInstance.Feasible(eval);
    180247                if (cost < minimumCost && feasible) {
    181248                  minimumCost = cost;
    182249                  indexOfMinimumCost = i;
    183                   indexOfMinimumCost2 = j;
    184250                  indexOfCustomer = c;
    185251                }
    186252              }
    187             } else {
    188               cost = tourCost;
    189               bool feasible = problemInstance.Feasible(eval);
    190               if (cost < minimumCost && feasible) {
    191                 minimumCost = cost;
    192                 indexOfMinimumCost = i;
    193                 indexOfCustomer = c;
    194               }
     253
     254              tour.Stops.RemoveAt(i);
    195255            }
    196 
    197             tour.Stops.RemoveAt(i);           
    198           }
    199         }
    200 
    201         // insert customer if found
    202         if (indexOfMinimumCost != -1) {
    203           tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
    204           if (pdp != null) {
    205             tour.Stops.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[unroutedList[indexOfCustomer]]);
    206           }
    207 
    208           unroutedList.RemoveAt(indexOfCustomer);
    209         } else { // no feasible customer found
    210           tour = new Tour();
    211           result.Tours.Add(tour);
    212 
    213           tour.Stops.Add(unroutedList[0]);
    214           if (pdp != null) {
    215             tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
    216           }
    217 
    218           unroutedList.RemoveAt(0);
    219         }
    220         // reset minimum   
    221         minimumCost = double.MaxValue;
    222         indexOfMinimumCost = -1;
    223         indexOfMinimumCost2 = -1;
    224         indexOfCustomer = -1;
     256          }
     257
     258          // insert customer if found
     259          if (indexOfMinimumCost != -1) {
     260            tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
     261            if (pdp != null) {
     262              tour.Stops.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[unroutedList[indexOfCustomer]]);
     263            }
     264
     265            unrouted.Remove(unroutedList[indexOfCustomer]);
     266            unroutedList.RemoveAt(indexOfCustomer);
     267          } else if (tours < vehicleCount || depot == depots - 1) { // no feasible customer found
     268            tour = new Tour();
     269            result.Tours.Add(tour);
     270            result.VehicleAssignment[totalTours] = vehicles[0];
     271            vehicles.RemoveAt(0);
     272            tours++;
     273            totalTours++;
     274
     275            tour.Stops.Add(unroutedList[0]);
     276            if (pdp != null) {
     277              tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
     278            }
     279
     280            unrouted.Remove(unroutedList[0]);
     281            unroutedList.RemoveAt(0);
     282          }
     283          // reset minimum   
     284          minimumCost = double.MaxValue;
     285          indexOfMinimumCost = -1;
     286          indexOfMinimumCost2 = -1;
     287          indexOfCustomer = -1;
     288        }
     289      }
     290
     291      if (mdp != null) {
     292        List<int> availableVehicles = new List<int>();
     293        for (int i = 0; i < mdp.Vehicles.Value; i++)
     294          availableVehicles.Add(i);
     295
     296        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
     297          if (result.VehicleAssignment[i] != -1)
     298            availableVehicles.Remove(result.VehicleAssignment[i]);
     299        }
     300
     301        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
     302          if (result.VehicleAssignment[i] == -1) {
     303            result.VehicleAssignment[i] = availableVehicles[0];
     304            availableVehicles.RemoveAt(0);
     305          }
     306        }
    225307      }
    226308
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/GVR/Crossovers/GVRCrossover.cs

    r4752 r6851  
    8282      for (int i = 1; i <= ProblemInstance.Cities.Value; i++) {
    8383        if (!subroute.Contains(i)) {
    84           double distance = ProblemInstance.GetDistance(subroute[0], i);
     84          double distance = ProblemInstance.GetDistance(subroute[0], i, child);
    8585
    8686          if (customer == -1 || distance < minDistance) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/GVR/GVREncoding.cs

    r4752 r6851  
    4242        double currentDemand = 0;
    4343
    44         DoubleArray demand = ProblemInstance.Demand;
    4544        DoubleValue capacity = new DoubleValue(double.MaxValue);
    4645        if (ProblemInstance is IHomogenousCapacitatedProblemInstance) {
     
    5049
    5150        foreach (int city in tour.Stops) {
    52           currentDemand += demand[city];
     51          currentDemand += ProblemInstance.GetDemand(city);
    5352
    5453          if (currentDemand > capacity.Value) {
     
    5857            newTour = new Tour();
    5958            newTour.Stops.Add(city);
    60             currentDemand = demand[city];
     59            currentDemand = ProblemInstance.GetDemand(city);
    6160          } else {
    6261            newTour.Stops.Add(city);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Crossovers/BiasedMultiVRPSolutionCrossover.cs

    r6716 r6851  
    160160      OperationCollection next = new OperationCollection(successorOp);
    161161      if (successor != null) {
    162         SelectedOperatorParameter.ActualValue = new StringValue(successor.GetType().Name);
     162        SelectedOperatorParameter.ActualValue = new StringValue(successor.Name);
    163163
    164164        if (CreateChildOperation)
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Manipulators/BiasedMultiVRPSolutionManipulator.cs

    r6716 r6851  
    160160      OperationCollection next = new OperationCollection(successorOp);
    161161      if (successor != null) {
    162         SelectedOperatorParameter.ActualValue = new StringValue(successor.GetType().Name);
     162        SelectedOperatorParameter.ActualValue = new StringValue(successor.Name);
    163163
    164164        if (CreateChildOperation)
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs

    r4899 r6851  
    3535    #region IVRPEncoding Members
    3636    public abstract List<Tour> GetTours();
     37
     38    public int GetTourIndex(Tour tour) {
     39      int index = -1;
     40
     41      List<Tour> tours = GetTours();
     42      for (int i = 0; i < tours.Count; i++) {
     43        if (tours[i].IsEqual(tour)) {
     44          index = i;
     45          break;
     46        }
     47      }
     48
     49      return index;
     50    }
     51
     52    public virtual int GetVehicleAssignment(int tour) {
     53      return tour;
     54    }
    3755    #endregion
    3856
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

    r6837 r6851  
    3838   
    3939    #region IVRPEncoding Members
    40     public void Repair() {
     40    public virtual void Repair() {
    4141      List<Tour> toBeRemoved = new List<Tour>();
    4242      foreach (Tour tour in Tours) {
     
    6262
    6363     return result;
     64    }
     65
     66    public int GetTourIndex(Tour tour) {
     67      int index = -1;
     68
     69      for (int i = 0; i < Tours.Count; i++) {
     70        if (Tours[i].IsEqual(tour)) {
     71          index = i;
     72          break;
     73        }
     74      }
     75
     76      return index;
     77    }
     78
     79    public virtual int GetVehicleAssignment(int tour) {
     80      return tour;
    6481    }
    6582
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs

    r6838 r6851  
    2828using HeuristicLab.Parameters;
    2929using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
     30using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3031
    3132namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    7475    }
    7576
    76     private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {
     77    private double CalculateCentroidDistance(Tour t1, Tour t2, IVRPProblemInstance instance) {
    7778      double xSum = 0;
    7879      double ySum = 0;
     
    8081
    8182      for (int i = 0; i < t1.Stops.Count; i++) {
    82         xSum += coordinates[t1.Stops[i], 0];
    83         ySum += coordinates[t1.Stops[i], 1];
     83        xSum += instance.GetCoordinates(t1.Stops[i])[0];
     84        ySum += instance.GetCoordinates(t1.Stops[i])[1];
    8485      }
    8586      c1X = xSum / t1.Stops.Count;
     
    8788
    8889      for (int i = 0; i < t2.Stops.Count; i++) {
    89         xSum += coordinates[t2.Stops[i], 0];
    90         ySum += coordinates[t2.Stops[i], 1];
     90        xSum += instance.GetCoordinates(t2.Stops[i])[0];
     91        ySum += instance.GetCoordinates(t2.Stops[i])[1];
    9192      }
    9293      c2X = xSum / t1.Stops.Count;
     
    9899    }
    99100
    100     private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {
     101    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, IVRPProblemInstance instance) {
    101102      double sum = 0;
    102103
    103104      for (int i = 0; i < tours.Count; i++) {
    104         sum += CalculateCentroidDistance(t1, tours[i], coordinates);
     105        sum += CalculateCentroidDistance(t1, tours[i], instance);
    105106      }
    106107
     
    108109    }
    109110
    110     private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour) {
     111    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, IVRPEncoding solution) {
    111112      int cityIndex = -1;
    112113
     
    120121          next = tour.Stops[i + 1];
    121122        double distance = ProblemInstance.GetDistance(
    122           tour.Stops[i], next);
     123          tour.Stops[i], next, solution);
    123124
    124125        int prev;
     
    128129          prev = tour.Stops[i - 1];
    129130        distance += ProblemInstance.GetDistance(
    130           tour.Stops[i], prev);
     131          tour.Stops[i], prev, solution);
    131132
    132133        probabilities[i] = distance;
     
    168169      for (int i = 0; i <= tour.Stops.Count; i++) {
    169170        bool feasible;
    170         double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
     171        double detour = ProblemInstance.GetInsertionCosts(eval, individual, city, 0, i, out feasible);
    171172        if (feasible || allowInfeasible) {
    172173          if (place < 0 || detour < minDetour) {
     
    195196
    196197    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
    197       PotvinEncoding child = new PotvinEncoding(ProblemInstance);
     198      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
     199      child.Tours.Clear();
    198200
    199201      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     
    213215        List<int> R2 = new List<int>();
    214216
    215         double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance.Coordinates);
     217        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance);
    216218        foreach (Tour tour in parent2.Tours) {
    217           if (CalculateCentroidDistance(r1, tour, ProblemInstance.Coordinates) <= r) {
     219          if (CalculateCentroidDistance(r1, tour, ProblemInstance) <= r) {
    218220            R2.AddRange(tour.Stops);
    219221          }
     
    227229        int removed = random.Next(1, r1.Stops.Count + 1);
    228230        for (int i = 0; i < removed; i++) {
    229           childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour));
     231          childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, child));
    230232        }
    231233
    232234        //REPAIR - add cities from R2
    233         int maxCount = random.Next(1, Math.Min(5, R2.Count));
     235        int maxCount = 1;
     236        if(R2.Count > 1)
     237          maxCount = random.Next(1, Math.Min(5, R2.Count));
    234238        int count = 0;
    235239
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

    r6607 r6851  
    2626using HeuristicLab.Data;
    2727using HeuristicLab.Common;
     28using HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin;
    2829
    2930namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    5758
    5859      child.Tours.Remove(replaced);
    59       child.Tours.Add(replacing);
     60      child.Tours.Insert(tourParent2, replacing);
     61
     62      if (parent1 is ExtendedPotvinEncoding && child is ExtendedPotvinEncoding) {
     63        Permutation vehicleAssignment = (child as ExtendedPotvinEncoding).VehicleAssignment;
     64
     65        int vehicle = vehicleAssignment[tourParent2];
     66        int vehicle2 = (parent1 as ExtendedPotvinEncoding).VehicleAssignment[tourParent1];
     67        vehicleAssignment[tourParent2] = vehicle2;
     68
     69        for (int i = 0; i < vehicleAssignment.Length; i++) {
     70          if (vehicleAssignment[i] == vehicle2 && i != tourParent2) {
     71            vehicleAssignment[i] = vehicle;
     72            break;
     73          }
     74        }       
     75      }
    6076
    6177      foreach (int city in replaced.Stops)
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

    r6607 r6851  
    6767        newTour.Stops.Add(tour2.Stops[i]);
    6868
     69      int tour1Index = child.Tours.IndexOf(tour1);
    6970      child.Tours.Remove(tour1);
    70       child.Tours.Add(newTour);
     71      child.Tours.Insert(tour1Index, newTour);
    7172
    7273      foreach (int city in tour1.Stops)
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs

    r6753 r6851  
    6767        for (int i = 0; i < route1.Stops.Count; i++) {
    6868          int stop = route1.Stops[i];
    69           if (ProblemInstance.Demand[stop] < 0) {
     69          if (ProblemInstance.GetDemand(stop) < 0) {
    7070            int source = pdp.PickupDeliveryLocation[stop];
    7171
     
    158158
    159159            //drive there
    160             double currentDistace = vrptw.GetDistance(start, end);
     160            double currentDistace = vrptw.GetDistance(start, end, individual);
    161161            time += currentDistace;
    162162
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeExhaustiveMoveGenerator.cs

    r6773 r6851  
    6262            if (k != i) {
    6363              int city1 = individual.Tours[i].Stops[j];
    64               if (pdp == null || pdp.Demand[city1] >= 0) {
     64              if (pdp == null || pdp.GetDemand(city1) >= 0) {
    6565                for (int l = 0; l < individual.Tours[k].Stops.Count; l++) {
    6666                  int city2 = individual.Tours[k].Stops[l];
    67                   if (pdp == null || pdp.Demand[city2] >= 0) {
     67                  if (pdp == null || pdp.GetDemand(city2) >= 0) {
    6868                    bool valid = pdp == null ||
    6969                      (pdp.PickupDeliveryLocation[city2] != pdp.PickupDeliveryLocation[city1] &&
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeSingleMoveGenerator.cs

    r6773 r6851  
    6262      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    6363      for (int i = 1; i <= individual.Cities; i++) {
    64         if (pdp == null || pdp.Demand[i] >= 0)
     64        if (pdp == null || pdp.GetDemand(i) >= 0)
    6565          cities.Add(i);
    6666      }
     
    8484        foreach (int stop in newTour.Stops) {
    8585          if (pdp == null ||
    86             (pdp.Demand[stop] >= 0 &&
     86            (pdp.GetDemand(stop) >= 0 &&
    8787             pdp.PickupDeliveryLocation[stop] != pdp.PickupDeliveryLocation[city] &&
    8888             pdp.PickupDeliveryLocation[stop] != city &&
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeExhaustiveMoveGenerator.cs

    r6773 r6851  
    5454
    5555      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
    56         if (pdp == null || pdp.Demand[i] >= 0) {
     56        if (pdp == null || pdp.GetDemand(i) >= 0) {
    5757          int tour = individual.Tours.FindIndex(t => t.Stops.Contains(i));
    5858
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs

    r6838 r6851  
    7474          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
    7575            bool feasible;
    76             double targetCosts = problemInstance.GetInsertionCosts(tourEval, target, 0, j, out feasible);
     76            double targetCosts = problemInstance.GetInsertionCosts(tourEval, solution, target, 0, j, out feasible);
    7777
    7878            double costs = sourceCosts + targetCosts;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeSingleMoveGenerator.cs

    r6773 r6851  
    6262      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    6363      for (int i = 1; i <= individual.Cities; i++) {
    64         if(pdp == null || pdp.Demand[i] >= 0)
     64        if(pdp == null || pdp.GetDemand(i) >= 0)
    6565          cities.Add(i);
    6666      }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftExhaustiveMoveGenerator.cs

    r6773 r6851  
    6262            if (k != i) {
    6363              int city = individual.Tours[i].Stops[j];
    64               if (pdp == null || pdp.Demand[city] >= 0) {
     64              if (pdp == null || pdp.GetDemand(city) >= 0) {
    6565                PotvinPDShiftMove move = new PotvinPDShiftMove(
    6666                  city, i, k, individual);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftSingleMoveGenerator.cs

    r6773 r6851  
    6262      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    6363      for (int i = 1; i <= individual.Cities; i++) {
    64         if(pdp == null || pdp.Demand[i] >= 0)
     64        if(pdp == null || pdp.GetDemand(i) >= 0)
    6565          cities.Add(i);
    6666      }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

    r6838 r6851  
    4545
    4646    [StorableConstructor]
    47     private PotvinEncoding(bool serializing)
     47    protected PotvinEncoding(bool serializing)
    4848      : base(serializing) {
    4949    }
     
    7575
    7676    public double GetTourLength(Tour tour) {
    77       return tour.GetTourLength(ProblemInstance);
     77      return tour.GetTourLength(ProblemInstance, this);
    7878    }
    7979
     
    8787        if (positionToAvoid != i) {
    8888          bool feasible;
    89           double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
     89          double quality = ProblemInstance.GetInsertionCosts(eval, this, city, 0, i, out feasible);
    9090          if (place < 0 || quality < minQuality) {
    9191            place = i;
     
    115115          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
    116116            bool feasible;
    117             double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible);
    118            
     117            double detour = ProblemInstance.GetInsertionCosts(eval, this, city, tour, i, out feasible);
     118
    119119            if (feasible || allowInfeasible) {
    120120              if (route < 0 || detour < minDetour) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Tour.cs

    r6607 r6851  
    4848    }
    4949
    50     public double GetTourLength(IVRPProblemInstance instance) {
     50    public double GetTourLength(IVRPProblemInstance instance, IVRPEncoding solution) {
    5151      double length = 0;
    5252
     
    6060
    6161        for (int i = 1; i < cities.Count; i++) {
    62           length += instance.GetDistance(cities[i - 1], cities[i]);
     62          length += instance.GetDistance(cities[i - 1], cities[i], solution);
    6363        }
    6464      }
     
    6666      return length;
    6767    }
     68
     69    public bool IsEqual(Tour tour) {
     70      bool equal = (tour != null) && (tour.Stops.Count == Stops.Count);
     71      int index = 0;
     72
     73      while (equal && index < Stops.Count) {
     74        equal = equal && tour.Stops[index] == Stops[index];
     75        index++;
     76      }     
     77
     78      return equal;
     79    }
    6880  }
    6981}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/Crossovers/ZhuHeuristicCrossover1.cs

    r6771 r6851  
    7777
    7878        if (ProblemInstance.GetDistance(
    79           child[i] + 1, parent1[(i + 1) % child.Length] + 1)
     79          child[i] + 1, parent1[(i + 1) % child.Length] + 1, child)
    8080          <
    8181          ProblemInstance.GetDistance(
    82           child[i] + 1, parent2[(i + 1) % child.Length] + 1)) {
     82          child[i] + 1, parent2[(i + 1) % child.Length] + 1, child)) {
    8383          child[(i + 1) % child.Length] = parent1[(i + 1) % child.Length];
    8484          Swap(parent2, parent2[(i + 1) % child.Length], parent1[(i + 1) % child.Length]);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/Crossovers/ZhuHeuristicCrossover2.cs

    r6771 r6851  
    7979
    8080        if (ProblemInstance.GetDistance(
    81          child[i] + 1, p1[parent1Index] + 1)
     81         child[i] + 1, p1[parent1Index] + 1, child)
    8282         <
    8383         ProblemInstance.GetDistance(
    84          child[i] + 1, p2[parent2Index] + 1)) {
     84         child[i] + 1, p2[parent2Index] + 1, child)) {
    8585          child[(i + 1) % child.Length] = p1[parent1Index];
    8686        } else {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r6838 r6851  
    170170    <Compile Include="Encodings\Alba\Moves\ThreeOpt\AlbaStochasticTranslocationSingleMoveGenerator.cs" />
    171171    <Compile Include="Encodings\Alba\Moves\ThreeOpt\IAlbaTranslocationMoveOperator.cs" />
     172    <Compile Include="Encodings\ExtendedPotvin\Creators\ExtendedPotvinCreator.cs" />
     173    <Compile Include="Encodings\ExtendedPotvin\Crossovers\ExtendedPotvinCrossover.cs" />
     174    <Compile Include="Encodings\ExtendedPotvin\IExtendedPotvinOperator.cs" />
     175    <Compile Include="Encodings\ExtendedPotvin\ExtendedPotvinEncoding.cs" />
     176    <Compile Include="Encodings\ExtendedPotvin\Manipulators\ExtendedPotvinManipulator.cs" />
    172177    <Compile Include="Encodings\General\Creators\MultiVRPSolutionCreator.cs" />
    173178    <Compile Include="Encodings\General\Creators\VRPCreator.cs" />
     
    202207    <Compile Include="Encodings\GVR\Manipulators\GVRManipulator.cs" />
    203208    <Compile Include="Encodings\GVR\Manipulators\GVRSwapManipulator.cs" />
    204     <Compile Include="Encodings\Potvin\Creators\PushForwardInsertionCreator.cs" />
     209    <Compile Include="Encodings\ExtendedPotvin\Creators\PushForwardInsertionCreator.cs" />
    205210    <Compile Include="Encodings\Potvin\Creators\PotvinCreator.cs" />
    206     <Compile Include="Encodings\Potvin\Creators\IterativeInsertionCreator.cs" />
     211    <Compile Include="Encodings\ExtendedPotvin\Creators\IterativeInsertionCreator.cs" />
    207212    <Compile Include="Encodings\Potvin\Crossovers\PotvinCrossover.cs" />
    208213    <Compile Include="Encodings\Potvin\Crossovers\PotvinInsertionBasedCrossover.cs" />
     
    292297    <Compile Include="Interfaces\IVRPEncoding.cs" />
    293298    <Compile Include="Interfaces\IVRPProblemInstance.cs" />
     299    <Compile Include="Parsers\CordeauParser.cs" />
    294300    <Compile Include="Parsers\LiLimParser.cs" />
     301    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPEvaluator.cs" />
     302    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPProblemInstance.cs" />
     303    <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPProblemInstance.cs" />
     304    <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPEvaluator.cs" />
    295305    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWProblemInstance.cs" />
    296306    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWEvaluation.cs" />
    297307    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWEvaluator.cs" />
     308    <Compile Include="ProblemInstances\SingleDepotVRP\SingleDepotVRPEvaluator.cs" />
    298309    <Compile Include="SolutionParser.cs" />
    299310    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedProblemInstance.cs" />
    300311    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedOperator.cs" />
    301     <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedEncoding.cs" />
    302312    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedOperator.cs" />
    303313    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedProblemInstance.cs" />
     
    305315    <Compile Include="Variants\Capacitated\ICapacitatedOperator.cs" />
    306316    <Compile Include="Variants\General\IGeneralVRPOperator.cs" />
     317    <Compile Include="Variants\MultiDepot\IMultiDepotOperator.cs" />
     318    <Compile Include="Variants\MultiDepot\IMultiDepotProblemInstance.cs" />
    307319    <Compile Include="Variants\PickupAndDelivery\IPickupAndDeliveryOperator.cs" />
    308320    <Compile Include="Variants\PickupAndDelivery\IPickupAndDeliveryProblemInstance.cs" />
     
    318330    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPTWEvaluator.cs" />
    319331    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPEvaluator.cs" />
    320     <Compile Include="ProblemInstances\SingleDepotVRP\SingleDepotVRPEvaluator.cs" />
    321332    <Compile Include="ProblemInstances\VRPEvaluator.cs" />
    322333    <Compile Include="ProblemInstances\VRPEvaluation.cs" />
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEncoding.cs

    r4363 r6851  
    2929  public interface IVRPEncoding: IItem {
    3030    List<Tour> GetTours();
     31    int GetTourIndex(Tour tour);
     32    int GetVehicleAssignment(int tour);
    3133  }
    3234}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs

    r6838 r6851  
    3535    VRPEvaluation EvaluateTour(IVRPProblemInstance instance, Tour tour, IVRPEncoding solution);
    3636    bool Feasible(VRPEvaluation evaluation);
    37     double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
     37    double GetInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
    3838  }
    3939}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs

    r6838 r6851  
    4848    DoubleValue DistanceFactor { get; }
    4949
    50     double GetDistance(int start, int end);
     50    double[] GetCoordinates(int city);
     51    double GetDemand(int city);
     52    double GetDistance(int start, int end, IVRPEncoding solution);
     53    double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution);
    5154    bool Feasible(IVRPEncoding solution);
    5255    bool TourFeasible(Tour tour, IVRPEncoding solution);
     
    5457    VRPEvaluation EvaluateTour(Tour tour, IVRPEncoding solution);
    5558    bool Feasible(VRPEvaluation eval);
    56     double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
     59    double GetInsertionCosts(VRPEvaluation eval, IVRPEncoding solution, int customer, int tour, int index, out bool feasible);
    5760  }
    5861}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

    r6838 r6851  
    3838  [Item("CVRPEvaluator", "Represents a single depot CVRP evaluator.")]
    3939  [StorableClass]
    40   public class CVRPEvaluator: SingleDepotVRPEvaluator {
     40  public class CVRPEvaluator: VRPEvaluator {
    4141    public ILookupParameter<DoubleValue> OverloadParameter {
    4242      get { return (ILookupParameter<DoubleValue>)Parameters["Overload"]; }
     
    7979
    8080        //drive there
    81         double currentDistace = instance.GetDistance(start, end);
     81        double currentDistace = instance.GetDistance(start, end, solution);
    8282        distance += currentDistace;
    8383
     
    103103    }
    104104
    105     protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     105    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
    106106      out bool feasible) {
    107107      CVRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPInsertionInfo;
     
    113113      double overloadPenalty = cvrp.OverloadPenalty.Value;
    114114
    115       double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     115      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
    116116      double newDistance =
    117         instance.GetDistance(insertionInfo.Start, customer) +
    118         instance.GetDistance(customer, insertionInfo.End);
     117        instance.GetDistance(insertionInfo.Start, customer, solution) +
     118        instance.GetDistance(customer, insertionInfo.End, solution);
    119119      costs += instance.DistanceFactor.Value * (newDistance - distance);
    120120
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs

    r6838 r6851  
    8585
    8686        //drive there
    87         double currentDistace = vrptw.GetDistance(start, end);
     87        double currentDistace = vrptw.GetDistance(start, end, solution);
    8888        time += currentDistace;
    8989        distance += currentDistace;
     
    166166    }
    167167
    168     protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     168    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
    169169      out bool feasible) {
    170170      CVRPPDTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPPDTWInsertionInfo;
     
    187187      double pickupPenalty = pdp.PickupViolationPenalty.Value;
    188188
    189       double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     189      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
    190190      double newDistance =
    191         instance.GetDistance(insertionInfo.Start, customer) +
    192         instance.GetDistance(customer, insertionInfo.End);
     191        instance.GetDistance(insertionInfo.Start, customer, solution) +
     192        instance.GetDistance(customer, insertionInfo.End, solution);
    193193      costs += instance.DistanceFactor.Value * (newDistance - distance);
    194194
     
    215215      if (index > 0)
    216216        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
    217       time += instance.GetDistance(insertionInfo.Start, customer);
     217      time += instance.GetDistance(insertionInfo.Start, customer, solution);
    218218      if (time > dueTime[customer]) {
    219219        tardiness += time - dueTime[customer];
     
    222222        time += readyTime[customer] - time;
    223223      time += serviceTimes[customer];
    224       time += instance.GetDistance(customer, insertionInfo.End);
     224      time += instance.GetDistance(customer, insertionInfo.End, solution);
    225225
    226226      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs

    r6838 r6851  
    9292
    9393        //drive there
    94         double currentDistace = vrptw.GetDistance(start, end);
     94        double currentDistace = vrptw.GetDistance(start, end, solution);
    9595        time += currentDistace;
    9696        distance += currentDistace;
     
    150150    }
    151151
    152     protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     152    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
    153153      out bool feasible) {
    154154      CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;
     
    166166      double tardinessPenalty = vrptw.TardinessPenalty.Value;
    167167
    168       double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     168      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
    169169      double newDistance =
    170         instance.GetDistance(insertionInfo.Start, customer) +
    171         instance.GetDistance(customer, insertionInfo.End);
     170        instance.GetDistance(insertionInfo.Start, customer, solution) +
     171        instance.GetDistance(customer, insertionInfo.End, solution);
    172172      costs += instance.DistanceFactor.Value * (newDistance - distance);
    173173
     
    186186      if (index > 0)
    187187        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
    188       time += instance.GetDistance(insertionInfo.Start, customer);
     188      time += instance.GetDistance(insertionInfo.Start, customer, solution);
    189189      if (time > dueTime[customer]) {
    190190        tardiness += time - dueTime[customer];
     
    193193        time += readyTime[customer] - time;
    194194      time += serviceTimes[customer];
    195       time += instance.GetDistance(customer, insertionInfo.End);
     195      time += instance.GetDistance(customer, insertionInfo.End, solution);
    196196
    197197      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs

    r6838 r6851  
    5757
    5858        //drive there
    59         double currentDistace = instance.GetDistance(start, end);
     59        double currentDistace = instance.GetDistance(start, end, solution);
    6060        distance += currentDistace;
    6161
     
    7575    }
    7676
    77     protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     77    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
    7878      out bool feasible) {
    7979      StopInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index);
     
    8282      feasible = true;
    8383
    84       double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     84      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
    8585      double newDistance =
    86         instance.GetDistance(insertionInfo.Start, customer) +
    87         instance.GetDistance(customer, insertionInfo.End);
     86        instance.GetDistance(insertionInfo.Start, customer, solution) +
     87        instance.GetDistance(customer, insertionInfo.End, solution);
    8888
    8989      costs += instance.DistanceFactor.Value * (newDistance - distance);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs

    r6838 r6851  
    103103    }
    104104
    105     protected abstract double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible);
     105    protected abstract double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible);
    106106
    107     public double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
     107    public double GetInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
    108108      bool tourFeasible;
    109109      double costs = GetTourInsertionCosts(
    110110        instance,
     111        solution,
    111112        eval.InsertionInfo.GetTourInsertionInfo(tour), index,
    112113        customer, out tourFeasible);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

    r6838 r6851  
    188188    }
    189189
     190    public virtual double[] GetCoordinates(int city) {
     191      double[] coordinates = new double[Coordinates.Columns];
     192
     193      for (int i = 0; i < Coordinates.Columns; i++) {
     194        coordinates[i] = Coordinates[city, i];
     195      }
     196
     197      return coordinates;
     198    }
     199
     200    public virtual double GetDemand(int city) {
     201      return Demand[city];
     202    }
     203
    190204    //cache for performance improvement
    191205    private DoubleMatrix distanceMatrix = null;
    192206    private IVRPEvaluator evaluator = null;
    193207
    194     public double GetDistance(int start, int end) {
     208    public virtual double GetDistance(int start, int end, IVRPEncoding solution) {
    195209      double distance = 0.0;
    196210      if (distanceMatrix == null && UseDistanceMatrix.Value) {
     
    206220    }
    207221
     222    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution) {
     223      double distance = GetDistance(start, end, solution);
     224      double newDistance =
     225        GetDistance(start, customer, solution) +
     226        GetDistance(customer, end, solution);
     227
     228      return newDistance - distance;
     229    }
     230
    208231    public bool Feasible(IVRPEncoding solution) {
    209232      return evaluator.Feasible(
     
    230253    }
    231254
    232     public double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
    233       return evaluator.GetInsertionCosts(this, eval, customer, tour, index, out feasible);
     255    public double GetInsertionCosts(VRPEvaluation eval, IVRPEncoding solution, int customer, int tour, int index, out bool feasible) {
     256      return evaluator.GetInsertionCosts(this, solution, eval, customer, tour, index, out feasible);
    234257    }
    235258
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs

    r6710 r6851  
    243243    #endregion
    244244
     245    public void ImportFromCordeau(string cordeauFileName) {
     246      CordeauParser parser = new CordeauParser(cordeauFileName);
     247      parser.Parse();
     248
     249      MDCVRPProblemInstance problem = new MDCVRPProblemInstance();
     250
     251      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
     252      problem.Vehicles.Value = parser.Vehicles;
     253      problem.Capacity = new DoubleArray(parser.Capacity);
     254      problem.Demand = new DoubleArray(parser.Demands);
     255      problem.Depots.Value = parser.Depots;
     256      problem.VehicleDepotAssignment = new IntArray(parser.Vehicles);
     257      int depot = 0;
     258      int i = 0;
     259      while(i < parser.Vehicles) {
     260        problem.VehicleDepotAssignment[i] = depot;
     261
     262        i++;
     263        if (i % (parser.Vehicles / parser.Depots) == 0)
     264          depot++;
     265      }
     266
     267      this.ProblemInstance = problem;
     268
     269      OnReset();
     270    }
     271
    245272    public void ImportFromLiLim(string liLimFileName) {
    246273      LiLimParser parser = new LiLimParser(liLimFileName);
    247274      parser.Parse();
    248      
     275
    249276      CVRPPDTWProblemInstance problem = new CVRPPDTWProblemInstance();
    250277
     
    372399        } else {
    373400          problem.Demand[i] = rand.Next(10, 50);
    374           problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i)), 1200);
     401          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
    375402          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
    376403          problem.ServiceTime[i] = 90;
Note: See TracChangeset for help on using the changeset viewer.