1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022011 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.Collections.Generic;


23  using HeuristicLab.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Data;


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


27  using HeuristicLab.Problems.VehicleRouting.Encodings.General;


28 


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


30  [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions. It is implemented as described in Potvin, J.Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows  Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]


31  [StorableClass]


32  public class PotvinEncoding : TourEncoding {


33  [Storable]


34  public List<int> Unrouted { get; set; }


35 


36  [StorableConstructor]


37  protected PotvinEncoding(bool deserializing) : base(deserializing) { }


38  protected PotvinEncoding(PotvinEncoding original, Cloner cloner)


39  : base(original, cloner) {


40  Tours = cloner.Clone(original.Tours);


41  Unrouted = new List<int>(original.Unrouted);


42  }


43  public PotvinEncoding()


44  : base() {


45  Unrouted = new List<int>();


46  }


47 


48  public override IDeepCloneable Clone(Cloner cloner) {


49  return new PotvinEncoding(this, cloner);


50  }


51 


52  public static PotvinEncoding ConvertFrom(IVRPEncoding encoding, ILookupParameter<DoubleMatrix> distanceMatrix) {


53  PotvinEncoding solution = new PotvinEncoding();


54 


55  TourEncoding.ConvertFrom(encoding, solution, distanceMatrix);


56 


57  return solution;


58  }


59 


60  public static PotvinEncoding ConvertFrom(List<int> route) {


61  PotvinEncoding solution = new PotvinEncoding();


62 


63  TourEncoding.ConvertFrom(route, solution);


64 


65  return solution;


66  }


67 


68  public bool FindInsertionPlace(


69  DoubleArray dueTimeArray,


70  DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,


71  DistanceMatrix distMatrix,


72  int city, int routeToAvoid, out int route, out int place) {


73  route = 1;


74  place = 1;


75  bool bestFeasible = false;


76  double minDetour = 0;


77 


78  for (int tour = 0; tour < Tours.Count; tour++) {


79  if (tour != routeToAvoid) {


80  for (int i = 0; i <= Tours[tour].Cities.Count; i++) {


81  double length = Tours[tour].GetLength(distMatrix);


82 


83  Tours[tour].Cities.Insert(i, city);


84 


85  bool feasible = Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,


86  capacity, distMatrix);


87 


88  if (!bestFeasible  feasible) {


89  double newLength = Tours[tour].GetLength(distMatrix);


90  double detour = newLength  length;


91 


92  if (route <= 0  detour < minDetour  (!(bestFeasible && !feasible)) && detour < minDetour  (feasible && !bestFeasible)) {


93  route = tour;


94  place = i;


95  minDetour = detour;


96 


97  if (feasible)


98  bestFeasible = true;


99  }


100  }


101 


102  Tours[tour].Cities.RemoveAt(i);


103  }


104  }


105  }


106 


107  return route >= 0 && place >= 0;


108  }


109  }


110  }

