- Timestamp:
- 02/18/14 08:57:37 (11 years ago)
- Location:
- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs
r9456 r10460 52 52 } 53 53 54 private bool FindBetterInsertionPlace(55 PotvinEncoding individual, int tour, int city, int length,54 private static bool FindBetterInsertionPlace( 55 PotvinEncoding individual, IVRPProblemInstance instance, int tour, int city, int length, 56 56 out int insertionTour, out int insertionPlace) { 57 57 bool insertionFound = false; … … 70 70 distance = individual.GetTourLength(individual.Tours[currentTour]); 71 71 individual.Tours[currentTour].Stops.InsertRange(currentCity, toBeDeleted); 72 if ( ProblemInstance.TourFeasible(individual.Tours[currentTour], individual)) {72 if (instance.TourFeasible(individual.Tours[currentTour], individual)) { 73 73 double lengthIncrease = 74 74 individual.GetTourLength(individual.Tours[currentTour]) - distance; … … 92 92 } 93 93 94 p rotected override void Manipulate(IRandom random, PotvinEncoding individual) {94 public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, int maxIterations) { 95 95 //only apply to feasible individuals 96 if ( ProblemInstance.Feasible(individual)) {96 if (instance.Feasible(individual)) { 97 97 bool insertionFound; 98 98 int iterations = 0; … … 107 107 while (city <= individual.Tours[tour].Stops.Count - length && !insertionFound) { 108 108 int insertionTour, insertionPlace; 109 if (FindBetterInsertionPlace(individual, tour, city, length,109 if (FindBetterInsertionPlace(individual, instance, tour, city, length, 110 110 out insertionTour, out insertionPlace)) { 111 111 insertionFound = true; … … 126 126 iterations++; 127 127 } while (insertionFound && 128 iterations < Iterations.Value.Value);128 iterations < maxIterations); 129 129 130 130 IList<Tour> toBeRemoved = new List<Tour>(); … … 139 139 } 140 140 } 141 142 143 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 144 ApplyManipulation(random, individual, ProblemInstance, Iterations.Value.Value); 145 } 141 146 } 142 147 } -
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs
r10298 r10460 55 55 protected abstract void Manipulate(IRandom random, PotvinEncoding individual); 56 56 57 protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {57 protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance) { 58 58 int tourIndex = -1; 59 59 … … 61 61 double[] probabilities = new double[individual.Tours.Count]; 62 62 for (int i = 0; i < individual.Tours.Count; i++) { 63 probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double) ProblemInstance.Cities.Value);63 probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)instance.Cities.Value); 64 64 sum += probabilities[i]; 65 65 } … … 82 82 } 83 83 84 protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {84 protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) { 85 85 return individual.FindInsertionPlace( 86 86 city, routeToAvoid, allowInfeasible, out route, out place); -
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs
r9456 r10460 23 23 using HeuristicLab.Core; 24 24 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 25 using HeuristicLab.Problems.VehicleRouting.Interfaces; 25 26 26 27 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin { … … 41 42 } 42 43 43 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 44 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; 45 46 int selectedIndex = SelectRandomTourBiasedByLength(random, individual); 44 public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) { 45 int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance); 47 46 if (selectedIndex >= 0) { 48 47 Tour route1 = … … 68 67 } 69 68 } 69 70 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 71 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; 72 ApplyManipulation(random, individual, ProblemInstance, allowInfeasible); 73 } 70 74 } 71 75 } -
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs
r9456 r10460 25 25 using HeuristicLab.Problems.VehicleRouting.ProblemInstances; 26 26 using HeuristicLab.Problems.VehicleRouting.Variants; 27 using HeuristicLab.Problems.VehicleRouting.Interfaces; 27 28 28 29 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin { … … 43 44 } 44 45 45 public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {46 public static bool PairwiseMove(PotvinEncoding individual, IVRPProblemInstance instance, int city, bool allowInfeasible) { 46 47 bool success; 47 48 48 IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;49 IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance; 49 50 50 51 if (pdp != null) { … … 64 65 65 66 int source, target; 66 if ( ProblemInstance.GetDemand(city) >= 0) {67 if (instance.GetDemand(city) >= 0) { 67 68 source = city; 68 69 target = dest; … … 80 81 if (tourIdx != routeToAvoid) { 81 82 Tour tour = individual.Tours[tourIdx]; 82 VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);83 individual.InsertPair(tour, source, target, ProblemInstance);84 VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);83 VRPEvaluation eval = instance.EvaluateTour(tour, individual); 84 individual.InsertPair(tour, source, target, instance); 85 VRPEvaluation evalNew = instance.EvaluateTour(tour, individual); 85 86 86 87 double delta = evalNew.Quality - eval.Quality; 87 88 88 89 if (delta < bestQuality && 89 ( ProblemInstance.Feasible(evalNew) || allowInfeasible)) {90 (instance.Feasible(evalNew) || allowInfeasible)) { 90 91 bestQuality = delta; 91 92 bestTour = tourIdx; … … 127 128 } 128 129 130 public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) { 131 int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp); 132 if (selectedIndex >= 0) { 133 Tour route1 = 134 individual.Tours[selectedIndex]; 135 136 int count = route1.Stops.Count; 137 138 if (count > 0) { 139 int i = random.Next(0, count); 140 int city = route1.Stops[i]; 141 142 if (!PairwiseMove(individual, pdp, city, allowInfeasible)) 143 i++; 144 145 count = route1.Stops.Count; 146 } 147 } 148 } 149 150 129 151 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 130 152 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; 153 131 154 IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance; 132 155 133 156 if (pdp != null) { 134 int selectedIndex = SelectRandomTourBiasedByLength(random, individual); 135 if (selectedIndex >= 0) { 136 Tour route1 = 137 individual.Tours[selectedIndex]; 138 139 int count = route1.Stops.Count; 140 141 if (count > 0) { 142 int i = random.Next(0, count); 143 int city = route1.Stops[i]; 144 145 if (!PairwiseMove(individual, city, allowInfeasible)) 146 i++; 147 148 count = route1.Stops.Count; 149 } 150 } 157 ApplyManipulation(random, individual, pdp, allowInfeasible); 151 158 } 152 159 } -
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs
r9456 r10460 26 26 using HeuristicLab.Problems.VehicleRouting.ProblemInstances; 27 27 using HeuristicLab.Problems.VehicleRouting.Variants; 28 using HeuristicLab.Problems.VehicleRouting.Interfaces; 28 29 29 30 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin { … … 44 45 } 45 46 46 private PotvinEncoding ReplacePair(PotvinEncoding individual, int replaced, int replacing, bool allowInfeasible) {47 private static PotvinEncoding ReplacePair(PotvinEncoding individual, IVRPProblemInstance instance, int replaced, int replacing, bool allowInfeasible) { 47 48 individual = individual.Clone() as PotvinEncoding; 48 IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;49 IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance; 49 50 50 51 int replacedDest = pdp.GetPickupDeliveryLocation(replaced); … … 76 77 77 78 replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource; 78 if (!allowInfeasible && ! ProblemInstance.TourFeasible(replacedSourceTour, individual))79 if (!allowInfeasible && !instance.TourFeasible(replacedSourceTour, individual)) 79 80 return null; 80 81 81 82 replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget; 82 if (!allowInfeasible && ! ProblemInstance.TourFeasible(replacedTargetTour, individual))83 if (!allowInfeasible && !instance.TourFeasible(replacedTargetTour, individual)) 83 84 return null; 84 85 … … 93 94 if (tourIdx != routeToAvoid) { 94 95 Tour tour = individual.Tours[tourIdx]; 95 VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);96 individual.InsertPair(tour, replacedSource, replacedTarget, ProblemInstance);97 VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);96 VRPEvaluation eval = instance.EvaluateTour(tour, individual); 97 individual.InsertPair(tour, replacedSource, replacedTarget, instance); 98 VRPEvaluation evalNew = instance.EvaluateTour(tour, individual); 98 99 99 100 double delta = evalNew.Quality - eval.Quality; 100 101 101 102 if (delta < bestQuality && 102 ( ProblemInstance.Feasible(evalNew) || allowInfeasible)) {103 (instance.Feasible(evalNew) || allowInfeasible)) { 103 104 bestQuality = delta; 104 105 bestTour = tourIdx; … … 127 128 } 128 129 130 public static PotvinEncoding ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) { 131 PotvinEncoding result = null; 132 133 int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp); 134 if (selectedIndex >= 0) { 135 bool performed = false; 136 Tour route1 = individual.Tours[selectedIndex]; 137 138 if (route1.Stops.Count > 0) { 139 //randomize customer selection 140 Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random); 141 int customer1Position = 0; 142 143 while (customer1Position < route1.Stops.Count) { 144 performed = false; 145 146 int customer1 = route1.Stops[perm[customer1Position]]; 147 int customer2 = -1; 148 149 for (int i = 0; i < individual.Tours.Count; i++) { 150 if (i != selectedIndex) { 151 Tour tour = individual.Tours[i]; 152 for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) { 153 customer2 = tour.Stops[customer2Position]; 154 155 if (pdp.GetPickupDeliveryLocation(customer1) != customer2) { 156 result = ReplacePair(individual, pdp, customer2, customer1, allowInfeasible); 157 if (result != null) { 158 individual = result; 159 160 route1 = individual.Tours[selectedIndex]; 161 performed = true; 162 break; 163 } 164 } 165 } 166 } 167 168 if (performed) { 169 break; 170 } 171 } 172 173 if (!performed) 174 customer1Position++; 175 else 176 break; 177 } 178 } 179 } 180 181 return result; 182 } 183 129 184 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 130 185 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; … … 132 187 133 188 if (pdp != null) { 134 int selectedIndex = SelectRandomTourBiasedByLength(random, individual); 135 if (selectedIndex >= 0) { 136 bool performed = false; 137 Tour route1 = individual.Tours[selectedIndex]; 138 139 if (route1.Stops.Count > 0) { 140 //randomize customer selection 141 Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random); 142 int customer1Position = 0; 143 144 while (customer1Position < route1.Stops.Count) { 145 performed = false; 146 147 int customer1 = route1.Stops[perm[customer1Position]]; 148 int customer2 = -1; 149 150 for (int i = 0; i < individual.Tours.Count; i++) { 151 if (i != selectedIndex) { 152 Tour tour = individual.Tours[i]; 153 for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) { 154 customer2 = tour.Stops[customer2Position]; 155 156 if (pdp.GetPickupDeliveryLocation(customer1) != customer2) { 157 PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible); 158 if (result != null) { 159 VRPToursParameter.ActualValue = result; 160 individual = result; 161 162 route1 = individual.Tours[selectedIndex]; 163 performed = true; 164 break; 165 } 166 } 167 } 168 } 169 170 if (performed) { 171 break; 172 } 173 } 174 175 if (!performed) 176 customer1Position++; 177 else 178 break; 179 } 180 } 181 } 189 PotvinEncoding result = ApplyManipulation(random, individual, pdp, allowInfeasible); 190 if (result != null) { 191 VRPToursParameter.ActualValue = result; 192 } 182 193 } 183 194 } -
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs
r9456 r10460 23 23 using HeuristicLab.Core; 24 24 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 25 using HeuristicLab.Problems.VehicleRouting.Interfaces; 25 26 26 27 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin { … … 41 42 } 42 43 43 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 44 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; 45 46 int selectedIndex = SelectRandomTourBiasedByLength(random, individual); 44 public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) { 45 int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance); 47 46 if (selectedIndex >= 0) { 48 47 Tour route1 = individual.Tours[selectedIndex]; … … 63 62 route1.Stops.RemoveAt(customer1Position); 64 63 65 if ( ProblemInstance.TourFeasible(tour, individual)) {64 if (instance.TourFeasible(tour, individual)) { 66 65 int routeIdx, place; 67 66 if (FindInsertionPlace(individual, … … 92 91 } 93 92 } 93 94 95 protected override void Manipulate(IRandom random, PotvinEncoding individual) { 96 bool allowInfeasible = AllowInfeasibleSolutions.Value.Value; 97 98 ApplyManipulation(random, individual, ProblemInstance, allowInfeasible); 99 } 94 100 } 95 101 }
Note: See TracChangeset
for help on using the changeset viewer.