source: trunk/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs @ 18242

#region License Information
/* HeuristicLab
 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HEAL.Attic;
using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
using HeuristicLab.Problems.VehicleRouting.Variants;
using HeuristicLab.Problems.VehicleRouting.Interfaces;

namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("PotvinPairwiseTwoLevelExchangeManipulator", "The 2M operator which manipulates a VRP representation.   It has been adapted to pickup and delivery from Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.  It was adapted to the PDP formulation.")]
  [StorableType("8E4D8A17-1204-45CC-8ED7-375FCE0355E8")]
  public sealed class PotvinPairwiseTwoLevelExchangeManipulator : PotvinManipulator {
    [StorableConstructor]
    private PotvinPairwiseTwoLevelExchangeManipulator(StorableConstructorFlag _) : base(_) { }

    public PotvinPairwiseTwoLevelExchangeManipulator() : base() { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PotvinPairwiseTwoLevelExchangeManipulator(this, cloner);
    }

    private PotvinPairwiseTwoLevelExchangeManipulator(PotvinPairwiseTwoLevelExchangeManipulator original, Cloner cloner)
      : base(original, cloner) {
    }

    private static PotvinEncoding ReplacePair(PotvinEncoding individual, IVRPProblemInstance instance, int replaced, int replacing, bool allowInfeasible) {
      individual = individual.Clone() as PotvinEncoding;
      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;

      int replacedDest = pdp.GetPickupDeliveryLocation(replaced);
      int replacedSource, replacedTarget;
      if (pdp.GetDemand(replaced) >= 0) {
        replacedSource = replaced;
        replacedTarget = replacedDest;
      } else {
        replacedSource = replacedDest;
        replacedTarget = replaced;
      }
      Tour replacedSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacedSource));
      Tour replacedTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacedTarget));

      int replacingDest = pdp.GetPickupDeliveryLocation(replacing);
      int replacingSource, replacingTarget;
      if (pdp.GetDemand(replacing) >= 0) {
        replacingSource = replacing;
        replacingTarget = replacingDest;
      } else {
        replacingSource = replacingDest;
        replacingTarget = replacing;
      }
      Tour replacingSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacingSource));
      Tour replacingTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacingTarget));

      replacingSourceTour.Stops.Remove(replacingSource);
      replacingTargetTour.Stops.Remove(replacingTarget);

      replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource;
      if (!allowInfeasible && !instance.TourFeasible(replacedSourceTour, individual))
        return null;

      replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget;
      if (!allowInfeasible && !instance.TourFeasible(replacedTargetTour, individual))
        return null;

      double bestQuality = double.MaxValue;
      int bestTour = -1;
      int bestPositionSource = -1;
      int bestPositionTarget = -1;

      int routeToAvoid = individual.Tours.IndexOf(replacingSourceTour);

      for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
        if (tourIdx != routeToAvoid) {
          Tour tour = individual.Tours[tourIdx];
          VRPEvaluation eval = instance.EvaluateTour(tour, individual);
          individual.InsertPair(tour, replacedSource, replacedTarget, instance);
          VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);

          double delta = evalNew.Quality - eval.Quality;

          if (delta < bestQuality &&
              (instance.Feasible(evalNew) || allowInfeasible)) {
            bestQuality = delta;
            bestTour = tourIdx;
            bestPositionSource = tour.Stops.IndexOf(replacedSource);
            bestPositionTarget = tour.Stops.IndexOf(replacedTarget);
          }

          tour.Stops.Remove(replacedSource);
          tour.Stops.Remove(replacedTarget);
        }
      }

      if (bestTour != -1) {
        if (bestPositionTarget < bestPositionSource) {
          individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
          individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
        } else {
          individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
          individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
        }

        return individual;
      } else {
        return null;
      }
    }

    public static PotvinEncoding ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
      PotvinEncoding result = null;
      
      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
      if (selectedIndex >= 0) {
        bool performed = false;
        Tour route1 = individual.Tours[selectedIndex];

        if (route1.Stops.Count > 0) {
          //randomize customer selection
          Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
          int customer1Position = 0;

          while (customer1Position < route1.Stops.Count) {
            performed = false;

            int customer1 = route1.Stops[perm[customer1Position]];
            int customer2 = -1;

            for (int i = 0; i < individual.Tours.Count; i++) {
              if (i != selectedIndex) {
                Tour tour = individual.Tours[i];
                for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
                  customer2 = tour.Stops[customer2Position];

                  if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
                    result = ReplacePair(individual, pdp, customer2, customer1, allowInfeasible);
                    if (result != null) {
                      individual = result;

                      route1 = individual.Tours[selectedIndex];
                      performed = true;
                      break;
                    }
                  }
                }
              }

              if (performed) {
                break;
              }
            }

            if (!performed)
              customer1Position++;
            else
              break;
          }
        }
      }

      return result;
    }

    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;

      if (pdp != null) {
        PotvinEncoding result = ApplyManipulation(random, individual, pdp, allowInfeasible);
        if (result != null) {
          VRPToursParameter.ActualValue = result;
        }        
      }
    }
  }
}