Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs @ 17712

Last change on this file since 17712 was 17712, checked in by abeham, 4 years ago

#2521: working on VRP

File size: 5.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HEAL.Attic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Problems.VehicleRouting.Interfaces;
26using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
27using HeuristicLab.Problems.VehicleRouting.Variants;
28
29namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
30  [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.")]
31  [StorableType("BF040F90-535E-4F3D-9420-0123565A252D")]
32  public sealed class PotvinPairwiseOneLevelExchangeMainpulator : PotvinManipulator {
33    [StorableConstructor]
34    private PotvinPairwiseOneLevelExchangeMainpulator(StorableConstructorFlag _) : base(_) { }
35
36    public PotvinPairwiseOneLevelExchangeMainpulator() : base() { }
37
38    public override IDeepCloneable Clone(Cloner cloner) {
39      return new PotvinPairwiseOneLevelExchangeMainpulator(this, cloner);
40    }
41
42    private PotvinPairwiseOneLevelExchangeMainpulator(PotvinPairwiseOneLevelExchangeMainpulator original, Cloner cloner)
43      : base(original, cloner) {
44    }
45
46    public static bool PairwiseMove(PotvinEncodedSolution individual, IVRPProblemInstance instance, int city, bool allowInfeasible) {
47      bool success;
48
49      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
50
51      if (pdp != null) {
52        Tour route1 = individual.Tours.Find(t => t.Stops.Contains(city));
53        int i = route1.Stops.IndexOf(city);
54
55        int dest = pdp.GetPickupDeliveryLocation(city);
56        Tour destRoute = individual.Tours.Find(t => t.Stops.Contains(dest));
57        int j = destRoute.Stops.IndexOf(dest);
58
59        route1.Stops.Remove(city);
60        destRoute.Stops.Remove(dest);
61
62        int routeToAvoid = -1;
63        if (route1 == destRoute)
64          routeToAvoid = individual.Tours.IndexOf(route1);
65
66        int source, target;
67        if (instance.GetDemand(city) >= 0) {
68          source = city;
69          target = dest;
70        } else {
71          source = dest;
72          target = city;
73        }
74
75        double bestQuality = double.MaxValue;
76        int bestTour = -1;
77        int bestPositionSource = -1;
78        int bestPositionTarget = -1;
79
80        for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
81          if (tourIdx != routeToAvoid) {
82            Tour tour = individual.Tours[tourIdx];
83            VRPEvaluation eval = instance.EvaluateTour(tour, individual);
84            individual.InsertPair(tour, source, target, instance);
85            VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);
86
87            double delta = evalNew.Quality - eval.Quality;
88
89            if (delta < bestQuality &&
90               (evalNew.IsFeasible || allowInfeasible)) {
91              bestQuality = delta;
92              bestTour = tourIdx;
93              bestPositionSource = tour.Stops.IndexOf(source);
94              bestPositionTarget = tour.Stops.IndexOf(target);
95            }
96
97            tour.Stops.Remove(source);
98            tour.Stops.Remove(target);
99          }
100        }
101
102        if (bestTour >= 0) {
103          if (bestPositionTarget < bestPositionSource) {
104            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
105            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
106          } else {
107            individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
108            individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
109          }
110
111          success = true;
112        } else {
113          if (j < i) {
114            destRoute.Stops.Insert(j, dest);
115            route1.Stops.Insert(i, city);
116          } else {
117            route1.Stops.Insert(i, city);
118            destRoute.Stops.Insert(j, dest);
119          }
120
121          success = false;
122        }
123      } else {
124        success = false;
125      }
126
127      return success;
128    }
129
130    public static void ApplyManipulation(IRandom random, PotvinEncodedSolution individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
131      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
132      if (selectedIndex >= 0) {
133        Tour route1 =
134          individual.Tours[selectedIndex];
135
136        int count = route1.Stops.Count;
137
138        if (count > 0) {
139          int i = random.Next(0, count);
140          int city = route1.Stops[i];
141
142          if (!PairwiseMove(individual, pdp, city, allowInfeasible))
143            i++;
144
145          count = route1.Stops.Count;
146        }
147      }
148    }
149
150
151    protected override void Manipulate(IRandom random, PotvinEncodedSolution individual) {
152      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
153
154      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
155
156      if (pdp != null) {
157        ApplyManipulation(random, individual, pdp, allowInfeasible);
158      }
159    }
160  }
161}
Note: See TracBrowser for help on using the repository browser.