Changeset 7791


Ignore:
Timestamp:
05/10/12 15:31:22 (7 years ago)
Author:
svonolfe
Message:

Improved PDP moves (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveTabuCriterion.cs

    r6857 r7791  
    140140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    141141
     142          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     143          if (pdp != null)
     144            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
     145
    142146          if (!useAspiration || moveQuality >= quality) {
    143147            if ((attribute.City == move.City && attribute.Tour == move.Tour) ||
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveTabuMaker.cs

    r6773 r7791  
    7373      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
    7474    }
     75    public ILookupParameter<IntValue> PickupViolationsParameter {
     76      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
     77    }
    7578
    7679    [StorableConstructor]
     
    9295        Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
    9396        Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
     97        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
    9498    }
    9599
     
    128132        tardiness = TardinessParameter.ActualValue.Value;
    129133
    130       tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness));
    131       tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.Replaced, distance, overload, tardiness));
     134      int pickupViolations = 0;
     135      if (PickupViolationsParameter.ActualValue != null)
     136        pickupViolations = PickupViolationsParameter.ActualValue.Value;
     137
     138      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness, pickupViolations));
     139      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.Replaced, distance, overload, tardiness, pickupViolations));
    132140      return base.Apply();
    133141    }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveTabuCriterion.cs

    r6857 r7791  
    140140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    141141
     142          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     143          if (pdp != null)
     144            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
     145
    142146          if (!useAspiration || moveQuality >= quality) {
    143147            if (attribute.City == move.City && attribute.Tour == move.Tour) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveTabuMaker.cs

    r6773 r7791  
    5555      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
    5656    }
     57    public ILookupParameter<IntValue> PickupViolationsParameter {
     58      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
     59    }
    5760
    5861    [StorableConstructor]
     
    6871        Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
    6972        Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
     73        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
    7074    }
    7175
     
    9195        tardiness = TardinessParameter.ActualValue.Value;
    9296
    93       return new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.City, distance, overload, tardiness);
     97      int pickupViolations = 0;
     98      if (PickupViolationsParameter.ActualValue != null)
     99        pickupViolations = PickupViolationsParameter.ActualValue.Value;
     100
     101      return new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.City, distance, overload, tardiness, pickupViolations);
    94102    }
    95103  }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftExhaustiveMoveGenerator.cs

    r6851 r7791  
    5454
    5555      int max = individual.Tours.Count;
    56       if (individual.Tours.Count < problemInstance.Vehicles.Value)
     56      if (individual.Tours.Count >= problemInstance.Vehicles.Value)
    5757        max = max - 1;
    5858
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs

    r7080 r7791  
    3030using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3131using HeuristicLab.Problems.VehicleRouting.Variants;
     32using System.Collections.Generic;
    3233
    3334namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    6061
    6162    public static void Apply(PotvinEncoding solution, PotvinPDShiftMove move, IVRPProblemInstance problemInstance) {
    62       if (move.Tour >= solution.Tours.Count)
     63      bool newTour = false;
     64
     65      if (move.Tour >= solution.Tours.Count) {
    6366        solution.Tours.Add(new Tour());
     67        newTour = true;
     68      }
    6469      Tour tour = solution.Tours[move.Tour];
    6570
     
    8085      }
    8186
     87      if (newTour) {
     88        List<int> vehicles = new List<int>();
     89        for (int i = move.Tour; i < problemInstance.Vehicles.Value; i++) {
     90          vehicles.Add(solution.GetVehicleAssignment(i));
     91        }
     92
     93        double bestQuality = double.MaxValue;
     94        int bestVehicle = -1;
     95
     96        int originalVehicle = solution.GetVehicleAssignment(move.Tour);
     97        foreach (int vehicle in vehicles) {
     98          solution.VehicleAssignment[move.Tour] = vehicle;
     99
     100          double quality = problemInstance.EvaluateTour(tour, solution).Quality;
     101          if (quality < bestQuality) {
     102            bestQuality = quality;
     103            bestVehicle = vehicle;
     104          }
     105        }
     106
     107        solution.VehicleAssignment[move.Tour] = originalVehicle;
     108
     109        int index = -1;
     110        for (int i = move.Tour; i < solution.VehicleAssignment.Length; i++) {
     111          if (solution.VehicleAssignment[i] == bestVehicle) {
     112            index = i;
     113            break;
     114          }
     115        }
     116        solution.VehicleAssignment[index] = originalVehicle;
     117        solution.VehicleAssignment[move.Tour] = bestVehicle;
     118      }
     119
    82120      solution.Repair();
    83121    }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveTabuCriterion.cs

    r6857 r7791  
    140140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    141141
     142          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     143          if (pdp != null)
     144            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
     145
    142146          if (!useAspiration || moveQuality >= quality) {
    143147            if (attribute.City == move.City && attribute.Tour == move.Tour) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveTabuMaker.cs

    r6773 r7791  
    5454      get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
    5555    }
     56    public ILookupParameter<IntValue> PickupViolationsParameter {
     57      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
     58    }
    5659
    5760    [StorableConstructor]
     
    6770        Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
    6871        Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
     72        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
    6973    }
    7074
     
    8993      if (TardinessParameter.ActualValue != null)
    9094        tardiness = TardinessParameter.ActualValue.Value;
     95
     96      int pickupViolations = 0;
     97      if (PickupViolationsParameter.ActualValue != null)
     98        pickupViolations = PickupViolationsParameter.ActualValue.Value;
    9199     
    92       return new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness);
     100      return new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness, pickupViolations);
    93101    }
    94102  }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftSingleMoveGenerator.cs

    r6909 r7791  
    6666      }
    6767
    68       if (cities.Count > 1 && individual.Tours.Count > 1) {
     68      if (cities.Count >= 1) {
    6969        int city = cities[rand.Next(cities.Count)];
    7070        Tour oldTour = individual.Tours.Find(t => t.Stops.Contains(city));
     
    7272
    7373        int max = individual.Tours.Count;
    74         if (individual.Tours.Count < problemInstance.Vehicles.Value)
     74        if (individual.Tours.Count >= problemInstance.Vehicles.Value)
    7575          max = max - 1;
    7676
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PotvinPDRelocateMoveAttribute.cs

    r6773 r7791  
    4040    [Storable]
    4141    public double Tardiness { get; private set; }
     42    [Storable]
     43    public int PickupViolations { get; private set; }
    4244
    4345    [StorableConstructor]
     
    5052        this.Overload = original.Overload;
    5153        this.Tardiness = original.Tardiness;
     54        this.PickupViolations = original.PickupViolations;
    5255    }
    53     public PotvinPDRelocateMoveAttribute(double moveQuality, int tour, int city, 
    54       double distance, double overload, double tardiness)
     56    public PotvinPDRelocateMoveAttribute(double moveQuality, int tour, int city,
     57      double distance, double overload, double tardiness, int pickupViolations)
    5558      : base(moveQuality) {
    5659      Tour = tour;
     
    5962      Overload = overload;
    6063      Tardiness = tardiness;
     64      PickupViolations = pickupViolations;
    6165    }
    6266
Note: See TracChangeset for help on using the changeset viewer.