source: branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinGreedyTourCreationManipulator.cs @ 14559

#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.Linq.Expressions;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.Problems.VehicleRouting.ProblemInstances;

namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("PotvinGreedyTourCreationManipulator", "This Manipulator reorders the stops within all tours of a solution candidate by following the greedy heuristic: gradually adding those stops to a tour with the least effect on the overall costs.")]
  [StorableClass]
  public sealed class PotvinGreedyTourCreationManipulator : PotvinManipulator {
    public IValueParameter<BoolValue> IncludeCosts {
      get { return (IValueParameter<BoolValue>) Parameters["IncludeCosts"]; }
    }

    [StorableConstructor]
    private PotvinGreedyTourCreationManipulator(bool deserializing) : base(deserializing) { }

    public PotvinGreedyTourCreationManipulator() : base() {
      Parameters.Add(new ValueParameter<BoolValue>("IncludeCosts", "Indicates if the actual costs should be taken into account when evaluating a tour. Otherwise only the distances between stops are counted.", new BoolValue(true)));
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PotvinGreedyTourCreationManipulator(this, cloner);
    }

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

    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance,
      bool allowInfeasible, bool includeCosts) {

      for (int i = 0; i < individual.Tours.Count; i++) {
        Tour tour = individual.Tours[i];
        Tour unrouted = individual.Tours[i].Clone() as Tour;
        tour.Stops.Clear();
        VRPEvaluation evaluation = instance.EvaluateTour(tour, individual);
        double currentQuality = (includeCosts) ? evaluation.Quality : evaluation.Distance;

        while (unrouted.Stops.Count > 0) {
          int insertionPosition = tour.Stops.Count;
          int nextCityIdxToAdd = 0;

          tour.Stops.Add(unrouted.Stops[nextCityIdxToAdd]);
          evaluation = instance.EvaluateTour(tour, individual);
          double minQualityIncrease = ((includeCosts) ? evaluation.Quality : evaluation.Distance) - currentQuality;
          tour.Stops.RemoveAt(insertionPosition);

          for (int j = 1; j < unrouted.Stops.Count; j++) {
            tour.Stops.Insert(insertionPosition, unrouted.Stops[j]);
            evaluation = instance.EvaluateTour(tour, individual);
            double qualityIncrease = ((includeCosts) ? evaluation.Quality : evaluation.Distance) - currentQuality;
            tour.Stops.RemoveAt(insertionPosition);

            if (qualityIncrease < minQualityIncrease) {
              nextCityIdxToAdd = j;
              minQualityIncrease = qualityIncrease;
            }
          }

          currentQuality += minQualityIncrease;
          tour.Stops.Insert(insertionPosition, unrouted.Stops[nextCityIdxToAdd]);
          unrouted.Stops.RemoveAt(nextCityIdxToAdd);
        }
      }
    }

    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
      bool includeCosts = IncludeCosts.Value.Value;
      ApplyManipulation(random, individual, ProblemInstance, allowInfeasible, includeCosts);
    }
  }
}