Free cookie consent management tool by TermsFeed Policy Generator

Changeset 4174


Ignore:
Timestamp:
08/06/10 16:08:46 (14 years ago)
Author:
svonolfe
Message:

Refactored VRP, added some Potvin operators (WIP) (#1039)

Location:
trunk/sources
Files:
5 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.VehicleRouting.Views/3.3/VRPSolutionView.cs

    r4154 r4174  
    138138                foreach (Tour tour in Content.Solution.Tours) {
    139139                  double t = 0.0;
    140                   Point[] tourPoints = new Point[tour.Count + 2];
     140                  Point[] tourPoints = new Point[tour.Cities.Count + 2];
    141141                  int lastCustomer = 0;
    142142
    143                   for (int i = -1; i <= tour.Count; i++) {
     143                  for (int i = -1; i <= tour.Cities.Count; i++) {
    144144                    int location = 0;
    145145
    146                     if (i == -1 || i == tour.Count)
     146                    if (i == -1 || i == tour.Cities.Count)
    147147                      location = 0; //depot
    148148                    else
    149                       location = tour[i].Value;
     149                      location = tour.Cities[i];
    150150
    151151                    Point locationPoint = new Point(border + ((int)((coordinates[location, 0] - xMin) * xStep)),
    … …  
    153153                    tourPoints[i + 1] = locationPoint;
    154154
    155                     if (i != -1 && i != tour.Count) {
     155                    if (i != -1 && i != tour.Cities.Count) {
    156156                      Brush customerBrush = Brushes.Black;
    157157

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/AlbaEncoding.cs

    r4150 r4174  
    4242        for (int i = 0; i < this.array.Length; i++) {
    4343          if (this.array[i] >= cities) {
    44             if (tour.Count > 0) {
     44            if (tour.Cities.Count > 0) {
    4545              result.Add(tour);
    4646
    … …  
    4848            }
    4949          } else {
    50             tour.Add(new IntValue(this.array[i] + 1));
     50            tour.Cities.Add(this.array[i] + 1);
    5151          }
    5252        }
    5353
    54         if (tour.Count > 0) {
     54        if (tour.Cities.Count > 0) {
    5555          result.Add(tour);
    5656        }
    … …  
    9797      int cities = 0;
    9898      foreach (Tour tour in tours) {
    99         cities += tour.Count;
     99        cities += tour.Cities.Count;
    100100      }
    101101
    … …  
    107107
    108108      foreach (Tour tour in tours) {
    109         foreach (IntValue city in tour) {
    110             array[arrayIndex] = city.Value - 1;
     109        foreach (int city in tour.Cities) {
     110            array[arrayIndex] = city - 1;
    111111            arrayIndex++;
    112112        }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/PotvinEncoding.cs

    r4150 r4174  
    3131  [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions.")]
    3232  [StorableClass]
    33   class PotvinEncoding : Item, IVRPEncoding {
     33  public class PotvinEncoding : Item, IVRPEncoding {
    3434    public override Image ItemImage {
    3535      get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Class; }
    … …  
    4646
    4747        foreach (Tour tour in Tours) {
    48           cities += tour.Count;
     48          cities += tour.Cities.Count;
    4949        }
    5050
    … …  
    5555
    5656    [Storable]
    57     public ItemList<IntValue> Unrouted { get; set; }
     57    public List<int> Unrouted { get; set; }
    5858
    5959    public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
    … …  
    6161      cloner.RegisterClonedObject(this, clone);
    6262      clone.Tours = (ItemList<Tour>)cloner.Clone(this.Tours);
    63       clone.Unrouted = (ItemList<IntValue>)cloner.Clone(this.Unrouted);
     63      clone.Unrouted = new List<int>(Unrouted);
    6464      return clone;
    6565    }
    … …  
    6767    public PotvinEncoding() {
    6868      Tours = new ItemList<Tour>();
    69       Unrouted = new ItemList<IntValue>();
     69      Unrouted = new List<int>();
    7070    }
    7171   
    … …  
    8585      for (int i = 0; i < route.Count; i++) {
    8686        if (route[i] == 0) {
    87           if (tour.Count > 0) {
     87          if (tour.Cities.Count > 0) {
    8888            solution.Tours.Add(tour);
    8989            tour = new Tour();
    9090          }
    9191        } else {
    92           tour.Add(new IntValue(route[i]));
     92          tour.Cities.Add(route[i]);
    9393        }
    9494      }
    … …  
    9696      return solution;
    9797    }
     98
     99    public bool FindInsertionPlace(
     100      DoubleArray dueTimeArray,
     101      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     102      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix,
     103      int city, int routeToAvoid, out int route, out int place) {
     104      route = -1;
     105      place = -1;
     106      double minDetour = 0;
     107
     108      for (int tour = 0; tour < Tours.Count; tour++) {
     109        if (tour != routeToAvoid) {
     110          for (int i = 0; i <= Tours[tour].Cities.Count; i++) {
     111            double length = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
     112
     113            Tours[tour].Cities.Insert(i, city);
     114
     115            if (Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     116              capacity, coordinates, distanceMatrix, useDistanceMatrix)) {
     117              double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
     118
     119              double detour = newLength - length;
     120
     121              if (route <= 0 || detour < minDetour) {
     122                route = tour;
     123                place = i;
     124                minDetour = detour;
     125              }
     126            }
     127
     128            Tours[tour].Cities.RemoveAt(i);
     129          }
     130        }
     131      }
     132
     133      return route >= 0 && place >= 0;
     134    }
    98135  }
    99136}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Tour.cs

    r4068 r4174  
    2222using HeuristicLab.Core;
    2323using HeuristicLab.Data;
     24using System.Collections.Generic;
     25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Common;
    2427
    2528namespace HeuristicLab.Problems.VehicleRouting.Encodings {
    26   public class Tour : ItemList<IntValue> {
     29  [StorableClass]
     30  public class Tour : Item {
     31    [Storable]
     32    public List<int> Cities { get; private set; }
     33
     34    public Tour() {
     35      Cities = new List<int>();
     36    }
     37
     38    public override IDeepCloneable Clone(Cloner cloner) {
     39      Tour clone = base.Clone(cloner) as Tour;
     40      clone.Cities = new List<int>(Cities);
     41
     42      return clone;
     43    }
     44
     45    public bool Feasible(DoubleArray dueTimeArray,
     46      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     47      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
     48      TourEvaluation eval = VRPEvaluator.EvaluateTour(this,
     49        dueTimeArray,
     50        serviceTimeArray,
     51        readyTimeArray,
     52        demandArray,
     53        capacity,
     54        new DoubleValue(0),
     55        new DoubleValue(0),
     56        new DoubleValue(0),
     57        new DoubleValue(1),
     58        new DoubleValue(1),
     59        coordinates,
     60        distanceMatrix,
     61        useDistanceMatrix);
     62
     63      return eval.Overload < double.Epsilon && eval.Tardiness < double.Epsilon;
     64    }
     65   
     66    public double GetLength(DoubleMatrix coordinates,
     67      ILookupParameter<DoubleMatrix> distanceMatrix,
     68      BoolValue useDistanceMatrix) {
     69      double length = 0;
     70
     71      if (Cities.Count > 0) {
     72        List<int> cities = new List<int>();
     73        cities.Add(0);
     74        foreach (int city in Cities) {
     75          cities.Add(city);
     76        }
     77        cities.Add(0);
     78
     79        for (int i = 1; i < cities.Count; i++) {
     80          length += VRPUtilities.GetDistance(
     81            cities[i - 1], cities[i], coordinates, distanceMatrix, useDistanceMatrix);
     82        }
     83      }
     84
     85      return length;
     86    }
    2787  }
    2888}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Evaluators/VRPEvaluator.cs

    r4154 r4174  
    104104    }
    105105
    106     private static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
     106    internal static TourEvaluation EvaluateTour(Tour tour, DoubleArray dueTimeArray,
    107107      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
    108108      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
    … …  
    122122
    123123      //simulate a tour, start and end at depot
    124       for (int i = 0; i <= tour.Count; i++) {
     124      for (int i = 0; i <= tour.Cities.Count; i++) {
    125125        int start = 0;
    126126        if(i > 0)
    127           start = tour[i - 1].Value;
     127          start = tour.Cities[i - 1];
    128128        int end = 0;
    129         if(i < tour.Count)
    130           end = tour[i].Value;
     129        if (i < tour.Cities.Count)
     130          end = tour.Cities[i];
    131131
    132132        //drive there

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/HeuristicLab.Problems.VehicleRouting-3.3.csproj

    r4154 r4174  
    107107  <ItemGroup>
    108108    <Compile Include="Analyzers\BestVRPSolutionAnalyzer.cs" />
     109    <Compile Include="Encodings\Potvin\Crossovers\PotvinSBXCrossover.cs" />
     110    <Compile Include="Encodings\Potvin\Crossovers\PotvinCrossover.cs" />
     111    <Compile Include="Encodings\Potvin\Manipulators\Potvin2MManipulator.cs" />
     112    <Compile Include="Encodings\Potvin\Manipulators\Potvin1MManipulator.cs" />
     113    <Compile Include="Encodings\Potvin\Manipulators\PotvinManipulator.cs" />
    109114    <Compile Include="VRPUtilities.cs" />
    110115    <Compile Include="VRPOperator.cs" />
    … …  
    222227    </BootstrapperPackage>
    223228  </ItemGroup>
    224   <ItemGroup>
    225     <Folder Include="Encodings\Potvin\Crossovers\" />
    226     <Folder Include="Encodings\Potvin\Manipulators\" />
    227   </ItemGroup>
     229  <ItemGroup />
    228230  <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
    229231  <!-- To modify your build process, add your task inside one of the targets below and uncomment it.

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/VRPOperator.cs

    r4154 r4174  
    2424using HeuristicLab.Parameters;
    2525using HeuristicLab.Data;
     26using HeuristicLab.Problems.VehicleRouting.Encodings;
    2627
    2728namespace HeuristicLab.Problems.VehicleRouting {
    … …  
    7172      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
    7273    }
     74
     75    protected bool Feasible(Tour tour) {
     76      return tour.Feasible(
     77                  DueTimeParameter.ActualValue,
     78                  ServiceTimeParameter.ActualValue,
     79                  ReadyTimeParameter.ActualValue,
     80                  DemandParameter.ActualValue,
     81                  CapacityParameter.ActualValue,
     82                  CoordinatesParameter.ActualValue,
     83                  DistanceMatrixParameter,
     84                  UseDistanceMatrixParameter.ActualValue);
     85    }
     86
     87    protected double GetLength(Tour tour) {
     88      return tour.GetLength(
     89                CoordinatesParameter.ActualValue,
     90                DistanceMatrixParameter,
     91                UseDistanceMatrixParameter.ActualValue);
     92    }
    7393  }
    7494}
Note: See TracChangeset for help on using the changeset viewer.