source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs @ 6960

Last change on this file since 6960 was 6960, checked in by svonolfe, 11 years ago

Added pairwise manipulators, removed relocation manipulator (#1177)

File size: 7.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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
22using HeuristicLab.Core;
23using HeuristicLab.Encodings.PermutationEncoding;
24using HeuristicLab.Parameters;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Data;
27using System.Collections.Generic;
28using HeuristicLab.Common;
29using HeuristicLab.Problems.VehicleRouting.Variants;
30using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
31
32namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
33  [Item("PotvinPairwiseTwoLevelExchangeManipulator", "The 2M operator which manipulates a VRP representation.  It is implemented as 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.  It was adapted to the PDP formulation.")]
34  [StorableClass]
35  public sealed class PotvinPairwiseTwoLevelExchangeManipulator : PotvinManipulator {
36    [StorableConstructor]
37    private PotvinPairwiseTwoLevelExchangeManipulator(bool deserializing) : base(deserializing) { }
38
39    public PotvinPairwiseTwoLevelExchangeManipulator() : base() { }
40
41    public override IDeepCloneable Clone(Cloner cloner) {
42      return new PotvinPairwiseTwoLevelExchangeManipulator(this, cloner);
43    }
44
45    private PotvinPairwiseTwoLevelExchangeManipulator(PotvinPairwiseTwoLevelExchangeManipulator original, Cloner cloner)
46      : base(original, cloner) {
47    }
48
49    private PotvinEncoding ReplacePair(PotvinEncoding individual, int replaced, int replacing, bool allowInfeasible) {
50      individual = individual.Clone() as PotvinEncoding;
51      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
52
53      int replacedDest = pdp.GetPickupDeliveryLocation(replaced);
54      int replacedSource, replacedTarget;
55      if (pdp.GetDemand(replaced) >= 0) {
56        replacedSource = replaced;
57        replacedTarget = replacedDest;
58      } else {
59        replacedSource = replacedDest;
60        replacedTarget = replaced;
61      }
62      Tour replacedSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacedSource));
63      Tour replacedTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacedTarget));
64
65      int replacingDest = pdp.GetPickupDeliveryLocation(replacing);
66      int replacingSource, replacingTarget;
67      if (pdp.GetDemand(replacing) >= 0) {
68        replacingSource = replacing;
69        replacingTarget = replacingDest;
70      } else {
71        replacingSource = replacingDest;
72        replacingTarget = replacing;
73      }
74      Tour replacingSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacingSource));
75      Tour replacingTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacingTarget));
76
77      replacingSourceTour.Stops.Remove(replacingSource);
78      replacingTargetTour.Stops.Remove(replacingTarget);
79
80      replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource;
81      replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget;
82
83      double bestQuality = double.MaxValue;
84      int bestTour = -1;
85      int bestPositionSource = -1;
86      int bestPositionTarget = -1;
87
88      int routeToAvoid = individual.Tours.IndexOf(replacingSourceTour);
89
90      for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
91        if (tourIdx != routeToAvoid) {
92          Tour tour = individual.Tours[tourIdx];
93          VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
94          individual.InsertPair(tour, replacedSource, replacedTarget, ProblemInstance);
95          VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
96
97          double delta = evalNew.Quality - eval.Quality;
98
99          if (delta < bestQuality &&
100              (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
101            bestQuality = delta;
102            bestTour = tourIdx;
103            bestPositionSource = tour.Stops.IndexOf(replacedSource);
104            bestPositionTarget = tour.Stops.IndexOf(replacedTarget);
105          }
106
107          tour.Stops.Remove(replacedSource);
108          tour.Stops.Remove(replacedTarget);
109        }
110      }
111
112      if (bestTour != -1) {
113        if (bestPositionTarget < bestPositionSource) {
114          individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
115          individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
116        } else {
117          individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
118          individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
119        }
120
121        return individual;
122      } else {
123        return null;
124      }
125    }
126
127    protected override void Manipulate(IRandom random, PotvinEncoding individual) {     
128      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
129      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
130
131      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
132      if (selectedIndex >= 0) {
133        bool performed = false;
134        Tour route1 = individual.Tours[selectedIndex];
135
136        if (route1.Stops.Count > 0) {
137          //randomize customer selection
138          Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
139          int customer1Position = 0;
140
141          while (customer1Position < route1.Stops.Count) {
142            performed = false;
143
144            int customer1 = route1.Stops[perm[customer1Position]];
145            int customer2 = -1;
146
147            for (int i = 0; i < individual.Tours.Count; i++) {
148              if (i != selectedIndex) {
149                Tour tour = individual.Tours[i];
150                for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
151                  customer2 = tour.Stops[customer2Position];
152
153                  if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
154                    PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible);
155                    if (result != null) {
156                      VRPToursParameter.ActualValue = result;
157                      individual = result;
158
159                      route1 = individual.Tours[selectedIndex];
160                      performed = true;
161                      break;
162                    }
163                  }
164                }
165              }
166
167              if (performed) {
168                break;
169              }
170            }
171
172            if (!performed)
173              customer1Position++;
174            else
175              break;
176          }
177        }
178      }
179    }
180  }
181}
Note: See TracBrowser for help on using the repository browser.