Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeSingleMoveGenerator.cs @ 6856

Last change on this file since 6856 was 6856, checked in by svonolfe, 11 years ago

Added support for the multi depot pickup and delivery problem with time windows (#1177)

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