Changeset 6960


Ignore:
Timestamp:
11/08/11 09:47:31 (11 years ago)
Author:
svonolfe
Message:

Added pairwise manipulators, removed relocation manipulator (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
Files:
2 added
1 deleted
6 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs

    r6837 r6960  
    136136      }
    137137
    138       if (!allowInfeasible && !instance.TourFeasible(newTour, solution))
     138      if (newTour.Stops.Count > 0 && !allowInfeasible && !instance.TourFeasible(newTour, solution))
    139139        return false;
    140140
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs

    r6857 r6960  
    8080        tour.Stops.Remove(move.Replaced);
    8181
    82         PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
    83         PotvinPDRearrangeMoveMaker.InsertPair(solution, oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
     82        solution.InsertPair(tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
     83        solution.InsertPair(oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
    8484      } else {
    8585        tour.Stops.Remove(move.Replaced);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs

    r6857 r6960  
    5959    }
    6060
    61     public static void InsertPair(PotvinEncoding solution, Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
    62       int stops = tour.Stops.Count;
    63       VRPEvaluation eval = problemInstance.EvaluateTour(tour, solution);
    64       double minCosts = double.MaxValue;
    65       int sourceLocation = -1;
    66       int targetLocation = -1;
    67 
    68       for (int i = 0; i <= stops; i++) {
    69         tour.Stops.Insert(i, source);
    70         VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, solution);
    71         double sourceCosts = tourEval.Quality - eval.Quality;
    72 
    73         for (int j = i + 1; j <= stops + 1; j++) {
    74           if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
    75             bool feasible;
    76             double targetCosts = problemInstance.GetInsertionCosts(tourEval, solution, target, 0, j, out feasible);
    77 
    78             double costs = sourceCosts + targetCosts;
    79             if (costs < minCosts) {
    80               minCosts = costs;
    81               sourceLocation = i;
    82               targetLocation = j;
    83             }
    84           }
    85         }
    86         tour.Stops.Remove(source);
    87       }
    88 
    89       tour.Stops.Insert(sourceLocation, source);
    90       tour.Stops.Insert(targetLocation, target);
    91     }
    92 
    9361    public static void Apply(PotvinEncoding solution, PotvinPDRearrangeMove move, IVRPProblemInstance problemInstance) {
    9462      Tour tour = solution.Tours[move.Tour];
     
    10472        tour2.Stops.Remove(location);
    10573
    106         PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance, position, position2);
     74        solution.InsertPair(tour, move.City, location, problemInstance, position, position2);
    10775      } else {
    10876        tour.Stops.Remove(move.City);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs

    r6857 r6960  
    7474        oldTour2.Stops.Remove(location);
    7575
    76         PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance);
     76        solution.InsertPair(tour, move.City, location, problemInstance);
    7777      } else {
    7878        int place = solution.FindBestInsertionPlace(tour, move.City);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

    r6907 r6960  
    165165    }
    166166
     167    public void InsertPair(Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
     168      int stops = tour.Stops.Count;
     169      VRPEvaluation eval = problemInstance.EvaluateTour(tour, this);
     170      double minCosts = double.MaxValue;
     171      int sourceLocation = -1;
     172      int targetLocation = -1;
     173
     174      for (int i = 0; i <= stops; i++) {
     175        tour.Stops.Insert(i, source);
     176        VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, this);
     177        double sourceCosts = tourEval.Quality - eval.Quality;
     178
     179        for (int j = i + 1; j <= stops + 1; j++) {
     180          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
     181            bool feasible;
     182            double targetCosts = problemInstance.GetInsertionCosts(tourEval, this, target, 0, j, out feasible);
     183
     184            double costs = sourceCosts + targetCosts;
     185            if (costs < minCosts) {
     186              minCosts = costs;
     187              sourceLocation = i;
     188              targetLocation = j;
     189            }
     190          }
     191        }
     192        tour.Stops.Remove(source);
     193      }
     194
     195      tour.Stops.Insert(sourceLocation, source);
     196      tour.Stops.Insert(targetLocation, target);
     197    }
     198
    167199    public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
    168200      route = -1;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r6857 r6960  
    210210    <Compile Include="Encodings\Potvin\Crossovers\PotvinSequenceBasedCrossover.cs" />
    211211    <Compile Include="Encodings\Potvin\IPotvinOperator.cs" />
     212    <Compile Include="Encodings\Potvin\Manipulators\PotvinPairwiseTwoLevelExchangeManipulator.cs" />
     213    <Compile Include="Encodings\Potvin\Manipulators\PotvinPairwiseOneLevelExchangeManipulator.cs" />
    212214    <Compile Include="Encodings\Potvin\Manipulators\PotvinVehicleAssignmentManipulator.cs" />
    213     <Compile Include="Encodings\Potvin\Manipulators\PotvinCustomerRelocationManipulator.cs" />
    214215    <Compile Include="Encodings\Potvin\Manipulators\PotvinLocalSearchManipulator.cs" />
    215216    <Compile Include="Encodings\Potvin\Manipulators\PotvinManipulator.cs" />
Note: See TracChangeset for help on using the changeset viewer.