[8346] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
| 25 | using HeuristicLab.Common;
|
---|
| 26 | using HeuristicLab.Core;
|
---|
| 27 | using HeuristicLab.Data;
|
---|
| 28 | using HeuristicLab.Optimization;
|
---|
| 29 | using HeuristicLab.Optimization.Operators;
|
---|
| 30 | using HeuristicLab.Parameters;
|
---|
| 31 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 32 | using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
|
---|
| 33 | using HeuristicLab.Problems.VehicleRouting.Interfaces;
|
---|
| 34 | using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
|
---|
| 35 | using HeuristicLab.Problems.VehicleRouting.Variants;
|
---|
| 36 |
|
---|
| 37 | namespace HeuristicLab.Problems.VehicleRouting {
|
---|
| 38 | /// <summary>
|
---|
| 39 | /// An operator that relinks paths between vehicle routing solutions.
|
---|
| 40 | /// </summary>
|
---|
| 41 | [Item("VRPPathRelinker", "An operator that relinks paths between vehicle routing solutions.")]
|
---|
| 42 | [StorableClass]
|
---|
| 43 | public sealed class VRPPathRelinker : SingleObjectivePathRelinker, IGeneralVRPOperator, IStochasticOperator {
|
---|
| 44 | #region Parameter properties
|
---|
| 45 | public ILookupParameter<IRandom> RandomParameter {
|
---|
| 46 | get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
|
---|
| 47 | }
|
---|
| 48 | public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
|
---|
| 49 | get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
|
---|
| 50 | }
|
---|
| 51 | public IValueParameter<IntValue> SampleSizeParameter {
|
---|
| 52 | get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
|
---|
| 53 | }
|
---|
| 54 | public IValueParameter<IntValue> IterationsParameter {
|
---|
| 55 | get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
|
---|
| 56 | }
|
---|
| 57 | #endregion
|
---|
| 58 |
|
---|
| 59 | [StorableConstructor]
|
---|
| 60 | private VRPPathRelinker(bool deserializing) : base(deserializing) { }
|
---|
| 61 | private VRPPathRelinker(VRPPathRelinker original, Cloner cloner) : base(original, cloner) { }
|
---|
| 62 | public VRPPathRelinker()
|
---|
| 63 | : base() {
|
---|
| 64 | Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
|
---|
| 65 | Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
|
---|
| 66 | Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(10)));
|
---|
| 67 | Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of iterations the operator should perform.", new IntValue(50)));
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 71 | return new VRPPathRelinker(this, cloner);
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | private static int MatchingCities(Tour tour1, Tour tour2) {
|
---|
| 75 | return tour1.Stops.Intersect(tour2.Stops).Count();
|
---|
| 76 | }
|
---|
| 77 |
|
---|
| 78 | private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide, IVRPProblemInstance problemInstance) {
|
---|
| 79 | PotvinEncoding result = new PotvinEncoding(problemInstance);
|
---|
| 80 |
|
---|
| 81 | List<bool> used = new List<bool>();
|
---|
| 82 | for (int i = 0; i < initiator.Tours.Count; i++) {
|
---|
| 83 | used.Add(false);
|
---|
| 84 | }
|
---|
| 85 |
|
---|
| 86 | for (int i = 0; i < guide.Tours.Count; i++) {
|
---|
| 87 | int bestMatch = -1;
|
---|
| 88 | int bestTour = -1;
|
---|
| 89 |
|
---|
| 90 | for (int j = 0; j < initiator.Tours.Count; j++) {
|
---|
| 91 | if (!used[j]) {
|
---|
| 92 | int match = MatchingCities(guide.Tours[i], initiator.Tours[j]);
|
---|
| 93 | if (match > bestMatch) {
|
---|
| 94 | bestMatch = match;
|
---|
| 95 | bestTour = j;
|
---|
| 96 | }
|
---|
| 97 | }
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | if (bestTour != -1) {
|
---|
| 101 | result.Tours.Add(initiator.Tours[bestTour]);
|
---|
| 102 | used[bestTour] = true;
|
---|
| 103 | }
|
---|
| 104 | }
|
---|
| 105 |
|
---|
| 106 | for (int i = 0; i < initiator.Tours.Count; i++) {
|
---|
| 107 | if (!used[i])
|
---|
| 108 | result.Tours.Add(initiator.Tours[i]);
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | return result;
|
---|
| 112 | }
|
---|
| 113 |
|
---|
| 114 | #region moves
|
---|
| 115 | public static PotvinEncoding RouteBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random, IVRPProblemInstance problemInstance) {
|
---|
| 116 | return PotvinRouteBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
|
---|
| 117 | }
|
---|
| 118 |
|
---|
| 119 | public static PotvinEncoding SequenceBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random, IVRPProblemInstance problemInstance) {
|
---|
| 120 | return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
|
---|
| 121 | }
|
---|
| 122 |
|
---|
| 123 |
|
---|
| 124 | public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
|
---|
| 125 | List<int> cities = new List<int>();
|
---|
| 126 | foreach (Tour tour in initiator.Tours) {
|
---|
| 127 | foreach (int city in tour.Stops) {
|
---|
| 128 | Tour guideTour = guide.Tours.First(t => t.Stops.Contains(city));
|
---|
| 129 | if (guide.Tours.IndexOf(guideTour) != initiator.Tours.IndexOf(tour)) {
|
---|
| 130 | cities.Add(city);
|
---|
| 131 | }
|
---|
| 132 | }
|
---|
| 133 | }
|
---|
| 134 |
|
---|
| 135 | if (cities.Count == 0) {
|
---|
| 136 | RelocateMove(initiator, random);
|
---|
| 137 | } else {
|
---|
| 138 | int city = cities[random.Next(cities.Count)];
|
---|
| 139 | Tour tour = initiator.Tours.First(t => t.Stops.Contains(city));
|
---|
| 140 | tour.Stops.Remove(city);
|
---|
| 141 |
|
---|
| 142 | Tour guideTour = guide.Tours.First(t => t.Stops.Contains(city));
|
---|
| 143 | int guideTourIndex = guide.Tours.IndexOf(guideTour);
|
---|
| 144 |
|
---|
| 145 | if (guideTourIndex < initiator.Tours.Count) {
|
---|
| 146 | Tour tour2 = initiator.Tours[guideTourIndex];
|
---|
| 147 |
|
---|
| 148 | int guideIndex = guideTour.Stops.IndexOf(city);
|
---|
| 149 | if (guideIndex == 0) {
|
---|
| 150 | tour2.Stops.Insert(0, city);
|
---|
| 151 | } else {
|
---|
| 152 | int predecessor = guideTour.Stops[guideIndex - 1];
|
---|
| 153 | int initIndex = tour2.Stops.IndexOf(predecessor);
|
---|
| 154 | if (initIndex != -1) {
|
---|
| 155 | tour2.Stops.Insert(initIndex + 1, city);
|
---|
| 156 | } else {
|
---|
| 157 | if (guideIndex == guideTour.Stops.Count - 1) {
|
---|
| 158 | tour2.Stops.Insert(tour2.Stops.Count, city);
|
---|
| 159 | } else {
|
---|
| 160 | int sucessor = guideTour.Stops[guideIndex + 1];
|
---|
| 161 | initIndex = tour2.Stops.IndexOf(sucessor);
|
---|
| 162 | if (initIndex != -1) {
|
---|
| 163 | tour2.Stops.Insert(initIndex, city);
|
---|
| 164 | } else {
|
---|
| 165 | tour2.Stops.Insert(random.Next(tour2.Stops.Count + 1), city);
|
---|
| 166 | }
|
---|
| 167 | }
|
---|
| 168 | }
|
---|
| 169 | }
|
---|
| 170 | } else {
|
---|
| 171 | Tour tour2 = new Tour();
|
---|
| 172 | tour2.Stops.Add(city);
|
---|
| 173 | initiator.Tours.Add(tour2);
|
---|
| 174 | }
|
---|
| 175 |
|
---|
| 176 | if (tour.Stops.Count == 0)
|
---|
| 177 | initiator.Tours.Remove(tour);
|
---|
| 178 | }
|
---|
| 179 | }
|
---|
| 180 |
|
---|
| 181 | public static void RelocateMove(PotvinEncoding individual, IRandom random) {
|
---|
| 182 | int cities = individual.Cities;
|
---|
| 183 | int city = 1 + random.Next(cities);
|
---|
| 184 | Tour originalTour = individual.Tours.Find(t => t.Stops.Contains(city));
|
---|
| 185 | //consider creating new route
|
---|
| 186 | individual.Tours.Add(new Tour());
|
---|
| 187 |
|
---|
| 188 | int position = 1 + random.Next(cities + individual.Tours.Count - 1);
|
---|
| 189 | if (position >= city) {
|
---|
| 190 | position++;
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 | int originalPosition = originalTour.Stops.IndexOf(city);
|
---|
| 194 | originalTour.Stops.RemoveAt(originalPosition);
|
---|
| 195 |
|
---|
| 196 | Tour insertionTour;
|
---|
| 197 | int insertionPosition;
|
---|
| 198 | if (position <= cities) {
|
---|
| 199 | insertionTour = individual.Tours.Find(t => t.Stops.Contains(position));
|
---|
| 200 | insertionPosition = insertionTour.Stops.IndexOf(position) + 1;
|
---|
| 201 | } else {
|
---|
| 202 | insertionTour = individual.Tours[position - cities - 1];
|
---|
| 203 | insertionPosition = 0;
|
---|
| 204 | }
|
---|
| 205 |
|
---|
| 206 | insertionTour.Stops.Insert(insertionPosition, city);
|
---|
| 207 |
|
---|
| 208 | individual.Tours.RemoveAll(t => t.Stops.Count == 0);
|
---|
| 209 | }
|
---|
| 210 |
|
---|
| 211 | public static void ExchangeMove(PotvinEncoding individual, IRandom random) {
|
---|
| 212 | if (individual.Tours.Count > 1) {
|
---|
| 213 | int tour1Idx = random.Next(individual.Tours.Count);
|
---|
| 214 | int tour2Idx = random.Next(individual.Tours.Count - 1);
|
---|
| 215 | if (tour2Idx >= tour1Idx)
|
---|
| 216 | tour2Idx++;
|
---|
| 217 |
|
---|
| 218 | Tour tour1 = individual.Tours[tour1Idx];
|
---|
| 219 | Tour tour2 = individual.Tours[tour2Idx];
|
---|
| 220 |
|
---|
| 221 | int index1 = random.Next(tour1.Stops.Count);
|
---|
| 222 | int city1 = tour1.Stops[index1];
|
---|
| 223 |
|
---|
| 224 | int index2 = random.Next(tour2.Stops.Count);
|
---|
| 225 | int city2 = tour2.Stops[index2];
|
---|
| 226 |
|
---|
| 227 | tour1.Stops.RemoveAt(index1);
|
---|
| 228 | tour1.Stops.Insert(index1, city2);
|
---|
| 229 |
|
---|
| 230 | tour2.Stops.RemoveAt(index2);
|
---|
| 231 | tour2.Stops.Insert(index2, city1);
|
---|
| 232 | }
|
---|
| 233 | }
|
---|
| 234 |
|
---|
| 235 | public static void TwoOptMove(PotvinEncoding individual, IRandom random) {
|
---|
| 236 | List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
|
---|
| 237 |
|
---|
| 238 | if (tours.Count > 0) {
|
---|
| 239 | int tourIdx = random.Next(tours.Count);
|
---|
| 240 | Tour tour = tours[tourIdx];
|
---|
| 241 |
|
---|
| 242 | int a;
|
---|
| 243 | if (tour.Stops.Count == 4) {
|
---|
| 244 | a = 0;
|
---|
| 245 | } else if (tour.Stops.Count == 5) {
|
---|
| 246 | int idx = random.Next(4);
|
---|
| 247 | if (idx >= 2)
|
---|
| 248 | idx++;
|
---|
| 249 | a = idx;
|
---|
| 250 | } else {
|
---|
| 251 | a = random.Next(tour.Stops.Count);
|
---|
| 252 | }
|
---|
| 253 |
|
---|
| 254 | int b;
|
---|
| 255 | List<int> indices = new List<int>();
|
---|
| 256 | for (int i = 0; i < tour.Stops.Count; i++) {
|
---|
| 257 | if (Math.Abs(i - a) > 2) {
|
---|
| 258 | indices.Add(i);
|
---|
| 259 | }
|
---|
| 260 | }
|
---|
| 261 | b = indices[random.Next(indices.Count)];
|
---|
| 262 |
|
---|
| 263 | if (b < a) {
|
---|
| 264 | int tmp = a;
|
---|
| 265 | a = b;
|
---|
| 266 | b = tmp;
|
---|
| 267 | }
|
---|
| 268 |
|
---|
| 269 | int index = a + 1;
|
---|
| 270 | int count = b - a - 1;
|
---|
| 271 | List<int> segment = tour.Stops.GetRange(index, count);
|
---|
| 272 | tour.Stops.RemoveRange(index, count);
|
---|
| 273 | segment.Reverse();
|
---|
| 274 | tour.Stops.InsertRange(index, segment);
|
---|
| 275 | }
|
---|
| 276 | }
|
---|
| 277 |
|
---|
| 278 | public static void TwoOptStarMove(PotvinEncoding individual, IRandom random) {
|
---|
| 279 | //consider creating new tour
|
---|
| 280 | individual.Tours.Add(new Tour());
|
---|
| 281 |
|
---|
| 282 | int route1Idx = random.Next(individual.Tours.Count);
|
---|
| 283 | int route2Idx = random.Next(individual.Tours.Count - 1);
|
---|
| 284 | if (route2Idx >= route1Idx)
|
---|
| 285 | route2Idx++;
|
---|
| 286 |
|
---|
| 287 | Tour route1 = individual.Tours[route1Idx];
|
---|
| 288 | Tour route2 = individual.Tours[route2Idx];
|
---|
| 289 |
|
---|
| 290 | int x1 = random.Next(route1.Stops.Count + 1);
|
---|
| 291 | int x2 = random.Next(route2.Stops.Count + 1);
|
---|
| 292 |
|
---|
| 293 | int count = route1.Stops.Count - x1;
|
---|
| 294 | List<int> segmentX1 = new List<int>();
|
---|
| 295 | if (count > 0) {
|
---|
| 296 | segmentX1 = route1.Stops.GetRange(x1, count);
|
---|
| 297 | route1.Stops.RemoveRange(x1, count);
|
---|
| 298 | }
|
---|
| 299 |
|
---|
| 300 | count = route2.Stops.Count - x2;
|
---|
| 301 | List<int> segmentX2 = new List<int>();
|
---|
| 302 | if (count > 0) {
|
---|
| 303 | segmentX2 = route2.Stops.GetRange(x2, count);
|
---|
| 304 | route2.Stops.RemoveRange(x2, count);
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | route1.Stops.AddRange(segmentX2);
|
---|
| 308 | route2.Stops.AddRange(segmentX1);
|
---|
| 309 |
|
---|
| 310 | individual.Tours.RemoveAll(t => t.Stops.Count == 0);
|
---|
| 311 | }
|
---|
| 312 |
|
---|
| 313 | public static void OrOptMove(PotvinEncoding individual, IRandom random) {
|
---|
| 314 | List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
|
---|
| 315 |
|
---|
| 316 | if (tours.Count > 0) {
|
---|
| 317 | int tourIdx = random.Next(tours.Count);
|
---|
| 318 | Tour tour = tours[tourIdx];
|
---|
| 319 |
|
---|
| 320 | int segmentStart = random.Next(tour.Stops.Count);
|
---|
| 321 | int segmentLength;
|
---|
| 322 | if (segmentStart == 0) {
|
---|
| 323 | segmentLength = 1 + random.Next(tour.Stops.Count - 1);
|
---|
| 324 | } else {
|
---|
| 325 | segmentLength = 1 + random.Next(tour.Stops.Count - segmentStart);
|
---|
| 326 | }
|
---|
| 327 |
|
---|
| 328 | List<int> segment = tour.Stops.GetRange(segmentStart, segmentLength);
|
---|
| 329 | tour.Stops.RemoveRange(segmentStart, segmentLength);
|
---|
| 330 | int newPos;
|
---|
| 331 | if (tour.Stops.Count == 1)
|
---|
| 332 | newPos = 0;
|
---|
| 333 | else
|
---|
| 334 | newPos = random.Next(tour.Stops.Count - 1);
|
---|
| 335 |
|
---|
| 336 | if (newPos >= segmentStart)
|
---|
| 337 | newPos++;
|
---|
| 338 | tour.Stops.InsertRange(newPos, segment);
|
---|
| 339 | }
|
---|
| 340 | }
|
---|
| 341 | #endregion
|
---|
| 342 |
|
---|
| 343 | private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
|
---|
| 344 | IList<IItem> selection = new List<IItem>();
|
---|
| 345 | if (solutions.Count > 0) {
|
---|
| 346 | int noSol = (int)(solutions.Count * n.Value);
|
---|
| 347 | if (noSol <= 0) noSol++;
|
---|
| 348 | double stepSize = (double)solutions.Count / (double)noSol;
|
---|
| 349 | for (int i = 0; i < noSol; i++)
|
---|
| 350 | selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
|
---|
| 351 | }
|
---|
| 352 |
|
---|
| 353 | return selection;
|
---|
| 354 | }
|
---|
| 355 |
|
---|
| 356 | public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand, IVRPProblemInstance problemInstance) {
|
---|
| 357 |
|
---|
| 358 | if (initiator == null || guide == null)
|
---|
| 359 | throw new ArgumentException("Cannot relink path because one of the provided solutions or both are null.");
|
---|
| 360 |
|
---|
| 361 | double sigma = 1.5;
|
---|
| 362 |
|
---|
| 363 | DoubleValue originalOverloadPenalty = new DoubleValue();
|
---|
| 364 | if (problemInstance is IHomogenousCapacitatedProblemInstance)
|
---|
| 365 | originalOverloadPenalty.Value = (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value;
|
---|
| 366 | DoubleValue originalTardinessPenalty = new DoubleValue();
|
---|
| 367 | if (problemInstance is ITimeWindowedProblemInstance)
|
---|
| 368 | originalTardinessPenalty.Value = (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value;
|
---|
| 369 |
|
---|
| 370 | PotvinEncoding current = MatchTours(initiator, guide, problemInstance);
|
---|
| 371 | double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
|
---|
| 372 |
|
---|
| 373 | IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
|
---|
| 374 | int i = 0;
|
---|
| 375 | while (i < iterations && currentSimilarity != 1.0) {
|
---|
| 376 | VRPEvaluation currentEval = problemInstance.Evaluate(current);
|
---|
| 377 | currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
|
---|
| 378 |
|
---|
| 379 | if (currentSimilarity < 1.0) {
|
---|
| 380 | for (int sample = 0; sample < sampleSize; sample++) {
|
---|
| 381 | PotvinEncoding next = current.Clone() as PotvinEncoding;
|
---|
| 382 |
|
---|
| 383 | int neighborhood = rand.Next(4);
|
---|
| 384 | switch (neighborhood) {
|
---|
| 385 | case 0: next = RouteBasedXOver(next, guide, rand,
|
---|
| 386 | problemInstance);
|
---|
| 387 | break;
|
---|
| 388 | case 1: next = SequenceBasedXOver(next, guide, rand,
|
---|
| 389 | problemInstance);
|
---|
| 390 | break;
|
---|
| 391 | case 2: TwoOptMove(next, rand);
|
---|
| 392 | break;
|
---|
| 393 | case 3: GuidedRelocateMove(next, guide, rand);
|
---|
| 394 | break;
|
---|
| 395 | }
|
---|
| 396 |
|
---|
| 397 | next = MatchTours(next, guide, problemInstance);
|
---|
| 398 |
|
---|
| 399 | VRPEvaluation nextEval = problemInstance.Evaluate(next);
|
---|
| 400 | double nextSimilarity = VRPSimilarityCalculator.CalculateSimilarity(next, guide);
|
---|
| 401 |
|
---|
| 402 | if (nextSimilarity > currentSimilarity && nextEval.Quality <= currentEval.Quality) {
|
---|
| 403 | current = next;
|
---|
| 404 | solutions.Add(current);
|
---|
| 405 | break;
|
---|
| 406 | }
|
---|
| 407 | }
|
---|
| 408 |
|
---|
| 409 | if (problemInstance is IHomogenousCapacitatedProblemInstance) {
|
---|
| 410 | if (((CVRPEvaluation)currentEval).Overload > 0)
|
---|
| 411 | (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value *= sigma;
|
---|
| 412 | else
|
---|
| 413 | (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value /= sigma;
|
---|
| 414 | }
|
---|
| 415 |
|
---|
| 416 |
|
---|
| 417 | if (problemInstance is ITimeWindowedProblemInstance) {
|
---|
| 418 | if (((CVRPTWEvaluation)currentEval).Tardiness > 0)
|
---|
| 419 | (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value *= sigma;
|
---|
| 420 | else
|
---|
| 421 | (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value /= sigma;
|
---|
| 422 | }
|
---|
| 423 |
|
---|
| 424 | i++;
|
---|
| 425 | }
|
---|
| 426 | }
|
---|
| 427 |
|
---|
| 428 | if (problemInstance is IHomogenousCapacitatedProblemInstance)
|
---|
| 429 | (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value = originalOverloadPenalty.Value;
|
---|
| 430 | if (problemInstance is ITimeWindowedProblemInstance)
|
---|
| 431 | (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value = originalTardinessPenalty.Value;
|
---|
| 432 |
|
---|
| 433 | return new ItemArray<IItem>(ChooseSelection(solutions, n));
|
---|
| 434 | }
|
---|
| 435 |
|
---|
| 436 | protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
|
---|
| 437 | if (parents.Length != 2)
|
---|
| 438 | throw new ArgumentException("The number of parents is not equal to 2.");
|
---|
| 439 |
|
---|
| 440 | if (!(parents[0] is PotvinEncoding))
|
---|
| 441 | parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
|
---|
| 442 | if (!(parents[1] is PotvinEncoding))
|
---|
| 443 | parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
|
---|
| 444 |
|
---|
| 445 | return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
|
---|
| 446 | SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue, ProblemInstanceParameter.ActualValue);
|
---|
| 447 | }
|
---|
| 448 | }
|
---|
| 449 | }
|
---|