Free cookie consent management tool by TermsFeed Policy Generator

source: branches/gteufl/HeuristicLab.Problems.VehicleRouting/3.4/Improver/VRPIntraRouteImprovementOperator.cs @ 12969

Last change on this file since 12969 was 12969, checked in by gkronber, 9 years ago

#2478 merged all changes from trunk to branch before trunk-reintegration

File size: 3.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 System.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
27
28namespace HeuristicLab.Problems.VehicleRouting {
29  /// <summary>
30  /// An operator which improves VRP solutions.
31  /// </summary>
32  [Item("VRPIntraRouteImprovementOperator", "An operator which improves VRP solutions.")]
33  [StorableClass]
34  public sealed class VRPIntraRouteImprovementOperator : VRPImprovementOperator {
35    [StorableConstructor]
36    private VRPIntraRouteImprovementOperator(bool deserializing) : base(deserializing) { }
37    private VRPIntraRouteImprovementOperator(VRPIntraRouteImprovementOperator original, Cloner cloner) : base(original, cloner) { }
38    public VRPIntraRouteImprovementOperator() : base() { }
39
40    public override IDeepCloneable Clone(Cloner cloner) {
41      return new VRPIntraRouteImprovementOperator(this, cloner);
42    }
43
44    protected override int Improve(PotvinEncoding solution) {
45      int evaluatedSolutions = 0;
46
47      var rand = RandomParameter.ActualValue;
48      var instance = ProblemInstance;
49      int sampleSize = SampleSizeParameter.Value.Value;
50      int attempts = ImprovementAttemptsParameter.Value.Value;
51      int customers = instance.Cities.Value;
52
53      // store city-to-tour assignment and position of the city within the tour
54      var tours = new Dictionary<int, Tour>();
55      var position = new Dictionary<int, int>();
56      foreach (Tour tour in solution.Tours) {
57        for (int stop = 0; stop < tour.Stops.Count; stop++) {
58          int city = tour.Stops[stop];
59          tours[city] = tour;
60          position[city] = stop;
61        }
62      }
63
64      for (int attempt = 0; attempt < attempts; attempt++) {
65        for (int sample = 0; sample < sampleSize; sample++) {
66          int chosenCust = 1 + rand.Next(customers);
67          var custTour = tours[chosenCust];
68
69          double beforeQuality = instance.EvaluateTour(custTour, solution).Quality;
70          evaluatedSolutions++;
71
72          custTour.Stops.RemoveAt(position[chosenCust]);
73          int place = solution.FindBestInsertionPlace(custTour, chosenCust);
74          evaluatedSolutions += custTour.Stops.Count;
75          custTour.Stops.Insert(place, chosenCust);
76
77          if (place != position[chosenCust]) {
78            double afterQuality = instance.EvaluateTour(custTour, solution).Quality;
79            if (afterQuality > beforeQuality) {
80              // revert move
81              custTour.Stops.RemoveAt(place);
82              custTour.Stops.Insert(position[chosenCust], chosenCust);
83            } else {
84              // accept move and update positions of the cities within the tour
85              for (int stop = 0; stop < custTour.Stops.Count; stop++) {
86                int city = custTour.Stops[stop];
87                position[city] = stop;
88              }
89              break;
90            }
91          }
92        }
93      }
94
95      return evaluatedSolutions;
96    }
97  }
98}
Note: See TracBrowser for help on using the repository browser.