Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/ZhuEncoding.cs @ 4899

Last change on this file since 4899 was 4752, checked in by svonolfe, 14 years ago

Merged relevant changes from the trunk into the branch (cloning,...) (#1177)

File size: 4.7 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.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27using System.Collections.Generic;
28using HeuristicLab.Problems.VehicleRouting.Encodings.General;
29using System;
30using HeuristicLab.Problems.VehicleRouting.Interfaces;
31
32namespace HeuristicLab.Problems.VehicleRouting.Encodings.Zhu {
33  [Item("ZhuEncoding", "Represents a Zhu encoding of VRP solutions. It is implemented as described in Zhu, K.Q. (2000). A New Genetic Algorithm For VRPTW. Proceedings of the International Conference on Artificial Intelligence.")]
34  [StorableClass]
35  public class ZhuEncoding : PermutationEncoding {
36    #region IVRPEncoding Members
37    public override List<Tour> GetTours() {
38      List<Tour> result = new List<Tour>();
39
40      Tour newTour = new Tour();
41
42      for (int i = 0; i < this.Length; i++) {
43        int city = this[i] + 1;
44        newTour.Stops.Add(city);
45        if (!ProblemInstance.Feasible(newTour)) {
46          newTour.Stops.Remove(city);
47          if (newTour.Stops.Count > 0)
48              result.Add(newTour);
49
50            newTour = new Tour();
51            newTour.Stops.Add(city);
52        }
53      }
54
55      if (newTour.Stops.Count > 0)
56        result.Add(newTour);
57
58      //if there are too many vehicles - repair
59      while (result.Count > ProblemInstance.Vehicles.Value) {
60        Tour tour = result[result.Count - 1];
61
62        //find predecessor / successor in permutation
63        int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1;
64        if (predecessorIndex >= 0) {
65          int predecessor = this[predecessorIndex] + 1;
66
67          foreach (Tour t in result) {
68            int insertPosition = t.Stops.IndexOf(predecessor) + 1;
69            if (insertPosition != -1) {
70              t.Stops.InsertRange(insertPosition, tour.Stops);
71              break;
72            }
73          }
74        } else {
75          int successorIndex = Array.IndexOf(this.array,
76            tour.Stops[tour.Stops.Count - 1] - 1) + 1;
77          int successor = this[successorIndex] + 1;
78
79          foreach (Tour t in result) {
80            int insertPosition = t.Stops.IndexOf(successor);
81            if (insertPosition != -1) {
82              t.Stops.InsertRange(insertPosition, tour.Stops);
83              break;
84            }
85          }
86        }
87
88        result.Remove(tour);
89      }
90
91      return result;
92    }
93    #endregion
94
95    public ZhuEncoding(Permutation permutation, IVRPProblemInstance problemInstance)
96      : base(permutation, problemInstance) {
97    }
98
99    public override IDeepCloneable Clone(Cloner cloner) {
100      return new ZhuEncoding(this, cloner);
101    }
102
103    protected ZhuEncoding(ZhuEncoding original, Cloner cloner)
104      : base(original, cloner) {
105    }
106
107    [StorableConstructor]
108    private ZhuEncoding(bool serializing)
109      : base(serializing) {
110    }
111
112    public static ZhuEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance problemInstance) {
113      List<Tour> tours = encoding.GetTours();
114      List<int> route = new List<int>();
115
116      foreach (Tour tour in tours) {
117        foreach (int city in tour.Stops)
118          route.Add(city - 1);
119      }
120
121      return new ZhuEncoding(
122        new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance);
123    }
124
125    public static ZhuEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance problemInstance) {
126      List<int> route = new List<int>(routeParam);
127
128      while (route.Remove(0)) { //remove all delimiters (0)
129      }
130
131      for (int i = 0; i < route.Count; i++)
132        route[i]--;
133
134      return new ZhuEncoding(
135        new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance);
136    }
137  }
138}
Note: See TracBrowser for help on using the repository browser.