Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OaaS/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs @ 9363

Last change on this file since 9363 was 9363, checked in by spimming, 11 years ago

#1888:

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