1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Optimization;


28  using HeuristicLab.Parameters;


29  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


30  using HeuristicLab.Problems.VehicleRouting.Interfaces;


31  using HeuristicLab.Problems.VehicleRouting.ProblemInstances;


32  using HeuristicLab.Problems.VehicleRouting.Variants;


33 


34  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {


35  [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.")]


36  [StorableClass]


37  public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {


38  #region IStochasticOperator Members


39  public ILookupParameter<IRandom> RandomParameter {


40  get { return (LookupParameter<IRandom>)Parameters["Random"]; }


41  }


42  #endregion


43 


44  public IValueParameter<DoubleValue> Alpha {


45  get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }


46  }


47  public IValueParameter<DoubleValue> AlphaVariance {


48  get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }


49  }


50  public IValueParameter<DoubleValue> Beta {


51  get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }


52  }


53  public IValueParameter<DoubleValue> BetaVariance {


54  get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }


55  }


56  public IValueParameter<DoubleValue> Gamma {


57  get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }


58  }


59  public IValueParameter<DoubleValue> GammaVariance {


60  get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }


61  }


62 


63  [StorableConstructor]


64  private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { }


65 


66  public PushForwardInsertionCreator()


67  : base() {


68  Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));


69  Parameters.Add(new ValueParameter<DoubleValue>("Alpha", "The alpha value.", new DoubleValue(0.7)));


70  Parameters.Add(new ValueParameter<DoubleValue>("AlphaVariance", "The alpha variance.", new DoubleValue(0.5)));


71  Parameters.Add(new ValueParameter<DoubleValue>("Beta", "The beta value.", new DoubleValue(0.1)));


72  Parameters.Add(new ValueParameter<DoubleValue>("BetaVariance", "The beta variance.", new DoubleValue(0.07)));


73  Parameters.Add(new ValueParameter<DoubleValue>("Gamma", "The gamma value.", new DoubleValue(0.2)));


74  Parameters.Add(new ValueParameter<DoubleValue>("GammaVariance", "The gamma variance.", new DoubleValue(0.14)));


75  }


76 


77  public override IDeepCloneable Clone(Cloner cloner) {


78  return new PushForwardInsertionCreator(this, cloner);


79  }


80 


81  private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner)


82  : base(original, cloner) {


83  }


84 


85  // use the BoxMueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables


86  private static double Gauss(IRandom random) {


87  double u = 0.0, v = 0.0, s = 0.0;


88  do {


89  u = (random.NextDouble() * 2)  1;


90  v = (random.NextDouble() * 2)  1;


91  s = Math.Sqrt(u * u + v * v);


92  } while (s < Double.Epsilon  s > 1);


93  return u * Math.Sqrt((2.0 * Math.Log(s)) / s);


94  }


95 


96  private static double N(double mu, double sigma, IRandom random) {


97  return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)


98  }


99 


100  private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance) {


101  double distance = 0.0;


102 


103  double startX = problemInstance.Coordinates[start, 0];


104  double startY = problemInstance.Coordinates[start, 1];


105 


106  double endX = problemInstance.Coordinates[end, 0];


107  double endY = problemInstance.Coordinates[end, 1];


108 


109  distance =


110  Math.Sqrt(


111  Math.Pow(startX  endX, 2) +


112  Math.Pow(startY  endY, 2));


113 


114  return distance;


115  }


116 


117  private static int GetNearestDepot(IVRPProblemInstance problemInstance, List<int> depots, int customer,


118  double alpha, double beta, double gamma, out double minCost) {


119  int nearest = 1;


120  minCost = double.MaxValue;


121 


122  int depotCount = 1;


123  IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;


124  if (mdp != null) {


125  depotCount = mdp.Depots.Value;


126  }


127 


128  foreach (int depot in depots) {


129  double x0 = problemInstance.Coordinates[depot, 0];


130  double y0 = problemInstance.Coordinates[depot, 1];


131 


132  double distance = GetDistance(customer + depotCount  1, depot, problemInstance);


133 


134  double dueTime = 0;


135  if (problemInstance is ITimeWindowedProblemInstance)


136  dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[customer + depotCount  1];


137  if (dueTime == double.MaxValue)


138  dueTime = 0;


139 


140  double x = problemInstance.Coordinates[customer + depotCount  1, 0];


141  double y = problemInstance.Coordinates[customer + depotCount  1, 1];


142 


143  double cost = alpha * distance + // distance 0 <> City[i]


144  beta * dueTime + // latest arrival time


145  gamma * ((Math.Atan2(y  y0, x  x0) + Math.PI) / (2.0 * Math.PI) * distance); // polar angle


146 


147  if (cost < minCost) {


148  minCost = cost;


149  nearest = depot;


150  }


151  }


152 


153  return nearest;


154  }


155 


156  private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots,


157  Dictionary<int, int> depotAssignment,


158  double alpha, double beta, double gamma) {


159  List<int> sortedCustomers = new List<int>();


160  depotAssignment.Clear();


161 


162  List<double> costList = new List<double>();


163 


164  for (int i = 0; i < customers.Count; i++) {


165  double cost;


166  int depot = GetNearestDepot(problemInstance, depots, customers[i],


167  alpha, beta, gamma,


168  out cost);


169  depotAssignment[customers[i]] = depot;


170 


171  int index = 0;


172  while (index < costList.Count && costList[index] < cost) index++;


173  costList.Insert(index, cost);


174  sortedCustomers.Insert(index, customers[i]);


175  }


176 


177  return sortedCustomers;


178  }


179 


180  private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {


181  List<int> toBeRemoved = new List<int>();


182 


183  foreach (int depot in depots) {


184  if (vehicles[depot].Count == 0)


185  toBeRemoved.Add(depot);


186  }


187 


188  foreach (int depot in toBeRemoved) {


189  depots.Remove(depot);


190  vehicles.Remove(depot);


191  }


192 


193  return toBeRemoved.Count > 0;


194  }


195 


196  public static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,


197  double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,


198  double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {


199  PotvinEncoding result = new PotvinEncoding(problemInstance);


200 


201  IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;


202  IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;


203 


204  double alpha, beta, gamma;


205  alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);


206  beta = N(betaValue, Math.Sqrt(betaVariance), random);


207  gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);


208 


209  List<int> unroutedCustomers = new List<int>();


210  for (int i = 1; i <= problemInstance.Cities.Value; i++) {


211  if (pdp == null  (problemInstance.GetDemand(i) >= 0))


212  unroutedCustomers.Add(i);


213  }


214 


215  List<int> depots = new List<int>();


216  if (mdp != null) {


217  for (int i = 0; i < mdp.Depots.Value; i++) {


218  depots.Add(i);


219  }


220  } else {


221  depots.Add(0);


222  }


223 


224  Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();


225  foreach (int depot in depots) {


226  vehicles[depot] = new List<int>();


227 


228  int vehicleCount = problemInstance.Vehicles.Value;


229  if (mdp != null) {


230  for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {


231  if (mdp.VehicleDepotAssignment[vehicle] == depot) {


232  vehicles[depot].Add(vehicle);


233  }


234  }


235  } else {


236  for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {


237  vehicles[depot].Add(vehicle);


238  }


239  }


240  }


241 


242  RemoveUnusedDepots(depots, vehicles);


243  Dictionary<int, int> depotAssignment = new Dictionary<int, int>();


244 


245  unroutedCustomers = SortCustomers(


246  problemInstance, unroutedCustomers, depots, depotAssignment,


247  alpha, beta, gamma);


248 


249  /////////


250  Tour tour = new Tour();


251  result.Tours.Add(tour);


252  int currentCustomer = unroutedCustomers[0];


253  unroutedCustomers.RemoveAt(0);


254 


255  int currentDepot = depotAssignment[currentCustomer];


256  int currentVehicle = vehicles[currentDepot][0];


257  vehicles[currentDepot].RemoveAt(0);


258  if (RemoveUnusedDepots(depots, vehicles)) {


259  unroutedCustomers = SortCustomers(


260  problemInstance, unroutedCustomers, depots, depotAssignment,


261  alpha, beta, gamma);


262  }


263 


264  result.VehicleAssignment[result.Tours.Count  1] = currentVehicle;


265 


266  tour.Stops.Add(currentCustomer);


267  if (pdp != null) {


268  tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));


269  }


270  ////////


271 


272  while (unroutedCustomers.Count > 0) {


273  double minimumCost = double.MaxValue;


274  int customer = 1;


275  int indexOfMinimumCost = 1;


276  int indexOfMinimumCost2 = 1;


277 


278  foreach (int unrouted in unroutedCustomers) {


279  VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);


280  double originalCosts = eval.Quality;


281 


282  for (int i = 0; i <= tour.Stops.Count; i++) {


283  tour.Stops.Insert(i, unrouted);


284  eval = problemInstance.EvaluateTour(tour, result);


285  double tourCost = eval.Quality  originalCosts;


286 


287  if (pdp != null) {


288  for (int j = i + 1; j <= tour.Stops.Count; j++) {


289  bool feasible;


290  double cost = tourCost +


291  problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);


292  if (cost < minimumCost && feasible) {


293  customer = unrouted;


294  minimumCost = cost;


295  indexOfMinimumCost = i;


296  indexOfMinimumCost2 = j;


297  }


298  }


299  } else {


300  double cost = tourCost;


301  bool feasible = problemInstance.Feasible(eval);


302  if (cost < minimumCost && feasible) {


303  customer = unrouted;


304  minimumCost = cost;


305  indexOfMinimumCost = i;


306  }


307  }


308 


309  tour.Stops.RemoveAt(i);


310  }


311  }


312 


313  if (indexOfMinimumCost == 1 && vehicles.Count == 0) {


314  indexOfMinimumCost = tour.Stops.Count;


315  indexOfMinimumCost2 = tour.Stops.Count + 1;


316  customer = unroutedCustomers[0];


317  }


318 


319  // insert customer if found


320  if (indexOfMinimumCost != 1) {


321  tour.Stops.Insert(indexOfMinimumCost, customer);


322  if (pdp != null) {


323  tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));


324  }


325 


326  unroutedCustomers.Remove(customer);


327  } else { // no feasible customer found


328  tour = new Tour();


329  result.Tours.Add(tour);


330  currentCustomer = unroutedCustomers[0];


331  unroutedCustomers.RemoveAt(0);


332 


333  currentDepot = depotAssignment[currentCustomer];


334  currentVehicle = vehicles[currentDepot][0];


335  vehicles[currentDepot].RemoveAt(0);


336  if (RemoveUnusedDepots(depots, vehicles)) {


337  unroutedCustomers = SortCustomers(


338  problemInstance, unroutedCustomers, depots, depotAssignment,


339  alpha, beta, gamma);


340  }


341 


342  result.VehicleAssignment[result.Tours.Count  1] = currentVehicle;


343 


344  tour.Stops.Add(currentCustomer);


345  if (pdp != null) {


346  tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));


347  }


348  }


349  }


350 


351  if (mdp != null) {


352  List<int> availableVehicles = new List<int>();


353  for (int i = 0; i < mdp.Vehicles.Value; i++)


354  availableVehicles.Add(i);


355 


356  for (int i = 0; i < result.VehicleAssignment.Length; i++) {


357  if (result.VehicleAssignment[i] != 1)


358  availableVehicles.Remove(result.VehicleAssignment[i]);


359  }


360 


361  for (int i = 0; i < result.VehicleAssignment.Length; i++) {


362  if (result.VehicleAssignment[i] == 1) {


363  result.VehicleAssignment[i] = availableVehicles[0];


364  availableVehicles.RemoveAt(0);


365  }


366  }


367  }


368 


369  return result;


370  }


371 


372  public override IOperation InstrumentedApply() {


373  VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, RandomParameter.ActualValue,


374  Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,


375  AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);


376 


377  return base.InstrumentedApply();


378  }


379  }


380  }

