Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeSingleMoveGenerator.cs @ 13420

Last change on this file since 13420 was 13420, checked in by pfleck, 9 years ago

#2532
Corrected the range of randomly selected tours for the PDExchange-move.
Because the PDExchange-move swaps two cities from different tours, it makes no sense to select a new(empty) tour as there aren't any cities to swap.

File size: 4.3 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.Optimization;
26using HeuristicLab.Parameters;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Problems.VehicleRouting.Interfaces;
29using HeuristicLab.Problems.VehicleRouting.Variants;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
32  [Item("PotvinPDExchangeSingleMoveGenerator", "Generates a single exchange move from a given PDP encoding.")]
33  [StorableClass]
34  public sealed class PotvinPDExchangeSingleMoveGenerator : PotvinPDExchangeMoveGenerator,
35    ISingleMoveGenerator {
36    public ILookupParameter<IRandom> RandomParameter {
37      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
38    }
39
40    public override IDeepCloneable Clone(Cloner cloner) {
41      return new PotvinPDExchangeSingleMoveGenerator(this, cloner);
42    }
43
44    [StorableConstructor]
45    private PotvinPDExchangeSingleMoveGenerator(bool deserializing) : base(deserializing) { }
46
47    public PotvinPDExchangeSingleMoveGenerator()
48      : base() {
49      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
50    }
51
52    private PotvinPDExchangeSingleMoveGenerator(PotvinPDExchangeSingleMoveGenerator original, Cloner cloner)
53      : base(original, cloner) {
54    }
55
56    public static PotvinPDExchangeMove Apply(PotvinEncoding individual, IVRPProblemInstance problemInstance, IRandom rand) {
57      List<int> cities = new List<int>();
58
59      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
60      for (int i = 1; i <= individual.Cities; i++) {
61        if (pdp == null || pdp.GetDemand(i) >= 0)
62          cities.Add(i);
63      }
64
65      if (cities.Count > 1 && individual.Tours.Count > 1) {
66        PotvinPDExchangeMove move = null;
67        while (cities.Count > 1 && move == null) {
68          int city = cities[rand.Next(cities.Count)];
69          Tour oldTour = individual.Tours.Find(t => t.Stops.Contains(city));
70          int oldTourIndex = individual.Tours.IndexOf(oldTour);
71
72          int max = individual.Tours.Count - 1;
73
74          int newTourIndex = rand.Next(max);
75          if (newTourIndex >= oldTourIndex)
76            newTourIndex++;
77
78          Tour newTour = individual.Tours[newTourIndex];
79          List<int> tourCities = new List<int>();
80          foreach (int stop in newTour.Stops) {
81            if (pdp == null ||
82              (pdp.GetDemand(stop) >= 0 &&
83              pdp.GetPickupDeliveryLocation(stop) != pdp.GetPickupDeliveryLocation(city) &&
84              pdp.GetPickupDeliveryLocation(stop) != city &&
85              pdp.GetPickupDeliveryLocation(city) != stop))
86              tourCities.Add(stop);
87          }
88
89          if (tourCities.Count > 0) {
90            int replaced = tourCities[rand.Next(tourCities.Count)];
91            move = new PotvinPDExchangeMove(city, oldTourIndex, newTourIndex, replaced, individual);
92          }
93        }
94
95        return move;
96      } else {
97        return null;
98      }
99    }
100
101    protected override PotvinPDExchangeMove[] GenerateMoves(PotvinEncoding individual, IVRPProblemInstance problemInstance) {
102      List<PotvinPDExchangeMove> result = new List<PotvinPDExchangeMove>();
103
104      PotvinPDExchangeMove move = Apply(individual, ProblemInstance, RandomParameter.ActualValue);
105      if (move != null)
106        result.Add(move);
107
108      return result.ToArray();
109    }
110  }
111}
Note: See TracBrowser for help on using the repository browser.