source: branches/2707_HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/ClusterCreator.cs @ 17011

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2019 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 System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
using HeuristicLab.Problems.VehicleRouting.Variants;
using HeuristicLab.Random;
using HEAL.Attic;

namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("ClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm and building tours afterwards alternatevly in a random or a greedy fashion.")]
  [StorableType("B57A7C93-FE0B-4D3E-BC2D-DD2B8F4323CB")]
  public abstract class ClusterCreator : PotvinCreator, IStochasticOperator {

    public ILookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    }

    public IValueParameter<IntValue> MinK {
      get { return (IValueParameter<IntValue>)Parameters["MinK"]; }
    }
    public IValueParameter<IntValue> MaxK {
      get { return (IValueParameter<IntValue>)Parameters["MaxK"]; }
    }

    public IValueParameter<DoubleValue> ClusterChangeThreshold {
      get { return (IValueParameter<DoubleValue>)Parameters["ClusterChangeThreshold"]; }
    }

    public IValueParameter<DoubleArray> TourCreationProbabilities {
      get { return (IValueParameter<DoubleArray>)Parameters["TourCreationProbabilities"]; }
    }

    [StorableConstructor]
    public ClusterCreator(StorableConstructorFlag _) : base(_) { }

    public ClusterCreator() : base() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
      Parameters.Add(new ValueParameter<IntValue>("MinK", "Minimum number of clusters which should be created", new IntValue(1)));
      Parameters.Add(new OptionalValueParameter<IntValue>("MaxK", "Maximum number of clusters which should be created"));
      Parameters.Add(new ValueParameter<DoubleValue>("ClusterChangeThreshold", "A certain ratio below which a cluster should be considered as computed satisfactory", new DoubleValue(0.0)));
      Parameters.Add(new ValueParameter<DoubleArray>("TourCreationProbabilities", "This weightage array denotes the probability which tour creation method is employed: [shuffled; greedy]", new DoubleArray(new double[] { 1, 1 })));
    }

    protected ClusterCreator(ClusterCreator original, Cloner cloner)
      : base(original, cloner) {
    }

    protected static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
      double dx = instance.GetCoordinates(0)[0];
      double dy = instance.GetCoordinates(0)[1];

      double cx = instance.GetCoordinates(city)[0];
      double cy = instance.GetCoordinates(city)[1];

      double alpha = Math.Atan((cx - dx) / (dy - cy)) * (180.0 / Math.PI);
      if (cx > dx && cy > dy)
        alpha = (90.0 + alpha) + 90.0;
      else if (cx < dx && cy > dy)
        alpha = alpha + 180.0;
      else if (cx < dx && cy < dy)
        alpha = (90.0 + alpha) + 270.0;

      return alpha;
    }

    protected static void GreedyTourCreation(IVRPProblemInstance instance, PotvinEncoding individual, Tour tour, bool includeCosts) {
      Tour unrouted = tour.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);
      }
    }

  }
}