Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Manipulators/LocalSearchManipulator.cs @ 4206

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

Updated naming and description of the VRP operators (#1039)

File size: 4.5 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    [StorableConstructor]
34    private LocalSearchManipulator(bool deserializing) : base(deserializing) { }
35
36    public LocalSearchManipulator() : base() { }
37
38    private bool FindBetterInsertionPlace(
39      PotvinEncoding individual, int tour, int city, int length,
40      out int insertionTour, out int insertionPlace) {
41      bool insertionFound = false;
42      insertionTour = -1;
43      insertionPlace = 1;
44
45      List<int> toBeDeleted = individual.Tours[tour].Cities.GetRange(city, length);
46      double distance = GetLength(individual.Tours[tour]);
47      individual.Tours[tour].Cities.RemoveRange(city, length);
48      double removalBenefit = distance - GetLength(individual.Tours[tour]);
49
50      int currentTour = 0;
51      while (currentTour < individual.Tours.Count && !insertionFound) {
52        int currentCity = 0;
53        while (currentCity <= individual.Tours[currentTour].Cities.Count && !insertionFound) {
54          distance = GetLength(individual.Tours[currentTour]);
55          individual.Tours[currentTour].Cities.InsertRange(currentCity, toBeDeleted);
56          if (Feasible(individual.Tours[currentTour])) {
57            double lengthIncrease =
58              GetLength(individual.Tours[currentTour]) - distance;
59            if (removalBenefit > lengthIncrease) {
60              insertionTour = currentTour;
61              insertionPlace = currentCity;
62
63              insertionFound = true;
64            }
65          }
66          individual.Tours[currentTour].Cities.RemoveRange(currentCity, length);
67         
68          currentCity++;
69        }
70        currentTour++;
71      }
72
73      individual.Tours[tour].Cities.InsertRange(city, toBeDeleted);
74
75      return insertionFound;
76    }
77
78    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
79      //only apply to feasible individuals
80      if (Feasible(individual)) {
81        bool insertionFound;
82
83        do {
84          insertionFound = false;
85          int length = 3;
86          while (length > 0 && !insertionFound) {
87            int tour = 0;
88            while (tour < individual.Tours.Count && !insertionFound) {
89              int city = 0;
90              while (city <= individual.Tours[tour].Cities.Count - length && !insertionFound) {
91                int insertionTour, insertionPlace;
92                if (FindBetterInsertionPlace(individual, tour, city, length,
93                 out insertionTour, out insertionPlace)) {
94                  insertionFound = true;
95
96                  List<int> toBeInserted = individual.Tours[tour].Cities.GetRange(city, length);
97
98                  individual.Tours[tour].Cities.RemoveRange(city, length);
99                  individual.Tours[insertionTour].Cities.InsertRange(
100                    insertionPlace,
101                    toBeInserted);
102                }
103                city++;
104              }
105              tour++;
106            }
107            length--;
108          }
109        } while (insertionFound);
110      }
111    }
112  }
113}
Note: See TracBrowser for help on using the repository browser.