1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using HeuristicLab.Core;


23  using HeuristicLab.Data;


24  using HeuristicLab.Operators;


25  using HeuristicLab.Optimization;


26  using HeuristicLab.Parameters;


27  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


28  using HeuristicLab.Common;


29  using HeuristicLab.Problems.VehicleRouting.ProblemInstances;


30  using HeuristicLab.Problems.VehicleRouting.Interfaces;


31  using HeuristicLab.Problems.VehicleRouting.Variants;


32  using System.Collections.Generic;


33 


34  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {


35  [Item("PotvinPDShiftMoveMaker", "Peforms the shift move on a given PDP encoding and updates the quality.")]


36  [StorableClass]


37  public class PotvinPDShiftMoveMaker : PotvinMoveMaker, IPotvinPDShiftMoveOperator, IMoveMaker {


38  public ILookupParameter<PotvinPDShiftMove> PDShiftMoveParameter {


39  get { return (ILookupParameter<PotvinPDShiftMove>)Parameters["PotvinPDShiftMove"]; }


40  }


41 


42  public override ILookupParameter VRPMoveParameter {


43  get { return PDShiftMoveParameter; }


44  }


45 


46  [StorableConstructor]


47  private PotvinPDShiftMoveMaker(bool deserializing) : base(deserializing) { }


48 


49  public PotvinPDShiftMoveMaker()


50  : base() {


51  Parameters.Add(new LookupParameter<PotvinPDShiftMove>("PotvinPDShiftMove", "The moves that should be made."));


52  }


53 


54  public override IDeepCloneable Clone(Cloner cloner) {


55  return new PotvinPDShiftMoveMaker(this, cloner);


56  }


57 


58  protected PotvinPDShiftMoveMaker(PotvinPDShiftMoveMaker original, Cloner cloner)


59  : base(original, cloner) {


60  }


61 


62  public static void Apply(PotvinEncoding solution, PotvinPDShiftMove move, IVRPProblemInstance problemInstance) {


63  bool newTour = false;


64 


65  if (move.Tour >= solution.Tours.Count) {


66  solution.Tours.Add(new Tour());


67  newTour = true;


68  }


69  Tour tour = solution.Tours[move.Tour];


70 


71  Tour oldTour = solution.Tours.Find(t => t.Stops.Contains(move.City));


72  oldTour.Stops.Remove(move.City);


73 


74  if (problemInstance is IPickupAndDeliveryProblemInstance) {


75  IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;


76 


77  int location = pdp.GetPickupDeliveryLocation(move.City);


78  Tour oldTour2 = solution.Tours.Find(t => t.Stops.Contains(location));


79  oldTour2.Stops.Remove(location);


80 


81  solution.InsertPair(tour, move.City, location, problemInstance);


82  } else {


83  int place = solution.FindBestInsertionPlace(tour, move.City);


84  tour.Stops.Insert(place, move.City);


85  }


86 


87  if (newTour) {


88  List<int> vehicles = new List<int>();


89  for (int i = move.Tour; i < problemInstance.Vehicles.Value; i++) {


90  vehicles.Add(solution.GetVehicleAssignment(i));


91  }


92 


93  double bestQuality = double.MaxValue;


94  int bestVehicle = 1;


95 


96  int originalVehicle = solution.GetVehicleAssignment(move.Tour);


97  foreach (int vehicle in vehicles) {


98  solution.VehicleAssignment[move.Tour] = vehicle;


99 


100  double quality = problemInstance.EvaluateTour(tour, solution).Quality;


101  if (quality < bestQuality) {


102  bestQuality = quality;


103  bestVehicle = vehicle;


104  }


105  }


106 


107  solution.VehicleAssignment[move.Tour] = originalVehicle;


108 


109  int index = 1;


110  for (int i = move.Tour; i < solution.VehicleAssignment.Length; i++) {


111  if (solution.VehicleAssignment[i] == bestVehicle) {


112  index = i;


113  break;


114  }


115  }


116  solution.VehicleAssignment[index] = originalVehicle;


117  solution.VehicleAssignment[move.Tour] = bestVehicle;


118  }


119 


120  solution.Repair();


121  }


122 


123  protected override void PerformMove() {


124  PotvinPDShiftMove move = PDShiftMoveParameter.ActualValue;


125 


126  PotvinEncoding newSolution = move.Individual.Clone() as PotvinEncoding;


127  Apply(newSolution, move, ProblemInstance);


128  VRPToursParameter.ActualValue = newSolution;


129  }


130  }


131  }

