Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/20/11 13:36:49 (14 years ago)
Author:
svonolfe
Message:

Improved performance of many VRP operators by optimizing the parameter lookup (#1561)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/PushForwardInsertionCreator.cs

    r5445 r6449  
    9191    }
    9292
    93     private double CalculateDistance(int start, int end) {
     93    private double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
    9494      double distance = 0.0;
    95       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    9695
    9796      distance =
    … …  
    103102    }
    104103
    105     private DoubleMatrix CreateDistanceMatrix() {
    106       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     104    private DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates) {
    107105      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
    108106
    109107      for (int i = 0; i < distanceMatrix.Rows; i++) {
    110108        for (int j = i; j < distanceMatrix.Columns; j++) {
    111           double distance = CalculateDistance(i, j);
     109          double distance = CalculateDistance(i, j, coordinates);
    112110
    113111          distanceMatrix[i, j] = distance;
    … …  
    119117    }
    120118
    121     private double Distance(int start, int end) {
     119    private double Distance(int start, int end, DoubleMatrix coordinates, bool useDistanceMatrix) {
    122120      double distance = 0.0;
    123121
    124       if (UseDistanceMatrixParameter.ActualValue.Value) {
    125         if (DistanceMatrixParameter.ActualValue == null) {
    126           DistanceMatrixParameter.ActualValue = CreateDistanceMatrix();
    127         }
    128 
    129         distance = DistanceMatrixParameter.ActualValue[start, end];
    130       } else {
    131         distance = CalculateDistance(start, end);
     122      if (useDistanceMatrix) {
     123        distance = coordinates[start, end];
     124      } else { 
     125        distance = CalculateDistance(start, end, coordinates);
    132126      }
    133127
    … …  
    135129    }
    136130
    137     private double TravelDistance(List<int> route, int begin) {
     131    private double TravelDistance(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix) {
    138132      double distance = 0;
    139133      for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
    140         distance += Distance(route[i], route[i + 1]);
     134        distance += Distance(route[i], route[i + 1], coordinates, useDistanceMatrix);
    141135      }
    142136      return distance;
    143137    }
    144138
    145     private bool SubrouteConstraintsOK(List<int> route, int begin) {
     139    private bool SubrouteConstraintsOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
     140      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
    146141      double t = 0.0, o = 0.0;
    147142      for (int i = begin + 1; i < route.Count; i++) {
    148         t += Distance(route[i - 1], route[i]);
     143        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
    149144        if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
    150145        else {
    151           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    152           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    153           t += ServiceTimeParameter.ActualValue[route[i]];
    154           o += DemandParameter.ActualValue[route[i]];
    155           if (o > CapacityParameter.ActualValue.Value) return false; // premature exit on capacity constraint violation
     146          if (t > dueTime[route[i]]) return false;
     147          t = Math.Max(readyTime[route[i]], t);
     148          t += serviceTime[route[i]];
     149          o += demand[route[i]];
     150          if (o > capacity.Value) return false; // premature exit on capacity constraint violation
    156151        }
    157152      }
    … …  
    159154    }
    160155
    161     private bool SubrouteTardinessOK(List<int> route, int begin) {
     156    private bool SubrouteTardinessOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
     157      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime) {
    162158      double t = 0.0;
    163159      for (int i = begin + 1; i < route.Count; i++) {
    164         t += Distance(route[i - 1], route[i]);
     160        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
    165161        if (route[i] == 0) {
    166           if (t < DueTimeParameter.ActualValue[0]) return true;
     162          if (t < dueTime[0]) return true;
    167163          else return false;
    168164        } else {
    169           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    170           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    171           t += ServiceTimeParameter.ActualValue[route[i]];
     165          if (t > dueTime[route[i]]) return false;
     166          t = Math.Max(readyTime[route[i]], t);
     167          t += serviceTime[route[i]];
    172168        }
    173169      }
    … …  
    175171    }
    176172
    177     private bool SubrouteLoadOK(List<int> route, int begin) {
     173    private bool SubrouteLoadOK(List<int> route, int begin, DoubleValue capacity, DoubleArray demand) {
    178174      double o = 0.0;
    179175      for (int i = begin + 1; i < route.Count; i++) {
    180         if (route[i] == 0) return (o < CapacityParameter.ActualValue.Value);
     176        if (route[i] == 0) return (o < capacity.Value);
    181177        else {
    182           o += DemandParameter.ActualValue[route[i]];
    183         }
    184       }
    185       return (o < CapacityParameter.ActualValue.Value);
     178          o += demand[route[i]];
     179        }
     180      }
     181      return (o < capacity.Value);
    186182    }
    187183
    188184    protected override List<int> CreateSolution() {
    189       double alpha, beta, gamma;
    190       alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
    191       beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
    192       gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
     185      //double alpha, beta, gamma;
     186      double alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
     187      double beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
     188      double gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
    193189
    194190      double x0 = CoordinatesParameter.ActualValue[0, 0];
    … …  
    203199      int indexOfCustomer = -1;
    204200
     201      int vehicles = VehiclesParameter.ActualValue.Value;
     202      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     203      DoubleArray dueTime = DueTimeParameter.ActualValue;
     204      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     205      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     206      DoubleArray demand = DemandParameter.ActualValue;
     207      DoubleValue capacity = CapacityParameter.ActualValue;
     208
     209      bool useDistanceMatrix = UseDistanceMatrixParameter.ActualValue.Value;
     210      if (useDistanceMatrix) {
     211        if (DistanceMatrixParameter.ActualValue == null) {
     212          DistanceMatrixParameter.ActualValue = CreateDistanceMatrix(coordinates);
     213        }
     214
     215        coordinates = DistanceMatrixParameter.ActualValue;
     216      }
     217
    205218      /*-----------------------------------------------------------------------------
    206219       * generate cost list
    … …  
    208221       */
    209222      for (int i = 1; i <= Cities; i++) {
    210         distance = Distance(i, 0);
    211         if (CoordinatesParameter.ActualValue[i, 0] < x0) distance = -distance;
     223        distance = Distance(i, 0, coordinates, useDistanceMatrix);
     224        if (coordinates[i, 0] < x0) distance = -distance;
    212225        cost = -alpha * distance + // distance 0 <-> City[i]
    213226                 beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
    214                  gamma * (Math.Asin((CoordinatesParameter.ActualValue[i, 1] - y0) / distance) / 360 * distance); // polar angle
     227                 gamma * (Math.Asin((coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
    215228
    216229        index = 0;
    … …  
    229242      int customer = -1;
    230243      int subTourCount = 1;
    231       List<int> route = new List<int>(Cities + VehiclesParameter.ActualValue.Value - 1);
     244
     245      List<int> route = new List<int>(Cities + vehicles - 1);
    232246      minimumCost = double.MaxValue;
    233247      indexOfMinimumCost = -1;
    … …  
    244258            route.Insert(i, (int)unroutedList[c]);
    245259            if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
    246             cost = TravelDistance(route, currentRoute);
    247             if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute)) {
     260            cost = TravelDistance(route, currentRoute, coordinates, useDistanceMatrix);
     261            if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute, coordinates, useDistanceMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
    248262              minimumCost = cost;
    249263              indexOfMinimumCost = i;
    … …  
    275289        customer = -1;
    276290      } while (unroutedList.Count > 0);
    277       while (route.Count < Cities + VehiclesParameter.ActualValue.Value - 1)
     291      while (route.Count < Cities + vehicles)
    278292        route.Add(0);
    279293
Note: See TracChangeset for help on using the changeset viewer.