Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs @ 6753

Last change on this file since 6753 was 6753, checked in by svonolfe, 13 years ago

Added customer relocation manipulator (#1177)

File size: 7.9 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;
28using HeuristicLab.Common;
29using HeuristicLab.Problems.VehicleRouting.Variants;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
32  [Item("PotvinCustomerRelocationMainpulator", "A customer relocation operator")]
33  [StorableClass]
34  public sealed class PotvinCustomerRelocationMainpulator : PotvinManipulator, IPickupAndDeliveryOperator {
35    [StorableConstructor]
36    private PotvinCustomerRelocationMainpulator(bool deserializing) : base(deserializing) { }
37
38    public PotvinCustomerRelocationMainpulator() : base() { }
39
40    public override IDeepCloneable Clone(Cloner cloner) {
41      return new PotvinCustomerRelocationMainpulator(this, cloner);
42    }
43
44    private PotvinCustomerRelocationMainpulator(PotvinCustomerRelocationMainpulator original, Cloner cloner)
45      : base(original, cloner) {
46    }
47
48    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
49      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
50      bool performed = false;
51
52      int selectedIndex;
53      Tour route1;
54
55      int mode = random.Next(0,3);
56
57      //Try pickup and delivery first
58      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
59      if (pdp != null && mode == 0) {
60        selectedIndex = SelectRandomTourBiasedByLength(random, individual);
61        route1 =
62          individual.Tours[selectedIndex];
63
64        List<int> deliveryViolations = new List<int>();
65
66        Dictionary<int, bool> visited = new Dictionary<int, bool>();
67        for (int i = 0; i < route1.Stops.Count; i++) {
68          int stop = route1.Stops[i];
69          if (ProblemInstance.Demand[stop] < 0) {
70            int source = pdp.PickupDeliveryLocation[stop];
71
72            if (!visited.ContainsKey(source))
73              deliveryViolations.Add(stop);
74          }
75
76          visited.Add(stop, true);
77        }
78
79        if (deliveryViolations.Count > 0) {
80          int selected =
81            deliveryViolations[random.Next(deliveryViolations.Count)];
82
83          int source = pdp.PickupDeliveryLocation[selected];
84
85          //find route of source
86          Tour found = null;
87          foreach (Tour tour in individual.Tours) {
88            if (tour.Stops.Contains(source)) {
89              found = tour;
90              break;
91            }
92          }
93
94          if (found != null) {
95            double rand = random.NextDouble();
96            if (rand < 0.33) {
97              route1.Stops.Remove(selected);
98
99              int index = individual.FindBestInsertionPlace(found, selected);
100              found.Stops.Insert(index, selected);
101              performed = true;
102
103              if (route1.Stops.Count == 0)
104                individual.Tours.Remove(route1);
105            } else if (rand < 0.66) {
106              found.Stops.Remove(source);
107
108              int index = individual.FindBestInsertionPlace(route1, source);
109              route1.Stops.Insert(index, source);
110              performed = true;
111
112              if (found.Stops.Count == 0)
113                individual.Tours.Remove(found);
114            } else {
115              found.Stops.Remove(source);
116              route1.Stops.Remove(selected);
117
118              int chosenRoute = random.Next(individual.Tours.Count);
119              Tour tour = individual.Tours[chosenRoute];
120
121              int index = individual.FindBestInsertionPlace(tour, source);
122              tour.Stops.Insert(index, source);
123              index = individual.FindBestInsertionPlace(tour, selected);
124              tour.Stops.Insert(index, selected);
125
126              if (found.Stops.Count == 0)
127                individual.Tours.Remove(found);
128              if (route1.Stops.Count == 0)
129                individual.Tours.Remove(route1);
130            }
131          }
132        }
133      }
134
135      //then try tw
136      if (!performed && mode == 1) {
137        ITimeWindowedProblemInstance vrptw = ProblemInstance as ITimeWindowedProblemInstance;
138
139        if (vrptw != null) {
140          selectedIndex = SelectRandomTourBiasedByLength(random, individual);
141          route1 =
142            individual.Tours[selectedIndex];
143
144          DoubleArray dueTime = vrptw.DueTime;
145          DoubleArray readyTime = vrptw.ReadyTime;
146          DoubleArray serviceTimes = vrptw.ServiceTime;
147
148          List<int> timeWindowViolations = new List<int>();
149          double time = 0;
150
151          for (int i = 0; i < route1.Stops.Count; i++) {
152            int start = 0;
153            if (i > 0)
154              start = route1.Stops[i - 1];
155            int end = 0;
156            if (i < route1.Stops.Count)
157              end = route1.Stops[i];
158
159            //drive there
160            double currentDistace = vrptw.GetDistance(start, end);
161            time += currentDistace;
162
163            //check if it was serviced on time
164            if (time > dueTime[end]) {
165              timeWindowViolations.Add(end);
166            }
167
168            //wait
169            double currentWaitingTime = 0.0;
170            if (time < readyTime[end])
171              currentWaitingTime = readyTime[end] - time;
172            time += currentWaitingTime;
173
174            //service
175            double currentServiceTime = serviceTimes[end];
176            time += currentServiceTime;
177          }
178
179          if (timeWindowViolations.Count > 0) {
180            int selected =
181              timeWindowViolations[random.Next(timeWindowViolations.Count)];
182
183            int oldIndex = route1.Stops.IndexOf(selected);
184            route1.Stops.Remove(selected);
185
186            int route, place;
187            if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
188              Tour newTour = individual.Tours[route];
189              newTour.Stops.Insert(place, selected);
190              performed = true;
191            } else {
192              route1.Stops.Insert(oldIndex, selected);
193            }
194
195            if (route1.Stops.Count == 0)
196              individual.Tours.Remove(route1);
197          }
198        }
199      }
200
201      //finally relocate random customer
202      if (!performed) {
203        selectedIndex = SelectRandomTourBiasedByLength(random, individual);
204        route1 =
205          individual.Tours[selectedIndex];
206
207        int selected = route1.Stops[random.Next(route1.Stops.Count)];
208        int oldIndex = route1.Stops.IndexOf(selected);
209        route1.Stops.Remove(selected);
210
211        int route, place;
212        if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
213          Tour tour = individual.Tours[route];
214          tour.Stops.Insert(place, selected);
215          performed = true;
216        } else {
217          route1.Stops.Insert(oldIndex, selected);
218        }
219
220        if (route1.Stops.Count == 0)
221          individual.Tours.Remove(route1);
222      }
223    }
224  }
225}
Note: See TracBrowser for help on using the repository browser.