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 |
|
---|
22 | using HeuristicLab.Core;
|
---|
23 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
24 | using HeuristicLab.Parameters;
|
---|
25 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
26 | using HeuristicLab.Data;
|
---|
27 | using System.Collections.Generic;
|
---|
28 |
|
---|
29 | namespace HeuristicLab.Problems.VehicleRouting.Encodings.Prins {
|
---|
30 | [Item("PrinsLSManipulator", "An operator which manipulates a VRP representation by using the Prins local search. It is implemented as described in Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 12:1985-2002.")]
|
---|
31 | [StorableClass]
|
---|
32 | public abstract class PrinsLSManipulator : PrinsManipulator {
|
---|
33 | public IValueParameter<IntValue> Iterations {
|
---|
34 | get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
|
---|
35 | }
|
---|
36 |
|
---|
37 | [StorableConstructor]
|
---|
38 | protected PrinsLSManipulator(bool deserializing) : base(deserializing) { }
|
---|
39 |
|
---|
40 | public PrinsLSManipulator()
|
---|
41 | : base() {
|
---|
42 | Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of max iterations.", new IntValue(5)));
|
---|
43 | }
|
---|
44 |
|
---|
45 | protected double GetQuality(PrinsEncoding individual) {
|
---|
46 | return VRPEvaluator.Evaluate(individual,
|
---|
47 | VehiclesParameter.ActualValue,
|
---|
48 | DueTimeParameter.ActualValue,
|
---|
49 | ServiceTimeParameter.ActualValue,
|
---|
50 | ReadyTimeParameter.ActualValue,
|
---|
51 | DemandParameter.ActualValue,
|
---|
52 | CapacityParameter.ActualValue,
|
---|
53 | FleetUsageFactor.ActualValue,
|
---|
54 | TimeFactor.ActualValue,
|
---|
55 | DistanceFactor.ActualValue,
|
---|
56 | OverloadPenalty.ActualValue,
|
---|
57 | TardinessPenalty.ActualValue,
|
---|
58 | CoordinatesParameter.ActualValue,
|
---|
59 | DistanceMatrixParameter,
|
---|
60 | UseDistanceMatrixParameter.ActualValue).Quality;
|
---|
61 | }
|
---|
62 |
|
---|
63 | private int FindCity(PrinsEncoding individual, int city) {
|
---|
64 | int index = -1;
|
---|
65 |
|
---|
66 | int i = 0;
|
---|
67 | while (i < individual.Length && index == -1) {
|
---|
68 | if (individual[i] == city)
|
---|
69 | index = i;
|
---|
70 |
|
---|
71 | i++;
|
---|
72 | }
|
---|
73 |
|
---|
74 | return index;
|
---|
75 | }
|
---|
76 |
|
---|
77 | protected const int depot = -1;
|
---|
78 |
|
---|
79 | private Tour FindTour(PrinsEncoding individual, int citiy) {
|
---|
80 | Tour found = null;
|
---|
81 |
|
---|
82 | List<Tour> tours = individual.GetTours(DistanceMatrixParameter);
|
---|
83 | int i = 0;
|
---|
84 |
|
---|
85 | while (found == null && i < tours.Count) {
|
---|
86 | if (tours[i].Cities.Contains(citiy + 1))
|
---|
87 | found = tours[i];
|
---|
88 |
|
---|
89 | i++;
|
---|
90 | }
|
---|
91 |
|
---|
92 | return found;
|
---|
93 | }
|
---|
94 |
|
---|
95 | //inserts u after v in the child
|
---|
96 | private void InsertAfter(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
97 | int pi = 0;
|
---|
98 | int ci = 0;
|
---|
99 |
|
---|
100 | while (ci != child.Length) {
|
---|
101 | if (parent[pi] != u) {
|
---|
102 | child[ci] = parent[pi];
|
---|
103 | ci++;
|
---|
104 | }
|
---|
105 | if (parent[pi] == v) {
|
---|
106 | child[ci] = u;
|
---|
107 | ci++;
|
---|
108 | }
|
---|
109 |
|
---|
110 | pi++;
|
---|
111 | }
|
---|
112 | }
|
---|
113 |
|
---|
114 | //inserts (u, x) after v in the child
|
---|
115 | private void InsertAfter(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
116 | int pi = 0;
|
---|
117 | int ci = 0;
|
---|
118 |
|
---|
119 | while (ci != child.Length) {
|
---|
120 | if (parent[pi] != u && parent[pi] != x) {
|
---|
121 | child[ci] = parent[pi];
|
---|
122 | ci++;
|
---|
123 | }
|
---|
124 | if (parent[pi] == v) {
|
---|
125 | child[ci] = u;
|
---|
126 | ci++;
|
---|
127 |
|
---|
128 | child[ci] = x;
|
---|
129 | ci++;
|
---|
130 | }
|
---|
131 |
|
---|
132 | pi++;
|
---|
133 | }
|
---|
134 | }
|
---|
135 |
|
---|
136 | //inserts u before v in the child
|
---|
137 | private void InsertBefore(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
138 | int pi = 0;
|
---|
139 | int ci = 0;
|
---|
140 |
|
---|
141 | while (ci != child.Length) {
|
---|
142 | if (parent[pi] == v) {
|
---|
143 | child[ci] = u;
|
---|
144 | ci++;
|
---|
145 | }
|
---|
146 | if (parent[pi] != u) {
|
---|
147 | child[ci] = parent[pi];
|
---|
148 | ci++;
|
---|
149 | }
|
---|
150 |
|
---|
151 | pi++;
|
---|
152 | }
|
---|
153 | }
|
---|
154 |
|
---|
155 | //inserts (u, x) before v in the child
|
---|
156 | private void InsertBefore(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
157 | int pi = 0;
|
---|
158 | int ci = 0;
|
---|
159 |
|
---|
160 | while (ci != child.Length) {
|
---|
161 | if (parent[pi] == v) {
|
---|
162 | child[ci] = u;
|
---|
163 | ci++;
|
---|
164 |
|
---|
165 | child[ci] = x;
|
---|
166 | ci++;
|
---|
167 | }
|
---|
168 | if (parent[pi] != u && parent[pi] != x) {
|
---|
169 | child[ci] = parent[pi];
|
---|
170 | ci++;
|
---|
171 | }
|
---|
172 |
|
---|
173 | pi++;
|
---|
174 | }
|
---|
175 | }
|
---|
176 |
|
---|
177 | //swaps u and v
|
---|
178 | private void Swap(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
179 | for (int i = 0; i < child.Length; i++) {
|
---|
180 | if (parent[i] == u)
|
---|
181 | child[i] = v;
|
---|
182 | else if (parent[i] == v)
|
---|
183 | child[i] = u;
|
---|
184 | else
|
---|
185 | child[i] = parent[i];
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | //swaps (u, x) and v
|
---|
190 | private void Swap(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
|
---|
191 | int childIndex = 0;
|
---|
192 | int parentIndex = 0;
|
---|
193 |
|
---|
194 | while(childIndex < child.Length) {
|
---|
195 | if (parent[parentIndex] == u) {
|
---|
196 | child[childIndex] = v;
|
---|
197 | parentIndex++;
|
---|
198 | } else if (parent[parentIndex] == v) {
|
---|
199 | child[childIndex] = u;
|
---|
200 | childIndex++;
|
---|
201 | child[childIndex] = x;
|
---|
202 | } else {
|
---|
203 | child[childIndex] = parent[parentIndex];
|
---|
204 | }
|
---|
205 |
|
---|
206 | childIndex++;
|
---|
207 | parentIndex++;
|
---|
208 | }
|
---|
209 | }
|
---|
210 |
|
---|
211 | //swaps (u, x) and (v, y)
|
---|
212 | private void Swap(int u, int x, int v, int y, PrinsEncoding parent, PrinsEncoding child) {
|
---|
213 | int i = 0;
|
---|
214 |
|
---|
215 | while (i < child.Length) {
|
---|
216 | if (child[i] == u) {
|
---|
217 | child[i] = v;
|
---|
218 | i++;
|
---|
219 | child[i] = y;
|
---|
220 | } else if (child[i] == v) {
|
---|
221 | child[i] = u;
|
---|
222 | i++;
|
---|
223 | child[i] = x;
|
---|
224 | } else {
|
---|
225 | child[i] = parent[i];
|
---|
226 | }
|
---|
227 |
|
---|
228 | i++;
|
---|
229 | }
|
---|
230 | }
|
---|
231 |
|
---|
232 | //swaps (u, x) and (v, y) by (u, y) and (x, v)
|
---|
233 | private void Swap2(int u, int x, int v, int y, PrinsEncoding parent, PrinsEncoding child) {
|
---|
234 | int i = 0;
|
---|
235 |
|
---|
236 | while (i < child.Length) {
|
---|
237 | if(parent[i] == x) {
|
---|
238 | child[i] = y;
|
---|
239 | } else if(parent[i] == v) {
|
---|
240 | child[i] = x;
|
---|
241 | } else if(parent[i] == y) {
|
---|
242 | child[i] = v;
|
---|
243 | } else {
|
---|
244 | child[i] = parent[i];
|
---|
245 | }
|
---|
246 |
|
---|
247 | i++;
|
---|
248 | }
|
---|
249 | }
|
---|
250 |
|
---|
251 | private void M1(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
252 | if (u != depot) {
|
---|
253 | if (v == depot) {
|
---|
254 | Tour tour = FindTour(child, u);
|
---|
255 | v = tour.Cities[0] - 1;
|
---|
256 | InsertBefore(u, v, parent, child);
|
---|
257 | } else {
|
---|
258 | InsertAfter(u, v, parent, child);
|
---|
259 | }
|
---|
260 | }
|
---|
261 |
|
---|
262 | if(!child.Validate()) {
|
---|
263 | }
|
---|
264 | }
|
---|
265 |
|
---|
266 | private void M2(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
267 | if (u != depot) {
|
---|
268 | Tour tour = FindTour(child, u);
|
---|
269 | int iu = tour.Cities.IndexOf(u + 1);
|
---|
270 | if (iu < tour.Cities.Count - 1) {
|
---|
271 | int x = tour.Cities[iu + 1] - 1;
|
---|
272 |
|
---|
273 | if (v == depot) {
|
---|
274 | tour = FindTour(child, u);
|
---|
275 | v = tour.Cities[0] - 1;
|
---|
276 | InsertBefore(u, x, v, parent, child);
|
---|
277 | } else {
|
---|
278 | InsertAfter(u, x, v, parent, child);
|
---|
279 | }
|
---|
280 | }
|
---|
281 | }
|
---|
282 |
|
---|
283 | if (!child.Validate()) {
|
---|
284 | }
|
---|
285 | }
|
---|
286 |
|
---|
287 | private void M3(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
288 | if (u != depot) {
|
---|
289 | Tour tour = FindTour(child, u);
|
---|
290 | int iu = tour.Cities.IndexOf(u + 1);
|
---|
291 | if (iu < tour.Cities.Count - 1) {
|
---|
292 | int x = tour.Cities[iu + 1] - 1;
|
---|
293 |
|
---|
294 | if (v == depot) {
|
---|
295 | tour = FindTour(child, u);
|
---|
296 | v = tour.Cities[0] - 1;
|
---|
297 | InsertBefore(x, u, v, parent, child);
|
---|
298 | } else {
|
---|
299 | InsertAfter(x, u, v, parent, child);
|
---|
300 | }
|
---|
301 | }
|
---|
302 | }
|
---|
303 |
|
---|
304 | if (!child.Validate()) {
|
---|
305 | }
|
---|
306 | }
|
---|
307 |
|
---|
308 | private void M4(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
309 | if (u != depot && v != depot) {
|
---|
310 | Swap(u, v, parent, child);
|
---|
311 | }
|
---|
312 |
|
---|
313 | if (!child.Validate()) {
|
---|
314 | }
|
---|
315 | }
|
---|
316 |
|
---|
317 | private void M5(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
318 | if (u != depot && v != depot) {
|
---|
319 | Tour tour = FindTour(child, u);
|
---|
320 | int iu = tour.Cities.IndexOf(u + 1);
|
---|
321 | if (iu < tour.Cities.Count - 1) {
|
---|
322 | int x = tour.Cities[iu + 1] - 1;
|
---|
323 |
|
---|
324 | if(x != v)
|
---|
325 | Swap(u, x, v, parent, child);
|
---|
326 | }
|
---|
327 | }
|
---|
328 |
|
---|
329 | if (!child.Validate()) {
|
---|
330 | }
|
---|
331 | }
|
---|
332 |
|
---|
333 | private void M6(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
334 | if (u != depot && v != depot) {
|
---|
335 | Tour tour = FindTour(child, u);
|
---|
336 | int iu = tour.Cities.IndexOf(u + 1);
|
---|
337 | if (iu < tour.Cities.Count - 1) {
|
---|
338 | int x = tour.Cities[iu + 1] - 1;
|
---|
339 |
|
---|
340 | tour = FindTour(child, v);
|
---|
341 | int iv = tour.Cities.IndexOf(v + 1);
|
---|
342 | if (iv < tour.Cities.Count - 1) {
|
---|
343 | int y = tour.Cities[iv + 1] - 1;
|
---|
344 |
|
---|
345 | if (x != v && y != u)
|
---|
346 | Swap(u, x, v, y, parent, child);
|
---|
347 | }
|
---|
348 | }
|
---|
349 | }
|
---|
350 |
|
---|
351 | if (!child.Validate()) {
|
---|
352 | }
|
---|
353 | }
|
---|
354 |
|
---|
355 | private void M7(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
356 | if (u != depot && v != depot) {
|
---|
357 | Tour tu = FindTour(child, u);
|
---|
358 | Tour tv = FindTour(child, v);
|
---|
359 |
|
---|
360 | if (tu.Cities[0] == tv.Cities[0]) {
|
---|
361 | int iu = tu.Cities.IndexOf(u + 1);
|
---|
362 | if (iu < tu.Cities.Count - 1) {
|
---|
363 | int x = tu.Cities[iu + 1] - 1;
|
---|
364 |
|
---|
365 | int iv = tv.Cities.IndexOf(v + 1);
|
---|
366 | if (iv < tv.Cities.Count - 1) {
|
---|
367 | int y = tv.Cities[iv + 1] - 1;
|
---|
368 |
|
---|
369 | if (x != v && y != u)
|
---|
370 | Swap(x, v, parent, child);
|
---|
371 | }
|
---|
372 | }
|
---|
373 | }
|
---|
374 | }
|
---|
375 |
|
---|
376 | if (!child.Validate()) {
|
---|
377 | }
|
---|
378 | }
|
---|
379 |
|
---|
380 | private void M8(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
381 | if (u != depot && v != depot) {
|
---|
382 | Tour tu = FindTour(child, u);
|
---|
383 | Tour tv = FindTour(child, v);
|
---|
384 |
|
---|
385 | if (tu.Cities[0] != tv.Cities[0]) {
|
---|
386 | int iu = tu.Cities.IndexOf(u + 1);
|
---|
387 | if (iu < tu.Cities.Count - 1) {
|
---|
388 | int x = tu.Cities[iu + 1] - 1;
|
---|
389 |
|
---|
390 | int iv = tv.Cities.IndexOf(v + 1);
|
---|
391 | if (iv < tv.Cities.Count - 1) {
|
---|
392 | int y = tv.Cities[iv + 1] - 1;
|
---|
393 |
|
---|
394 | if (x != v && y != u)
|
---|
395 | Swap(x, v, parent, child);
|
---|
396 | }
|
---|
397 | }
|
---|
398 | }
|
---|
399 | }
|
---|
400 |
|
---|
401 | if (!child.Validate()) {
|
---|
402 | }
|
---|
403 | }
|
---|
404 |
|
---|
405 | private void M9(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
|
---|
406 | if (u != depot && v != depot) {
|
---|
407 | Tour tu = FindTour(child, u);
|
---|
408 | Tour tv = FindTour(child, v);
|
---|
409 |
|
---|
410 | if (tu.Cities[0] != tv.Cities[0]) {
|
---|
411 | int iu = tu.Cities.IndexOf(u + 1);
|
---|
412 | if (iu < tu.Cities.Count - 1) {
|
---|
413 | int x = tu.Cities[iu + 1] - 1;
|
---|
414 |
|
---|
415 | int iv = tv.Cities.IndexOf(v + 1);
|
---|
416 | if (iv < tv.Cities.Count - 1) {
|
---|
417 | int y = tv.Cities[iv + 1] - 1;
|
---|
418 |
|
---|
419 | if (x != v && y != u)
|
---|
420 | Swap2(u, x, v, y, parent, child);
|
---|
421 | }
|
---|
422 | }
|
---|
423 | }
|
---|
424 | }
|
---|
425 |
|
---|
426 | if (!child.Validate()) {
|
---|
427 | }
|
---|
428 | }
|
---|
429 |
|
---|
430 | protected PrinsEncoding Manipulate(PrinsEncoding individual,
|
---|
431 | double originalQuality, int u, int v) {
|
---|
432 | PrinsEncoding child = null;
|
---|
433 | bool improvement = false;
|
---|
434 |
|
---|
435 | if (u != v) {
|
---|
436 | child = individual.Clone() as PrinsEncoding;
|
---|
437 | M1(individual, child, u, v);
|
---|
438 | improvement = GetQuality(child) < originalQuality;
|
---|
439 |
|
---|
440 | if (!improvement) {
|
---|
441 | child = individual.Clone() as PrinsEncoding;
|
---|
442 | M2(individual, child, u, v);
|
---|
443 | improvement = GetQuality(child) < originalQuality;
|
---|
444 | }
|
---|
445 |
|
---|
446 | if (!improvement) {
|
---|
447 | child = individual.Clone() as PrinsEncoding;
|
---|
448 | M3(individual, child, u, v);
|
---|
449 | improvement = GetQuality(child) < originalQuality;
|
---|
450 | }
|
---|
451 |
|
---|
452 | if (!improvement) {
|
---|
453 | child = individual.Clone() as PrinsEncoding;
|
---|
454 | M4(individual, child, u, v);
|
---|
455 | improvement = GetQuality(child) < originalQuality;
|
---|
456 | }
|
---|
457 |
|
---|
458 | if (!improvement) {
|
---|
459 | child = individual.Clone() as PrinsEncoding;
|
---|
460 | M5(individual, child, u, v);
|
---|
461 | improvement = GetQuality(child) < originalQuality;
|
---|
462 | }
|
---|
463 |
|
---|
464 | if (!improvement) {
|
---|
465 | child = individual.Clone() as PrinsEncoding;
|
---|
466 | M6(individual, child, u, v);
|
---|
467 | improvement = GetQuality(child) < originalQuality;
|
---|
468 | }
|
---|
469 |
|
---|
470 | if (!improvement) {
|
---|
471 | child = individual.Clone() as PrinsEncoding;
|
---|
472 | M7(individual, child, u, v);
|
---|
473 | improvement = GetQuality(child) < originalQuality;
|
---|
474 | }
|
---|
475 |
|
---|
476 | if (!improvement) {
|
---|
477 | child = individual.Clone() as PrinsEncoding;
|
---|
478 | M8(individual, child, u, v);
|
---|
479 | improvement = GetQuality(child) < originalQuality;
|
---|
480 | }
|
---|
481 |
|
---|
482 | if (!improvement) {
|
---|
483 | child = individual.Clone() as PrinsEncoding;
|
---|
484 | M9(individual, child, u, v);
|
---|
485 | improvement = GetQuality(child) < originalQuality;
|
---|
486 | }
|
---|
487 | }
|
---|
488 |
|
---|
489 | if (improvement)
|
---|
490 | return child;
|
---|
491 | else
|
---|
492 | return null;
|
---|
493 | }
|
---|
494 |
|
---|
495 | protected override void Manipulate(IRandom random, PrinsEncoding individual) {
|
---|
496 | List<Tour> tours = individual.GetTours(DistanceMatrixParameter);
|
---|
497 | bool improvement = false;
|
---|
498 | int iterations = 0;
|
---|
499 |
|
---|
500 | do {
|
---|
501 | int u = depot;
|
---|
502 | improvement = false;
|
---|
503 | double originalQuality = GetQuality(individual);
|
---|
504 | PrinsEncoding child = null;
|
---|
505 |
|
---|
506 | while (!improvement && u < Cities) {
|
---|
507 | int v = depot;
|
---|
508 | while (!improvement && v < Cities) {
|
---|
509 | if (u != v) {
|
---|
510 | child = Manipulate(individual,
|
---|
511 | originalQuality, u, v);
|
---|
512 |
|
---|
513 | improvement = child != null;
|
---|
514 | }
|
---|
515 | v++;
|
---|
516 | }
|
---|
517 | u++;
|
---|
518 | }
|
---|
519 |
|
---|
520 | if (improvement) {
|
---|
521 | for (int i = 0; i < child.Length; i++) {
|
---|
522 | individual[i] = child[i];
|
---|
523 | }
|
---|
524 | }
|
---|
525 |
|
---|
526 | iterations++;
|
---|
527 | } while (improvement &&
|
---|
528 | iterations < Iterations.Value.Value);
|
---|
529 | }
|
---|
530 | }
|
---|
531 | }
|
---|