Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12012 was 12012, checked in by ascheibe, 9 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 4.4 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;
73          if (individual.Tours.Count < problemInstance.Vehicles.Value)
74            max = max - 1;
75
76          int newTourIndex = rand.Next(max);
77          if (newTourIndex >= oldTourIndex)
78            newTourIndex++;
79
80          Tour newTour = individual.Tours[newTourIndex];
81          List<int> tourCities = new List<int>();
82          foreach (int stop in newTour.Stops) {
83            if (pdp == null ||
84              (pdp.GetDemand(stop) >= 0 &&
85              pdp.GetPickupDeliveryLocation(stop) != pdp.GetPickupDeliveryLocation(city) &&
86              pdp.GetPickupDeliveryLocation(stop) != city &&
87              pdp.GetPickupDeliveryLocation(city) != stop))
88              tourCities.Add(stop);
89          }
90
91          if (tourCities.Count > 0) {
92            int replaced = tourCities[rand.Next(tourCities.Count)];
93            move = new PotvinPDExchangeMove(city, oldTourIndex, newTourIndex, replaced, individual);
94          }
95        }
96
97        return move;
98      } else {
99        return null;
100      }
101    }
102
103    protected override PotvinPDExchangeMove[] GenerateMoves(PotvinEncoding individual, IVRPProblemInstance problemInstance) {
104      List<PotvinPDExchangeMove> result = new List<PotvinPDExchangeMove>();
105
106      PotvinPDExchangeMove move = Apply(individual, ProblemInstance, RandomParameter.ActualValue);
107      if (move != null)
108        result.Add(move);
109
110      return result.ToArray();
111    }
112  }
113}
Note: See TracBrowser for help on using the repository browser.