Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs (revision 6947)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs (revision 6960)
@@ -136,5 +136,5 @@
}
- if (!allowInfeasible && !instance.TourFeasible(newTour, solution))
+ if (newTour.Stops.Count > 0 && !allowInfeasible && !instance.TourFeasible(newTour, solution))
return false;
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs (revision 6947)
+++ (revision )
@@ -1,240 +1,0 @@
-#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see .
- */
-#endregion
-
-using HeuristicLab.Core;
-using HeuristicLab.Encodings.PermutationEncoding;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Data;
-using System.Collections.Generic;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.VehicleRouting.Variants;
-
-namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
- [Item("PotvinCustomerRelocationMainpulator", "A customer relocation operator")]
- [StorableClass]
- public sealed class PotvinCustomerRelocationMainpulator : PotvinManipulator, IPickupAndDeliveryOperator {
- [StorableConstructor]
- private PotvinCustomerRelocationMainpulator(bool deserializing) : base(deserializing) { }
-
- public PotvinCustomerRelocationMainpulator() : base() { }
-
- public override IDeepCloneable Clone(Cloner cloner) {
- return new PotvinCustomerRelocationMainpulator(this, cloner);
- }
-
- private PotvinCustomerRelocationMainpulator(PotvinCustomerRelocationMainpulator original, Cloner cloner)
- : base(original, cloner) {
- }
-
- protected override void Manipulate(IRandom random, PotvinEncoding individual) {
- bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
- bool performed = false;
-
- int selectedIndex;
- Tour route1;
-
- if (individual.Tours.Count > 0) {
- int mode = random.Next(0, 3);
-
- //Try pickup and delivery first
- IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
- if (pdp != null && mode == 0) {
- selectedIndex = SelectRandomTourBiasedByLength(random, individual);
- route1 =
- individual.Tours[selectedIndex];
-
- List deliveryViolations = new List();
-
- Dictionary visited = new Dictionary();
- for (int i = 0; i < route1.Stops.Count; i++) {
- int stop = route1.Stops[i];
- if (ProblemInstance.GetDemand(stop) < 0) {
- int source = pdp.GetPickupDeliveryLocation(stop);
-
- if (!visited.ContainsKey(source))
- deliveryViolations.Add(stop);
- }
-
- visited.Add(stop, true);
- }
-
- if (deliveryViolations.Count > 0) {
- int selected =
- deliveryViolations[random.Next(deliveryViolations.Count)];
-
- int source = pdp.GetPickupDeliveryLocation(selected);
-
- //find route of source
- Tour found = null;
- foreach (Tour tour in individual.Tours) {
- if (tour.Stops.Contains(source)) {
- found = tour;
- break;
- }
- }
-
- if (found != null) {
- double rand = random.NextDouble();
- if (rand < 0.33) {
- route1.Stops.Remove(selected);
-
- int index = individual.FindBestInsertionPlace(found, selected);
- found.Stops.Insert(index, selected);
- performed = true;
-
- if (route1.Stops.Count == 0)
- individual.Tours.Remove(route1);
- } else if (rand < 0.66) {
- found.Stops.Remove(source);
-
- int index = individual.FindBestInsertionPlace(route1, source);
- route1.Stops.Insert(index, source);
- performed = true;
-
- if (found.Stops.Count == 0)
- individual.Tours.Remove(found);
- } else {
- found.Stops.Remove(source);
- route1.Stops.Remove(selected);
-
- int chosenRoute = random.Next(individual.Tours.Count);
- Tour tour = individual.Tours[chosenRoute];
-
- int index = individual.FindBestInsertionPlace(tour, source);
- tour.Stops.Insert(index, source);
- index = individual.FindBestInsertionPlace(tour, selected);
- tour.Stops.Insert(index, selected);
-
- if (found.Stops.Count == 0)
- individual.Tours.Remove(found);
- if (route1.Stops.Count == 0)
- individual.Tours.Remove(route1);
- }
- }
- }
- }
-
- //then try tw
- if (!performed && mode == 1) {
- ITimeWindowedProblemInstance vrptw = ProblemInstance as ITimeWindowedProblemInstance;
-
- if (vrptw != null) {
- selectedIndex = SelectRandomTourBiasedByLength(random, individual);
- route1 =
- individual.Tours[selectedIndex];
-
- DoubleArray dueTime = vrptw.DueTime;
- DoubleArray readyTime = vrptw.ReadyTime;
- DoubleArray serviceTimes = vrptw.ServiceTime;
-
- int depot = 0;
- int depots = 1;
-
- int tourIndex = individual.GetTourIndex(route1);
- int vehicle = individual.GetVehicleAssignment(tourIndex);
-
- if (ProblemInstance is IMultiDepotProblemInstance) {
- depots = (ProblemInstance as IMultiDepotProblemInstance).Depots.Value;
- depot = (ProblemInstance as IMultiDepotProblemInstance).VehicleDepotAssignment[vehicle];
- }
-
- List timeWindowViolations = new List();
- double time = 0;
-
- for (int i = 0; i < route1.Stops.Count; i++) {
- int start = 0;
- if (i > 0)
- start = route1.Stops[i - 1];
- int end = route1.Stops[i];
-
- //drive there
- double currentDistace = vrptw.GetDistance(start, end, individual);
- time += currentDistace;
-
- int endIndex = end + depots - 1;
-
- //check if it was serviced on time
- if (time > dueTime[endIndex]) {
- timeWindowViolations.Add(end);
- }
-
- //wait
- double currentWaitingTime = 0.0;
- if (time < readyTime[endIndex])
- currentWaitingTime = readyTime[endIndex] - time;
- time += currentWaitingTime;
-
- if (end > 0) {
- //service
- double currentServiceTime = serviceTimes[end - 1];
- time += currentServiceTime;
- }
- }
-
- if (timeWindowViolations.Count > 0) {
- int selected =
- timeWindowViolations[random.Next(timeWindowViolations.Count)];
-
- int oldIndex = route1.Stops.IndexOf(selected);
- route1.Stops.Remove(selected);
-
- int route, place;
- if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
- Tour newTour = individual.Tours[route];
- newTour.Stops.Insert(place, selected);
- performed = true;
- } else {
- route1.Stops.Insert(oldIndex, selected);
- }
-
- if (route1.Stops.Count == 0)
- individual.Tours.Remove(route1);
- }
- }
- }
-
- //finally relocate random customer
- if (!performed) {
- selectedIndex = SelectRandomTourBiasedByLength(random, individual);
- route1 =
- individual.Tours[selectedIndex];
-
- int selected = route1.Stops[random.Next(route1.Stops.Count)];
- int oldIndex = route1.Stops.IndexOf(selected);
- route1.Stops.Remove(selected);
-
- int route, place;
- if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
- Tour tour = individual.Tours[route];
- tour.Stops.Insert(place, selected);
- performed = true;
- } else {
- route1.Stops.Insert(oldIndex, selected);
- }
-
- if (route1.Stops.Count == 0)
- individual.Tours.Remove(route1);
- }
- }
- }
- }
-}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs (revision 6960)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs (revision 6960)
@@ -0,0 +1,155 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+ [Item("PotvinPairwiseOneLevelExchangeMainpulator", "The 1M operator which manipulates a VRP representation. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172. It was adapted to the PDP formulation.")]
+ [StorableClass]
+ public sealed class PotvinPairwiseOneLevelExchangeMainpulator : PotvinManipulator {
+ [StorableConstructor]
+ private PotvinPairwiseOneLevelExchangeMainpulator(bool deserializing) : base(deserializing) { }
+
+ public PotvinPairwiseOneLevelExchangeMainpulator() : base() { }
+
+ public override IDeepCloneable Clone(Cloner cloner) {
+ return new PotvinPairwiseOneLevelExchangeMainpulator(this, cloner);
+ }
+
+ private PotvinPairwiseOneLevelExchangeMainpulator(PotvinPairwiseOneLevelExchangeMainpulator original, Cloner cloner)
+ : base(original, cloner) {
+ }
+
+ public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {
+ bool success;
+
+ IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
+
+ if (pdp != null) {
+ Tour route1 = individual.Tours.Find(t => t.Stops.Contains(city));
+ int i = route1.Stops.IndexOf(city);
+
+ int dest = pdp.GetPickupDeliveryLocation(city);
+ Tour destRoute = individual.Tours.Find(t => t.Stops.Contains(dest));
+ int j = destRoute.Stops.IndexOf(dest);
+
+ route1.Stops.Remove(city);
+ destRoute.Stops.Remove(dest);
+
+ int routeToAvoid = -1;
+ if (route1 == destRoute)
+ routeToAvoid = individual.Tours.IndexOf(route1);
+
+ int source, target;
+ if (ProblemInstance.GetDemand(city) >= 0) {
+ source = city;
+ target = dest;
+ } else {
+ source = dest;
+ target = city;
+ }
+
+ double bestQuality = double.MaxValue;
+ int bestTour = -1;
+ int bestPositionSource = -1;
+ int bestPositionTarget = -1;
+
+ for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
+ if (tourIdx != routeToAvoid) {
+ Tour tour = individual.Tours[tourIdx];
+ VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
+ individual.InsertPair(tour, source, target, ProblemInstance);
+ VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
+
+ double delta = evalNew.Quality - eval.Quality;
+
+ if (delta < bestQuality &&
+ (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
+ bestQuality = delta;
+ bestTour = tourIdx;
+ bestPositionSource = tour.Stops.IndexOf(source);
+ bestPositionTarget = tour.Stops.IndexOf(target);
+ }
+
+ tour.Stops.Remove(source);
+ tour.Stops.Remove(target);
+ }
+ }
+
+ if (bestTour >= 0) {
+ if (bestPositionTarget < bestPositionSource) {
+ individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
+ individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
+ } else {
+ individual.Tours[bestTour].Stops.Insert(bestPositionSource, source);
+ individual.Tours[bestTour].Stops.Insert(bestPositionTarget, target);
+ }
+
+ success = true;
+ } else {
+ if (j < i) {
+ destRoute.Stops.Insert(j, dest);
+ route1.Stops.Insert(i, city);
+ } else {
+ route1.Stops.Insert(i, city);
+ destRoute.Stops.Insert(j, dest);
+ }
+
+ success = false;
+ }
+ } else {
+ success = false;
+ }
+
+ return success;
+ }
+
+ protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+ bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
+ int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+ if (selectedIndex >= 0) {
+ Tour route1 =
+ individual.Tours[selectedIndex];
+
+ int count = route1.Stops.Count;
+
+ if (count > 0) {
+ int i = random.Next(0, count);
+ int city = route1.Stops[i];
+
+ if (!PairwiseMove(individual, city, allowInfeasible))
+ i++;
+
+ count = route1.Stops.Count;
+ }
+ }
+ }
+ }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs (revision 6960)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs (revision 6960)
@@ -0,0 +1,181 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+ [Item("PotvinPairwiseTwoLevelExchangeManipulator", "The 2M operator which manipulates a VRP representation. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172. It was adapted to the PDP formulation.")]
+ [StorableClass]
+ public sealed class PotvinPairwiseTwoLevelExchangeManipulator : PotvinManipulator {
+ [StorableConstructor]
+ private PotvinPairwiseTwoLevelExchangeManipulator(bool deserializing) : base(deserializing) { }
+
+ public PotvinPairwiseTwoLevelExchangeManipulator() : base() { }
+
+ public override IDeepCloneable Clone(Cloner cloner) {
+ return new PotvinPairwiseTwoLevelExchangeManipulator(this, cloner);
+ }
+
+ private PotvinPairwiseTwoLevelExchangeManipulator(PotvinPairwiseTwoLevelExchangeManipulator original, Cloner cloner)
+ : base(original, cloner) {
+ }
+
+ private PotvinEncoding ReplacePair(PotvinEncoding individual, int replaced, int replacing, bool allowInfeasible) {
+ individual = individual.Clone() as PotvinEncoding;
+ IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
+
+ int replacedDest = pdp.GetPickupDeliveryLocation(replaced);
+ int replacedSource, replacedTarget;
+ if (pdp.GetDemand(replaced) >= 0) {
+ replacedSource = replaced;
+ replacedTarget = replacedDest;
+ } else {
+ replacedSource = replacedDest;
+ replacedTarget = replaced;
+ }
+ Tour replacedSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacedSource));
+ Tour replacedTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacedTarget));
+
+ int replacingDest = pdp.GetPickupDeliveryLocation(replacing);
+ int replacingSource, replacingTarget;
+ if (pdp.GetDemand(replacing) >= 0) {
+ replacingSource = replacing;
+ replacingTarget = replacingDest;
+ } else {
+ replacingSource = replacingDest;
+ replacingTarget = replacing;
+ }
+ Tour replacingSourceTour = individual.Tours.Find(t => t.Stops.Contains(replacingSource));
+ Tour replacingTargetTour = individual.Tours.Find(t => t.Stops.Contains(replacingTarget));
+
+ replacingSourceTour.Stops.Remove(replacingSource);
+ replacingTargetTour.Stops.Remove(replacingTarget);
+
+ replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource;
+ replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget;
+
+ double bestQuality = double.MaxValue;
+ int bestTour = -1;
+ int bestPositionSource = -1;
+ int bestPositionTarget = -1;
+
+ int routeToAvoid = individual.Tours.IndexOf(replacingSourceTour);
+
+ for (int tourIdx = 0; tourIdx < individual.Tours.Count; tourIdx++) {
+ if (tourIdx != routeToAvoid) {
+ Tour tour = individual.Tours[tourIdx];
+ VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
+ individual.InsertPair(tour, replacedSource, replacedTarget, ProblemInstance);
+ VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
+
+ double delta = evalNew.Quality - eval.Quality;
+
+ if (delta < bestQuality &&
+ (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
+ bestQuality = delta;
+ bestTour = tourIdx;
+ bestPositionSource = tour.Stops.IndexOf(replacedSource);
+ bestPositionTarget = tour.Stops.IndexOf(replacedTarget);
+ }
+
+ tour.Stops.Remove(replacedSource);
+ tour.Stops.Remove(replacedTarget);
+ }
+ }
+
+ if (bestTour != -1) {
+ if (bestPositionTarget < bestPositionSource) {
+ individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
+ individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
+ } else {
+ individual.Tours[bestTour].Stops.Insert(bestPositionSource, replacedSource);
+ individual.Tours[bestTour].Stops.Insert(bestPositionTarget, replacedTarget);
+ }
+
+ return individual;
+ } else {
+ return null;
+ }
+ }
+
+ protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+ bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+ IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
+
+ int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+ if (selectedIndex >= 0) {
+ bool performed = false;
+ Tour route1 = individual.Tours[selectedIndex];
+
+ if (route1.Stops.Count > 0) {
+ //randomize customer selection
+ Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
+ int customer1Position = 0;
+
+ while (customer1Position < route1.Stops.Count) {
+ performed = false;
+
+ int customer1 = route1.Stops[perm[customer1Position]];
+ int customer2 = -1;
+
+ for (int i = 0; i < individual.Tours.Count; i++) {
+ if (i != selectedIndex) {
+ Tour tour = individual.Tours[i];
+ for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
+ customer2 = tour.Stops[customer2Position];
+
+ if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
+ PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible);
+ if (result != null) {
+ VRPToursParameter.ActualValue = result;
+ individual = result;
+
+ route1 = individual.Tours[selectedIndex];
+ performed = true;
+ break;
+ }
+ }
+ }
+ }
+
+ if (performed) {
+ break;
+ }
+ }
+
+ if (!performed)
+ customer1Position++;
+ else
+ break;
+ }
+ }
+ }
+ }
+ }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs (revision 6947)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs (revision 6960)
@@ -80,6 +80,6 @@
tour.Stops.Remove(move.Replaced);
- PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
- PotvinPDRearrangeMoveMaker.InsertPair(solution, oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
+ solution.InsertPair(tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
+ solution.InsertPair(oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
} else {
tour.Stops.Remove(move.Replaced);
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs (revision 6947)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs (revision 6960)
@@ -59,36 +59,4 @@
}
- public static void InsertPair(PotvinEncoding solution, Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
- int stops = tour.Stops.Count;
- VRPEvaluation eval = problemInstance.EvaluateTour(tour, solution);
- double minCosts = double.MaxValue;
- int sourceLocation = -1;
- int targetLocation = -1;
-
- for (int i = 0; i <= stops; i++) {
- tour.Stops.Insert(i, source);
- VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, solution);
- double sourceCosts = tourEval.Quality - eval.Quality;
-
- for (int j = i + 1; j <= stops + 1; j++) {
- if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
- bool feasible;
- double targetCosts = problemInstance.GetInsertionCosts(tourEval, solution, target, 0, j, out feasible);
-
- double costs = sourceCosts + targetCosts;
- if (costs < minCosts) {
- minCosts = costs;
- sourceLocation = i;
- targetLocation = j;
- }
- }
- }
- tour.Stops.Remove(source);
- }
-
- tour.Stops.Insert(sourceLocation, source);
- tour.Stops.Insert(targetLocation, target);
- }
-
public static void Apply(PotvinEncoding solution, PotvinPDRearrangeMove move, IVRPProblemInstance problemInstance) {
Tour tour = solution.Tours[move.Tour];
@@ -104,5 +72,5 @@
tour2.Stops.Remove(location);
- PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance, position, position2);
+ solution.InsertPair(tour, move.City, location, problemInstance, position, position2);
} else {
tour.Stops.Remove(move.City);
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs (revision 6947)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs (revision 6960)
@@ -74,5 +74,5 @@
oldTour2.Stops.Remove(location);
- PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance);
+ solution.InsertPair(tour, move.City, location, problemInstance);
} else {
int place = solution.FindBestInsertionPlace(tour, move.City);
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs (revision 6947)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs (revision 6960)
@@ -165,4 +165,36 @@
}
+ public void InsertPair(Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
+ int stops = tour.Stops.Count;
+ VRPEvaluation eval = problemInstance.EvaluateTour(tour, this);
+ double minCosts = double.MaxValue;
+ int sourceLocation = -1;
+ int targetLocation = -1;
+
+ for (int i = 0; i <= stops; i++) {
+ tour.Stops.Insert(i, source);
+ VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, this);
+ double sourceCosts = tourEval.Quality - eval.Quality;
+
+ for (int j = i + 1; j <= stops + 1; j++) {
+ if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
+ bool feasible;
+ double targetCosts = problemInstance.GetInsertionCosts(tourEval, this, target, 0, j, out feasible);
+
+ double costs = sourceCosts + targetCosts;
+ if (costs < minCosts) {
+ minCosts = costs;
+ sourceLocation = i;
+ targetLocation = j;
+ }
+ }
+ }
+ tour.Stops.Remove(source);
+ }
+
+ tour.Stops.Insert(sourceLocation, source);
+ tour.Stops.Insert(targetLocation, target);
+ }
+
public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
route = -1;