source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.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: 5.7 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("PotvinPairwiseOneLevelExchangeMainpulator", "The 1M 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 PotvinPairwiseOneLevelExchangeMainpulator : PotvinManipulator {
36    [StorableConstructor]
37    private PotvinPairwiseOneLevelExchangeMainpulator(bool deserializing) : base(deserializing) { }
38
39    public PotvinPairwiseOneLevelExchangeMainpulator() : base() { }
40
41    public override IDeepCloneable Clone(Cloner cloner) {
42      return new PotvinPairwiseOneLevelExchangeMainpulator(this, cloner);
43    }
44
45    private PotvinPairwiseOneLevelExchangeMainpulator(PotvinPairwiseOneLevelExchangeMainpulator original, Cloner cloner)
46      : base(original, cloner) {
47    }
48
49    public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {
50      bool success;
51
52      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
53
54      if (pdp != null) {
55        Tour route1 = individual.Tours.Find(t => t.Stops.Contains(city));
56        int i = route1.Stops.IndexOf(city);
57
58        int dest = pdp.GetPickupDeliveryLocation(city);
59        Tour destRoute = individual.Tours.Find(t => t.Stops.Contains(dest));
60        int j = destRoute.Stops.IndexOf(dest);
61
62        route1.Stops.Remove(city);
63        destRoute.Stops.Remove(dest);
64
65        int routeToAvoid = -1;
66        if (route1 == destRoute)
67          routeToAvoid = individual.Tours.IndexOf(route1);
68
69        int source, target;
70        if (ProblemInstance.GetDemand(city) >= 0) {
71          source = city;
72          target = dest;
73        } else {
74          source = dest;
75          target = city;
76        }
77
78        double bestQuality = double.MaxValue;
79        int bestTour = -1;
80        int bestPositionSource = -1;
81        int bestPositionTarget = -1;
82
83        for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
84          if (tourIdx != routeToAvoid) {
85            Tour tour = individual.Tours[tourIdx];
86            VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
87            individual.InsertPair(tour, source, target, ProblemInstance);
88            VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
89
90            double delta = evalNew.Quality - eval.Quality;
91
92            if (delta < bestQuality &&
93               (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
94              bestQuality = delta;
95              bestTour = tourIdx;
96              bestPositionSource = tour.Stops.IndexOf(source);
97              bestPositionTarget = tour.Stops.IndexOf(target);
98            }
99
100            tour.Stops.Remove(source);
101            tour.Stops.Remove(target);
102          }
103        }
104
105        if (bestTour >= 0) {
106          if (bestPositionTarget < bestPositionSource) {
107            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
108            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
109          } else {
110            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
111            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
112          }
113
114          success = true;
115        } else {
116          if (j < i) {
117            destRoute.Stops.Insert(j, dest);
118            route1.Stops.Insert(i, city);
119          } else {
120            route1.Stops.Insert(i, city);
121            destRoute.Stops.Insert(j, dest);
122          }
123
124          success = false;
125        }
126      } else {
127        success = false;
128      }
129
130      return success;
131    }
132
133    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
134      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
135
136      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
137      if (selectedIndex >= 0) {
138        Tour route1 =
139          individual.Tours[selectedIndex];
140
141        int count = route1.Stops.Count;
142
143        if (count > 0) {
144          int i = random.Next(0, count);
145          int city = route1.Stops[i];
146
147          if (!PairwiseMove(individual, city, allowInfeasible))
148            i++;
149
150          count = route1.Stops.Count;
151        }
152      }
153    }
154  }
155}
Note: See TracBrowser for help on using the repository browser.