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.Common; |
---|
23 | using HeuristicLab.Core; |
---|
24 | using HeuristicLab.Data; |
---|
25 | using HeuristicLab.Encodings.PermutationEncoding; |
---|
26 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; |
---|
27 | using System.Collections.Generic; |
---|
28 | using HeuristicLab.Problems.VehicleRouting.Encodings.General; |
---|
29 | using HeuristicLab.Problems.VehicleRouting.Interfaces; |
---|
30 | using HeuristicLab.Problems.VehicleRouting.Variants; |
---|
31 | |
---|
32 | namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba { |
---|
33 | [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")] |
---|
34 | [StorableClass] |
---|
35 | public class AlbaEncoding : PermutationEncoding { |
---|
36 | #region IVRPEncoding Members |
---|
37 | public override List<Tour> GetTours() { |
---|
38 | Repair(); |
---|
39 | List<Tour> result = new List<Tour>(); |
---|
40 | |
---|
41 | int cities = ProblemInstance.Cities.Value; |
---|
42 | |
---|
43 | Tour tour = new Tour(); |
---|
44 | for (int i = 0; i < this.array.Length; i++) { |
---|
45 | if (this.array[i] >= cities) { |
---|
46 | if (tour.Stops.Count > 0) { |
---|
47 | result.Add(tour); |
---|
48 | |
---|
49 | tour = new Tour(); |
---|
50 | } |
---|
51 | } else { |
---|
52 | tour.Stops.Add(this.array[i] + 1); |
---|
53 | } |
---|
54 | } |
---|
55 | |
---|
56 | if (tour.Stops.Count > 0) { |
---|
57 | result.Add(tour); |
---|
58 | } |
---|
59 | |
---|
60 | return result; |
---|
61 | } |
---|
62 | |
---|
63 | public override int GetVehicleAssignment(int tour) { |
---|
64 | int vehicleAssignment = -1; |
---|
65 | Tour currentTour = GetTours()[tour]; |
---|
66 | |
---|
67 | int lastStop = currentTour.Stops[ |
---|
68 | currentTour.Stops.Count - 1] - 1; |
---|
69 | |
---|
70 | int lastStopIndex = this.IndexOf(lastStop); |
---|
71 | |
---|
72 | if (lastStopIndex == this.Length - 1) { |
---|
73 | int i = this.Length - 1; |
---|
74 | |
---|
75 | while (vehicleAssignment == -1) { |
---|
76 | if (this.array[i] >= ProblemInstance.Cities.Value) { |
---|
77 | vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value; |
---|
78 | } |
---|
79 | |
---|
80 | i--; |
---|
81 | } |
---|
82 | } |
---|
83 | else |
---|
84 | vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value; |
---|
85 | |
---|
86 | return vehicleAssignment; |
---|
87 | } |
---|
88 | #endregion |
---|
89 | |
---|
90 | public void Repair() { |
---|
91 | int cities = ProblemInstance.Cities.Value; |
---|
92 | |
---|
93 | if (this[this.Length - 1] < cities) { |
---|
94 | int index = this.Length - 2; |
---|
95 | while (this[index] < cities) { |
---|
96 | index--; |
---|
97 | } |
---|
98 | |
---|
99 | int vehicle = this[index]; |
---|
100 | for (int i = index; i < this.Length - 1; i++) |
---|
101 | this[i] = this[i + 1]; |
---|
102 | this[Length - 1] = vehicle; |
---|
103 | } |
---|
104 | } |
---|
105 | |
---|
106 | public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance) |
---|
107 | : base(permutation, instance) { |
---|
108 | } |
---|
109 | |
---|
110 | [StorableConstructor] |
---|
111 | private AlbaEncoding(bool serializing) |
---|
112 | : base(serializing) { |
---|
113 | } |
---|
114 | |
---|
115 | public override IDeepCloneable Clone(Cloner cloner) { |
---|
116 | return new AlbaEncoding(this, cloner); |
---|
117 | } |
---|
118 | |
---|
119 | protected AlbaEncoding(AlbaEncoding original, Cloner cloner) |
---|
120 | : base(original, cloner) { |
---|
121 | } |
---|
122 | |
---|
123 | public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) { |
---|
124 | List<int> route = new List<int>(routeParam); |
---|
125 | |
---|
126 | int cities = instance.Cities.Value; |
---|
127 | |
---|
128 | for (int i = 0; i < route.Count; i++) { |
---|
129 | if (route[i] <= 0) { |
---|
130 | int vehicle = -route[i]; |
---|
131 | route[i] = cities + vehicle; |
---|
132 | } else { |
---|
133 | route[i] = route[i] - 1; |
---|
134 | } |
---|
135 | } |
---|
136 | |
---|
137 | return new AlbaEncoding( |
---|
138 | new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), |
---|
139 | instance); |
---|
140 | } |
---|
141 | |
---|
142 | public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) { |
---|
143 | List<Tour> tours = encoding.GetTours(); |
---|
144 | |
---|
145 | int cities = 0; |
---|
146 | foreach (Tour tour in tours) { |
---|
147 | cities += tour.Stops.Count; |
---|
148 | } |
---|
149 | |
---|
150 | int emptyVehicles = instance.Vehicles.Value - tours.Count; |
---|
151 | |
---|
152 | int[] array = new int[cities + tours.Count + emptyVehicles]; |
---|
153 | int delimiter = 0; |
---|
154 | int arrayIndex = 0; |
---|
155 | |
---|
156 | foreach (Tour tour in tours) { |
---|
157 | foreach (int city in tour.Stops) { |
---|
158 | array[arrayIndex] = city - 1; |
---|
159 | arrayIndex++; |
---|
160 | } |
---|
161 | |
---|
162 | if (arrayIndex != array.Length) { |
---|
163 | array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter); |
---|
164 | |
---|
165 | delimiter++; |
---|
166 | arrayIndex++; |
---|
167 | } |
---|
168 | } |
---|
169 | |
---|
170 | for (int i = 0; i < emptyVehicles; i++) { |
---|
171 | array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter); |
---|
172 | |
---|
173 | delimiter++; |
---|
174 | arrayIndex++; |
---|
175 | } |
---|
176 | |
---|
177 | AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected, new IntArray(array)), instance); |
---|
178 | |
---|
179 | return solution; |
---|
180 | } |
---|
181 | } |
---|
182 | } |
---|