Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs @ 6710

Last change on this file since 6710 was 6710, checked in by svonolfe, 13 years ago

Added support for pickups and deliveries (#1177)

File size: 9.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 System.Collections.Generic;
26using HeuristicLab.Data;
27using System;
28using HeuristicLab.Parameters;
29using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
32  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations. It is implemented as described in Berger, J and Solois, M and Begin, R (1998). A hybrid genetic algorithm for the vehicle routing problem with time windows. LNCS 1418. Springer, London 114-127.")]
33  [StorableClass]
34  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {
35    public IValueParameter<IntValue> Length {
36      get { return (IValueParameter<IntValue>)Parameters["Length"]; }
37    }
38
39    [StorableConstructor]
40    private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }
41    private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)
42      : base(original, cloner) {
43    }
44    public override IDeepCloneable Clone(Cloner cloner) {
45      return new PotvinInsertionBasedCrossover(this, cloner);
46    }
47    public PotvinInsertionBasedCrossover()
48      : base() {
49      Parameters.Add(new ValueParameter<IntValue>("Length", "The maximum length of the replaced route.", new IntValue(1)));
50    }
51
52    private static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
53      int tourIndex = -1;
54
55      double sum = 0.0;
56      double[] probabilities = new double[individual.Tours.Count];
57      for (int i = 0; i < individual.Tours.Count; i++) {
58        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)individual.Cities);
59        sum += probabilities[i];
60      }
61
62      double rand = random.NextDouble() * sum;
63      double cumulatedProbabilities = 0.0;
64      int index = 0;
65      while (tourIndex == -1 && index < probabilities.Length) {
66        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
67          tourIndex = index;
68
69        cumulatedProbabilities += probabilities[index];
70        index++;
71      }
72
73      return tourIndex;
74    }
75
76    private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {
77      double xSum = 0;
78      double ySum = 0;
79      double c1X, c1Y, c2X, c2Y;
80
81      for (int i = 0; i < t1.Stops.Count; i++) {
82        xSum += coordinates[t1.Stops[i], 0];
83        ySum += coordinates[t1.Stops[i], 1];
84      }
85      c1X = xSum / t1.Stops.Count;
86      c1Y = ySum / t1.Stops.Count;
87
88      for (int i = 0; i < t2.Stops.Count; i++) {
89        xSum += coordinates[t2.Stops[i], 0];
90        ySum += coordinates[t2.Stops[i], 1];
91      }
92      c2X = xSum / t1.Stops.Count;
93      c2Y = ySum / t1.Stops.Count;
94
95      return Math.Sqrt(
96           (c1X - c2X) * (c1X - c2X) +
97           (c1Y - c2Y) * (c1Y - c2Y));
98    }
99
100    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {
101      double sum = 0;
102
103      for (int i = 0; i < tours.Count; i++) {
104        sum += CalculateCentroidDistance(t1, tours[i], coordinates);
105      }
106
107      return sum / tours.Count;
108    }
109
110    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour) {
111      int cityIndex = -1;
112
113      double sum = 0.0;
114      double[] probabilities = new double[tour.Stops.Count];
115      for (int i = 0; i < tour.Stops.Count; i++) {
116        int next;
117        if (i + 1 >= tour.Stops.Count)
118          next = 0;
119        else
120          next = tour.Stops[i + 1];
121        double distance = ProblemInstance.GetDistance(
122          tour.Stops[i], next);
123
124        int prev;
125        if (i - 1 < 0)
126          prev = 0;
127        else
128          prev = tour.Stops[i - 1];
129        distance += ProblemInstance.GetDistance(
130          tour.Stops[i], prev);
131
132        probabilities[i] = distance;
133        sum += probabilities[i];
134      }
135
136      double rand = random.NextDouble() * sum;
137      double cumulatedProbabilities = 0.0;
138      int index = 0;
139      while (cityIndex == -1 && index < probabilities.Length) {
140        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
141          cityIndex = index;
142
143        cumulatedProbabilities += probabilities[index];
144        index++;
145      }
146
147      return cityIndex;
148    }
149
150    private bool FindRouteInsertionPlace(
151      Tour tour,
152      int city, bool allowInfeasible, out int place) {
153      place = -1;
154
155      if (tour.Stops.Contains(city))
156        return false;
157
158      bool bestFeasible = false;
159      double minDetour = 0;
160
161      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
162      double length = eval.Quality;
163      for (int i = 0; i <= tour.Stops.Count; i++) {
164        tour.Stops.Insert(i, city);
165
166        eval = ProblemInstance.Evaluate(tour);
167        bool feasible = ProblemInstance.Feasible(eval);
168
169        if (feasible || allowInfeasible && !bestFeasible) {
170          double newLength = eval.Quality;
171          double detour = newLength - length;
172
173          if (place < 0 || detour < minDetour || feasible && !bestFeasible) {
174            place = i;
175            minDetour = detour;
176
177            if (feasible)
178              bestFeasible = true;
179          }
180        }
181
182        tour.Stops.RemoveAt(i);
183      }
184
185      return place >= 0;
186    }
187
188    private ICollection<int> GetUnrouted(PotvinEncoding solution, int cities) {
189      HashSet<int> undiscovered = new HashSet<int>();
190      for (int i = 1; i <= cities; i++) {
191        undiscovered.Add(i);
192      }
193
194      foreach (Tour tour in solution.Tours) {
195        foreach (int city in tour.Stops)
196          undiscovered.Remove(city);
197      }
198
199      return undiscovered;
200    }
201
202    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
203      PotvinEncoding child = new PotvinEncoding(ProblemInstance);
204
205      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
206
207      List<Tour> R1 = new List<Tour>();
208      PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
209
210      int length = Math.Min(Length.Value.Value, parent1.Tours.Count) + 1;
211      int k = random.Next(1, length);
212      for (int i = 0; i < k; i++) {
213        int index = SelectRandomTourBiasedByLength(random, p1Clone);
214        R1.Add(p1Clone.Tours[index]);
215        p1Clone.Tours.RemoveAt(index);
216      }
217
218      foreach (Tour r1 in R1) {
219        List<int> R2 = new List<int>();
220
221        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance.Coordinates);
222        foreach (Tour tour in parent2.Tours) {
223          if (CalculateCentroidDistance(r1, tour, ProblemInstance.Coordinates) <= r) {
224            R2.AddRange(tour.Stops);
225          }
226        }
227
228        Tour childTour = new Tour();
229        childTour.Stops.AddRange(r1.Stops);
230
231        //DESTROY - remove cities from r1
232        int removed = random.Next(1, r1.Stops.Count + 1);
233        for (int i = 0; i < removed; i++) {
234          childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour));
235        }
236
237        //REPAIR - add cities from R2
238        int maxCount = random.Next(1, Math.Min(5, R2.Count));
239        int count = 0;
240
241        while (count < maxCount && R2.Count != 0) {
242          PotvinEncoding newChild = child.Clone() as PotvinEncoding;
243          newChild.Tours.Add(childTour);
244
245          int index = random.Next(R2.Count);
246          int city = R2[index];
247          R2.RemoveAt(index);
248
249          int place = -1;
250          if (FindRouteInsertionPlace(childTour, city, allowInfeasible, out place)) {
251            childTour.Stops.Insert(place, city);
252
253            if (!Repair(random, child, childTour, ProblemInstance, allowInfeasible)) {
254              childTour.Stops.RemoveAt(place);
255            } else {
256              count++;
257            }
258          }
259        }
260
261        child.Tours.Add(childTour);
262        Repair(random, child, childTour, ProblemInstance, allowInfeasible);
263      }
264
265      for (int i = 0; i < p1Clone.Tours.Count; i++) {
266        Tour childTour = p1Clone.Tours[i].Clone() as Tour;
267        child.Tours.Add(childTour);
268        Repair(random, child, childTour, ProblemInstance, allowInfeasible);
269      }
270
271      //route unrouted customers
272      child.Unrouted.AddRange(GetUnrouted(child, ProblemInstance.Cities.Value));
273      bool success = RouteUnrouted(child, allowInfeasible);
274
275      if (success || allowInfeasible)
276        return child;
277      else {
278        if (random.NextDouble() < 0.5)
279          return parent1.Clone() as PotvinEncoding;
280        else
281          return parent2.Clone() as PotvinEncoding;
282      }
283    }
284  }
285}
Note: See TracBrowser for help on using the repository browser.