#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 .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.Problems.VehicleRouting.Variants;
using HeuristicLab.Random;
namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
[Item("TemporalDistanceClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm based on their geographic position and building tours afterwards alternatevly in a random or a greedy fashion.")]
[StorableClass]
public sealed class TemporalDistanceClusterCreator : ClusterCreator {
[StorableConstructor]
private TemporalDistanceClusterCreator(bool deserializing) : base(deserializing) { }
public TemporalDistanceClusterCreator() : base() {
}
private TemporalDistanceClusterCreator(TemporalDistanceClusterCreator original, Cloner cloner)
: base(original, cloner) {
}
public override IDeepCloneable Clone(Cloner cloner) {
return new TemporalDistanceClusterCreator(this, cloner);
}
public static List CreateClusterElements(ITimeWindowedProblemInstance instance) {
IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
// add all customers
List customers = new List();
for (int i = 1; i <= instance.Cities.Value; i++) {
if (pdp == null || pdp.GetDemand(i) >= 0)
customers.Add(i);
}
// wrap stops in TemporalDistanceClusterElement
List clusterObjects = new List();
foreach (int customer in customers) {
clusterObjects.Add(new TemporalDistanceClusterElement(customer, instance.ReadyTime[customer], instance.DueTime[customer]));
}
return clusterObjects;
}
public static PotvinEncoding CreateSolution(ITimeWindowedProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
PotvinEncoding result = new PotvinEncoding(instance);
// (1) wrap stops in cluster elements
List clusterElements = CreateClusterElements(instance);
// (2) create a random number k of clusters
int k = random.Next(minK, maxK);
List clusters = ClusterAlgorithm
.KMeans(random, clusterElements, k, clusterChangeThreshold);
// (3) build tours with a (a) shuffling (b) greedy tour creation routine
foreach (var c in clusters) {
Tour newTour = new Tour();
result.Tours.Add(newTour);
if (creationOption == 0) {
// (a) shuffle
c.Elements.Shuffle(random);
foreach (var o in c.Elements) {
newTour.Stops.Add(o.Id);
}
} else {
// (b) greedy
foreach (var o in c.Elements) {
newTour.Stops.Add(o.Id);
}
GreedyTourCreation(instance, result, newTour, true); // "true" means include costs
}
}
return result;
}
public override IOperation InstrumentedApply() {
IRandom random = RandomParameter.ActualValue;
int minK = (MinK.Value.Value > 0) ? MinK.Value.Value : 1;
int maxK = (MaxK.Value != null) ? MaxK.Value.Value : ProblemInstance.Vehicles.Value;
double clusterChangeThreshold = (ClusterChangeThreshold.Value.Value >= 0.0 &&
ClusterChangeThreshold.Value.Value <= 1.0)
? ClusterChangeThreshold.Value.Value
: 0.0;
// normalize probabilities
double max = TourCreationProbabilities.Value.Max();
double[] probabilites = new double[2];
for (int i = 0; i < TourCreationProbabilities.Value.Length; i++) {
probabilites[i] = TourCreationProbabilities.Value[i] / max;
}
List creationOptions = new List() { 0, 1 };
int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
var instance = ProblemInstance as ITimeWindowedProblemInstance;
if (instance == null) {
throw new ArgumentException(string.Format("Cannot initialize {0} with data from {1}", instance.GetType(), ProblemInstance.GetType()));
}
VRPToursParameter.ActualValue = CreateSolution(instance, random, minK, maxK, clusterChangeThreshold, creationOption);
return base.InstrumentedApply();
}
}
}