Changeset 6759 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs
 Timestamp:
 09/14/11 13:00:09 (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs
r5230 r6759 31 31 using HeuristicLab.Common; 32 32 using HeuristicLab.Problems.VehicleRouting.Interfaces; 33 using HeuristicLab.Problems.VehicleRouting.ProblemInstances; 33 34 34 35 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba { 35 [Item("PushForward Creator", "The push forward insertion heuristic. It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]36 [Item("PushForwardInsertionCreator", "The push forward insertion heuristic. It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")] 36 37 [StorableClass] 37 public sealed class PushForward Creator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator {38 public sealed class PushForwardInsertionCreator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator { 38 39 #region IStochasticOperator Members 39 40 public ILookupParameter<IRandom> RandomParameter { … … 62 63 63 64 [StorableConstructor] 64 private PushForward Creator(bool deserializing) : base(deserializing) { }65 66 public PushForward Creator()65 private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { } 66 67 public PushForwardInsertionCreator() 67 68 : base() { 68 69 Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator.")); … … 76 77 77 78 public override IDeepCloneable Clone(Cloner cloner) { 78 return new PushForward Creator(this, cloner);79 } 80 81 private PushForward Creator(PushForwardCreator original, Cloner cloner)79 return new PushForwardInsertionCreator(this, cloner); 80 } 81 82 private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner) 82 83 : base(original, cloner) { 83 84 } … … 102 103 } 103 104 104 private static double TravelDistance(IVRPProblemInstance problemInstance, List<int> route, int begin) {105 double distance = 0;106 for (int i = begin; i < route.Count  1 && (i == begin  route[i] != 0); i++) {107 distance += Distance(problemInstance, route[i], route[i + 1]);108 }109 return distance;110 }111 112 private static bool SubrouteConstraintsOK(IVRPProblemInstance problemInstance, List<int> route, int begin) {113 AlbaEncoding solution = AlbaEncoding.ConvertFrom(route, problemInstance);114 115 return problemInstance.Feasible(solution);116 }117 118 105 public static List<int> CreateSolution(IVRPProblemInstance problemInstance, IRandom random, 119 106 double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2, … … 133 120 int index; 134 121 int indexOfMinimumCost = 1; 122 int indexOfMinimumCost2 = 1; 135 123 int indexOfCustomer = 1; 124 125 IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance; 136 126 137 127 /* … … 140 130 */ 141 131 for (int i = 1; i <= problemInstance.Cities.Value; i++) { 142 distance = Distance(problemInstance, i, 0); 143 if (problemInstance.Coordinates[i, 0] < x0) distance = distance; 144 145 cost = alpha * distance + // distance 0 <> City[i] 146 beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time 147 gamma * (Math.Asin((problemInstance.Coordinates[i, 1]  y0) / distance) / 360 * distance); // polar angle 148 149 index = 0; 150 while (index < costList.Count && costList[index] < cost) index++; 151 costList.Insert(index, cost); 152 unroutedList.Insert(index, i); 132 //only insert sources 133 if (pdp == null  problemInstance.Demand[i] >= 0) { 134 distance = Distance(problemInstance, i, 0); 135 if (problemInstance.Coordinates[i, 0] < x0) distance = distance; 136 137 cost = alpha * distance + // distance 0 <> City[i] 138 beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time 139 gamma * (Math.Asin((problemInstance.Coordinates[i, 1]  y0) / distance) / 360 * distance); // polar angle 140 141 index = 0; 142 while (index < costList.Count && costList[index] < cost) index++; 143 144 costList.Insert(index, cost); 145 146 unroutedList.Insert(index, i); 147 } 153 148 } 154 149 … … 163 158 int subTourCount = 1; 164 159 List<int> route = new List<int>(problemInstance.Cities.Value + problemInstance.Vehicles.Value  1); 160 currentRoute = routeIndex; 165 161 minimumCost = double.MaxValue; 166 162 indexOfMinimumCost = 1; 163 indexOfMinimumCost2 = 1; 167 164 route.Add(0); 168 165 route.Add(0); 166 167 if (pdp != null) { 168 route.Insert(1, pdp.PickupDeliveryLocation[unroutedList[0]]); 169 routeIndex++; 170 } 171 169 172 route.Insert(1, unroutedList[0]); 173 routeIndex++; 174 170 175 unroutedList.RemoveAt(0); 171 currentRoute = routeIndex;172 routeIndex++;173 176 174 177 while (unroutedList.Count > 0) { 175 178 for (c = 0; c < unroutedList.Count; c++) { 179 Tour tour = new Tour(); 180 tour.Stops.AddRange(route.GetRange(currentRoute + 1, route.Count  (currentRoute + 1)  1)); 181 VRPEvaluation eval = problemInstance.Evaluate(tour); 182 double originalCosts = eval.Quality; 183 176 184 for (int i = currentRoute + 1; i < route.Count; i++) { 177 185 route.Insert(i, (int)unroutedList[c]); 178 if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); } 179 cost = TravelDistance(problemInstance, route, currentRoute); 180 if (cost < minimumCost && SubrouteConstraintsOK(problemInstance, route, currentRoute)) { 181 minimumCost = cost; 182 indexOfMinimumCost = i; 183 customer = (int)unroutedList[c]; 184 indexOfCustomer = c; 186 tour = new Tour(); 187 tour.Stops.AddRange(route.GetRange(currentRoute+1, route.Count  (currentRoute+1)  1)); 188 eval = problemInstance.Evaluate(tour); 189 double tourCost = eval.Quality  originalCosts; 190 191 if (pdp != null) { 192 for (int j = i  (currentRoute); j <= tour.Stops.Count; j++) { 193 bool feasible; 194 cost = tourCost + 195 problemInstance.GetInsertionCosts(eval, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible); 196 if (cost < minimumCost && feasible) { 197 minimumCost = cost; 198 indexOfMinimumCost = i; 199 indexOfMinimumCost2 = j + currentRoute + 1; 200 customer = (int)unroutedList[c]; 201 indexOfCustomer = c; 202 } 203 } 204 } else { 205 cost = tourCost; 206 bool feasible = problemInstance.Feasible(eval); 207 if (cost < minimumCost && feasible) { 208 minimumCost = cost; 209 indexOfMinimumCost = i; 210 customer = (int)unroutedList[c]; 211 indexOfCustomer = c; 212 } 185 213 } 186 214 route.RemoveAt(i); … … 191 219 route.Insert(indexOfMinimumCost, customer); 192 220 routeIndex++; 221 222 if (pdp != null) { 223 route.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[customer]); 224 routeIndex++; 225 } 226 193 227 unroutedList.RemoveAt(indexOfCustomer); 194 228 costList.RemoveAt(indexOfCustomer); … … 198 232 currentRoute = routeIndex; 199 233 route.Insert(route.Count  1, (int)unroutedList[0]); 234 routeIndex++; 235 if (pdp != null) { 236 route.Insert(route.Count  1, (int)pdp.PickupDeliveryLocation[unroutedList[0]]); 237 routeIndex++; 238 } 200 239 unroutedList.RemoveAt(0); 201 routeIndex++;202 240 subTourCount++; 203 241 } … … 205 243 minimumCost = double.MaxValue; 206 244 indexOfMinimumCost = 1; 245 indexOfMinimumCost2 = 1; 207 246 indexOfCustomer = 1; 208 247 customer = 1;
Note: See TracChangeset
for help on using the changeset viewer.