Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs @ 9456

Last change on this file since 9456 was 9456, checked in by swagner, 11 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 5.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
26using HeuristicLab.Problems.VehicleRouting.Variants;
27
28namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
29  [Item("PotvinPairwiseOneLevelExchangeMainpulator", "The 1M operator which manipulates a PDP 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.")]
30  [StorableClass]
31  public sealed class PotvinPairwiseOneLevelExchangeMainpulator : PotvinManipulator {
32    [StorableConstructor]
33    private PotvinPairwiseOneLevelExchangeMainpulator(bool deserializing) : base(deserializing) { }
34
35    public PotvinPairwiseOneLevelExchangeMainpulator() : base() { }
36
37    public override IDeepCloneable Clone(Cloner cloner) {
38      return new PotvinPairwiseOneLevelExchangeMainpulator(this, cloner);
39    }
40
41    private PotvinPairwiseOneLevelExchangeMainpulator(PotvinPairwiseOneLevelExchangeMainpulator original, Cloner cloner)
42      : base(original, cloner) {
43    }
44
45    public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {
46      bool success;
47
48      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
49
50      if (pdp != null) {
51        Tour route1 = individual.Tours.Find(t => t.Stops.Contains(city));
52        int i = route1.Stops.IndexOf(city);
53
54        int dest = pdp.GetPickupDeliveryLocation(city);
55        Tour destRoute = individual.Tours.Find(t => t.Stops.Contains(dest));
56        int j = destRoute.Stops.IndexOf(dest);
57
58        route1.Stops.Remove(city);
59        destRoute.Stops.Remove(dest);
60
61        int routeToAvoid = -1;
62        if (route1 == destRoute)
63          routeToAvoid = individual.Tours.IndexOf(route1);
64
65        int source, target;
66        if (ProblemInstance.GetDemand(city) >= 0) {
67          source = city;
68          target = dest;
69        } else {
70          source = dest;
71          target = city;
72        }
73
74        double bestQuality = double.MaxValue;
75        int bestTour = -1;
76        int bestPositionSource = -1;
77        int bestPositionTarget = -1;
78
79        for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
80          if (tourIdx != routeToAvoid) {
81            Tour tour = individual.Tours[tourIdx];
82            VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
83            individual.InsertPair(tour, source, target, ProblemInstance);
84            VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
85
86            double delta = evalNew.Quality - eval.Quality;
87
88            if (delta < bestQuality &&
89               (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
90              bestQuality = delta;
91              bestTour = tourIdx;
92              bestPositionSource = tour.Stops.IndexOf(source);
93              bestPositionTarget = tour.Stops.IndexOf(target);
94            }
95
96            tour.Stops.Remove(source);
97            tour.Stops.Remove(target);
98          }
99        }
100
101        if (bestTour >= 0) {
102          if (bestPositionTarget < bestPositionSource) {
103            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
104            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
105          } else {
106            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
107            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
108          }
109
110          success = true;
111        } else {
112          if (j < i) {
113            destRoute.Stops.Insert(j, dest);
114            route1.Stops.Insert(i, city);
115          } else {
116            route1.Stops.Insert(i, city);
117            destRoute.Stops.Insert(j, dest);
118          }
119
120          success = false;
121        }
122      } else {
123        success = false;
124      }
125
126      return success;
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          Tour route1 =
137            individual.Tours[selectedIndex];
138
139          int count = route1.Stops.Count;
140
141          if (count > 0) {
142            int i = random.Next(0, count);
143            int city = route1.Stops[i];
144
145            if (!PairwiseMove(individual, city, allowInfeasible))
146              i++;
147
148            count = route1.Stops.Count;
149          }
150        }
151      }
152    }
153  }
154}
Note: See TracBrowser for help on using the repository browser.