1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022010 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 HeuristicLab.Common;


23  using HeuristicLab.Core;


24  using HeuristicLab.Data;


25  using HeuristicLab.Encodings.PermutationEncoding;


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


27  using System.Collections.Generic;


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


29  using System;


30  using HeuristicLab.Problems.VehicleRouting.Interfaces;


31  using HeuristicLab.Problems.VehicleRouting.ProblemInstances;


32 


33  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Prins {


34  [Item("PrinsEncoding", "Represents an Prins encoding of VRP solutions. It is implemented as described in Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 12:19852002.")]


35  [StorableClass]


36  public class PrinsEncoding : PermutationEncoding {


37  #region IVRPEncoding Members


38  public override List<Tour> GetTours() {


39  List<Tour> result = new List<Tour>();


40 


41  int cities = ProblemInstance.Cities.Value;


42 


43  //Split permutation into vector P


44  int[] P = new int[cities + 1];


45  for (int i = 0; i <= cities; i++)


46  P[i] = 1;


47 


48  double[] V = new double[cities + 1];


49  V[0] = 0;


50  for (int i = 1; i <= cities; i++) {


51  V[i] = double.MaxValue;


52  }


53 


54  for (int i = 1; i <= cities; i++) {


55  int j = i;


56  Tour tour = new Tour();


57  bool feasible = true;


58 


59  do {


60  tour.Stops.Add(this[j1] + 1);


61 


62  VRPEvaluation eval =


63  ProblemInstance.EvaluateTour(tour, this);


64 


65  double cost = eval.Quality;


66  feasible = ProblemInstance.Feasible(eval);


67 


68  if (feasible  j == i) {


69  if (V[i  1] + cost < V[j]) {


70  V[j] = V[i  1] + cost;


71  P[j] = i  1;


72  }


73  j++;


74  }


75 


76  } while (j <= cities && feasible);


77  }


78 


79  //extract VRP solution from vector P


80  int index = 0;


81  int index2 = cities;


82  Tour trip = null;


83  do {


84  index = P[index2];


85  trip = new Tour();


86 


87  for (int k = index + 1; k <= index2; k++) {


88  trip.Stops.Add(this[k  1] + 1);


89  }


90 


91  if (trip.Stops.Count > 0)


92  result.Add(trip);


93 


94  index2 = index;


95  } while (index != 0);


96 


97  //if there are too many vehicles  repair


98  while (result.Count > ProblemInstance.Vehicles.Value) {


99  Tour tour = result[result.Count  1];


100 


101  //find predecessor / successor in permutation


102  int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0]  1)  1;


103  if (predecessorIndex >= 0) {


104  int predecessor = this[predecessorIndex] + 1;


105 


106  foreach (Tour t in result) {


107  int insertPosition = t.Stops.IndexOf(predecessor) + 1;


108  if (insertPosition != 1) {


109  t.Stops.InsertRange(insertPosition, tour.Stops);


110  break;


111  }


112  }


113  } else {


114  int successorIndex = Array.IndexOf(this.array,


115  tour.Stops[tour.Stops.Count  1]  1) + 1;


116  int successor = this[successorIndex] + 1;


117 


118  foreach (Tour t in result) {


119  int insertPosition = t.Stops.IndexOf(successor);


120  if (insertPosition != 1) {


121  t.Stops.InsertRange(insertPosition, tour.Stops);


122  break;


123  }


124  }


125  }


126 


127  result.Remove(tour);


128  }


129 


130  return result;


131  }


132  #endregion


133  public PrinsEncoding(Permutation permutation, IVRPProblemInstance problemInstance)


134  : base(permutation, problemInstance) {


135  }


136 


137  [StorableConstructor]


138  private PrinsEncoding(bool serializing)


139  : base(serializing) {


140  }


141 


142  public override IDeepCloneable Clone(Cloner cloner) {


143  return new PrinsEncoding(this, cloner);


144  }


145 


146  protected PrinsEncoding(PrinsEncoding original, Cloner cloner)


147  : base(original, cloner) {


148  }


149 


150  public static PrinsEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance problemInstance) {


151  List<Tour> tours = encoding.GetTours();


152  List<int> route = new List<int>();


153 


154  foreach (Tour tour in tours) {


155  foreach (int city in tour.Stops)


156  route.Add(city  1);


157  }


158 


159  return new PrinsEncoding(


160  new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance);


161  }


162 


163  public static PrinsEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance problemInstance) {


164  List<int> route = new List<int>(routeParam);


165 


166  while (route.Remove(0)) { //remove all delimiters (0)


167  }


168 


169  for (int i = 0; i < route.Count; i++)


170  route[i];


171 


172  return new PrinsEncoding(


173  new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance);


174  }


175  }


176  }

