source: branches/2707_HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinEdgePreservingSequenceBasedCrossover.cs @ 17010

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 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 System;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.VehicleRouting.Interfaces;


namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("PotvinEdgePreservingSequenceBasedCrossover", "An enhanced variant of the SBX crossover described in 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. In this SBX variant the second tour segment continues after the last stop of the first segment")]
  public sealed class PotvinEdgePreservingSequenceBasedCrossover : PotvinCrossover {
    private PotvinEdgePreservingSequenceBasedCrossover(bool deserializing) : base(deserializing) { }

    public PotvinEdgePreservingSequenceBasedCrossover() : base() { }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PotvinEdgePreservingSequenceBasedCrossover(this, cloner);
    }

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

    public static PotvinEncoding Apply(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2,
      IVRPProblemInstance problemInstance, bool allowInfeasible) {
      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
      Tour newTour = new Tour();

      int cities = problemInstance.Cities.Value;

      if (cities > 0) {
        // find random break point first tour
        int breakPoint1 = random.Next(1, cities + 1);
        Tour tour1 = FindRoute(child, breakPoint1);
        breakPoint1 = tour1.Stops.IndexOf(breakPoint1);

        // add all stops of the tour from parent1 before breakPoint1 
        // to the resulting child as first tour segment
        for (int i = 0; i < breakPoint1; i++)
          newTour.Stops.Add(tour1.Stops[i]);

        if (newTour.Stops.Count < 1) {
          Console.Write("x");
        } else {
          Console.Write(newTour.Stops.Count);
        }

        int lastStop = (newTour.Stops.Count > 0) ? newTour.Stops[newTour.Stops.Count - 1] : random.Next(1, cities + 1);

        // find the stop in advance to the breakPoint1
        // within the tour set of parent2
        // difference to standard SBX: breakPoint2 is not randomly set
        Tour tour2 = FindRoute(parent2, lastStop);
        int breakPoint2 = tour2.Stops.IndexOf(lastStop);
        breakPoint2++; // add everything after the last added stop

        for (int i = breakPoint2; i < tour2.Stops.Count; i++) {
          newTour.Stops.Add(tour2.Stops[i]);
        }

        int tour1Index = child.Tours.IndexOf(tour1);
        child.Tours.Remove(tour1);
        child.Tours.Insert(tour1Index, newTour);

        foreach (int city in tour1.Stops) {
          if (FindRoute(child, city) == null && !child.Unrouted.Contains(city))
            child.Unrouted.Add(city);
        }

        foreach (int city in tour2.Stops) {
          if (FindRoute(child, city) == null && !child.Unrouted.Contains(city))
            child.Unrouted.Add(city);
        }

        if (Repair(random, child, newTour, problemInstance, allowInfeasible) || allowInfeasible) {
          return child;
        } else {
          if (random.NextDouble() < 0.5)
            return parent1.Clone() as PotvinEncoding;
          else
            return parent2.Clone() as PotvinEncoding;
        }
      } else {
        return child;
      }
    }

    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
      return Apply(random, parent1, parent2, ProblemInstance, AllowInfeasibleSolutions.Value.Value);
    }
  }
}