Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6759


Ignore:
Timestamp:
09/14/11 13:00:09 (13 years ago)
Author:
svonolfe
Message:

Adapted creators to support pickup and delivery constraints (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs

    r5230 r6759  
    3131using HeuristicLab.Common;
    3232using HeuristicLab.Problems.VehicleRouting.Interfaces;
     33using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
    3334
    3435namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    35   [Item("PushForwardCreator", "The push forward insertion heuristic.  It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]
     36  [Item("PushForwardInsertionCreator", "The push forward insertion heuristic.  It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]
    3637  [StorableClass]
    37   public sealed class PushForwardCreator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator {
     38  public sealed class PushForwardInsertionCreator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator {
    3839    #region IStochasticOperator Members
    3940    public ILookupParameter<IRandom> RandomParameter {
     
    6263
    6364    [StorableConstructor]
    64     private PushForwardCreator(bool deserializing) : base(deserializing) { }
    65 
    66     public PushForwardCreator()
     65    private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { }
     66
     67    public PushForwardInsertionCreator()
    6768      : base() {
    6869      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
     
    7677
    7778    public override IDeepCloneable Clone(Cloner cloner) {
    78       return new PushForwardCreator(this, cloner);
    79     }
    80 
    81     private PushForwardCreator(PushForwardCreator original, Cloner cloner)
     79      return new PushForwardInsertionCreator(this, cloner);
     80    }
     81
     82    private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner)
    8283      : base(original, cloner) {
    8384    }
     
    102103    }
    103104
    104     private static double TravelDistance(IVRPProblemInstance problemInstance, List<int> route, int begin) {
    105       double distance = 0;
    106       for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
    107         distance += Distance(problemInstance, route[i], route[i + 1]);
    108       }
    109       return distance;
    110     }
    111 
    112     private static bool SubrouteConstraintsOK(IVRPProblemInstance problemInstance, List<int> route, int begin) {
    113       AlbaEncoding solution = AlbaEncoding.ConvertFrom(route, problemInstance);
    114 
    115       return problemInstance.Feasible(solution);
    116     }
    117 
    118105    public static List<int> CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
    119106      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
     
    133120      int index;
    134121      int indexOfMinimumCost = -1;
     122      int indexOfMinimumCost2 = -1;
    135123      int indexOfCustomer = -1;
     124
     125      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    136126
    137127      /*-----------------------------------------------------------------------------
     
    140130       */
    141131      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
    142         distance = Distance(problemInstance, i, 0);
    143         if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
    144 
    145         cost = -alpha * distance + // distance 0 <-> City[i]
    146                beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
    147                gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
    148 
    149         index = 0;
    150         while (index < costList.Count && costList[index] < cost) index++;
    151         costList.Insert(index, cost);
    152         unroutedList.Insert(index, i);
     132        //only insert sources
     133        if (pdp == null || problemInstance.Demand[i] >= 0) {
     134          distance = Distance(problemInstance, i, 0);
     135          if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
     136
     137          cost = -alpha * distance + // distance 0 <-> City[i]
     138                 beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
     139                 gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
     140
     141          index = 0;
     142          while (index < costList.Count && costList[index] < cost) index++;
     143
     144          costList.Insert(index, cost);
     145
     146          unroutedList.Insert(index, i);
     147        }
    153148      }
    154149
     
    163158      int subTourCount = 1;
    164159      List<int> route = new List<int>(problemInstance.Cities.Value + problemInstance.Vehicles.Value - 1);
     160      currentRoute = routeIndex;
    165161      minimumCost = double.MaxValue;
    166162      indexOfMinimumCost = -1;
     163      indexOfMinimumCost2 = -1;
    167164      route.Add(0);
    168165      route.Add(0);
     166
     167      if (pdp != null) {
     168        route.Insert(1, pdp.PickupDeliveryLocation[unroutedList[0]]);
     169        routeIndex++;
     170      }
     171
    169172      route.Insert(1, unroutedList[0]);
     173      routeIndex++;
     174
    170175      unroutedList.RemoveAt(0);
    171       currentRoute = routeIndex;
    172       routeIndex++;
    173176
    174177      while (unroutedList.Count > 0) {
    175178        for (c = 0; c < unroutedList.Count; c++) {
     179          Tour tour = new Tour();
     180          tour.Stops.AddRange(route.GetRange(currentRoute + 1, route.Count - (currentRoute + 1) - 1));
     181          VRPEvaluation eval = problemInstance.Evaluate(tour);
     182          double originalCosts = eval.Quality;
     183
    176184          for (int i = currentRoute + 1; i < route.Count; i++) {
    177185            route.Insert(i, (int)unroutedList[c]);
    178             if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
    179             cost = TravelDistance(problemInstance, route, currentRoute);
    180             if (cost < minimumCost && SubrouteConstraintsOK(problemInstance, route, currentRoute)) {
    181               minimumCost = cost;
    182               indexOfMinimumCost = i;
    183               customer = (int)unroutedList[c];
    184               indexOfCustomer = c;
     186            tour = new Tour();
     187            tour.Stops.AddRange(route.GetRange(currentRoute+1, route.Count - (currentRoute+1) - 1));
     188            eval = problemInstance.Evaluate(tour);
     189            double tourCost = eval.Quality - originalCosts;
     190
     191            if (pdp != null) {
     192              for (int j = i - (currentRoute); j <= tour.Stops.Count; j++) {
     193                bool feasible;
     194                cost = tourCost +
     195                  problemInstance.GetInsertionCosts(eval, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
     196                if (cost < minimumCost && feasible) {
     197                  minimumCost = cost;
     198                  indexOfMinimumCost = i;
     199                  indexOfMinimumCost2 = j + currentRoute + 1;
     200                  customer = (int)unroutedList[c];
     201                  indexOfCustomer = c;
     202                }
     203              }
     204            } else {
     205              cost = tourCost;
     206              bool feasible = problemInstance.Feasible(eval);
     207              if (cost < minimumCost && feasible) {
     208                minimumCost = cost;
     209                indexOfMinimumCost = i;
     210                customer = (int)unroutedList[c];
     211                indexOfCustomer = c;
     212              }
    185213            }
    186214            route.RemoveAt(i);
     
    191219          route.Insert(indexOfMinimumCost, customer);
    192220          routeIndex++;
     221
     222          if (pdp != null) {
     223            route.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[customer]);
     224            routeIndex++;
     225          }
     226
    193227          unroutedList.RemoveAt(indexOfCustomer);
    194228          costList.RemoveAt(indexOfCustomer);
     
    198232          currentRoute = routeIndex;
    199233          route.Insert(route.Count - 1, (int)unroutedList[0]);
     234          routeIndex++;
     235          if (pdp != null) {
     236            route.Insert(route.Count - 1, (int)pdp.PickupDeliveryLocation[unroutedList[0]]);
     237            routeIndex++;
     238          }
    200239          unroutedList.RemoveAt(0);
    201           routeIndex++;
    202240          subTourCount++;
    203241        }
     
    205243        minimumCost = double.MaxValue;
    206244        indexOfMinimumCost = -1;
     245        indexOfMinimumCost2 = -1;
    207246        indexOfCustomer = -1;
    208247        customer = -1;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/IterativeInsertionCreator.cs

    r6713 r6759  
    3131using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3232using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
     33using HeuristicLab.Problems.VehicleRouting.Variants;
    3334
    3435namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    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.Demand[i] >= 0)
     92          customers.Add(i);
     93
    8994      customers.Sort(delegate(int city1, int city2)
    9095          {
     
    104109        currentTour.Stops.Insert(stopIdx, customers[index]);
    105110
     111        if (pdp != null) {
     112          stopIdx = result.FindBestInsertionPlace(currentTour, pdp.PickupDeliveryLocation[customers[index]]);
     113          currentTour.Stops.Insert(stopIdx, pdp.PickupDeliveryLocation[customers[index]]);
     114        }
     115
    106116        CVRPEvaluation evaluation = instance.Evaluate(currentTour) as CVRPEvaluation;
    107117        if (result.Tours.Count < instance.Vehicles.Value &&
    108118          ((adhereTimeWindows && !instance.Feasible(evaluation)) || ((!adhereTimeWindows) && evaluation.Overload > double.Epsilon))) {
    109           currentTour.Stops.RemoveAt(stopIdx);
     119            currentTour.Stops.Remove(customers[index]);
     120            if (pdp != null)
     121              currentTour.Stops.Remove(pdp.PickupDeliveryLocation[customers[index]]);
    110122
    111123          if(currentTour.Stops.Count > 0)
Note: See TracChangeset for help on using the changeset viewer.