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

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

Improved compatibility of pairwise operators (#1177)

File size: 7.6 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      if (pdp != null) {
132        int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
133        if (selectedIndex >= 0) {
134          bool performed = false;
135          Tour route1 = individual.Tours[selectedIndex];
136
137          if (route1.Stops.Count > 0) {
138            //randomize customer selection
139            Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
140            int customer1Position = 0;
141
142            while (customer1Position < route1.Stops.Count) {
143              performed = false;
144
145              int customer1 = route1.Stops[perm[customer1Position]];
146              int customer2 = -1;
147
148              for (int i = 0; i < individual.Tours.Count; i++) {
149                if (i != selectedIndex) {
150                  Tour tour = individual.Tours[i];
151                  for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
152                    customer2 = tour.Stops[customer2Position];
153
154                    if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
155                      PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible);
156                      if (result != null) {
157                        VRPToursParameter.ActualValue = result;
158                        individual = result;
159
160                        route1 = individual.Tours[selectedIndex];
161                        performed = true;
162                        break;
163                      }
164                    }
165                  }
166                }
167
168                if (performed) {
169                  break;
170                }
171              }
172
173              if (!performed)
174                customer1Position++;
175              else
176                break;
177            }
178          }
179        }
180      }
181    }
182  }
183}
Note: See TracBrowser for help on using the repository browser.