Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7821


Ignore:
Timestamp:
05/15/12 10:42:00 (12 years ago)
Author:
svonolfe
Message:

Worked on VRP path relinking (#1331)

Location:
branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs

    r7259 r7821  
    101101    }
    102102
    103     public static void Apply(AlbaEncoding solution, int maxIterations,
     103    public static void Apply(AlbaEncoding solution, int maxIterations, bool firstImprovement,
    104104      int lambda, int samples, IRandom random, ref double quality, out int evaluatedSolutions,
    105105      DoubleMatrix distanceMatrix, IntValue vehicles, DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime,
     
    110110
    111111      evaluatedSolutions = 0;
     112
     113      if (quality == -1) {
     114        quality = VRPEvaluator.Evaluate(solution, vehicles, dueTime, serviceTime, readyTime,
     115          demand, capacity, fleetUsageFactor, timeFactor, distanceFactor,
     116          overloadPenalty, tardinessPenalty, coordinates,
     117          distanceMatrixParameter, useDistanceMatrix).Quality;
     118        evaluatedSolutions++;
     119      }
    112120
    113121      for (int i = 0; i < maxIterations; i++) {
     
    126134
    127135          evaluatedSolutions++;
    128           if (moveQuality < quality || quality == -1) {
     136          if (moveQuality < quality) {
    129137            quality = moveQuality;
    130138            bestMove = move;
     139
     140            if (firstImprovement)
     141              break;
    131142          }
    132143        }
     
    155166      int evaluatedSolutions;
    156167
    157       Apply(solution, maxIterations, lambda, samples, random, ref quality, out evaluatedSolutions,
     168      Apply(solution, maxIterations, false, lambda, samples, random, ref quality, out evaluatedSolutions,
    158169        problem.DistanceMatrix, problem.Vehicles, problem.DueTime, problem.ServiceTime,
    159170        problem.ReadyTime, problem.Demand, problem.Capacity, problem.Coordinates,
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Improvers/VRPImprovementOperator.cs

    r7793 r7821  
    146146      int evaluatedSolutions;
    147147
    148       AlbaLambdaInterchangeLocalImprovementOperator.Apply(solution, ImprovementAttemptsParameter.Value.Value, LambdaParameter.Value.Value,
     148      AlbaLambdaInterchangeLocalImprovementOperator.Apply(solution, ImprovementAttemptsParameter.Value.Value, true, LambdaParameter.Value.Value,
    149149        SampleSizeParameter.Value.Value, RandomParameter.ActualValue, ref quality, out evaluatedSolutions, DistanceMatrixParameter.ActualValue,
    150150        VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

    r7815 r7821  
    159159      Parameters.Add(new LookupParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation."));
    160160      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    161       Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(250)));
     161      Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(10)));
    162162      Parameters.Add(new ValueParameter<IntValue>("Iterations", new IntValue(50)));
    163163    }
     
    208208
    209209    #region moves
     210    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
     211      List<int> cities = new List<int>();
     212      foreach (Tour tour in initiator.Tours) {
     213        foreach (int city in tour.Cities) {
     214          Tour guideTour = guide.Tours.First(t => t.Cities.Contains(city));
     215          if (guide.Tours.IndexOf(guideTour) != initiator.Tours.IndexOf(tour)) {
     216            cities.Add(city);
     217          }
     218        }
     219      }
     220
     221      if (cities.Count == 0) {
     222        RelocateMove(initiator, random);
     223      } else {
     224        int city = cities[random.Next(cities.Count)];
     225        Tour tour = initiator.Tours.First(t => t.Cities.Contains(city));
     226        tour.Cities.Remove(city);
     227
     228        Tour guideTour = guide.Tours.First(t => t.Cities.Contains(city));
     229        int guideTourIndex = guide.Tours.IndexOf(guideTour);
     230
     231        if (guideTourIndex < initiator.Tours.Count) {
     232          Tour tour2 = initiator.Tours[guideTourIndex];
     233
     234          int guideIndex = guideTour.Cities.IndexOf(city);
     235          if (guideIndex == 0) {
     236            tour2.Cities.Insert(0, city);
     237          } else {
     238            int predecessor = guideTour.Cities[guideIndex - 1];
     239            int initIndex = tour2.Cities.IndexOf(predecessor);
     240            if (initIndex != -1) {
     241              tour2.Cities.Insert(initIndex + 1, city);
     242            } else {
     243              if (guideIndex == guideTour.Cities.Count - 1) {
     244                tour2.Cities.Insert(tour2.Cities.Count, city);
     245              } else {
     246                int sucessor = guideTour.Cities[guideIndex + 1];
     247                initIndex = tour2.Cities.IndexOf(sucessor);
     248                if (initIndex != -1) {
     249                  tour2.Cities.Insert(initIndex, city);
     250                } else {
     251                  tour2.Cities.Insert(random.Next(tour2.Cities.Count + 1), city);
     252                }
     253              }
     254            }
     255          }
     256        } else {
     257          Tour tour2 = new Tour();
     258          tour2.Cities.Add(city);
     259          initiator.Tours.Add(tour2);
     260        }
     261
     262        if (tour.Cities.Count == 0)
     263          initiator.Tours.Remove(tour);
     264      }
     265    }
     266
    210267    public static void RelocateMove(PotvinEncoding individual, IRandom random) {
    211268      int cities = individual.Cities;
     
    305362    }
    306363
    307     public static void TwoOptStartMove(PotvinEncoding individual, IRandom random) {
     364    public static void TwoOptStarMove(PotvinEncoding individual, IRandom random) {
    308365      //consider creating new tour
    309366      individual.Tours.Add(new Tour());
     
    411468            PotvinEncoding next = current.Clone() as PotvinEncoding;
    412469
    413             int neighborhood = rand.Next(5);
     470            int neighborhood = rand.Next(2);
    414471            switch (neighborhood) {
    415               case 0: RelocateMove(next, rand);
     472              case 0: GuidedRelocateMove(next, guide, rand);
    416473                break;
    417               case 1: ExchangeMove(next, rand);
     474              case 1: TwoOptMove(next, rand);
    418475                break;
    419               case 2: TwoOptMove(next, rand);
     476              case 2: TwoOptStarMove(next, rand);
    420477                break;
    421               case 3: TwoOptStartMove(next, rand);
     478              case 3: OrOptMove(next, rand);
    422479                break;
    423               case 4: OrOptMove(next, rand);
     480              case 4: ExchangeMove(next, rand);
    424481                break;
    425482            }
     483
     484            next = MatchTours(next, guide);
    426485
    427486            TourEvaluation nextEval = VRPEvaluator.Evaluate(next,
Note: See TracChangeset for help on using the changeset viewer.