Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Manipulators/LocalSearchManipulator.cs @ 4265

Last change on this file since 4265 was 4265, checked in by svonolfe, 12 years ago

Fixed a bug in the Local search manipulator (#1039)

File size: 5.1 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;
28
29namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
30  [Item("LocalSearchManipulator", "The LSM 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.")]
31  [StorableClass]
32  public sealed class LocalSearchManipulator : PotvinManipulator {
33    public IValueParameter<IntValue> Iterations {
34      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
35    }
36
37    [StorableConstructor]
38    private LocalSearchManipulator(bool deserializing) : base(deserializing) { }
39
40    public LocalSearchManipulator() : base() {
41      Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of max iterations.", new IntValue(100)));
42    }
43
44    private bool FindBetterInsertionPlace(
45      PotvinEncoding individual, int tour, int city, int length,
46      out int insertionTour, out int insertionPlace) {
47      bool insertionFound = false;
48      insertionTour = -1;
49      insertionPlace = 1;
50
51      List<int> toBeDeleted = individual.Tours[tour].Cities.GetRange(city, length);
52      double distance = GetLength(individual.Tours[tour]);
53      individual.Tours[tour].Cities.RemoveRange(city, length);
54      double removalBenefit = distance - GetLength(individual.Tours[tour]);
55
56      int currentTour = 0;
57      while (currentTour < individual.Tours.Count && !insertionFound) {
58        int currentCity = 0;
59        while (currentCity <= individual.Tours[currentTour].Cities.Count && !insertionFound) {
60          distance = GetLength(individual.Tours[currentTour]);
61          individual.Tours[currentTour].Cities.InsertRange(currentCity, toBeDeleted);
62          if (Feasible(individual.Tours[currentTour])) {
63            double lengthIncrease =
64              GetLength(individual.Tours[currentTour]) - distance;
65            if (removalBenefit > lengthIncrease) {
66              insertionTour = currentTour;
67              insertionPlace = currentCity;
68
69              insertionFound = true;
70            }
71          }
72          individual.Tours[currentTour].Cities.RemoveRange(currentCity, length);
73         
74          currentCity++;
75        }
76        currentTour++;
77      }
78
79      individual.Tours[tour].Cities.InsertRange(city, toBeDeleted);
80
81      return insertionFound;
82    }
83
84    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
85      //only apply to feasible individuals
86      if (Feasible(individual)) {
87        bool insertionFound;
88        int iterations = 0;
89
90        do {
91          insertionFound = false;
92          int length = 3;
93          while (length > 0 && !insertionFound) {
94            int tour = 0;
95            while (tour < individual.Tours.Count && !insertionFound) {
96              int city = 0;
97              while (city <= individual.Tours[tour].Cities.Count - length && !insertionFound) {
98                int insertionTour, insertionPlace;
99                if (FindBetterInsertionPlace(individual, tour, city, length,
100                 out insertionTour, out insertionPlace)) {
101                  insertionFound = true;
102
103                  List<int> toBeInserted = individual.Tours[tour].Cities.GetRange(city, length);
104
105                  individual.Tours[tour].Cities.RemoveRange(city, length);
106                  individual.Tours[insertionTour].Cities.InsertRange(
107                    insertionPlace,
108                    toBeInserted);
109                }
110                city++;
111              }
112              tour++;
113            }
114            length--;
115          }
116          iterations++;
117        } while (insertionFound &&
118          iterations < Iterations.Value.Value);
119
120        IList<Tour> toBeRemoved = new List<Tour>();
121        foreach (Tour tour in individual.Tours) {
122          if (tour.Cities.Count == 0)
123            toBeRemoved.Add(tour);
124        }
125
126        foreach (Tour tour in toBeRemoved) {
127          individual.Tours.Remove(tour);
128        }
129      }
130    }
131  }
132}
Note: See TracBrowser for help on using the repository browser.