1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022014 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 System.Globalization;


25  using System.IO;


26  using System.Linq;


27  using System.Threading;


28  using HeuristicLab.Analysis;


29  using HeuristicLab.Core;


30  using HeuristicLab.Optimization;


31  using HeuristicLab.Random;


32  using HeuristicLab.Scripting;


33 


34  namespace HeuristicLab.Problems.Orienteering {


35 


36  /*


37  * Based on


38  * Implementation of an Pareto Ant Colony


39  * Optimization (PACO) metaheuristic and a


40  * Pareto Variable Neighborhood Search (PVNS)


41  * metaheuristic for the MultiObjective


42  * Orienteering Problem (MOP)


43  * Copyright: © 2007 by Michael Schilde


44  *


45  * See Metaheuristics for the biobjective orienteering problem


46  * http://link.springer.com/article/10.1007/s1172100900295


47  * Michael Schilde, Karl F. Doerner, Richard F. Hartl, Guenter Kiechle


48  */


49  public class OrienteeringScript : CSharpScriptBase {


50  #region Constants


51 


52  private const bool ShowStatus = true;


53 


54  private const double PrecisionUsed = 0.0000001;


55 


56  private const string VersionRequired = "*tpv1.1* or *tpv1.0*";


57 


58  private const int ConstraintTimeDistance = 1;


59 


60  private static readonly TimeSpan RunDuration = TimeSpan.FromSeconds(15);


61 


62  public enum ErrorCode {


63  ErrorNone = 0,


64  ErrorOpenInputFile = 10,


65  ErrorOpenOutputFile = 11,


66  ErrorConvertToLower = 12,


67  ErrorRemovingWhitespace = 13,


68  ErrorWrongVersion = 14,


69  ErrorReadingData = 20,


70  ErrorInvalidDefinitionN = 30,


71  ErrorInvalidDefinitionC = 31,


72  ErrorInvalidDefinitionU = 32,


73  ErrorInvalidDefinitionL = 33,


74  ErrorInvalidDefinitionX = 34,


75  ErrorInvalidDefinitionI = 35,


76  ErrorInvalidDefinitionP = 36,


77  ErrorInvalidDefinitionS = 37,


78  ErrorInvalidDefinitionB = 38,


79  ErrorInvalidDefinitionE = 39,


80  ErrorInvalidDefinitionD = 40,


81  ErrorInvalidDefinitionM = 41,


82  ErrorMissingStartingPoint = 50,


83  ErrorMissingTerminusPoint = 51,


84  ErrorTooFewConstraints = 63,


85  ErrorTooFewPoints = 64,


86  ErrorTooFewScores = 65,


87  ErrorTooManyConstraints = 66,


88  ErrorTooManyPoints = 67,


89  ErrorTooManyScores = 68


90  }


91 


92  #endregion


93 


94  #region Fields


95  private TimeSpan avgTimeDurationVns;


96  private List<TimeSpan> timeDurationVns = new List<TimeSpan>();


97  private List<int> solutionsFoundVns = new List<int>();


98  private List<List<TourData>> TourBackupVNS = new List<List<TourData>>();


99  private List<int> solutionsFoundPrVns = new List<int>();


100  private List<ProblemData> problems = new List<ProblemData>();


101  private double averageScoreVns;


102  private double bestScoreVns;


103  private TimeSpan timeOfBestScoreVns;


104  private double worstScoreVns;


105 


106  private ItemList<IItem> results;


107  private DataTable scores;


108 


109  #endregion


110 


111  public override void Main() {


112  Thread.CurrentThread.CurrentCulture = new CultureInfo("enUS");


113 


114  vars.Clear();


115 


116  const int numberOfRuns = 10;


117  const string inputFilename = @"C:\Users\P41107\Desktop\moop\1 objective\1_p66\1_p66_t080.txt";


118  const string csvFilename = @"C:\temp\results1.csv";


119  const string summaryFilename = @"C:\temp\summary.csv";


120  const int numberOfIterations = 10000;


121  const int acceptFrequency = 100;


122  const double tresholdValue = 0.95;


123  const double fixedVisitingTime = 0.0;


124  const double fixedPenalty = fixedVisitingTime;


125  const double maximumDistanceOverride = 0.0;


126  const bool performPathRelinkingComparison = true;


127 


128  string testInstanceName = inputFilename.Contains(@"\")


129  ? inputFilename.Substring(inputFilename.LastIndexOf(@"\") + 1)


130  : inputFilename.Substring(inputFilename.LastIndexOf(@"/") + 1);


131 


132  bool csvExists = File.Exists(summaryFilename);


133 


134  // Open the results CSV file for writing the data


135  using (var csvFile = new StreamWriter(new FileStream(csvFilename, FileMode.Create)))


136  // Open the summary CSV file for appending the data


137  using (var summaryFile = new StreamWriter(new FileStream(summaryFilename, FileMode.OpenOrCreate))) {


138 


139  // Remember the overall starting time


140  var startOverall = DateTime.Now.Ticks;


141 


142  for (int runCounter = 0; runCounter < numberOfRuns; runCounter++) {


143  // Print out a status information


144  if (ShowStatus)


145  Console.WriteLine("Run {0} started.", (runCounter + 1));


146 


147  // Create a new problem data container


148  var problem = new ProblemData {


149  FixedPenalty = fixedVisitingTime,


150  Constraints = new List<ConstraintData>(),


151  Points = new List<PointData>(),


152  Edges = new List<List<EdgeData>>(),


153  MTR = new MersenneTwister(),


154  VNS = new VnsData {


155  NumberOfIterations = numberOfIterations,


156  AcceptFrequency = acceptFrequency,


157  TresholdValue = tresholdValue,


158  InitialTour = new TourData { Path = new List<int>(), Scores = new List<int>() },


159  DominantTours = new List<TourData>()


160  },


161  };


162 


163  // Do the initialization


164  ErrorCode errorCode = LoadData(inputFilename, problem);


165  if (errorCode != 0) {


166  Console.WriteLine("Initialization failed. (Code: {0})", errorCode);


167  Console.WriteLine(GetErrorDescription(errorCode));


168  Console.WriteLine("Exiting.");


169  return;


170  }


171 


172  // Override the distance limit from file by parameter if specified


173  if (maximumDistanceOverride > 0.0) {


174  problem.Constraints.Clear();


175  problem.Constraints.Add(new ConstraintData {


176  Type = Constraint.Upperbound,


177  Target = 1,


178  TargetValue = maximumDistanceOverride


179  });


180  }


181 


182  results = new ItemList<IItem>();


183  vars["run" + runCounter] = results;


184  scores = new DataTable("Scores");


185  results.Add(scores);


186  scores.Rows.AddRange(Enumerable.Range(0, problem.ScoreCount).Select(s => new DataRow("Score " + s)));


187 


188  if (ShowStatus)


189  Console.WriteLine("\tVNS started.");


190 


191  // Run the VNS algorithm


192  var startPart = DateTime.Now.Ticks;


193  var durationPart = RunDuration.Ticks;


194  RunVns(problem, startPart, durationPart);


195  var endPart = DateTime.Now.Ticks;


196  var temp = CalculateDifference(startPart, endPart);


197  avgTimeDurationVns += temp;


198  timeDurationVns.Add(temp);


199  solutionsFoundVns.Add((int)problem.VNS.DominantTours.Count);


200 


201  if (ShowStatus)


202  Console.WriteLine("\tVNS completed ({0} Tours in {1:g}).", problem.VNS.DominantTours.Count, temp);


203 


204  if (performPathRelinkingComparison) {


205  // Backup original VNS results


206  TourBackupVNS.Add(problem.VNS.DominantTours);


207  }


208 


209  // If we have two objectives, run path relinking


210  if (problem.ScoreCount == 2) {


211  // Run the path relinking for the VNS solutions


212  if (ShowStatus)


213  Console.WriteLine("\tPath relinking for VNS solutions started.");


214  int toursFoundPrVns = PathRelinking(problem, problem.VNS.DominantTours, startPart);


215 


216  temp = CalculateDifference(startPart, DateTime.Now.Ticks)  temp;


217  solutionsFoundPrVns.Add(toursFoundPrVns);


218  if (ShowStatus)


219  Console.WriteLine("\tPath relinking for VNS solutions completed ({0} tours in {1:g}).", toursFoundPrVns, temp);


220  }


221 


222  // Store all the information in the runspanning storage


223  problems.Add(problem);


224  }


225 


226  // If we have more than one objective, calculate metrics


227  if (problems[0].ScoreCount == 2) {


228  if (ShowStatus)


229  Console.WriteLine("Performing 2objective postcalculations.");


230  throw new NotImplementedException();


231  } else {


232  if (ShowStatus)


233  Console.WriteLine("\tPerforming 1objective postcalculations.");


234 


235  // Only one objective value, so just calculate best, average and worst score


236  for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {


237  averageScoreVns += problems[counterRuns].VNS.DominantTours[0].Scores[0];


238 


239  if (problems[counterRuns].VNS.DominantTours[0].Scores[0] > bestScoreVns) {


240  bestScoreVns = problems[counterRuns].VNS.DominantTours[0].Scores[0];


241  timeOfBestScoreVns = problems[counterRuns].VNS.DominantTours[0].TimeOfAdding;


242  }


243  if ((counterRuns == 0)  (problems[counterRuns].VNS.DominantTours[0].Scores[0] < worstScoreVns)) {


244  worstScoreVns = problems[counterRuns].VNS.DominantTours[0].Scores[0];


245  }


246  }


247 


248  // Calculate the average computation times


249  averageScoreVns /= numberOfRuns;


250 


251  if (ShowStatus)


252  Console.WriteLine("\tWriting output files.");


253 


254  // Write out the CSV results file


255  csvFile.WriteLine("Test instance;Tmax;# runs;iter. VNS;accept frequency;treshold");


256  csvFile.Write(testInstanceName + ";");


257  csvFile.Write("{0};", problems[0].Constraints[0].TargetValue);


258  csvFile.Write("{0};", numberOfRuns);


259  csvFile.Write("{0};", numberOfIterations);


260  csvFile.Write("{0};", acceptFrequency);


261  csvFile.Write("{0};", tresholdValue);


262  csvFile.WriteLine();


263  csvFile.WriteLine();


264 


265  // If we have more than one objective, print out the full detail report


266  if (problems[0].ScoreCount > 1) {


267  throw new NotImplementedException();


268  } else {


269  // Only one objective, so print out the short report only


270  csvFile.WriteLine("Run;CPU VNS;Score VNS");


271  for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {


272  csvFile.Write("{0};", counterRuns + 1); // Number of runs


273  csvFile.Write("{0};", timeDurationVns[counterRuns]); // CPU VNS


274  csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Scores[0]); // Score VNS


275  //csv_file << convert_locale(time_of_best_score_aco) << ";"; // Runtime until finding best tour ACO


276  //csv_file << convert_locale(time_of_best_score_vns) << ";"; // Runtime until finding best tour VNS


277  csvFile.WriteLine();


278  }


279  csvFile.WriteLine();


280  for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {


281  csvFile.WriteLine("Run;{0}", counterRuns + 1);


282  csvFile.WriteLine(";;Length;Time Of Adding;Score;Path");


283  csvFile.Write(";;");


284 


285 


286  csvFile.WriteLine();


287  csvFile.WriteLine();


288 


289  csvFile.WriteLine(";Tour VNS");


290  csvFile.WriteLine(";;Length;Time Of Adding;Score;Path");


291  csvFile.Write(";;");


292  csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Length);


293  csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].TimeOfAdding);


294  csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Scores[0]);


295  csvFile.Write("{0}", problems[counterRuns].VNS.DominantTours[0].Path[0]);


296  for (int counterPoints = 1;


297  counterPoints < problems[counterRuns].VNS.DominantTours[0].PathSize;


298  counterPoints++) {


299  csvFile.Write("{0}", problems[counterRuns].VNS.DominantTours[0].Path[counterPoints]);


300  }


301  csvFile.WriteLine();


302  csvFile.WriteLine();


303  }


304  // Append the CSV summary file information


305  if (!csvExists) {


306  summaryFile.Write("Test instance;Tmax;# runs;iter. VNS;accept frequency;treshold;");


307  summaryFile.Write("avg. CPU VNS;max score VNS;avg. score VNS;min score VNS;time of adding best tour VNS");


308  summaryFile.WriteLine();


309  }


310  summaryFile.Write("{0};", testInstanceName);


311  summaryFile.Write("{0};", problems[0].Constraints[0].TargetValue);


312  summaryFile.Write("{0};", numberOfRuns);


313  summaryFile.Write("{0};", numberOfIterations); // number of iterations vns


314  summaryFile.Write("{0};", acceptFrequency); // accept frequency


315  summaryFile.Write("{0};", tresholdValue); // treshold value


316  summaryFile.Write("{0};", avgTimeDurationVns); // CPU VNS


317  summaryFile.Write("{0};", bestScoreVns); // Best score VNS


318  summaryFile.Write("{0};", averageScoreVns); // Average score VNS


319  summaryFile.Write("{0};", worstScoreVns); // Worst score VNS


320  summaryFile.Write("{0};", timeOfBestScoreVns); // Time until best score VNS


321  summaryFile.WriteLine();


322  }


323  }


324  }


325  }


326 


327  #region Initialization


328 


329  private static ErrorCode LoadData(string fileName, ProblemData problem) {


330  StreamReader inputFile;


331  try {


332  // Open the input file


333  inputFile = new StreamReader(new FileStream(fileName, FileMode.OpenOrCreate));


334  } catch (IOException) {


335  return ErrorCode.ErrorOpenInputFile;


336  }


337 


338  // Initialize the Data structure


339  problem.ConstraintCount = 0;


340  problem.PointCount = 0;


341  problem.ScoreCount = 0;


342  problem.StartingPoint = 1;


343  problem.TerminusPoint = 1;


344  problem.MatrixGiven = false;


345 


346  ErrorCode error = ErrorCode.ErrorNone;


347 


348  int lineNumber = 0;


349 


350  // Read the lines from the file


351  while ((!inputFile.EndOfStream) && (error == ErrorCode.ErrorNone)) {


352  string lineBuffer;


353  try {


354  lineBuffer = inputFile.ReadLine();


355  } catch (IOException) {


356  return ErrorCode.ErrorReadingData;


357  }


358 


359  // Remove all whitespace


360  lineBuffer = new string(lineBuffer.ToCharArray().Where(c => !char.IsWhiteSpace(c)).ToArray());


361 


362  // If the line contains data, continue


363  if (lineBuffer.Length > 1) {


364  // If the line contains not only a comment, process it


365  int commentPosition = lineBuffer.IndexOf("//");


366  if (commentPosition != 0) {


367  // Count the lines that include data


368  lineNumber++;


369 


370  // Remove a comment if there is one


371  if (commentPosition > 0)


372  lineBuffer = lineBuffer.Remove(commentPosition);


373 


374  // Convert the line to lowercase characters


375  lineBuffer = lineBuffer.ToLower();


376 


377  // Make sure the first data line includes the correct version


378  if (lineNumber == 1) {


379  string versions = VersionRequired;


380  bool versionFound = false;


381  do {


382  if (lineBuffer == versions.Substring(versions.IndexOf(" or ") + 1)) {


383  versionFound = true;


384  break;


385  }


386  versions = versions.Remove(versions.IndexOf(" or "));


387  }


388  while (versions.IndexOf(" or ") != 1);


389 


390  //if (line_buffer != POPT_Version_Required) return ERROR_WRONG_VERSION;


391  } else {


392  // Extract the needed information


393  error = ExtractData(lineBuffer, problem);


394  }


395  }


396  }


397  }


398 


399  // Check the data for inconsistencies in the data structure


400  if (error == ErrorCode.ErrorNone) {


401  if (problem.Constraints.Count < problem.ConstraintCount)


402  return ErrorCode.ErrorTooFewConstraints;


403 


404  if (problem.Points.Count < problem.PointCount)


405  return ErrorCode.ErrorTooFewPoints;


406 


407  if (problem.StartingPoint == 1)


408  return ErrorCode.ErrorMissingStartingPoint;


409 


410  if (problem.TerminusPoint == 1)


411  return ErrorCode.ErrorMissingTerminusPoint;


412 


413  // Calculate all distances from one point to another


414  // and initialize pheromone values


415  int pointCounter1;


416  int pointCounter2;


417  double maxDistance;


418  if (!problem.MatrixGiven) {


419  maxDistance = 0.0;


420  for (pointCounter1 = (problem.PointCount  1); pointCounter1 >= 0; pointCounter1) {


421  // Delete the last generated edgeset


422  var tempEdgeset = new List<EdgeData>();


423 


424  for (pointCounter2 = (problem.PointCount  1); pointCounter2 >= 0; pointCounter2) {


425  // Calculate the distances


426  double distanceX = Math.Abs(problem.Points[pointCounter1].PositionX  problem.Points[pointCounter2].PositionX);


427  double distanceY = Math.Abs(problem.Points[pointCounter1].PositionY  problem.Points[pointCounter2].PositionY);


428  var tempEdge = new EdgeData {


429  Distance = Math.Sqrt(Math.Pow(distanceX, 2.0) + Math.Pow(distanceY, 2.0))


430  };


431 


432  // Remember the longest distance


433  if ((tempEdge.Distance  maxDistance) >= PrecisionUsed) maxDistance = tempEdge.Distance; //(temp_edge.Distance > max_distance)


434 


435  // Initialize the edge's pheromone values


436  //temp_edge.Pheromone.assign(Problem.Score_Count, Problem.ACO.Initial_Pheromone_Value);


437 


438  // Put the now generated edge to the temporal edge set


439  tempEdgeset.Insert(0, tempEdge);


440  }


441 


442  // Put the now generated temporal edge set to the original edge set


443  problem.Edges.Insert(0, tempEdgeset);


444  }


445  } else {


446  maxDistance = 0.0;


447 


448  // Find the maximum distance in the problem set


449  for (pointCounter1 = 0; pointCounter1 < problem.PointCount; pointCounter1++) {


450  for (pointCounter2 = 0; pointCounter2 < problem.PointCount; pointCounter2++) {


451  if ((problem.Edges[pointCounter1][pointCounter2].Distance  maxDistance) >= PrecisionUsed) { //(Problem.Edges[point_counter1][point_counter2].Distance > max_distance)


452  maxDistance = problem.Edges[pointCounter1][pointCounter2].Distance;


453  }


454  }


455  }


456  }


457  }


458 


459  // Close the input file


460  inputFile.Close();


461 


462  // Return with no error


463  return error;


464  }


465 


466  private static ErrorCode ExtractData(string inputString, ProblemData problem) {


467  string temp;


468 


469  switch (inputString[0]) {


470  case 'p': // Point description


471  if (inputString.Length < 8)


472  return ErrorCode.ErrorInvalidDefinitionP;


473 


474  // Remove the 'p,'


475  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


476  // Get the position_x


477  string positionX = inputString.Substring(0, inputString.IndexOf(','));


478  // Remove the position_x


479  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


480  // Get the postion_y


481  string positionY = inputString.Substring(0, inputString.IndexOf(','));


482  // Remove the position_y to get the scores


483  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


484 


485  var tempData = new PointData {


486  PositionX = double.Parse(positionX),


487  PositionY = double.Parse(positionY),


488  Score = new List<int>()


489  };


490 


491  // Extract all score values for this point


492  while (true) {


493  string score;


494  if (inputString.IndexOf(',') != 1) {


495  score = inputString.Substring(0, inputString.IndexOf(','));


496  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


497  tempData.Score.Add(int.Parse(score));


498  } else {


499  score = inputString;


500  tempData.Score.Add(int.Parse(score));


501  break;


502  }


503  }


504  problem.Points.Add(tempData);


505  break;


506 


507  case 'd': // Distance information


508  if (inputString.Length < 11)


509  return ErrorCode.ErrorInvalidDefinitionD;


510 


511  var tempEdges = new List<EdgeData>();


512 


513  // Remove the 'd,'


514  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


515 


516  // Extract all distances for this point


517  while (true) {


518  string distance;


519  if (inputString.IndexOf(',') != 1) {


520  distance = inputString.Substring(0, inputString.IndexOf(','));


521  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


522  var tempEdge = new EdgeData {


523  Distance = double.Parse(distance)


524  };


525  tempEdges.Add(tempEdge);


526  } else {


527  distance = inputString;


528  var tempEdge = new EdgeData {


529  Distance = double.Parse(distance)


530  };


531  tempEdges.Add(tempEdge);


532  break;


533  }


534  }


535  problem.Edges.Add(tempEdges);


536  break;


537 


538  case 'n': // Number of points


539  if (inputString.Length < 3)


540  return ErrorCode.ErrorInvalidDefinitionN;


541 


542  // Remove the 'n,'


543  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


544  // Extract the number of points


545  problem.PointCount = int.Parse(inputString);


546  break;


547 


548  case 'm': // 1 if DistanceMatrix is given


549  if (inputString.Length < 3)


550  return ErrorCode.ErrorInvalidDefinitionM;


551 


552  // Remove the 'm,'


553  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


554  // Extract the number of points


555  if (int.Parse(inputString) != 0) problem.MatrixGiven = true;


556  break;


557 


558  case 'c': // Number of constraints


559  if (inputString.Length < 3)


560  return ErrorCode.ErrorInvalidDefinitionC;


561 


562  // Remove the 'c,'


563  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


564  problem.ConstraintCount = int.Parse(inputString);


565  break;


566 


567  case 's': // Number of scores per point


568  if (inputString.Length < 3)


569  return ErrorCode.ErrorInvalidDefinitionS;


570 


571  // Remove the 's,'


572  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


573  problem.ScoreCount = int.Parse(inputString);


574  break;


575 


576  case 'b': // Index of the starting point


577  if (inputString.Length < 3)


578  return ErrorCode.ErrorInvalidDefinitionB;


579 


580  // Remove the 'b,'


581  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


582  problem.StartingPoint = int.Parse(inputString);


583  break;


584 


585  case 'e': // Index of the terminus point


586  if (inputString.Length < 3)


587  return ErrorCode.ErrorInvalidDefinitionE;


588 


589  // Remove the 'e,'


590  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


591  problem.TerminusPoint = int.Parse(inputString);


592  break;


593 


594  case 'u': // Upper bound constraint


595  if (inputString.Length < 5)


596  return ErrorCode.ErrorInvalidDefinitionU;


597 


598  // Remove the 'u,'


599  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


600  // Get the target


601  temp = inputString.Substring(0, inputString.IndexOf(','));


602  // Remove the target to get the target value


603  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


604 


605  problem.Constraints.Add(new ConstraintData {


606  Type = Constraint.Upperbound,


607  Target = int.Parse(temp),


608  TargetValue = double.Parse(inputString)


609  });


610  break;


611 


612  case 'l': // Lower bound constraint


613  if (inputString.Length < 5)


614  return ErrorCode.ErrorInvalidDefinitionL;


615 


616  // Remove the 'l,'


617  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


618  // Get the target


619  temp = inputString.Substring(0, inputString.IndexOf(','));


620  // Remove the target to get the target value


621  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


622 


623  problem.Constraints.Add(new ConstraintData {


624  Type = Constraint.Lowerbound,


625  Target = int.Parse(temp),


626  TargetValue = double.Parse(inputString)


627  });


628  break;


629 


630  case 'x': // Maximization constraint


631  if (inputString.Length < 5)


632  return ErrorCode.ErrorInvalidDefinitionX;


633 


634  // Remove the 'x,'


635  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


636  // Get the target


637  temp = inputString.Substring(0, inputString.IndexOf(','));


638  // Remove the target to get the target value


639  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


640 


641  problem.Constraints.Add(new ConstraintData {


642  Type = Constraint.Maximize,


643  Target = int.Parse(temp),


644  TargetValue = Double.Parse(inputString)


645  });


646  break;


647 


648  case 'i': // Minimization constraint


649  if (inputString.Length < 5)


650  return ErrorCode.ErrorInvalidDefinitionI;


651 


652  // Remove the 'i,'


653  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


654  // Get the target


655  temp = inputString.Substring(0, inputString.IndexOf(','));


656  // Remove the target to get the target value


657  inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);


658 


659  problem.Constraints.Add(new ConstraintData {


660  Type = Constraint.Minimize,


661  Target = int.Parse(temp),


662  TargetValue = double.Parse(inputString)


663  });


664  break;


665  }


666  return ErrorCode.ErrorNone;


667  }


668 


669  private static string GetErrorDescription(ErrorCode errorCode) {


670  switch (errorCode) {


671  case ErrorCode.ErrorOpenInputFile: return "The input file could not be opened.";


672  case ErrorCode.ErrorOpenOutputFile: return "The output file could not be opened.";


673  case ErrorCode.ErrorConvertToLower: return "An error occoured at the conversion to lowercase.";


674  case ErrorCode.ErrorRemovingWhitespace: return "An error occoured at the removal of whitespace.";


675  case ErrorCode.ErrorWrongVersion: return ("The input file has the wrong version. Version " + VersionRequired + " is required.");


676  case ErrorCode.ErrorReadingData: return "An error occoured while reading from the input file.";


677  case ErrorCode.ErrorInvalidDefinitionN: return "Check your definition for the number of points.";


678  case ErrorCode.ErrorInvalidDefinitionC: return "Check your definition for the number of constraints.";


679  case ErrorCode.ErrorInvalidDefinitionU: return "Check your definition for upper bound constraints.";


680  case ErrorCode.ErrorInvalidDefinitionL: return "Check your definition for lower bound constraints.";


681  case ErrorCode.ErrorInvalidDefinitionX: return "Check your definition for maximization constraints.";


682  case ErrorCode.ErrorInvalidDefinitionI: return "Check your definition for minimization constraints.";


683  case ErrorCode.ErrorInvalidDefinitionP: return "At least one point definition is missing something.";


684  case ErrorCode.ErrorInvalidDefinitionS: return "Check your definition for the number of scores.";


685  case ErrorCode.ErrorInvalidDefinitionB: return "Check your definition for the starting point.";


686  case ErrorCode.ErrorInvalidDefinitionE: return "Check your definition for the terminus point.";


687  case ErrorCode.ErrorInvalidDefinitionD: return "Check your definition for the distance matrix.";


688  case ErrorCode.ErrorInvalidDefinitionM: return "Check your definition for the distance matrix flag.";


689  case ErrorCode.ErrorMissingStartingPoint: return "The definition of the starting point is missing.";


690  case ErrorCode.ErrorMissingTerminusPoint: return "The definition of the terminus point is missing.";


691  case ErrorCode.ErrorTooFewConstraints: return "There are too few constraints on the list.";


692  case ErrorCode.ErrorTooFewPoints: return "There are too few points on the list.";


693  case ErrorCode.ErrorTooFewScores: return "There are too few scores on the list of at least one point.";


694  case ErrorCode.ErrorTooManyConstraints: return "There are too many constraints on the list.";


695  case ErrorCode.ErrorTooManyPoints: return "There are too many points on the list.";


696  case ErrorCode.ErrorTooManyScores: return "There are too many scores on the list of at least one point.";


697  default: return "Unknown error.";


698  }


699  }


700 


701  #endregion


702 


703  #region VNS


704 


705  private void RunVns(ProblemData problem, long startTime, long maxRuntime) {


706  long iterationCounter = 0;


707  int neighborhoodMax;


708  long iterationOfLastAcception = 0;


709  long iterationOfLastFinding = 0;


710  var preferences = new List<double>();


711  bool increasingPreference = false;


712  TourData newSolution;


713 


714  // Define the maximum neighborhood distance


715  //neighborhoodMax = 9;


716 


717  // Generate an initial solution


718  GenerateGreedyTour(problem);


719 


720  // Bring this tour to a local optimum


721  OptimizePath(problem, problem.VNS.InitialTour);


722 


723  // Save this tour as at the moment it seems efficient


724  SaveDominantToursVns(problem, problem.VNS.InitialTour, startTime);


725 


726  // Create the starting preference for the shaking


727  preferences.Add(1);


728  preferences.Add(0);


729 


730  // Perform the VNS


731  while ((DateTime.Now.Ticks  startTime) < maxRuntime) {


732  int neighborhoodCounter = 1;


733  //while ((neighborhoodCounter < neighborhoodMax) && ((DateTime.Now.Ticks  start_time) < max_runtime))


734  while ((neighborhoodCounter < problem.VNS.InitialTour.PathSize  2) && ((DateTime.Now.Ticks  startTime) < maxRuntime)) {


735  iterationCounter++;


736 


737  // Generate a random tour in the kth neighborhood


738  if ((iterationCounter  iterationOfLastFinding) > 1000) {


739  // Create the next preference vector for shaking


740  if (problem.ScoreCount == 2) {


741  double temp = problem.MTR.NextDouble() / 1000.0;


742  if (increasingPreference) {


743  preferences[0] += temp;


744  if (preferences[0] >= 1.0) {


745  preferences[0] = 1.0;


746  increasingPreference = false;


747  }


748  preferences[1] = 1.0  preferences[0];


749  } else {


750  preferences[1] += temp;


751  if (preferences[1] >= 1.0) {


752  preferences[1] = 1.0;


753  increasingPreference = true;


754  }


755  preferences[0] = 1.0  preferences[1];


756  }


757  }


758  }


759 


760  // Shake forcing one of the scores


761  ShakeTour(problem, neighborhoodCounter, preferences);


762 


763  // Bring the tour back to be feasible


764  CleanupTour(problem);


765 


766  // Bring this tour to a local optimum


767  OptimizePath(problem, problem.VNS.ActualTour);


768 


769 


770  for (int i = 0; i < problem.ScoreCount; i++)


771  scores.Rows["Score " + i].Values.Add(problem.VNS.ActualTour.Scores[i]);


772 


773  // Save the tour if it is pareto dominant


774  if (SaveDominantToursVns(problem, problem.VNS.ActualTour, startTime)) {


775  // Move to the better solution and return to the nearest neighborhood


776  problem.VNS.InitialTour = new TourData(problem.VNS.ActualTour);


777  iterationOfLastFinding = iterationCounter;


778  neighborhoodCounter = 0;


779  } else if ((iterationCounter  iterationOfLastAcception) >= problem.VNS.AcceptFrequency) {


780  // Sometimes accept a solution that is not more than a given ratio below


781  // any of the dominant solutions found so far


782  bool allow = true;


783  int tourMax = problem.VNS.DominantTours.Count;


784  for (int tourCounter = 0; tourCounter < tourMax; tourCounter++) {


785  for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


786  if ((problem.VNS.DominantTours[tourCounter].Scores[scoreCounter] * problem.VNS.TresholdValue) > problem.VNS.ActualTour.Scores[scoreCounter]) {


787  allow = false;


788  break;


789  }


790  }


791  if (!allow) break;


792  }


793  if (allow) {


794  // Move to the worse solution and return to the nearest neighborhood


795  problem.VNS.InitialTour = new TourData(problem.VNS.ActualTour);


796  iterationOfLastAcception = iterationCounter;


797  neighborhoodCounter = 0;


798  }


799  }


800 


801  // Increase the neighborhood to search


802  neighborhoodCounter++;


803  }


804  }


805 


806  Console.WriteLine("Time Of Adding of Best Tour: {0}", problem.VNS.DominantTours[0].TimeOfAdding.TotalSeconds);


807  //printf("DEBUG: iteration_counter = %d\n", iteration_counter);


808  }


809 


810  private static void GenerateGreedyTour(ProblemData problem) {


811  int constraintCounter;


812  double maxDistance = 0.0;


813  var feasiblePoints = new List<FeasiblePointVns>();


814 


815  // Find the maximum tour length


816  for (constraintCounter = 0; constraintCounter < problem.ConstraintCount; constraintCounter++) {


817  if ((problem.Constraints[constraintCounter].Type == Constraint.Upperbound) && (problem.Constraints[constraintCounter].Target == ConstraintTimeDistance)) {


818  maxDistance = problem.Constraints[constraintCounter].TargetValue;


819  break;


820  }


821  }


822 


823  int numberFeasiblePoints = 0;


824  // Find all points within the maximum distance allowed (ellipse)


825  for (int pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {


826  double distance = problem.Edges[problem.StartingPoint][pointCounter].Distance + problem.Edges[pointCounter][problem.TerminusPoint].Distance + problem.FixedPenalty;


827  // DEBUG


828  //printf("Distance = %.9f, max_dist = %.9f\n", distance, max_distance);


829  //if ((distance <= max_distance) && (point_counter != Problem.Starting_Point) && (point_counter != Problem.Terminus_Point))


830  if (((maxDistance  distance) >= PrecisionUsed) && (pointCounter != problem.StartingPoint) && (pointCounter != problem.TerminusPoint)) {


831  var tempPoint = new FeasiblePointVns {


832  Distance = distance,


833  Index = pointCounter,


834  Scores = new List<int>(problem.Points[pointCounter].Score)


835  };


836 


837  // Insert the point at the corresponding position


838  int sortMax = feasiblePoints.Count;


839  int sortCounter;


840  for (sortCounter = 0; sortCounter < sortMax; sortCounter++) {


841  int totalScoreNew = 0;


842  int totalScoreOld = 0;


843  for (int counterScores = 0; counterScores < problem.ScoreCount; counterScores++) {


844  totalScoreNew += feasiblePoints[sortCounter].Scores[counterScores];


845  totalScoreOld += tempPoint.Scores[counterScores];


846  }


847  if (totalScoreNew < totalScoreOld) {


848  feasiblePoints.Insert(sortCounter, tempPoint);


849  numberFeasiblePoints++;


850  distance = 1.0;


851  break;


852  }


853  }


854 


855  // If the point was not yet inserted, append it


856  if (distance > 0) {


857  feasiblePoints.Add(tempPoint);


858  numberFeasiblePoints++;


859  }


860  }


861  }


862 


863  // Add the starting and terminus point


864  problem.VNS.InitialTour.Path = new List<int> {


865  problem.StartingPoint,


866  problem.TerminusPoint


867  };


868  problem.VNS.InitialTour.PathSize = 2;


869  problem.VNS.InitialTour.Length = CalcLength(problem, problem.VNS.InitialTour.Path);


870  problem.VNS.InitialTour.Scores = new List<int>(Enumerable.Repeat(0, problem.ScoreCount));


871 


872  // Add points in a greedy way


873  bool insertionPerformed = true;


874  while (insertionPerformed) {


875  insertionPerformed = false;


876 


877  for (int pointCounter = 0; pointCounter < feasiblePoints.Count; pointCounter++) {


878  for (int positionCounter = 1; positionCounter < problem.VNS.InitialTour.Path.Count; positionCounter++) {


879  // Create the candidate tour


880  TourData tempTour = new TourData(problem.VNS.InitialTour);


881  tempTour.Path.Insert(positionCounter, feasiblePoints[pointCounter].Index);


882  tempTour.Length = CalcLength(problem, tempTour.Path);


883 


884  // If the insertion would be feasible, perform it


885  if ((maxDistance  tempTour.Length) >= PrecisionUsed) {//(Temp_Tour.Length <= max_distance)


886  problem.VNS.InitialTour.Length = tempTour.Length;


887  problem.VNS.InitialTour.Path = new List<int>(tempTour.Path);


888  problem.VNS.InitialTour.PathSize++;


889  for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


890  problem.VNS.InitialTour.Scores[scoreCounter] += feasiblePoints[pointCounter].Scores[scoreCounter];


891  }


892  feasiblePoints.RemoveAt(pointCounter);


893  insertionPerformed = true;


894  break;


895  }


896  }


897  if (insertionPerformed) break;


898  }


899  }


900  }


901 


902  private static void ShakeTour(ProblemData problem, int maxNeighborhood, List<double> preferences) {


903  var visitablePoints = new List<int>();


904 


905  // Limit the neighborhood to the tour length


906  int limit = problem.VNS.InitialTour.PathSize  3;


907  int neighborhood = problem.MTR.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;


908 


909  // Determine the maximum travelling distance


910  double maxDistance = problem.Constraints[0].TargetValue;


911 


912  // Elect the starting index of the part to be replaced


913  int tourSize = problem.VNS.InitialTour.PathSize;


914  int randomPosition = problem.MTR.Next(tourSize  neighborhood  2) + 1;


915 


916  // Initialize the new tour


917  problem.VNS.ActualTour = new TourData {


918  Length = 0.0,


919  Path = new List<int> { problem.StartingPoint },


920  PathSize = 1,


921  Scores = new List<int>(Enumerable.Repeat(0, problem.ScoreCount))


922  };


923 


924  // Find all points that are not yet included in the tour and are


925  // within the maximum distance allowed (ellipse) and sort them with


926  // regard to their utility


927  visitablePoints.Clear();


928  int numberVisitablePoints = 0;


929  int pathSize = problem.VNS.ActualTour.PathSize;


930  for (int pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {


931  // Calculate the distance when going from the starting


932  // point to this point and then to the end point


933  double distance = problem.Edges[problem.StartingPoint][pointCounter].Distance + problem.Edges[pointCounter][problem.TerminusPoint].Distance + problem.FixedPenalty;


934 


935  // If this distance is feasible and the point is


936  // neither starting nor ending point, check the point


937  if (((maxDistance  distance) >= PrecisionUsed) && (pointCounter != problem.StartingPoint) && (pointCounter != problem.TerminusPoint)) {


938  bool alreadyVisited = false;


939  int tourPointCounter;


940  for (tourPointCounter = 0; tourPointCounter < tourSize; tourPointCounter++) {


941  // Check if the point is included in the initial tour


942  if (pointCounter == problem.VNS.InitialTour.Path[tourPointCounter]) {


943  alreadyVisited = true;


944  break;


945  }


946  }


947 


948  // The point was not yet visited, so add it to the candidate list


949  if (!alreadyVisited) {


950  double utilityPoint = 0;


951  bool inserted = false;


952 


953  // Calculate the current point's utility


954  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


955  utilityPoint += problem.Points[pointCounter].Score[counterScore] * preferences[counterScore];


956  }


957 


958  // Add the point at the right position according to its utility (increasing)


959  for (int counterPosition = 0; counterPosition < numberVisitablePoints; counterPosition++) {


960  // Calculate the utility of the point at this position


961  double utilityPosition = 0;


962  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


963  utilityPosition += problem.Points[visitablePoints[counterPosition]].Score[counterScore] * preferences[counterScore];


964  }


965 


966  // If the utility of the point is lower, insert it here


967  if (utilityPosition > utilityPoint) {


968  visitablePoints.Insert(counterPosition, pointCounter);


969  inserted = true;


970  break;


971  }


972  }


973 


974  // If no bigger utility exists up to now, add the point at the end


975  if (!inserted) {


976  visitablePoints.Add(pointCounter);


977  }


978  numberVisitablePoints++;


979  }


980  }


981  }


982 


983  // Perform the insertions according to the utility sorting


984  for (int position = 1; position < tourSize; position++) {


985  int scoreCounter;


986  if ((position < randomPosition)  (position > (randomPosition + neighborhood  1))) {


987  // Add the waypoints to the new solution


988  problem.VNS.ActualTour.Path.Add(problem.VNS.InitialTour.Path[position]);


989  problem.VNS.ActualTour.PathSize++;


990  problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);


991  for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


992  problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[problem.VNS.InitialTour.Path[position]].Score[scoreCounter];


993  }


994 


995  // Delete this point from the candidate list


996  for (int pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {


997  if (problem.VNS.InitialTour.Path[position] == visitablePoints[pointCounter]) {


998  visitablePoints.RemoveAt(pointCounter);


999  numberVisitablePoints;


1000  break;


1001  }


1002  }


1003  } else {


1004  if (numberVisitablePoints > 0) {


1005  // Add the point with the highest utility from the candidate list


1006  int randomFactor = problem.MTR.Next(3);


1007  int insertionIndex = numberVisitablePoints  1;


1008  if (numberVisitablePoints > 4) insertionIndex = randomFactor;


1009  problem.VNS.ActualTour.Path.Add(visitablePoints[insertionIndex]); //[number_visitable_points  1]);


1010  problem.VNS.ActualTour.PathSize++;


1011  problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);


1012  for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


1013  //Problem.VNS.Actual_Tour.Scores[score_counter] += Problem.Points[visitable_points[number_visitable_points  1]].Score[score_counter];


1014  problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[visitablePoints[insertionIndex]].Score[scoreCounter];


1015  }


1016  //visitable_points.pop_back();


1017  visitablePoints.RemoveAt(insertionIndex);


1018  numberVisitablePoints;


1019  } else {


1020  // We don't have any points left that could be inserted so we can only reinsert


1021  // the removed and not already reinserted points in a random order


1022  for (int reinsertCounter = randomPosition; reinsertCounter < (randomPosition + neighborhood); reinsertCounter++) {


1023  bool alreadyReinserted = false;


1024  for (int checkCounter = 0; checkCounter < problem.VNS.ActualTour.PathSize; checkCounter++) {


1025  if (problem.VNS.InitialTour.Path[reinsertCounter] == problem.VNS.ActualTour.Path[checkCounter]) {


1026  alreadyReinserted = true;


1027  break;


1028  }


1029  }


1030  if (!alreadyReinserted) {


1031  visitablePoints.Add(problem.VNS.InitialTour.Path[reinsertCounter]);


1032  numberVisitablePoints++;


1033  }


1034  }


1035 


1036  int randomIndex = problem.MTR.Next(numberVisitablePoints  1);


1037  problem.VNS.ActualTour.Path.Add(visitablePoints[randomIndex]);


1038  problem.VNS.ActualTour.PathSize++;


1039  problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);


1040  for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


1041  problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[visitablePoints[randomIndex]].Score[scoreCounter];


1042  }


1043  visitablePoints.Clear();


1044  numberVisitablePoints = 0;


1045  }


1046  }


1047  }


1048  }


1049 


1050  private static void CleanupTour(ProblemData problem) {


1051  int tourPointCounter, sortCounter;


1052  var distanceSavingsList = new List<double>();


1053  var sortedPoints = new List<int>();


1054 


1055  // Find the maximum distance restriction


1056  double maxLength = problem.Constraints[0].TargetValue;


1057 


1058  distanceSavingsList.Clear();


1059  sortedPoints.Clear();


1060 


1061  // Sort the points on the tour according to their average score


1062  int tourPointMax = problem.VNS.ActualTour.PathSize  1;


1063  for (tourPointCounter = 1; tourPointCounter < tourPointMax; tourPointCounter++) {


1064  var tempPath = new List<int>();


1065 


1066  double distanceSaving = problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter  1]][problem.VNS.ActualTour.Path[tourPointCounter]].Distance;


1067  distanceSaving += problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter]][problem.VNS.ActualTour.Path[tourPointCounter + 1]].Distance;


1068  distanceSaving = problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter  1]][problem.VNS.ActualTour.Path[tourPointCounter + 1]].Distance;


1069 


1070  bool inserted = false;


1071  int sortMax = sortedPoints.Count;


1072  for (sortCounter = 0; sortCounter < sortMax; sortCounter++) {


1073  if (distanceSaving > distanceSavingsList[sortCounter]) {


1074  distanceSavingsList.Insert(sortCounter, distanceSaving);


1075  sortedPoints.Insert(sortCounter, tourPointCounter);


1076  inserted = true;


1077  break;


1078  }


1079  }


1080  if (!inserted) {


1081  distanceSavingsList.Add(distanceSaving);


1082  sortedPoints.Add(tourPointCounter);


1083  }


1084  }


1085 


1086  // As long as the created path is infeasible, remove elements


1087  while ((problem.VNS.ActualTour.Length  maxLength) >= PrecisionUsed) { //(Problem.VNS.Actual_Tour.Length > max_length)


1088  // Remove the point that frees the largest distance


1089  int scoreCounter;


1090  for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


1091  problem.VNS.ActualTour.Scores[scoreCounter] = problem.Points[problem.VNS.ActualTour.Path[sortedPoints[0]]].Score[scoreCounter];


1092  }


1093  problem.VNS.ActualTour.Path.RemoveAt(sortedPoints[0]);


1094  problem.VNS.ActualTour.PathSize;


1095  problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);


1096  int sortMax = sortedPoints.Count;


1097  for (sortCounter = 1; sortCounter < sortMax; sortCounter++) {


1098  if (sortedPoints[sortCounter] > sortedPoints[0]) {


1099  sortedPoints[sortCounter];


1100  }


1101  }


1102  sortedPoints.RemoveAt(0);


1103  distanceSavingsList.RemoveAt(0);


1104  }


1105  }


1106 


1107  private static bool SaveDominantToursVns(ProblemData problem, TourData tour, long startTime) {


1108  int tourCounter;


1109 


1110  bool processed = false;


1111  int tourCounterMax = problem.VNS.DominantTours.Count  1;


1112 


1113  for (tourCounter = tourCounterMax; tourCounter >= 0; tourCounter) {


1114  bool scoreGt = false;


1115  bool scoreLt = false;


1116  int scoreCounter = 0;


1117  for (scoreCounter = (problem.ScoreCount  1); scoreCounter >= 0; scoreCounter) {


1118  if (tour.Scores[scoreCounter] > problem.VNS.DominantTours[tourCounter].Scores[scoreCounter]) {


1119  scoreGt = true;


1120  } else if (tour.Scores[scoreCounter] < problem.VNS.DominantTours[tourCounter].Scores[scoreCounter]) {


1121  scoreLt = true;


1122  }


1123  }


1124 


1125  // If this tour equals an already existing one, skip it


1126  if (tour.Path == problem.VNS.DominantTours[tourCounter].Path) {


1127  processed = true;


1128  break;


1129  }


1130 


1131  // If the tour is dominated by an existing, skip it


1132  if (scoreLt && !scoreGt) {


1133  processed = true;


1134  break;


1135  }


1136 


1137  // If the tour dominates an existing one, eliminate the existing one


1138  if (!scoreLt && scoreGt) {


1139  problem.VNS.DominantTours.RemoveRange(tourCounter, 1);


1140  tourCounterMax;


1141  }


1142  }


1143  if (!processed) {


1144  // The tour either dominates an existing one or is just not dominated


1145  // by an existing tour, so we assume it to be dominant


1146  tour.TimeOfAdding = CalculateDifference(startTime, DateTime.Now.Ticks);


1147  problem.VNS.DominantTours.Add(tour);


1148  return true;


1149  } else {


1150  return false;


1151  }


1152  }


1153 


1154  #endregion


1155 


1156  #region Optimization


1157 


1158  private static void ShortenPath(ProblemData problem, TourData tour) {


1159  bool optimizationDone = true;


1160  int pathSize = tour.PathSize;


1161  int maxBlockLength = (pathSize > 31) ? 30 : (pathSize  2);


1162 


1163  // DEBUG


1164  //printf("Shorten:");


1165 


1166  // Perform a 2opt


1167  while (optimizationDone) {


1168  optimizationDone = false;


1169 


1170  int blockLength;


1171  for (blockLength = 2; blockLength < maxBlockLength; blockLength++) { //(path_size  1); ++block_length)


1172  // If an optimization has been done, start from the beginning


1173  if (optimizationDone) break;


1174 


1175  // DEBUG


1176  //printf("\tBlock length = %d, Max block length = %d.\n", block_length, max_block_length);


1177 


1178  int position;


1179  for (position = 1; position < (pathSize  blockLength); position++) {


1180  // If an optimization has been done, start from the beginning


1181  if (optimizationDone) break;


1182 


1183  // DEBUG


1184  //printf("\t\tPosition = %d, Path size = %d.\n", position, path_size);


1185 


1186  double newLength = tour.Length;


1187  for (int counterLength = (position  1); counterLength < (position + blockLength); counterLength++) {


1188  newLength = problem.Edges[tour.Path[counterLength]][tour.Path[counterLength + 1]].Distance;


1189  }


1190  for (int counterLength = (position + blockLength  1); counterLength > (position); counterLength) {


1191  newLength += problem.Edges[tour.Path[counterLength]][tour.Path[counterLength  1]].Distance;


1192  }


1193  newLength += problem.Edges[tour.Path[position  1]][tour.Path[position + blockLength  1]].Distance;


1194  newLength += problem.Edges[tour.Path[position]][tour.Path[position + blockLength]].Distance;


1195 


1196 


1197  if (newLength <= (tour.Length  0.00001)) { // Avoid cycling caused by precision


1198  var parthPath = tour.Path.GetRange(position, blockLength);


1199 


1200  tour.Path.RemoveRange(position, blockLength);


1201  tour.Path.InsertRange(position, parthPath.AsEnumerable().Reverse());


1202 


1203  tour.Length = CalcLength(problem, tour.Path);


1204 


1205  // Rerun the optimization


1206  optimizationDone = true;


1207  }


1208  }


1209  }


1210  }


1211  // DEBUG


1212  //printf("Shorten done.\n");


1213  }


1214 


1215  private static void OptimizePath(ProblemData problem, TourData tour, int optimizationPreference = 1) {


1216  bool optimizationDone = true;


1217  int acceptNonParetoExchange = 0;


1218  bool isFeasible = true;


1219  var visitablePoints = new List<int>();


1220 


1221  // Find the maximum distance restriction


1222  double maxLength = problem.Constraints[0].TargetValue;


1223 


1224  // Check if the tour can be improved by adding or replacing points


1225  while (optimizationDone) {


1226  optimizationDone = false;


1227 


1228  // Try to shorten the path


1229  ShortenPath(problem, tour);


1230 


1231  // Determine the number of points visited so far


1232  int tourSize = tour.PathSize; //, constraint_counter;


1233 


1234  // Determine all points that have not yet been visited by this tour


1235  visitablePoints.Clear();


1236  int numberVisitablePoints = 0; //, constraint_counter;


1237  int tourPointCounter; //, constraint_counter;


1238  int pointCounter; //, constraint_counter;


1239  for (pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {


1240  bool alreadyVisited = false;


1241  for (tourPointCounter = 0; tourPointCounter < tourSize; tourPointCounter++) {


1242  if (pointCounter == tour.Path[tourPointCounter]) {


1243  alreadyVisited = true;


1244  break;


1245  }


1246  }


1247  if (!alreadyVisited) {


1248  visitablePoints.Add(pointCounter);


1249  numberVisitablePoints++;


1250  }


1251  }


1252 


1253  // Determine if any of the visitable points can be included at any


1254  // position within the tour


1255  int scoreCounter; //, constraint_counter;


1256  for (tourPointCounter = 1; tourPointCounter < tourSize; tourPointCounter++) {


1257  // If an optimization has been done, start from the beginning


1258  if (optimizationDone) break;


1259 


1260  for (pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {


1261  // If an optimization has been done, start from the beginning


1262  if (optimizationDone) break;


1263 


1264  double newLength = tour.Length;


1265  newLength = problem.Edges[tour.Path[tourPointCounter  1]][tour.Path[tourPointCounter]].Distance;


1266  newLength += problem.Edges[tour.Path[tourPointCounter  1]][visitablePoints[pointCounter]].Distance;


1267  newLength += problem.Edges[visitablePoints[pointCounter]][tour.Path[tourPointCounter]].Distance;


1268  newLength += problem.FixedPenalty;


1269 


1270  // Determine if including the point does not violate any constraint


1271  if (newLength <= maxLength) {


1272  // We do not need to check if the point increases the score  it can only increase!


1273 


1274  // Update the scores achieved by visiting this point


1275  for (scoreCounter = (problem.ScoreCount  1); scoreCounter >= 0; scoreCounter) {


1276  tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];


1277  }


1278 


1279  // Insert the new point at this position


1280  tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);


1281  tour.PathSize++;


1282 


1283  // Update the overall tour length


1284  tour.Length = CalcLength(problem, tour.Path);


1285 


1286  // Rerun this optimization


1287  optimizationDone = true;


1288  }


1289  }


1290  }


1291 


1292  // Determine if any of the visitable points can take the place of an


1293  // already visited point in the tour to improve the scores


1294  for (tourPointCounter = 1; tourPointCounter < (tourSize  1); tourPointCounter++) {


1295  // If an optimization has been done, start from the beginning


1296  if (optimizationDone) break;


1297 


1298  for (pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {


1299  // If an optimization has been done, start from the beginning


1300  if (optimizationDone) break;


1301 


1302  double newLength = tour.Length;


1303  newLength = problem.Edges[tour.Path[tourPointCounter  1]][tour.Path[tourPointCounter]].Distance;


1304  newLength = problem.Edges[tour.Path[tourPointCounter]][tour.Path[tourPointCounter + 1]].Distance;


1305  newLength += problem.Edges[tour.Path[tourPointCounter  1]][visitablePoints[pointCounter]].Distance;


1306  newLength += problem.Edges[visitablePoints[pointCounter]][tour.Path[tourPointCounter + 1]].Distance;


1307 


1308  if (newLength <= maxLength) {


1309  // Check if the point dominated the one it would replace


1310  bool scoreGt = false;


1311  bool scoreLt = false;


1312  if (optimizationPreference == 1) {


1313  for (scoreCounter = (problem.ScoreCount  1); scoreCounter >= 0; scoreCounter) {


1314  if (problem.Points[visitablePoints[pointCounter]].Score[scoreCounter] > problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter])


1315  scoreGt = true;


1316  else if (problem.Points[visitablePoints[pointCounter]].Score[scoreCounter] < problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter])


1317  scoreLt = true;


1318  }


1319  } else {


1320  if (problem.Points[visitablePoints[pointCounter]].Score[optimizationPreference] > problem.Points[tour.Path[tourPointCounter]].Score[optimizationPreference])


1321  scoreGt = true;


1322  else if (problem.Points[visitablePoints[pointCounter]].Score[optimizationPreference] < problem.Points[tour.Path[tourPointCounter]].Score[optimizationPreference])


1323  scoreLt = true;


1324  }


1325 


1326  if (!scoreLt && scoreGt) {


1327  // Update the overall tour length


1328  // Tour.Length = new_length;


1329  // Update the scores achieved by visiting this point


1330  for (scoreCounter = (problem.ScoreCount  1); scoreCounter >= 0; scoreCounter) {


1331  tour.Scores[scoreCounter] = problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter];


1332  tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];


1333  }


1334 


1335  // Replace the old point by the new one


1336  tour.Path.RemoveAt(tourPointCounter);


1337  tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);


1338 


1339  // Update the overall tour length


1340  tour.Length = CalcLength(problem, tour.Path);


1341 


1342  // Rerun this optimization


1343  optimizationDone = true;


1344  }


1345 


1346  // If no dominant exchange could be performed, accept a non dominant exchange


1347  if (scoreGt && (acceptNonParetoExchange > 0) && (acceptNonParetoExchange < 6) && (optimizationPreference == 1)) {


1348  // Update the overall tour length


1349  //Tour.Length = new_length;


1350 


1351  // Update the scores achieved by visiting this point


1352  for (scoreCounter = (problem.ScoreCount  1); scoreCounter >= 0; scoreCounter) {


1353  tour.Scores[scoreCounter] = problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter];


1354  tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];


1355  }


1356 


1357  // Replace the old point by the new one


1358  tour.Path.RemoveAt(tourPointCounter);


1359  tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);


1360 


1361  // Update the overall tour length


1362  tour.Length = CalcLength(problem, tour.Path);


1363 


1364  // Rerun this optimization


1365  optimizationDone = true;


1366  }


1367  }


1368  }


1369  }


1370 


1371  if (!optimizationDone && (acceptNonParetoExchange == 0)) {


1372  // If no optimization has been done, accept non dominant exchanges


1373  // Non dominant exchanges will only be accepted 5 times to prevent infinite loops


1374  optimizationDone = true;


1375  acceptNonParetoExchange++;


1376  } else if (optimizationDone && (acceptNonParetoExchange > 0)) {


1377  // If an optimization has been done, do not accept non dominant exchange


1378  acceptNonParetoExchange++;


1379  }


1380  }


1381  }


1382 


1383  private static double CalcLength(ProblemData problem, List<int> path) {


1384  double length = 0.0;


1385 


1386  for (int pointCounter = 1; pointCounter < path.Count; pointCounter++) {


1387  length += problem.Edges[path[pointCounter  1]][path[pointCounter]].Distance;


1388  }


1389  // Add the fixed penalty for every vertex except for the starting and ending vertex


1390  if (path.Count > 1) {


1391  if (path[path.Count  1] == problem.TerminusPoint) length += ((path.Count()  2.0) * problem.FixedPenalty);


1392  else length += ((path.Count  1.0) * problem.FixedPenalty);


1393  }


1394 


1395  return length;


1396  }


1397 


1398  #endregion


1399 


1400  #region Path Relinking


1401 


1402  private static int PathRelinking(ProblemData problem, List<TourData> tours, long startTime) {


1403  int numberOfToursFound = 0;


1404 


1405  // Sort the tours with regard to their scores


1406  SortTours(tours);


1407 


1408  for (int counterGuidingTour = 1; counterGuidingTour < tours.Count; counterGuidingTour++) {


1409  TourData currentTour = tours[counterGuidingTour  1];


1410  TourData guidingTour = tours[counterGuidingTour];


1411  numberOfToursFound += PathRelinkingStep(0, problem, tours, currentTour, guidingTour, startTime);


1412  }


1413 


1414  return numberOfToursFound;


1415  }


1416 


1417  private static void SortTours(List<TourData> tours) {


1418  int numberTours = tours.Count;


1419 


1420  // Sort the tours with regard to their scores


1421  for (int counterTours = (numberTours  1); counterTours >= 0; counterTours) {


1422  for (int counterSearch = 1; counterSearch <= counterTours; counterSearch++) {


1423  if (tours[counterSearch].Scores[0] < tours[counterSearch  1].Scores[0]) {


1424  tours.Insert(counterSearch  1, tours[counterSearch]);


1425  tours.RemoveAt(counterSearch + 1);


1426  }


1427  }


1428  }


1429  }


1430 


1431  private static int PathRelinkingStep(int level, ProblemData problem, List<TourData> tours, TourData currentTour, TourData guidingTour, long startTime) {


1432  int numberOfToursFound = 0;


1433  List<int> nodesToRemove = new List<int>();


1434  List<int> nodesToInsert = new List<int>();


1435  int numberOfNodesToRemove = FindNodesToRemove(currentTour, guidingTour, nodesToRemove);


1436  int numberOfNodesToInsert = FindNodesToInsert(currentTour, guidingTour, nodesToInsert);


1437 


1438  // If no other transformations are possible without reaching the guiding solution, return


1439  if ((numberOfNodesToRemove <= 1) && (numberOfNodesToInsert <= 1)) {


1440  return 0;


1441  }


1442 


1443  if (numberOfNodesToRemove != 0 && numberOfNodesToInsert != 0) {


1444  // If too many combinations can be performed on this layer, draw one randomly


1445  if ((numberOfNodesToRemove * numberOfNodesToInsert) < 16) {


1446  // Nodes for removing and inserting are available


1447  for (int counterRemove = 0; counterRemove < numberOfNodesToRemove; counterRemove++) {


1448  for (int counterInsert = 0; counterInsert < numberOfNodesToInsert; counterInsert++) {


1449  // Make a working copy of the current tour


1450  TourData candidateTour = new TourData(currentTour);


1451 


1452  // Perform the transformation step


1453  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


1454  candidateTour.Scores[counterScore] = problem.Points[candidateTour.Path[nodesToRemove[counterRemove]]].Score[counterScore];


1455  candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[counterInsert]]].Score[counterScore];


1456  }


1457  candidateTour.Path.RemoveAt(nodesToRemove[counterRemove]);


1458  candidateTour.Path.Insert(nodesToRemove[counterRemove], guidingTour.Path[nodesToInsert[counterInsert]]);


1459  candidateTour.Length = CalcLength(problem, candidateTour.Path);


1460 


1461  // Locally optimize the modified tour


1462  TourData tempTour = new TourData(candidateTour);


1463  OptimizePath(problem, tempTour);


1464 


1465  // If the tour is efficient, save it and increase the number of tours found


1466  if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;


1467 


1468  // Recursively perform all remaining steps after this one


1469  if ((numberOfNodesToRemove > 1)  (numberOfNodesToInsert > 1)) {


1470  numberOfToursFound += PathRelinkingStep((level + 1), problem, tours, candidateTour, guidingTour, startTime);


1471  }


1472  }


1473  }


1474  } else {


1475  // Draw one combination randomly


1476  int nodeToRemove = problem.MTR.Next(numberOfNodesToRemove  1);


1477  int nodeToInsert = problem.MTR.Next(numberOfNodesToInsert  1);


1478 


1479  // Make a working copy of the current tour


1480  TourData candidateTour = currentTour;


1481 


1482  // Perform the transformation step


1483  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


1484  candidateTour.Scores[counterScore] = problem.Points[candidateTour.Path[nodesToRemove[nodeToRemove]]].Score[counterScore];


1485  candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[nodeToInsert]]].Score[counterScore];


1486  }


1487  candidateTour.Path.RemoveAt(nodesToRemove[nodeToRemove]);


1488  candidateTour.Path.Insert(nodesToRemove[nodeToRemove], guidingTour.Path[nodesToInsert[nodeToInsert]]);


1489  candidateTour.Length = CalcLength(problem, candidateTour.Path);


1490 


1491  // Locally optimize the modified tour


1492  TourData tempTour = new TourData(candidateTour);


1493  OptimizePath(problem, tempTour);


1494 


1495  // If the tour is efficient, save it and increase the number of tours found


1496  if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;


1497 


1498  // Recursively perform all remaining steps after this one


1499  if ((numberOfNodesToRemove > 1)  (numberOfNodesToInsert > 1)) {


1500  numberOfToursFound += PathRelinkingStep((level + 1), problem, tours, candidateTour, guidingTour, startTime);


1501  }


1502  }


1503  } else if (numberOfNodesToRemove != 0) {


1504  // Only removing nodes is possible


1505  for (int counter_remove = 0; counter_remove < numberOfNodesToRemove; counter_remove++) {


1506  // Make a working copy of the current tour


1507  TourData candidateTour = new TourData(currentTour);


1508 


1509  // Perform the transformation step


1510  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


1511  candidateTour.Scores[counterScore] = problem.Points[candidateTour.Path[nodesToRemove[counter_remove]]].Score[counterScore];


1512  }


1513  candidateTour.Path.RemoveAt(nodesToRemove[counter_remove]);


1514  candidateTour.PathSize;


1515  candidateTour.Length = CalcLength(problem, currentTour.Path);


1516 


1517  // Locally optimize the modified tour


1518  TourData tempTour = new TourData(candidateTour);


1519  OptimizePath(problem, tempTour);


1520 


1521  // If the tour is efficient, save it and increase the number of tours found


1522  if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;


1523  }


1524  } else if (numberOfNodesToInsert != 0) {


1525  // Only inserting nodes is possible


1526  for (int counterInsert = 0; counterInsert < numberOfNodesToInsert; counterInsert++) {


1527  // Make a working copy of the current tour


1528  TourData candidateTour = new TourData(currentTour);


1529 


1530  // Perform the transformation step


1531  for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {


1532  candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[counterInsert]]].Score[counterScore];


1533  }


1534  candidateTour.Path.Insert((candidateTour.PathSize / 2), guidingTour.Path[nodesToInsert[counterInsert]]);


1535  candidateTour.PathSize++;


1536  candidateTour.Length = CalcLength(problem, candidateTour.Path);


1537 


1538  // Locally optimize the modified tour


1539  TourData tempTour = new TourData(candidateTour);


1540  OptimizePath(problem, tempTour);


1541 


1542  // If the tour is efficient, save it and increase the number of tours found


1543  if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;


1544  }


1545  }


1546 


1547  return numberOfToursFound;


1548  }


1549 


1550  private static int FindNodesToRemove(TourData currentTour, TourData guidingTour, List<int> nodesToRemove) {


1551  // Find all node to remove from the current tour


1552  for (int counterNodes = 1; counterNodes < currentTour.PathSize; counterNodes++) {


1553  bool nodeFound = false;


1554  for (int counterSearch = 1; counterSearch < guidingTour.PathSize; counterSearch++) {


1555  if (guidingTour.Path[counterSearch] == currentTour.Path[counterNodes]) {


1556  nodeFound = true;


1557  break;


1558  }


1559  }


1560  if (!nodeFound) {


1561  // Remember the position of the node that has to be removed


1562  nodesToRemove.Add(counterNodes);


1563  }


1564  }


1565  return nodesToRemove.Count;


1566  }


1567 


1568  private static int FindNodesToInsert(TourData currentTour, TourData guidingTour, List<int> nodesToInsert) {


1569  // Find all node to insert into the current tour


1570  for (int counterNodes = 1; counterNodes < guidingTour.PathSize; counterNodes++) {


1571  bool nodeFound = false;


1572  for (int counterSearch = 1; counterSearch < currentTour.PathSize; counterSearch++) {


1573  if (currentTour.Path[counterSearch] == guidingTour.Path[counterNodes]) {


1574  nodeFound = true;


1575  break;


1576  }


1577  }


1578  if (!nodeFound) {


1579  // Remember the position of the node that has to be removed


1580  nodesToInsert.Add(counterNodes);


1581  }


1582  }


1583  return nodesToInsert.Count;


1584  }


1585 


1586  private static bool SaveCandidateTour(ProblemData problem, List<TourData> tours, TourData candidateTour, long startTime) {


1587  bool candidateSaved = false;


1588 


1589  if (candidateTour.Length <= problem.Constraints[0].TargetValue) {


1590  bool processed = false;


1591  int tourCounterMax = tours.Count  1;


1592  for (int tourCounter = tourCounterMax; tourCounter >= 0; tourCounter) {


1593  bool scoreGt = false;


1594  bool scoreLt = false;


1595  for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {


1596  if (candidateTour.Scores[scoreCounter] > tours[tourCounter].Scores[scoreCounter]) {


1597  scoreGt = true;


1598  } else if (candidateTour.Scores[scoreCounter] < tours[tourCounter].Scores[scoreCounter]) {


1599  scoreLt = true;


1600  }


1601  }


1602 


1603  // If this tour equals an already existing one, skip it


1604  if (candidateTour.Path == tours[tourCounter].Path) {


1605  processed = true;


1606  break;


1607  }


1608 


1609  // If the tour is dominated by an existing, skip it


1610  if (scoreLt && !scoreGt) {


1611  processed = true;


1612  break;


1613  }


1614 


1615  // If the tour yields the same scores as an existing one, skip it


1616  if (!scoreLt && !scoreGt) {


1617  processed = true;


1618  break;


1619  }


1620 


1621  // If the tour dominates an existing one, eliminate the existing one


1622  if (!scoreLt && scoreGt) {


1623  tours.RemoveAt(tourCounter);


1624  }


1625  }


1626  if (!processed) {


1627  // The tour is neither dominated by an existing one nor does it


1628  // dominate an existing tour, so we assume it to be dominant


1629  candidateTour.TimeOfAdding = CalculateDifference(startTime, DateTime.Now.Ticks);


1630  tours.Add(candidateTour);


1631  candidateSaved = true;


1632  }


1633  }


1634  return candidateSaved;


1635  }


1636 


1637  #endregion


1638 


1639  #region Helper


1640  private static TimeSpan CalculateDifference(long startValue, long endValue) {


1641  return TimeSpan.FromTicks(endValue  startValue);


1642  }


1643 


1644  #endregion


1645  }


1646 


1647  #region Data Structures


1648 


1649  public class FeasiblePointVns {


1650  public int Index;


1651  public double Distance;


1652  public List<int> Scores;


1653  }


1654 


1655  public enum Constraint {


1656  Upperbound = 0,


1657  Lowerbound = 1,


1658  Maximize = 2,


1659  Minimize = 3


1660  }


1661 


1662  public class ConstraintData {


1663  public Constraint Type; // 0...upper bound


1664  // 1...lower bound


1665  // 2...maximize


1666  // 3...minimize


1667  public int Target; // Which score is affected by


1668  // this constraint:


1669  // 0...Time/Distance


1670  // #...number of the score


1671  public double TargetValue; // The value that should


1672  // (not) be reached


1673  }


1674 


1675  public class PointData {


1676  public double PositionX; // XPosition of the point


1677  public double PositionY; // YPosition of the point


1678 


1679  public List<int> Score; // List of scores for this point


1680  public List<int> Neighbors; // List of all points in the neighborhood


1681  }


1682 


1683  public class EdgeData {


1684  public double Distance; // Length of this edge


1685 


1686  //vector<double> Pheromone; // List of pheromones deposited


1687  // on this edge


1688  }


1689 


1690  public class TourData {


1691  public TourData() { }


1692  public TourData(TourData other) {


1693  Length = other.Length;


1694  PathSize = other.PathSize;


1695  Scores = new List<int>(other.Scores);


1696  Path = new List<int>(other.Path);


1697  TimeOfAdding = other.TimeOfAdding;


1698  }


1699 


1700  public double Length; // Length of this tour


1701  public int PathSize;


1702 


1703  public List<int> Scores; // Scores achieved by this tour


1704  public List<int> Path; // Indices of the vertices visited by this tour


1705  public TimeSpan TimeOfAdding; // Time at which the solution was added


1706  }


1707 


1708  public class VnsData {


1709  public int NumberOfIterations; // Number of iterations to run


1710  public int AcceptFrequency; // How often "bad" solutions will be accepted


1711  public double TresholdValue; // Ratio that allows the system to accept


1712  // Solutions that are not dominant but do


1713  // not differ more than this from the actual


1714  // solution


1715  public TourData InitialTour; // Initially created solution tour


1716  public TourData ActualTour; // Actually created neighborhood tour


1717 


1718  public List<TourData> DominantTours; // List containing all dominant tours


1719  }


1720 


1721  public class ProblemData {


1722  public int StartingPoint; // Index of the starting point


1723  public int TerminusPoint; // Index of the ending point


1724  public int ConstraintCount; // Number of constraints


1725  public int ScoreCount; // Number of scores in the problem


1726  public int PointCount; // Number of points in the problem


1727  public bool MatrixGiven; // true if the distance matrix is given


1728 


1729  public List<ConstraintData> Constraints; // List of constraints


1730  public List<PointData> Points; // List of points


1731  public List<List<EdgeData>> Edges; // List of all edges (First index = origin, second index = target)


1732 


1733  public MersenneTwister MTR; // Mersenne Twister PRNG


1734 


1735  //ACO_Data ACO; // All data needed by the ACO algorithm


1736  public VnsData VNS; // All data needed by the VNS algorithm


1737  public double FixedPenalty; // User specified penalty for each visited vertex


1738  }


1739 


1740  #endregion


1741  }

