Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/30/11 15:23:48 (13 years ago)
Author:
svonolfe
Message:

Added vehicle assignment manipulator and move for multi depot instances (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin
Files:
13 added
10 edited
2 copied

Legend:

Unmodified
Added
Removed

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/IterativeInsertionCreator.cs

    r6753 r6857  
    3131using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3232using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
     33using HeuristicLab.Problems.VehicleRouting.Variants;
    3334
    3435namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    6465
    6566    private static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
    66       double dx = instance.Coordinates[0, 0];
    67       double dy = instance.Coordinates[0, 1];
     67      double dx = instance.GetCoordinates(0)[0];
     68      double dy = instance.GetCoordinates(0)[1];
    6869
    69       double cx = instance.Coordinates[city, 0];
    70       double cy = instance.Coordinates[city, 1];
     70      double cx = instance.GetCoordinates(city)[0];
     71      double cy = instance.GetCoordinates(city)[1];
    7172
    7273      double alpha = Math.Atan((cx - dx) / (dy - cy)) * (180.0 / Math.PI);
    … …  
    8485      PotvinEncoding result = new PotvinEncoding(instance);
    8586
     87      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     88
    8689      List<int> customers = new List<int>();
    87       for (int i = 0; i < instance.Cities.Value; i++)
    88         customers.Add(i + 1);
     90      for (int i = 1; i <= instance.Cities.Value; i++)
     91        if(pdp == null || pdp.GetDemand(i) >= 0)
     92          customers.Add(i);
     93
    8994      customers.Sort(delegate(int city1, int city2)
    9095          {
    … …  
    96101
    97102      Tour currentTour = new Tour();
     103      result.Tours.Add(currentTour);
    98104
    99105      int j = random.Next(customers.Count);
    … …  
    101107        int index = (i + j) % customers.Count;
    102108
    103         int stopIdx = result.FindBestInsertionPlace(currentTour, customers[index]);
     109        int stopIdx = 0;
     110        if(currentTour.Stops.Count > 0)
     111          result.FindBestInsertionPlace(currentTour, customers[index]);
    104112        currentTour.Stops.Insert(stopIdx, customers[index]);
    105113
    106         CVRPEvaluation evaluation = instance.Evaluate(currentTour) as CVRPEvaluation;
     114        if (pdp != null) {
     115          stopIdx = result.FindBestInsertionPlace(currentTour, pdp.GetPickupDeliveryLocation(customers[index]));
     116          currentTour.Stops.Insert(stopIdx, pdp.GetPickupDeliveryLocation(customers[index]));
     117        }
     118
     119        CVRPEvaluation evaluation = instance.EvaluateTour(currentTour, result) as CVRPEvaluation;
    107120        if (result.Tours.Count < instance.Vehicles.Value &&
    108121          ((adhereTimeWindows && !instance.Feasible(evaluation)) || ((!adhereTimeWindows) && evaluation.Overload > double.Epsilon))) {
    109           currentTour.Stops.RemoveAt(stopIdx);
     122            currentTour.Stops.Remove(customers[index]);
     123            if (pdp != null)
     124              currentTour.Stops.Remove(pdp.GetPickupDeliveryLocation(customers[index]));
    110125
    111           if(currentTour.Stops.Count > 0)
    112             result.Tours.Add(currentTour);
     126          if (currentTour.Stops.Count == 0)
     127            result.Tours.Remove(currentTour);
    113128          currentTour = new Tour();
     129          result.Tours.Add(currentTour);
    114130         
    115131          currentTour.Stops.Add(customers[index]);
     132          if (pdp != null) {
     133            currentTour.Stops.Add(pdp.GetPickupDeliveryLocation(customers[index]));
     134          }
    116135        }
    117136      }
    118137
    119       if (currentTour.Stops.Count > 0)
    120         result.Tours.Add(currentTour);
     138      if (currentTour.Stops.Count == 0)
     139        result.Tours.Remove(currentTour);
    121140
    122141      return result;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs

    r6856 r6857  
    3333using HeuristicLab.Problems.VehicleRouting.Variants;
    3434
    35 namespace HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin {
     35namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    3636  [Item("PushForwardInsertionCreator", "Creates a randomly initialized VRP solution.")]
    3737  [StorableClass]
    38   public sealed class PushForwardInsertionCreator : ExtendedPotvinCreator, IStochasticOperator {
     38  public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
    3939    #region IStochasticOperator Members
    4040    public ILookupParameter<IRandom> RandomParameter {
    … …  
    116116    }
    117117
    118     private static ExtendedPotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
     118    private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
    119119      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
    120120      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
    121       ExtendedPotvinEncoding result = new ExtendedPotvinEncoding(problemInstance);
     121      PotvinEncoding result = new PotvinEncoding(problemInstance);
    122122
    123123      double alpha, beta, gamma;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

    r6851 r6857  
    2626using HeuristicLab.Data;
    2727using HeuristicLab.Common;
    28 using HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin;
    2928
    3029namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    6059      child.Tours.Insert(tourParent2, replacing);
    6160
    62       if (parent1 is ExtendedPotvinEncoding && child is ExtendedPotvinEncoding) {
    63         Permutation vehicleAssignment = (child as ExtendedPotvinEncoding).VehicleAssignment;
     61        Permutation vehicleAssignment = child.VehicleAssignment;
    6462
    6563        int vehicle = vehicleAssignment[tourParent2];
    66         int vehicle2 = (parent1 as ExtendedPotvinEncoding).VehicleAssignment[tourParent1];
     64        int vehicle2 = parent1.VehicleAssignment[tourParent1];
    6765        vehicleAssignment[tourParent2] = vehicle2;
    6866
    … …  
    7371          }
    7472        }       
    75       }
    7673
    7774      foreach (int city in replaced.Stops)

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/IPotvinOperator.cs

    r4376 r6857  
    3232
    3333namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    34   public interface IPotvinOperator :
    35     ISingleDepotOperator, IHomogenousCapacitatedOperator, ITimeWindowedOperator {   
     34  public interface IPotvinOperator :
     35    ISingleDepotOperator, IHomogenousCapacitatedOperator, ITimeWindowedOperator,
     36    IMultiDepotOperator, IHeterogenousCapacitatedOperator {   
    3637  }
    3738}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveMaker.cs

    r6751 r6857  
    8989      PotvinEncoding newSolution = move.Individual.Clone() as PotvinEncoding;
    9090      Apply(newSolution, move, ProblemInstance);
     91      newSolution.Repair();
    9192      VRPToursParameter.ActualValue = newSolution;
    9293

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs

    r6856 r6857  
    9898      PotvinEncoding newSolution = move.Individual.Clone() as PotvinEncoding;
    9999      Apply(newSolution, move, ProblemInstance);
     100      newSolution.Repair();
    100101      VRPToursParameter.ActualValue = newSolution;
    101 
    102       //reset move quality
    103       VRPEvaluation eval = ProblemInstance.Evaluate(newSolution);
    104       MoveQualityParameter.ActualValue.Value = eval.Quality;
    105102    }
    106103  }

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

    r6797 r6857  
    116116        PotvinPDRelocateMoveAttribute attribute = tabuMove as PotvinPDRelocateMoveAttribute;
    117117
    118         double distance = 0;
    119         if (MoveDistanceParameter.ActualValue != null)
    120           distance = MoveDistanceParameter.ActualValue.Value;
     118        if (attribute != null) {
     119          double distance = 0;
     120          if (MoveDistanceParameter.ActualValue != null)
     121            distance = MoveDistanceParameter.ActualValue.Value;
    121122
    122         double overload = 0;
    123         if (MoveOverloadParameter.ActualValue != null)
    124           overload = MoveOverloadParameter.ActualValue.Value;
     123          double overload = 0;
     124          if (MoveOverloadParameter.ActualValue != null)
     125            overload = MoveOverloadParameter.ActualValue.Value;
    125126
    126         double tardiness = 0;
    127         if (MoveTardinessParameter.ActualValue != null)
    128           tardiness = MoveTardinessParameter.ActualValue.Value;
     127          double tardiness = 0;
     128          if (MoveTardinessParameter.ActualValue != null)
     129            tardiness = MoveTardinessParameter.ActualValue.Value;
    129130
    130         IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
    131         double quality = attribute.Distance * instance.DistanceFactor.Value;
     131          IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
     132          double quality = attribute.Distance * instance.DistanceFactor.Value;
    132133
    133         IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
    134         if (cvrp != null)
    135           quality += attribute.Overload * cvrp.OverloadPenalty.Value;
     134          IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
     135          if (cvrp != null)
     136            quality += attribute.Overload * cvrp.OverloadPenalty.Value;
    136137
    137         ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
    138         if (vrptw != null)
    139           quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
     138          ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
     139          if (vrptw != null)
     140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    140141
    141         if (!useAspiration || moveQuality >= quality) {
    142           if ((attribute.City == move.City && attribute.Tour == move.Tour) ||
    143             (attribute.City == move.Replaced && attribute.Tour == move.OldTour)) {
    144             isTabu = true;
    145             break;
    146           }
     142          if (!useAspiration || moveQuality >= quality) {
     143            if ((attribute.City == move.City && attribute.Tour == move.Tour) ||
     144              (attribute.City == move.Replaced && attribute.Tour == move.OldTour)) {
     145              isTabu = true;
     146              break;
     147            }
    147148
    148           if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
    149             isTabu = true;
    150             break;
     149            if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
     150              isTabu = true;
     151              break;
     152            }
    151153          }
    152154        }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs

    r6856 r6857  
    117117      PotvinEncoding newSolution = move.Individual.Clone() as PotvinEncoding;
    118118      Apply(newSolution, move, ProblemInstance);
     119      newSolution.Repair();
    119120      VRPToursParameter.ActualValue = newSolution;
    120 
    121       //reset move quality
    122       VRPEvaluation eval = ProblemInstance.Evaluate(newSolution);
    123       MoveQualityParameter.ActualValue.Value = eval.Quality;
    124121    }
    125122  }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveTabuCriterion.cs

    r6797 r6857  
    116116        PotvinPDRelocateMoveAttribute attribute = tabuMove as PotvinPDRelocateMoveAttribute;
    117117
    118         double distance = 0;
    119         if (MoveDistanceParameter.ActualValue != null)
    120           distance = MoveDistanceParameter.ActualValue.Value;
     118        if (attribute != null) {
     119          double distance = 0;
     120          if (MoveDistanceParameter.ActualValue != null)
     121            distance = MoveDistanceParameter.ActualValue.Value;
    121122
    122         double overload = 0;
    123         if (MoveOverloadParameter.ActualValue != null)
    124           overload = MoveOverloadParameter.ActualValue.Value;
     123          double overload = 0;
     124          if (MoveOverloadParameter.ActualValue != null)
     125            overload = MoveOverloadParameter.ActualValue.Value;
    125126
    126         double tardiness = 0;
    127         if (MoveTardinessParameter.ActualValue != null)
    128           tardiness = MoveTardinessParameter.ActualValue.Value;
     127          double tardiness = 0;
     128          if (MoveTardinessParameter.ActualValue != null)
     129            tardiness = MoveTardinessParameter.ActualValue.Value;
    129130
    130         IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
    131         double quality = attribute.Distance * instance.DistanceFactor.Value;
     131          IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
     132          double quality = attribute.Distance * instance.DistanceFactor.Value;
    132133
    133         IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
    134         if (cvrp != null)
    135           quality += attribute.Overload * cvrp.OverloadPenalty.Value;
     134          IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
     135          if (cvrp != null)
     136            quality += attribute.Overload * cvrp.OverloadPenalty.Value;
    136137
    137         ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
    138         if (vrptw != null)
    139           quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
     138          ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
     139          if (vrptw != null)
     140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    140141
    141         if (!useAspiration || moveQuality >= quality) {
    142           if (attribute.City == move.City && attribute.Tour == move.Tour) {
    143             isTabu = true;
    144             break;
    145           }
     142          if (!useAspiration || moveQuality >= quality) {
     143            if (attribute.City == move.City && attribute.Tour == move.Tour) {
     144              isTabu = true;
     145              break;
     146            }
    146147
    147           if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
    148             isTabu = true;
    149             break;
     148            if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
     149              isTabu = true;
     150              break;
     151            }
    150152          }
    151153        }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs

    r6856 r6857  
    8686      PotvinEncoding newSolution = move.Individual.Clone() as PotvinEncoding;
    8787      Apply(newSolution, move, ProblemInstance);
     88      newSolution.Repair();
    8889      VRPToursParameter.ActualValue = newSolution;
    89 
    90       //reset move quality
    91       VRPEvaluation eval = ProblemInstance.Evaluate(newSolution);
    92       MoveQualityParameter.ActualValue.Value = eval.Quality;
    9390    }
    9491  }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveTabuCriterion.cs

    r6797 r6857  
    116116        PotvinPDRelocateMoveAttribute attribute = tabuMove as PotvinPDRelocateMoveAttribute;
    117117
    118         double distance = 0;
    119         if (MoveDistanceParameter.ActualValue != null)
    120           distance = MoveDistanceParameter.ActualValue.Value;
     118        if (attribute != null) {
     119          double distance = 0;
     120          if (MoveDistanceParameter.ActualValue != null)
     121            distance = MoveDistanceParameter.ActualValue.Value;
    121122
    122         double overload = 0;
    123         if (MoveOverloadParameter.ActualValue != null)
    124           overload = MoveOverloadParameter.ActualValue.Value;
     123          double overload = 0;
     124          if (MoveOverloadParameter.ActualValue != null)
     125            overload = MoveOverloadParameter.ActualValue.Value;
    125126
    126         double tardiness = 0;
    127         if (MoveTardinessParameter.ActualValue != null)
    128           tardiness = MoveTardinessParameter.ActualValue.Value;
     127          double tardiness = 0;
     128          if (MoveTardinessParameter.ActualValue != null)
     129            tardiness = MoveTardinessParameter.ActualValue.Value;
    129130
    130         IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
    131         double quality = attribute.Distance * instance.DistanceFactor.Value;
     131          IVRPProblemInstance instance = ProblemInstanceParameter.ActualValue;
     132          double quality = attribute.Distance * instance.DistanceFactor.Value;
    132133
    133         IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
    134         if (cvrp != null)
    135           quality += attribute.Overload * cvrp.OverloadPenalty.Value;
     134          IHomogenousCapacitatedProblemInstance cvrp = instance as IHomogenousCapacitatedProblemInstance;
     135          if (cvrp != null)
     136            quality += attribute.Overload * cvrp.OverloadPenalty.Value;
    136137
    137         ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
    138         if (vrptw != null)
    139           quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
     138          ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
     139          if (vrptw != null)
     140            quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
    140141
    141         if (!useAspiration || moveQuality >= quality) {
    142           if (attribute.City == move.City && attribute.Tour == move.Tour) {
    143             isTabu = true;
    144             break;
    145           }
     142          if (!useAspiration || moveQuality >= quality) {
     143            if (attribute.City == move.City && attribute.Tour == move.Tour) {
     144              isTabu = true;
     145              break;
     146            }
    146147
    147           if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
    148             isTabu = true;
    149             break;
     148            if (attribute.Distance == distance && attribute.Overload == overload && attribute.Tardiness == tardiness) {
     149              isTabu = true;
     150              break;
     151            }
    150152          }
    151153        }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

    r6851 r6857  
    3939    public List<int> Unrouted { get; set; }
    4040
     41    [Storable]
     42    public Permutation VehicleAssignment { get; private set; }
     43
    4144    public PotvinEncoding(IVRPProblemInstance instance)
    4245      : base(instance) {
    4346      Unrouted = new List<int>();
     47      VehicleAssignment = new Permutation(PermutationTypes.Absolute, instance.Vehicles.Value);
    4448    }
    4549
    … …  
    5660      : base(original, cloner) {
    5761        this.Unrouted = new List<int>(original.Unrouted);
     62        this.VehicleAssignment = cloner.Clone<Permutation>(original.VehicleAssignment);
     63    }
     64
     65    public override int GetVehicleAssignment(int tour) {
     66      return VehicleAssignment[tour];
    5867    }
    5968
    … …  
    6271
    6372      TourEncoding.ConvertFrom(encoding, solution, instance);
     73
     74      List<int> vehicles = new List<int>();
     75      for (int i = 0; i < instance.Vehicles.Value; i++)
     76        vehicles.Add(i);
     77
     78      int[] assignment = new int[instance.Vehicles.Value];
     79      for (int i = 0; i < assignment.Length; i++)
     80        assignment[i] = -1;
     81
     82      for (int i = 0; i < solution.Tours.Count; i++) {
     83        int vehicle = encoding.GetVehicleAssignment(i);
     84        assignment[i] = vehicle;
     85        vehicles.Remove(vehicle);
     86      }
     87
     88      for (int i = 0; i < instance.Vehicles.Value; i++) {
     89        if (assignment[i] == -1) {
     90          int vehicle = vehicles[0];
     91          assignment[i] = vehicle;
     92          vehicles.RemoveAt(0);
     93        }
     94      }
     95
     96      solution.VehicleAssignment = new Permutation(PermutationTypes.Absolute, assignment);
    6497
    6598      return solution;
    … …  
    79112
    80113    public int FindBestInsertionPlace(Tour tour, int city, int positionToAvoid = -1) {
     114      if (tour.Stops.Count == 0)
     115        return 0;
     116     
    81117      int place = -1;
    82118      double minQuality = -1;
Note: See TracChangeset for help on using the changeset viewer.