Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11134


Ignore:
Timestamp:
07/08/14 11:24:00 (10 years ago)
Author:
pfleck
Message:

#2208 Added a tightly coupled VNS implementation of Orienteering Problem

Location:
branches/HeuristicLab.Problems.Orienteering
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.Orienteering

    • Property svn:ignore
      •  

        old new  
        2323bin
        2424protoc.exe
         25obj
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/HeuristicLab.Problems.Orienteering-3.3.csproj

    r11132 r11134  
    66    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    77    <ProjectGuid>{D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}</ProjectGuid>
    8     <OutputType>Library</OutputType>
     8    <OutputType>Exe</OutputType>
    99    <AppDesignerFolder>Properties</AppDesignerFolder>
    1010    <RootNamespace>HeuristicLab.Problems.Orienteering</RootNamespace>
     
    3636    <AssemblyOriginatorKeyFile>HeuristicLab.snk</AssemblyOriginatorKeyFile>
    3737  </PropertyGroup>
     38  <PropertyGroup>
     39    <StartupObject />
     40  </PropertyGroup>
    3841  <ItemGroup>
    3942    <Reference Include="System" />
     
    4346    <Compile Include="Program.cs" />
    4447    <Compile Include="Properties\AssemblyInfo.cs" />
     48  </ItemGroup>
     49  <ItemGroup>
     50    <None Include="HeuristicLab.snk" />
    4551    <None Include="Properties\AssemblyInfo.cs.frame" />
    4652  </ItemGroup>
    4753  <ItemGroup>
    48     <None Include="HeuristicLab.snk" />
     54    <ProjectReference Include="..\..\HeuristicLab.Common\3.3\HeuristicLab.Common-3.3.csproj">
     55      <Project>{A9AD58B9-3EF9-4CC1-97E5-8D909039FF5C}</Project>
     56      <Name>HeuristicLab.Common-3.3</Name>
     57      <Private>False</Private>
     58    </ProjectReference>
     59    <ProjectReference Include="..\..\HeuristicLab.Core\3.3\HeuristicLab.Core-3.3.csproj">
     60      <Project>{C36BD924-A541-4A00-AFA8-41701378DDC5}</Project>
     61      <Name>HeuristicLab.Core-3.3</Name>
     62      <Private>False</Private>
     63    </ProjectReference>
     64    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
     65      <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
     66      <Name>HeuristicLab.Random-3.3</Name>
     67      <Private>False</Private>
     68    </ProjectReference>
    4969  </ItemGroup>
    5070  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Program.cs

    r11132 r11134  
    1 namespace HeuristicLab.Problems.Orienteering {
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2014 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
     22using System;
     23using System.Collections.Generic;
     24using System.Globalization;
     25using System.IO;
     26using System.Linq;
     27using System.Threading;
     28using HeuristicLab.Random;
     29
     30namespace HeuristicLab.Problems.Orienteering {
     31
     32  /*
     33   * Based on
     34   * Implementation of an Pareto Ant Colony
     35   * Optimization (PACO) metaheuristic and a
     36   * Pareto Variable Neighborhood Search (PVNS)
     37   * metaheuristic for the Multi-Objective
     38   * Orienteering Problem (MOP)
     39   * Copyright: © 2007 by Michael Schilde
     40   *
     41   * See Metaheuristics for the bi-objective orienteering problem
     42   * http://link.springer.com/article/10.1007/s11721-009-0029-5
     43   * Michael Schilde, Karl F. Doerner, Richard F. Hartl, Guenter Kiechle
     44   */
    245  public class Program {
     46    #region Constants
     47
     48    private const bool ShowStatus = true;
     49
     50    private const double PrecisionUsed = 0.0000001;
     51
     52    private const string VersionRequired = "*tpv1.1* or *tpv1.0*";
     53
     54    private const int ConstraintTimeDistance = -1;
     55
     56    public enum ErrorCode {
     57      ErrorNone = 0,
     58      ErrorOpenInputFile = 10,
     59      ErrorOpenOutputFile = 11,
     60      ErrorConvertToLower = 12,
     61      ErrorRemovingWhitespace = 13,
     62      ErrorWrongVersion = 14,
     63      ErrorReadingData = 20,
     64      ErrorInvalidDefinitionN = 30,
     65      ErrorInvalidDefinitionC = 31,
     66      ErrorInvalidDefinitionU = 32,
     67      ErrorInvalidDefinitionL = 33,
     68      ErrorInvalidDefinitionX = 34,
     69      ErrorInvalidDefinitionI = 35,
     70      ErrorInvalidDefinitionP = 36,
     71      ErrorInvalidDefinitionS = 37,
     72      ErrorInvalidDefinitionB = 38,
     73      ErrorInvalidDefinitionE = 39,
     74      ErrorInvalidDefinitionD = 40,
     75      ErrorInvalidDefinitionM = 41,
     76      ErrorMissingStartingPoint = 50,
     77      ErrorMissingTerminusPoint = 51,
     78      ErrorTooFewConstraints = 63,
     79      ErrorTooFewPoints = 64,
     80      ErrorTooFewScores = 65,
     81      ErrorTooManyConstraints = 66,
     82      ErrorTooManyPoints = 67,
     83      ErrorTooManyScores = 68
     84    }
     85
     86    #endregion
     87
     88    #region Fields
     89    private static TimeSpan avgTimeDurationVns;
     90    private static List<TimeSpan> timeDurationVns = new List<TimeSpan>();
     91    private static List<int> solutionsFoundVns = new List<int>();
     92    private static List<List<TourData>> TourBackupVNS = new List<List<TourData>>();
     93    private static List<int> solutionsFoundPrVns = new List<int>();
     94    private static List<ProblemData> problems = new List<ProblemData>();
     95    private static double averageScoreVns;
     96    private static double bestScoreVns;
     97    private static TimeSpan timeOfBestScoreVns;
     98    private static double worstScoreVns;
     99    #endregion
     100
     101    static void Main() {
     102      Thread.CurrentThread.CurrentCulture = new CultureInfo("en-US");
     103
     104      const int numberOfRuns = 10;
     105      const string inputFilename = @"C:\Users\P41107\Desktop\moop\1 objective\1_p21\1_p21_t015.txt";
     106      const string csvFilename = @"C:\temp\results1.csv";
     107      const string summaryFilename = @"C:\temp\summary.csv";
     108      const int numberOfIterations = 10000;
     109      const int acceptFrequency = 100;
     110      const double tresholdValue = 0.95;
     111      const double fixedVisitingTime = 0.0;
     112      const double fixedPenalty = fixedVisitingTime;
     113      const double maximumDistanceOverride = 0.0;
     114      const bool performPathRelinkingComparison = true;
     115      TimeSpan runDuration = TimeSpan.FromSeconds(15);
     116
     117      string testInstanceName = inputFilename.Contains(@"\")
     118        ? inputFilename.Substring(inputFilename.LastIndexOf(@"\") + 1)
     119        : inputFilename.Substring(inputFilename.LastIndexOf(@"/") + 1);
     120
     121
     122      // Open the results CSV file for writing the data
     123      var csvFile = new StreamWriter(new FileStream(csvFilename, FileMode.Create));
     124      // Open the summary CSV file for appending the data
     125      bool csvExists = File.Exists(summaryFilename);
     126      var summaryFile = new StreamWriter(new FileStream(summaryFilename, FileMode.OpenOrCreate));
     127
     128      // Remember the overall starting time
     129      var startOverall = DateTime.Now.Ticks;
     130
     131      for (int runCounter = 0; runCounter < numberOfRuns; runCounter++) {
     132        // Print out a status information
     133        if (ShowStatus)
     134          Console.WriteLine("Run {0} started.", (runCounter + 1));
     135
     136        // Create a new problem data container
     137        var problem = new ProblemData {
     138          FixedPenalty = fixedVisitingTime,
     139          Constraints = new List<ConstraintData>(),
     140          Points = new List<PointData>(),
     141          Edges = new List<List<EdgeData>>(),
     142          MTR = new MersenneTwister(),
     143          VNS = new VnsData {
     144            NumberOfIterations = numberOfIterations,
     145            AcceptFrequency = acceptFrequency,
     146            TresholdValue = tresholdValue,
     147            InitialTour = new TourData { Path = new List<int>(), Scores = new List<int>() },
     148            DominantTours = new List<TourData>()
     149          },
     150        };
     151
     152        // Do the initialization
     153        ErrorCode errorCode = LoadData(inputFilename, problem);
     154        if (errorCode != 0) {
     155          Console.WriteLine("Initialization failed. (Code: {0})", errorCode);
     156          Console.WriteLine(GetErrorDescription(errorCode));
     157          Console.WriteLine("Exiting.");
     158          return;
     159        }
     160
     161        // Override the distance limit from file by parameter if specified
     162        if (maximumDistanceOverride > 0.0) {
     163          problem.Constraints.Clear();
     164          problem.Constraints.Add(new ConstraintData {
     165            Type = Constraint.Upperbound,
     166            Target = -1,
     167            TargetValue = maximumDistanceOverride
     168          });
     169        }
     170
     171        if (ShowStatus)
     172          Console.WriteLine("\tVNS started.");
     173
     174        // Run the VNS algorithm
     175        var startPart = DateTime.Now.Ticks;
     176        var durationPart = runDuration.Ticks;
     177        RunVns(problem, startPart, durationPart);
     178        var endPart = DateTime.Now.Ticks;
     179        var temp = CalculateDifference(startPart, endPart);
     180        avgTimeDurationVns += temp;
     181        timeDurationVns.Add(temp);
     182        solutionsFoundVns.Add((int)problem.VNS.DominantTours.Count);
     183
     184        if (ShowStatus)
     185          Console.WriteLine("\tVNS completed ({0} Tours in {1:g}).", problem.VNS.DominantTours.Count, temp);
     186
     187        if (performPathRelinkingComparison) {
     188          // Backup original VNS results
     189          TourBackupVNS.Add(problem.VNS.DominantTours);
     190        }
     191
     192        // If we have two objectives, run path relinking
     193        if (problem.ScoreCount == 2) {
     194          // Run the path relinking for the VNS solutions
     195          if (ShowStatus)
     196            Console.WriteLine("\tPath relinking for VNS solutions started.");
     197          int toursFoundPrVns = PathRelinking(problem, problem.VNS.DominantTours, startPart);
     198
     199          temp = CalculateDifference(startPart, DateTime.Now.Ticks) - temp;
     200          solutionsFoundPrVns.Add(toursFoundPrVns);
     201          if (ShowStatus)
     202            Console.WriteLine("\tPath relinking for VNS solutions completed ({0} tours in {1:g}).", toursFoundPrVns, temp);
     203        }
     204
     205        // Store all the information in the run-spanning storage
     206        problems.Add(problem);
     207      }
     208
     209      // If we have more than one objective, calculate metrics
     210      if (problems[0].ScoreCount == 2) {
     211        if (ShowStatus)
     212          Console.WriteLine("Performing 2-objective post-calculations.");
     213        throw new NotImplementedException();
     214      } else {
     215        if (ShowStatus)
     216          Console.WriteLine("\tPerforming 1-objective post-calculations.");
     217
     218        // Only one objective value, so just calculate best, average and worst score
     219        for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {
     220          averageScoreVns += problems[counterRuns].VNS.DominantTours[0].Scores[0];
     221
     222          if (problems[counterRuns].VNS.DominantTours[0].Scores[0] > bestScoreVns) {
     223            bestScoreVns = problems[counterRuns].VNS.DominantTours[0].Scores[0];
     224            timeOfBestScoreVns = problems[counterRuns].VNS.DominantTours[0].TimeOfAdding;
     225          }
     226          if ((counterRuns == 0) || (problems[counterRuns].VNS.DominantTours[0].Scores[0] < worstScoreVns)) {
     227            worstScoreVns = problems[counterRuns].VNS.DominantTours[0].Scores[0];
     228          }
     229        }
     230
     231        // Calculate the average computation times
     232        averageScoreVns /= numberOfRuns;
     233
     234        if (ShowStatus)
     235          Console.WriteLine("\tWriting output files.");
     236
     237        // Write out the CSV results file
     238        csvFile.WriteLine("Test instance;Tmax;# runs;iter. VNS;accept frequency;treshold");
     239        csvFile.Write(testInstanceName + ";");
     240        csvFile.Write("{0};", problems[0].Constraints[0].TargetValue);
     241        csvFile.Write("{0};", numberOfRuns);
     242        csvFile.Write("{0};", numberOfIterations);
     243        csvFile.Write("{0};", acceptFrequency);
     244        csvFile.Write("{0};", tresholdValue);
     245        csvFile.WriteLine();
     246        csvFile.WriteLine();
     247
     248        // If we have more than one objective, print out the full detail report
     249        if (problems[0].ScoreCount > 1) {
     250          throw new NotImplementedException();
     251        } else {
     252          // Only one objective, so print out the short report only
     253          csvFile.WriteLine("Run;CPU VNS;Score VNS");
     254          for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {
     255            csvFile.Write("{0};", counterRuns + 1); // Number of runs
     256            csvFile.Write("{0};", timeDurationVns[counterRuns]);      // CPU VNS
     257            csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Scores[0]);        // Score VNS
     258            //csv_file << convert_locale(time_of_best_score_aco) << ";";          // Runtime until finding best tour ACO
     259            //csv_file << convert_locale(time_of_best_score_vns) << ";";          // Runtime until finding best tour VNS
     260            csvFile.WriteLine();
     261          }
     262          csvFile.WriteLine();
     263          for (int counterRuns = 0; counterRuns < numberOfRuns; counterRuns++) {
     264            csvFile.WriteLine("Run;{0}", counterRuns + 1);
     265            csvFile.WriteLine(";;Length;Time Of Adding;Score;Path");
     266            csvFile.Write(";;");
     267
     268
     269            csvFile.WriteLine();
     270            csvFile.WriteLine();
     271
     272            csvFile.WriteLine(";Tour VNS");
     273            csvFile.WriteLine(";;Length;Time Of Adding;Score;Path");
     274            csvFile.Write(";;");
     275            csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Length);
     276            csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].TimeOfAdding);
     277            csvFile.Write("{0};", problems[counterRuns].VNS.DominantTours[0].Scores[0]);
     278            csvFile.Write("{0}", problems[counterRuns].VNS.DominantTours[0].Path[0]);
     279            for (int counterPoints = 1; counterPoints < problems[counterRuns].VNS.DominantTours[0].PathSize; counterPoints++) {
     280              csvFile.Write("-{0}", problems[counterRuns].VNS.DominantTours[0].Path[counterPoints]);
     281            }
     282            csvFile.WriteLine();
     283            csvFile.WriteLine();
     284          }
     285          // Append the CSV summary file information
     286          if (!csvExists) {
     287            summaryFile.Write("Test instance;Tmax;# runs;iter. VNS;accept frequency;treshold;");
     288            summaryFile.Write("avg. CPU VNS;max score VNS;avg. score VNS;min score VNS;time of adding best tour VNS");
     289            summaryFile.WriteLine();
     290          }
     291          summaryFile.Write("{0};", testInstanceName);
     292          summaryFile.Write("{0};", problems[0].Constraints[0].TargetValue);
     293          summaryFile.Write("{0};", numberOfRuns);
     294          summaryFile.Write("{0};", numberOfIterations);                  // number of iterations vns
     295          summaryFile.Write("{0};", acceptFrequency);                 // accept frequency
     296          summaryFile.Write("{0};", tresholdValue);   // treshold value
     297          summaryFile.Write("{0};", avgTimeDurationVns);    // CPU VNS
     298          summaryFile.Write("{0};", bestScoreVns);                // Best score VNS
     299          summaryFile.Write("{0};", averageScoreVns);     // Average score VNS
     300          summaryFile.Write("{0};", worstScoreVns);               // Worst score VNS
     301          summaryFile.Write("{0};", timeOfBestScoreVns);    // Time until best score VNS
     302          summaryFile.WriteLine();
     303        }
     304
     305        csvFile.Close();
     306        summaryFile.Close();
     307      }
     308    }
     309
     310    #region Initialization
     311
     312    private static ErrorCode LoadData(string fileName, ProblemData problem) {
     313      StreamReader inputFile;
     314      try {
     315        // Open the input file
     316        inputFile = new StreamReader(new FileStream(fileName, FileMode.OpenOrCreate));
     317      } catch (IOException) {
     318        return ErrorCode.ErrorOpenInputFile;
     319      }
     320
     321      // Initialize the Data structure
     322      problem.ConstraintCount = 0;
     323      problem.PointCount = 0;
     324      problem.ScoreCount = 0;
     325      problem.StartingPoint = -1;
     326      problem.TerminusPoint = -1;
     327      problem.MatrixGiven = false;
     328
     329      ErrorCode error = ErrorCode.ErrorNone;
     330
     331      int lineNumber = 0;
     332
     333      // Read the lines from the file
     334      while ((!inputFile.EndOfStream) && (error == ErrorCode.ErrorNone)) {
     335        string lineBuffer;
     336        try {
     337          lineBuffer = inputFile.ReadLine();
     338        } catch (IOException) {
     339          return ErrorCode.ErrorReadingData;
     340        }
     341
     342        // Remove all whitespace
     343        lineBuffer = new string(lineBuffer.ToCharArray().Where(c => !char.IsWhiteSpace(c)).ToArray());
     344
     345        // If the line contains data, continue
     346        if (lineBuffer.Length > 1) {
     347          // If the line contains not only a comment, process it
     348          int commentPosition = lineBuffer.IndexOf("//");
     349          if (commentPosition != 0) {
     350            // Count the lines that include data
     351            lineNumber++;
     352
     353            // Remove a comment if there is one
     354            if (commentPosition > 0)
     355              lineBuffer = lineBuffer.Remove(commentPosition);
     356
     357            // Convert the line to lowercase characters
     358            lineBuffer = lineBuffer.ToLower();
     359
     360            // Make sure the first data line includes the correct version
     361            if (lineNumber == 1) {
     362              string versions = VersionRequired;
     363              bool versionFound = false;
     364              do {
     365                if (lineBuffer == versions.Substring(versions.IndexOf(" or ") + 1)) {
     366                  versionFound = true;
     367                  break;
     368                }
     369                versions = versions.Remove(versions.IndexOf(" or "));
     370              }
     371              while (versions.IndexOf(" or ") != -1);
     372
     373              //if (line_buffer != POPT_Version_Required) return ERROR_WRONG_VERSION;
     374            } else {
     375              // Extract the needed information
     376              error = ExtractData(lineBuffer, problem);
     377            }
     378          }
     379        }
     380      }
     381
     382      // Check the data for inconsistencies in the data structure
     383      if (error == ErrorCode.ErrorNone) {
     384        if (problem.Constraints.Count < problem.ConstraintCount)
     385          return ErrorCode.ErrorTooFewConstraints;
     386
     387        if (problem.Points.Count < problem.PointCount)
     388          return ErrorCode.ErrorTooFewPoints;
     389
     390        if (problem.StartingPoint == -1)
     391          return ErrorCode.ErrorMissingStartingPoint;
     392
     393        if (problem.TerminusPoint == -1)
     394          return ErrorCode.ErrorMissingTerminusPoint;
     395
     396        // Calculate all distances from one point to another
     397        // and initialize pheromone values
     398        int pointCounter1;
     399        int pointCounter2;
     400        double maxDistance;
     401        if (!problem.MatrixGiven) {
     402          maxDistance = 0.0;
     403          for (pointCounter1 = (problem.PointCount - 1); pointCounter1 >= 0; --pointCounter1) {
     404            // Delete the last generated edgeset
     405            var tempEdgeset = new List<EdgeData>();
     406
     407            for (pointCounter2 = (problem.PointCount - 1); pointCounter2 >= 0; --pointCounter2) {
     408              // Calculate the distances
     409              double distanceX = Math.Abs(problem.Points[pointCounter1].PositionX - problem.Points[pointCounter2].PositionX);
     410              double distanceY = Math.Abs(problem.Points[pointCounter1].PositionY - problem.Points[pointCounter2].PositionY);
     411              var tempEdge = new EdgeData {
     412                Distance = Math.Sqrt(Math.Pow(distanceX, 2.0) + Math.Pow(distanceY, 2.0))
     413              };
     414
     415              // Remember the longest distance
     416              if ((tempEdge.Distance - maxDistance) >= PrecisionUsed) maxDistance = tempEdge.Distance; //(temp_edge.Distance > max_distance)
     417
     418              // Initialize the edge's pheromone values
     419              //temp_edge.Pheromone.assign(Problem.Score_Count, Problem.ACO.Initial_Pheromone_Value);
     420
     421              // Put the now generated edge to the temporal edge set
     422              tempEdgeset.Insert(0, tempEdge);
     423            }
     424
     425            // Put the now generated temporal edge set to the original edge set
     426            problem.Edges.Insert(0, tempEdgeset);
     427          }
     428        } else {
     429          maxDistance = 0.0;
     430
     431          // Find the maximum distance in the problem set
     432          for (pointCounter1 = 0; pointCounter1 < problem.PointCount; pointCounter1++) {
     433            for (pointCounter2 = 0; pointCounter2 < problem.PointCount; pointCounter2++) {
     434              if ((problem.Edges[pointCounter1][pointCounter2].Distance - maxDistance) >= PrecisionUsed) { //(Problem.Edges[point_counter1][point_counter2].Distance > max_distance)
     435                maxDistance = problem.Edges[pointCounter1][pointCounter2].Distance;
     436              }
     437            }
     438          }
     439        }
     440      }
     441
     442      // Close the input file
     443      inputFile.Close();
     444
     445      // Return with no error
     446      return error;
     447    }
     448
     449    private static ErrorCode ExtractData(string inputString, ProblemData problem) {
     450      string temp;
     451
     452      switch (inputString[0]) {
     453        case 'p': // Point description
     454          if (inputString.Length < 8)
     455            return ErrorCode.ErrorInvalidDefinitionP;
     456
     457          // Remove the 'p,'
     458          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     459          // Get the position_x
     460          string positionX = inputString.Substring(0, inputString.IndexOf(','));
     461          // Remove the position_x
     462          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     463          // Get the postion_y
     464          string positionY = inputString.Substring(0, inputString.IndexOf(','));
     465          // Remove the position_y to get the scores
     466          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     467
     468          var tempData = new PointData {
     469            PositionX = double.Parse(positionX),
     470            PositionY = double.Parse(positionY),
     471            Score = new List<int>()
     472          };
     473
     474          // Extract all score values for this point
     475          while (true) {
     476            string score;
     477            if (inputString.IndexOf(',') != -1) {
     478              score = inputString.Substring(0, inputString.IndexOf(','));
     479              inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     480              tempData.Score.Add(int.Parse(score));
     481            } else {
     482              score = inputString;
     483              tempData.Score.Add(int.Parse(score));
     484              break;
     485            }
     486          }
     487          problem.Points.Add(tempData);
     488          break;
     489
     490        case 'd': // Distance information
     491          if (inputString.Length < 11)
     492            return ErrorCode.ErrorInvalidDefinitionD;
     493
     494          var tempEdges = new List<EdgeData>();
     495
     496          // Remove the 'd,'
     497          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     498
     499          // Extract all distances for this point
     500          while (true) {
     501            string distance;
     502            if (inputString.IndexOf(',') != -1) {
     503              distance = inputString.Substring(0, inputString.IndexOf(','));
     504              inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     505              var tempEdge = new EdgeData {
     506                Distance = double.Parse(distance)
     507              };
     508              tempEdges.Add(tempEdge);
     509            } else {
     510              distance = inputString;
     511              var tempEdge = new EdgeData {
     512                Distance = double.Parse(distance)
     513              };
     514              tempEdges.Add(tempEdge);
     515              break;
     516            }
     517          }
     518          problem.Edges.Add(tempEdges);
     519          break;
     520
     521        case 'n': // Number of points
     522          if (inputString.Length < 3)
     523            return ErrorCode.ErrorInvalidDefinitionN;
     524
     525          // Remove the 'n,'
     526          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     527          // Extract the number of points
     528          problem.PointCount = int.Parse(inputString);
     529          break;
     530
     531        case 'm': // 1 if Distance-Matrix is given
     532          if (inputString.Length < 3)
     533            return ErrorCode.ErrorInvalidDefinitionM;
     534
     535          // Remove the 'm,'
     536          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     537          // Extract the number of points
     538          if (int.Parse(inputString) != 0) problem.MatrixGiven = true;
     539          break;
     540
     541        case 'c': // Number of constraints
     542          if (inputString.Length < 3)
     543            return ErrorCode.ErrorInvalidDefinitionC;
     544
     545          // Remove the 'c,'
     546          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     547          problem.ConstraintCount = int.Parse(inputString);
     548          break;
     549
     550        case 's': // Number of scores per point
     551          if (inputString.Length < 3)
     552            return ErrorCode.ErrorInvalidDefinitionS;
     553
     554          // Remove the 's,'
     555          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     556          problem.ScoreCount = int.Parse(inputString);
     557          break;
     558
     559        case 'b': // Index of the starting point
     560          if (inputString.Length < 3)
     561            return ErrorCode.ErrorInvalidDefinitionB;
     562
     563          // Remove the 'b,'
     564          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     565          problem.StartingPoint = int.Parse(inputString);
     566          break;
     567
     568        case 'e': // Index of the terminus point
     569          if (inputString.Length < 3)
     570            return ErrorCode.ErrorInvalidDefinitionE;
     571
     572          // Remove the 'e,'
     573          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     574          problem.TerminusPoint = int.Parse(inputString);
     575          break;
     576
     577        case 'u': // Upper bound constraint
     578          if (inputString.Length < 5)
     579            return ErrorCode.ErrorInvalidDefinitionU;
     580
     581          // Remove the 'u,'
     582          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     583          // Get the target
     584          temp = inputString.Substring(0, inputString.IndexOf(','));
     585          // Remove the target to get the target value
     586          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     587
     588          problem.Constraints.Add(new ConstraintData {
     589            Type = Constraint.Upperbound,
     590            Target = int.Parse(temp),
     591            TargetValue = double.Parse(inputString)
     592          });
     593          break;
     594
     595        case 'l': // Lower bound constraint
     596          if (inputString.Length < 5)
     597            return ErrorCode.ErrorInvalidDefinitionL;
     598
     599          // Remove the 'l,'
     600          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     601          // Get the target
     602          temp = inputString.Substring(0, inputString.IndexOf(','));
     603          // Remove the target to get the target value
     604          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     605
     606          problem.Constraints.Add(new ConstraintData {
     607            Type = Constraint.Lowerbound,
     608            Target = int.Parse(temp),
     609            TargetValue = double.Parse(inputString)
     610          });
     611          break;
     612
     613        case 'x': // Maximization constraint
     614          if (inputString.Length < 5)
     615            return ErrorCode.ErrorInvalidDefinitionX;
     616
     617          // Remove the 'x,'
     618          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     619          // Get the target
     620          temp = inputString.Substring(0, inputString.IndexOf(','));
     621          // Remove the target to get the target value
     622          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     623
     624          problem.Constraints.Add(new ConstraintData {
     625            Type = Constraint.Maximize,
     626            Target = int.Parse(temp),
     627            TargetValue = Double.Parse(inputString)
     628          });
     629          break;
     630
     631        case 'i': // Minimization constraint
     632          if (inputString.Length < 5)
     633            return ErrorCode.ErrorInvalidDefinitionI;
     634
     635          // Remove the 'i,'
     636          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     637          // Get the target
     638          temp = inputString.Substring(0, inputString.IndexOf(','));
     639          // Remove the target to get the target value
     640          inputString = inputString.Remove(0, inputString.IndexOf(',') + 1);
     641
     642          problem.Constraints.Add(new ConstraintData {
     643            Type = Constraint.Minimize,
     644            Target = int.Parse(temp),
     645            TargetValue = double.Parse(inputString)
     646          });
     647          break;
     648      }
     649      return ErrorCode.ErrorNone;
     650    }
     651
     652    private static string GetErrorDescription(ErrorCode errorCode) {
     653      switch (errorCode) {
     654        case ErrorCode.ErrorOpenInputFile: return "The input file could not be opened.";
     655        case ErrorCode.ErrorOpenOutputFile: return "The output file could not be opened.";
     656        case ErrorCode.ErrorConvertToLower: return "An error occoured at the conversion to lowercase.";
     657        case ErrorCode.ErrorRemovingWhitespace: return "An error occoured at the removal of whitespace.";
     658        case ErrorCode.ErrorWrongVersion: return ("The input file has the wrong version. Version " + VersionRequired + " is required.");
     659        case ErrorCode.ErrorReadingData: return "An error occoured while reading from the input file.";
     660        case ErrorCode.ErrorInvalidDefinitionN: return "Check your definition for the number of points.";
     661        case ErrorCode.ErrorInvalidDefinitionC: return "Check your definition for the number of constraints.";
     662        case ErrorCode.ErrorInvalidDefinitionU: return "Check your definition for upper bound constraints.";
     663        case ErrorCode.ErrorInvalidDefinitionL: return "Check your definition for lower bound constraints.";
     664        case ErrorCode.ErrorInvalidDefinitionX: return "Check your definition for maximization constraints.";
     665        case ErrorCode.ErrorInvalidDefinitionI: return "Check your definition for minimization constraints.";
     666        case ErrorCode.ErrorInvalidDefinitionP: return "At least one point definition is missing something.";
     667        case ErrorCode.ErrorInvalidDefinitionS: return "Check your definition for the number of scores.";
     668        case ErrorCode.ErrorInvalidDefinitionB: return "Check your definition for the starting point.";
     669        case ErrorCode.ErrorInvalidDefinitionE: return "Check your definition for the terminus point.";
     670        case ErrorCode.ErrorInvalidDefinitionD: return "Check your definition for the distance matrix.";
     671        case ErrorCode.ErrorInvalidDefinitionM: return "Check your definition for the distance matrix flag.";
     672        case ErrorCode.ErrorMissingStartingPoint: return "The definition of the starting point is missing.";
     673        case ErrorCode.ErrorMissingTerminusPoint: return "The definition of the terminus point is missing.";
     674        case ErrorCode.ErrorTooFewConstraints: return "There are too few constraints on the list.";
     675        case ErrorCode.ErrorTooFewPoints: return "There are too few points on the list.";
     676        case ErrorCode.ErrorTooFewScores: return "There are too few scores on the list of at least one point.";
     677        case ErrorCode.ErrorTooManyConstraints: return "There are too many constraints on the list.";
     678        case ErrorCode.ErrorTooManyPoints: return "There are too many points on the list.";
     679        case ErrorCode.ErrorTooManyScores: return "There are too many scores on the list of at least one point.";
     680        default: return "Unknown error.";
     681      }
     682    }
     683
     684    #endregion
     685
     686    #region VNS
     687
     688    private static void RunVns(ProblemData problem, long startTime, long maxRuntime) {
     689      long iterationCounter = 0;
     690      int neighborhoodMax;
     691      long iterationOfLastAcception = 0;
     692      long iterationOfLastFinding = 0;
     693      var preferences = new List<double>();
     694      bool increasingPreference = false;
     695      TourData newSolution;
     696
     697      // Define the maximum neighborhood distance
     698      //neighborhoodMax = 9;
     699
     700      // Generate an initial solution
     701      GenerateGreedyTour(problem);
     702
     703      // Bring this tour to a local optimum
     704      OptimizePath(problem, problem.VNS.InitialTour);
     705
     706      // Save this tour as at the moment it seems efficient
     707      SaveDominantToursVns(problem, problem.VNS.InitialTour, startTime);
     708
     709      // Create the starting preference for the shaking
     710      preferences.Add(1);
     711      preferences.Add(0);
     712
     713      // Perform the VNS
     714      while ((DateTime.Now.Ticks - startTime) < maxRuntime) {
     715        int neighborhoodCounter = 1;
     716        //while ((neighborhoodCounter < neighborhoodMax) && ((DateTime.Now.Ticks - start_time) < max_runtime))
     717        while ((neighborhoodCounter < problem.VNS.InitialTour.PathSize - 2) && ((DateTime.Now.Ticks - startTime) < maxRuntime)) {
     718          iterationCounter++;
     719
     720          // Generate a random tour in the kth neighborhood
     721          if ((iterationCounter - iterationOfLastFinding) > 1000) {
     722            // Create the next preference vector for shaking
     723            if (problem.ScoreCount == 2) {
     724              double temp = problem.MTR.NextDouble() / 1000.0;
     725              if (increasingPreference) {
     726                preferences[0] += temp;
     727                if (preferences[0] >= 1.0) {
     728                  preferences[0] = 1.0;
     729                  increasingPreference = false;
     730                }
     731                preferences[1] = 1.0 - preferences[0];
     732              } else {
     733                preferences[1] += temp;
     734                if (preferences[1] >= 1.0) {
     735                  preferences[1] = 1.0;
     736                  increasingPreference = true;
     737                }
     738                preferences[0] = 1.0 - preferences[1];
     739              }
     740            }
     741          }
     742
     743          // Shake forcing one of the scores
     744          ShakeTour(problem, neighborhoodCounter, preferences);
     745
     746          // Bring the tour back to be feasible
     747          CleanupTour(problem);
     748
     749          // Bring this tour to a local optimum
     750          OptimizePath(problem, problem.VNS.ActualTour);
     751
     752          // Save the tour if it is pareto dominant
     753          if (SaveDominantToursVns(problem, problem.VNS.ActualTour, startTime)) {
     754            // Move to the better solution and return to the nearest neighborhood
     755            problem.VNS.InitialTour = new TourData(problem.VNS.ActualTour);
     756            iterationOfLastFinding = iterationCounter;
     757            neighborhoodCounter = 0;
     758          } else if ((iterationCounter - iterationOfLastAcception) >= problem.VNS.AcceptFrequency) {
     759            // Sometimes accept a solution that is not more than a given ratio below
     760            // any of the dominant solutions found so far
     761            bool allow = true;
     762            int tourMax = problem.VNS.DominantTours.Count;
     763            for (int tourCounter = 0; tourCounter < tourMax; tourCounter++) {
     764              for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     765                if ((problem.VNS.DominantTours[tourCounter].Scores[scoreCounter] * problem.VNS.TresholdValue) > problem.VNS.ActualTour.Scores[scoreCounter]) {
     766                  allow = false;
     767                  break;
     768                }
     769              }
     770              if (!allow) break;
     771            }
     772            if (allow) {
     773              // Move to the worse solution and return to the nearest neighborhood
     774              problem.VNS.InitialTour = new TourData(problem.VNS.ActualTour);
     775              iterationOfLastAcception = iterationCounter;
     776              neighborhoodCounter = 0;
     777            }
     778          }
     779
     780          // Increase the neighborhood to search
     781          neighborhoodCounter++;
     782        }
     783      }
     784      //printf("DEBUG: iteration_counter = %d\n", iteration_counter);
     785    }
     786
     787    private static void GenerateGreedyTour(ProblemData problem) {
     788      int constraintCounter;
     789      double maxDistance = 0.0;
     790      var feasiblePoints = new List<FeasiblePointVns>();
     791
     792      // Find the maximum tour length
     793      for (constraintCounter = 0; constraintCounter < problem.ConstraintCount; constraintCounter++) {
     794        if ((problem.Constraints[constraintCounter].Type == Constraint.Upperbound) && (problem.Constraints[constraintCounter].Target == ConstraintTimeDistance)) {
     795          maxDistance = problem.Constraints[constraintCounter].TargetValue;
     796          break;
     797        }
     798      }
     799
     800      int numberFeasiblePoints = 0;
     801      // Find all points within the maximum distance allowed (ellipse)
     802      for (int pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {
     803        double distance = problem.Edges[problem.StartingPoint][pointCounter].Distance + problem.Edges[pointCounter][problem.TerminusPoint].Distance + problem.FixedPenalty;
     804        // DEBUG
     805        //printf("Distance = %.9f, max_dist = %.9f\n", distance, max_distance);
     806        //if ((distance <= max_distance) && (point_counter != Problem.Starting_Point) && (point_counter != Problem.Terminus_Point))
     807        if (((maxDistance - distance) >= PrecisionUsed) && (pointCounter != problem.StartingPoint) && (pointCounter != problem.TerminusPoint)) {
     808          var tempPoint = new FeasiblePointVns {
     809            Distance = distance,
     810            Index = pointCounter,
     811            Scores = new List<int>(problem.Points[pointCounter].Score)
     812          };
     813
     814          // Insert the point at the corresponding position
     815          int sortMax = feasiblePoints.Count;
     816          int sortCounter;
     817          for (sortCounter = 0; sortCounter < sortMax; sortCounter++) {
     818            int totalScoreNew = 0;
     819            int totalScoreOld = 0;
     820            for (int counterScores = 0; counterScores < problem.ScoreCount; counterScores++) {
     821              totalScoreNew += feasiblePoints[sortCounter].Scores[counterScores];
     822              totalScoreOld += tempPoint.Scores[counterScores];
     823            }
     824            if (totalScoreNew < totalScoreOld) {
     825              feasiblePoints.Insert(sortCounter, tempPoint);
     826              numberFeasiblePoints++;
     827              distance = -1.0;
     828              break;
     829            }
     830          }
     831
     832          // If the point was not yet inserted, append it
     833          if (distance > 0) {
     834            feasiblePoints.Add(tempPoint);
     835            numberFeasiblePoints++;
     836          }
     837        }
     838      }
     839
     840      // Add the starting and terminus point
     841      problem.VNS.InitialTour.Path = new List<int> {
     842        problem.StartingPoint,
     843        problem.TerminusPoint
     844      };
     845      problem.VNS.InitialTour.PathSize = 2;
     846      problem.VNS.InitialTour.Length = CalcLength(problem, problem.VNS.InitialTour.Path);
     847      problem.VNS.InitialTour.Scores = new List<int>(Enumerable.Repeat(0, problem.ScoreCount));
     848
     849      // Add points in a greedy way
     850      bool insertionPerformed = true;
     851      while (insertionPerformed) {
     852        insertionPerformed = false;
     853
     854        for (int pointCounter = 0; pointCounter < feasiblePoints.Count; pointCounter++) {
     855          for (int positionCounter = 1; positionCounter < problem.VNS.InitialTour.Path.Count; positionCounter++) {
     856            // Create the candidate tour
     857            TourData tempTour = new TourData(problem.VNS.InitialTour);
     858            tempTour.Path.Insert(positionCounter, feasiblePoints[pointCounter].Index);
     859            tempTour.Length = CalcLength(problem, tempTour.Path);
     860
     861            // If the insertion would be feasible, perform it
     862            if ((maxDistance - tempTour.Length) >= PrecisionUsed) {//(Temp_Tour.Length <= max_distance)
     863              problem.VNS.InitialTour.Length = tempTour.Length;
     864              problem.VNS.InitialTour.Path = new List<int>(tempTour.Path);
     865              problem.VNS.InitialTour.PathSize++;
     866              for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     867                problem.VNS.InitialTour.Scores[scoreCounter] += feasiblePoints[pointCounter].Scores[scoreCounter];
     868              }
     869              feasiblePoints.RemoveAt(pointCounter);
     870              insertionPerformed = true;
     871              break;
     872            }
     873          }
     874          if (insertionPerformed) break;
     875        }
     876      }
     877    }
     878
     879    private static void ShakeTour(ProblemData problem, int maxNeighborhood, List<double> preferences) {
     880      var visitablePoints = new List<int>();
     881
     882      // Limit the neighborhood to the tour length
     883      int limit = problem.VNS.InitialTour.PathSize - 3;
     884      int neighborhood = problem.MTR.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
     885
     886      // Determine the maximum travelling distance
     887      double maxDistance = problem.Constraints[0].TargetValue;
     888
     889      // Elect the starting index of the part to be replaced
     890      int tourSize = problem.VNS.InitialTour.PathSize;
     891      int randomPosition = problem.MTR.Next(tourSize - neighborhood - 2) + 1;
     892
     893      // Initialize the new tour
     894      problem.VNS.ActualTour = new TourData {
     895        Length = 0.0,
     896        Path = new List<int> { problem.StartingPoint },
     897        PathSize = 1,
     898        Scores = new List<int>(Enumerable.Repeat(0, problem.ScoreCount))
     899      };
     900
     901      // Find all points that are not yet included in the tour and are
     902      // within the maximum distance allowed (ellipse) and sort them with
     903      // regard to their utility
     904      visitablePoints.Clear();
     905      int numberVisitablePoints = 0;
     906      int pathSize = problem.VNS.ActualTour.PathSize;
     907      for (int pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {
     908        // Calculate the distance when going from the starting
     909        // point to this point and then to the end point
     910        double distance = problem.Edges[problem.StartingPoint][pointCounter].Distance + problem.Edges[pointCounter][problem.TerminusPoint].Distance + problem.FixedPenalty;
     911
     912        // If this distance is feasible and the point is
     913        // neither starting nor ending point, check the point
     914        if (((maxDistance - distance) >= PrecisionUsed) && (pointCounter != problem.StartingPoint) && (pointCounter != problem.TerminusPoint)) {
     915          bool alreadyVisited = false;
     916          int tourPointCounter;
     917          for (tourPointCounter = 0; tourPointCounter < tourSize; tourPointCounter++) {
     918            // Check if the point is included in the initial tour
     919            if (pointCounter == problem.VNS.InitialTour.Path[tourPointCounter]) {
     920              alreadyVisited = true;
     921              break;
     922            }
     923          }
     924
     925          // The point was not yet visited, so add it to the candidate list
     926          if (!alreadyVisited) {
     927            double utilityPoint = 0;
     928            bool inserted = false;
     929
     930            // Calculate the current point's utility
     931            for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     932              utilityPoint += problem.Points[pointCounter].Score[counterScore] * preferences[counterScore];
     933            }
     934
     935            // Add the point at the right position according to its utility (increasing)
     936            for (int counterPosition = 0; counterPosition < numberVisitablePoints; counterPosition++) {
     937              // Calculate the utility of the point at this position
     938              double utilityPosition = 0;
     939              for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     940                utilityPosition += problem.Points[visitablePoints[counterPosition]].Score[counterScore] * preferences[counterScore];
     941              }
     942
     943              // If the utility of the point is lower, insert it here
     944              if (utilityPosition > utilityPoint) {
     945                visitablePoints.Insert(counterPosition, pointCounter);
     946                inserted = true;
     947                break;
     948              }
     949            }
     950
     951            // If no bigger utility exists up to now, add the point at the end
     952            if (!inserted) {
     953              visitablePoints.Add(pointCounter);
     954            }
     955            numberVisitablePoints++;
     956          }
     957        }
     958      }
     959
     960      // Perform the insertions according to the utility sorting
     961      for (int position = 1; position < tourSize; position++) {
     962        int scoreCounter;
     963        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
     964          // Add the waypoints to the new solution
     965          problem.VNS.ActualTour.Path.Add(problem.VNS.InitialTour.Path[position]);
     966          problem.VNS.ActualTour.PathSize++;
     967          problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);
     968          for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     969            problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[problem.VNS.InitialTour.Path[position]].Score[scoreCounter];
     970          }
     971
     972          // Delete this point from the candidate list
     973          for (int pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {
     974            if (problem.VNS.InitialTour.Path[position] == visitablePoints[pointCounter]) {
     975              visitablePoints.RemoveAt(pointCounter);
     976              numberVisitablePoints--;
     977              break;
     978            }
     979          }
     980        } else {
     981          if (numberVisitablePoints > 0) {
     982            // Add the point with the highest utility from the candidate list
     983            int randomFactor = problem.MTR.Next(3);
     984            int insertionIndex = numberVisitablePoints - 1;
     985            if (numberVisitablePoints > 4) insertionIndex -= randomFactor;
     986            problem.VNS.ActualTour.Path.Add(visitablePoints[insertionIndex]); //[number_visitable_points - 1]);
     987            problem.VNS.ActualTour.PathSize++;
     988            problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);
     989            for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     990              //Problem.VNS.Actual_Tour.Scores[score_counter] += Problem.Points[visitable_points[number_visitable_points - 1]].Score[score_counter];
     991              problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[visitablePoints[insertionIndex]].Score[scoreCounter];
     992            }
     993            //visitable_points.pop_back();
     994            visitablePoints.RemoveAt(insertionIndex);
     995            numberVisitablePoints--;
     996          } else {
     997            // We don't have any points left that could be inserted so we can only re-insert
     998            // the removed and not already re-inserted points in a random order
     999            for (int reinsertCounter = randomPosition; reinsertCounter < (randomPosition + neighborhood); reinsertCounter++) {
     1000              bool alreadyReinserted = false;
     1001              for (int checkCounter = 0; checkCounter < problem.VNS.ActualTour.PathSize; checkCounter++) {
     1002                if (problem.VNS.InitialTour.Path[reinsertCounter] == problem.VNS.ActualTour.Path[checkCounter]) {
     1003                  alreadyReinserted = true;
     1004                  break;
     1005                }
     1006              }
     1007              if (!alreadyReinserted) {
     1008                visitablePoints.Add(problem.VNS.InitialTour.Path[reinsertCounter]);
     1009                numberVisitablePoints++;
     1010              }
     1011            }
     1012
     1013            int randomIndex = problem.MTR.Next(numberVisitablePoints - 1);
     1014            problem.VNS.ActualTour.Path.Add(visitablePoints[randomIndex]);
     1015            problem.VNS.ActualTour.PathSize++;
     1016            problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);
     1017            for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     1018              problem.VNS.ActualTour.Scores[scoreCounter] += problem.Points[visitablePoints[randomIndex]].Score[scoreCounter];
     1019            }
     1020            visitablePoints.Clear();
     1021            numberVisitablePoints = 0;
     1022          }
     1023        }
     1024      }
     1025    }
     1026
     1027    private static void CleanupTour(ProblemData problem) {
     1028      int tourPointCounter, sortCounter;
     1029      var distanceSavingsList = new List<double>();
     1030      var sortedPoints = new List<int>();
     1031
     1032      // Find the maximum distance restriction
     1033      double maxLength = problem.Constraints[0].TargetValue;
     1034
     1035      distanceSavingsList.Clear();
     1036      sortedPoints.Clear();
     1037
     1038      // Sort the points on the tour according to their average score
     1039      int tourPointMax = problem.VNS.ActualTour.PathSize - 1;
     1040      for (tourPointCounter = 1; tourPointCounter < tourPointMax; tourPointCounter++) {
     1041        var tempPath = new List<int>();
     1042
     1043        double distanceSaving = problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter - 1]][problem.VNS.ActualTour.Path[tourPointCounter]].Distance;
     1044        distanceSaving += problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter]][problem.VNS.ActualTour.Path[tourPointCounter + 1]].Distance;
     1045        distanceSaving -= problem.Edges[problem.VNS.ActualTour.Path[tourPointCounter - 1]][problem.VNS.ActualTour.Path[tourPointCounter + 1]].Distance;
     1046
     1047        bool inserted = false;
     1048        int sortMax = sortedPoints.Count;
     1049        for (sortCounter = 0; sortCounter < sortMax; sortCounter++) {
     1050          if (distanceSaving > distanceSavingsList[sortCounter]) {
     1051            distanceSavingsList.Insert(sortCounter, distanceSaving);
     1052            sortedPoints.Insert(sortCounter, tourPointCounter);
     1053            inserted = true;
     1054            break;
     1055          }
     1056        }
     1057        if (!inserted) {
     1058          distanceSavingsList.Add(distanceSaving);
     1059          sortedPoints.Add(tourPointCounter);
     1060        }
     1061      }
     1062
     1063      // As long as the created path is infeasible, remove elements
     1064      while ((problem.VNS.ActualTour.Length - maxLength) >= PrecisionUsed) { //(Problem.VNS.Actual_Tour.Length > max_length)
     1065        // Remove the point that frees the largest distance
     1066        int scoreCounter;
     1067        for (scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     1068          problem.VNS.ActualTour.Scores[scoreCounter] -= problem.Points[problem.VNS.ActualTour.Path[sortedPoints[0]]].Score[scoreCounter];
     1069        }
     1070        problem.VNS.ActualTour.Path.RemoveAt(sortedPoints[0]);
     1071        problem.VNS.ActualTour.PathSize--;
     1072        problem.VNS.ActualTour.Length = CalcLength(problem, problem.VNS.ActualTour.Path);
     1073        int sortMax = sortedPoints.Count;
     1074        for (sortCounter = 1; sortCounter < sortMax; sortCounter++) {
     1075          if (sortedPoints[sortCounter] > sortedPoints[0]) {
     1076            sortedPoints[sortCounter]--;
     1077          }
     1078        }
     1079        sortedPoints.RemoveAt(0);
     1080        distanceSavingsList.RemoveAt(0);
     1081      }
     1082    }
     1083
     1084    private static bool SaveDominantToursVns(ProblemData problem, TourData tour, long startTime) {
     1085      int tourCounter;
     1086
     1087      bool processed = false;
     1088      int tourCounterMax = problem.VNS.DominantTours.Count - 1;
     1089
     1090      for (tourCounter = tourCounterMax; tourCounter >= 0; --tourCounter) {
     1091        bool scoreGt = false;
     1092        bool scoreLt = false;
     1093        int scoreCounter = 0;
     1094        for (scoreCounter = (problem.ScoreCount - 1); scoreCounter >= 0; --scoreCounter) {
     1095          if (tour.Scores[scoreCounter] > problem.VNS.DominantTours[tourCounter].Scores[scoreCounter]) {
     1096            scoreGt = true;
     1097          } else if (tour.Scores[scoreCounter] < problem.VNS.DominantTours[tourCounter].Scores[scoreCounter]) {
     1098            scoreLt = true;
     1099          }
     1100        }
     1101
     1102        // If this tour equals an already existing one, skip it
     1103        if (tour.Path == problem.VNS.DominantTours[tourCounter].Path) {
     1104          processed = true;
     1105          break;
     1106        }
     1107
     1108        // If the tour is dominated by an existing, skip it
     1109        if (scoreLt && !scoreGt) {
     1110          processed = true;
     1111          break;
     1112        }
     1113
     1114        // If the tour dominates an existing one, eliminate the existing one
     1115        if (!scoreLt && scoreGt) {
     1116          problem.VNS.DominantTours.RemoveRange(tourCounter, 1);
     1117          tourCounterMax--;
     1118        }
     1119      }
     1120      if (!processed) {
     1121        // The tour either dominates an existing one or is just not dominated
     1122        // by an existing tour, so we assume it to be dominant
     1123        tour.TimeOfAdding = CalculateDifference(startTime, DateTime.Now.Ticks);
     1124        problem.VNS.DominantTours.Add(tour);
     1125        return true;
     1126      } else {
     1127        return false;
     1128      }
     1129    }
     1130
     1131    #endregion
     1132
     1133    #region Optimization
     1134
     1135    private static void ShortenPath(ProblemData problem, TourData tour) {
     1136      bool optimizationDone = true;
     1137      int pathSize = tour.PathSize;
     1138      int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2);
     1139
     1140      // DEBUG
     1141      //printf("Shorten:");
     1142
     1143      // Perform a 2-opt
     1144      while (optimizationDone) {
     1145        optimizationDone = false;
     1146
     1147        int blockLength;
     1148        for (blockLength = 2; blockLength < maxBlockLength; blockLength++) { //(path_size - 1); ++block_length)
     1149          // If an optimization has been done, start from the beginning
     1150          if (optimizationDone) break;
     1151
     1152          // DEBUG
     1153          //printf("\tBlock length = %d, Max block length = %d.\n", block_length, max_block_length);
     1154
     1155          int position;
     1156          for (position = 1; position < (pathSize - blockLength); position++) {
     1157            // If an optimization has been done, start from the beginning
     1158            if (optimizationDone) break;
     1159
     1160            // DEBUG
     1161            //printf("\t\tPosition = %d, Path size = %d.\n", position, path_size);
     1162
     1163            double newLength = tour.Length;
     1164            for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) {
     1165              newLength -= problem.Edges[tour.Path[counterLength]][tour.Path[counterLength + 1]].Distance;
     1166            }
     1167            for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) {
     1168              newLength += problem.Edges[tour.Path[counterLength]][tour.Path[counterLength - 1]].Distance;
     1169            }
     1170            newLength += problem.Edges[tour.Path[position - 1]][tour.Path[position + blockLength - 1]].Distance;
     1171            newLength += problem.Edges[tour.Path[position]][tour.Path[position + blockLength]].Distance;
     1172
     1173
     1174            if (newLength <= (tour.Length - 0.00001)) { // Avoid cycling caused by precision
     1175              var parthPath = tour.Path.GetRange(position, blockLength);
     1176
     1177              tour.Path.RemoveRange(position, blockLength);
     1178              tour.Path.InsertRange(position, parthPath.AsEnumerable().Reverse());
     1179
     1180              tour.Length = CalcLength(problem, tour.Path);
     1181
     1182              // Re-run the optimization
     1183              optimizationDone = true;
     1184            }
     1185          }
     1186        }
     1187      }
     1188      // DEBUG
     1189      //printf("Shorten done.\n");
     1190    }
     1191
     1192    private static void OptimizePath(ProblemData problem, TourData tour, int optimizationPreference = -1) {
     1193      bool optimizationDone = true;
     1194      int acceptNonParetoExchange = 0;
     1195      bool isFeasible = true;
     1196      var visitablePoints = new List<int>();
     1197
     1198      // Find the maximum distance restriction
     1199      double maxLength = problem.Constraints[0].TargetValue;
     1200
     1201      // Check if the tour can be improved by adding or replacing points
     1202      while (optimizationDone) {
     1203        optimizationDone = false;
     1204
     1205        // Try to shorten the path
     1206        ShortenPath(problem, tour);
     1207
     1208        // Determine the number of points visited so far
     1209        int tourSize = tour.PathSize; //, constraint_counter;
     1210
     1211        // Determine all points that have not yet been visited by this tour
     1212        visitablePoints.Clear();
     1213        int numberVisitablePoints = 0; //, constraint_counter;
     1214        int tourPointCounter; //, constraint_counter;
     1215        int pointCounter; //, constraint_counter;
     1216        for (pointCounter = 0; pointCounter < problem.PointCount; pointCounter++) {
     1217          bool alreadyVisited = false;
     1218          for (tourPointCounter = 0; tourPointCounter < tourSize; tourPointCounter++) {
     1219            if (pointCounter == tour.Path[tourPointCounter]) {
     1220              alreadyVisited = true;
     1221              break;
     1222            }
     1223          }
     1224          if (!alreadyVisited) {
     1225            visitablePoints.Add(pointCounter);
     1226            numberVisitablePoints++;
     1227          }
     1228        }
     1229
     1230        // Determine if any of the visitable points can be included at any
     1231        // position within the tour
     1232        int scoreCounter; //, constraint_counter;
     1233        for (tourPointCounter = 1; tourPointCounter < tourSize; tourPointCounter++) {
     1234          // If an optimization has been done, start from the beginning
     1235          if (optimizationDone) break;
     1236
     1237          for (pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {
     1238            // If an optimization has been done, start from the beginning
     1239            if (optimizationDone) break;
     1240
     1241            double newLength = tour.Length;
     1242            newLength -= problem.Edges[tour.Path[tourPointCounter - 1]][tour.Path[tourPointCounter]].Distance;
     1243            newLength += problem.Edges[tour.Path[tourPointCounter - 1]][visitablePoints[pointCounter]].Distance;
     1244            newLength += problem.Edges[visitablePoints[pointCounter]][tour.Path[tourPointCounter]].Distance;
     1245            newLength += problem.FixedPenalty;
     1246
     1247            // Determine if including the point does not violate any constraint
     1248            if (newLength <= maxLength) {
     1249              // We do not need to check if the point increases the score - it can only increase!
     1250
     1251              // Update the scores achieved by visiting this point
     1252              for (scoreCounter = (problem.ScoreCount - 1); scoreCounter >= 0; --scoreCounter) {
     1253                tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];
     1254              }
     1255
     1256              // Insert the new point at this position
     1257              tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);
     1258              tour.PathSize++;
     1259
     1260              // Update the overall tour length
     1261              tour.Length = CalcLength(problem, tour.Path);
     1262
     1263              // Re-run this optimization
     1264              optimizationDone = true;
     1265            }
     1266          }
     1267        }
     1268
     1269        // Determine if any of the visitable points can take the place of an
     1270        // already visited point in the tour to improve the scores
     1271        for (tourPointCounter = 1; tourPointCounter < (tourSize - 1); tourPointCounter++) {
     1272          // If an optimization has been done, start from the beginning
     1273          if (optimizationDone) break;
     1274
     1275          for (pointCounter = 0; pointCounter < numberVisitablePoints; pointCounter++) {
     1276            // If an optimization has been done, start from the beginning
     1277            if (optimizationDone) break;
     1278
     1279            double newLength = tour.Length;
     1280            newLength -= problem.Edges[tour.Path[tourPointCounter - 1]][tour.Path[tourPointCounter]].Distance;
     1281            newLength -= problem.Edges[tour.Path[tourPointCounter]][tour.Path[tourPointCounter + 1]].Distance;
     1282            newLength += problem.Edges[tour.Path[tourPointCounter - 1]][visitablePoints[pointCounter]].Distance;
     1283            newLength += problem.Edges[visitablePoints[pointCounter]][tour.Path[tourPointCounter + 1]].Distance;
     1284
     1285            if (newLength <= maxLength) {
     1286              // Check if the point dominated the one it would replace
     1287              bool scoreGt = false;
     1288              bool scoreLt = false;
     1289              if (optimizationPreference == -1) {
     1290                for (scoreCounter = (problem.ScoreCount - 1); scoreCounter >= 0; --scoreCounter) {
     1291                  if (problem.Points[visitablePoints[pointCounter]].Score[scoreCounter] > problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter])
     1292                    scoreGt = true;
     1293                  else if (problem.Points[visitablePoints[pointCounter]].Score[scoreCounter] < problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter])
     1294                    scoreLt = true;
     1295                }
     1296              } else {
     1297                if (problem.Points[visitablePoints[pointCounter]].Score[optimizationPreference] > problem.Points[tour.Path[tourPointCounter]].Score[optimizationPreference])
     1298                  scoreGt = true;
     1299                else if (problem.Points[visitablePoints[pointCounter]].Score[optimizationPreference] < problem.Points[tour.Path[tourPointCounter]].Score[optimizationPreference])
     1300                  scoreLt = true;
     1301              }
     1302
     1303              if (!scoreLt && scoreGt) {
     1304                // Update the overall tour length
     1305                // Tour.Length = new_length;
     1306                // Update the scores achieved by visiting this point
     1307                for (scoreCounter = (problem.ScoreCount - 1); scoreCounter >= 0; --scoreCounter) {
     1308                  tour.Scores[scoreCounter] -= problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter];
     1309                  tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];
     1310                }
     1311
     1312                // Replace the old point by the new one
     1313                tour.Path.RemoveAt(tourPointCounter);
     1314                tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);
     1315
     1316                // Update the overall tour length
     1317                tour.Length = CalcLength(problem, tour.Path);
     1318
     1319                // Re-run this optimization
     1320                optimizationDone = true;
     1321              }
     1322
     1323              // If no dominant exchange could be performed, accept a non dominant exchange
     1324              if (scoreGt && (acceptNonParetoExchange > 0) && (acceptNonParetoExchange < 6) && (optimizationPreference == -1)) {
     1325                // Update the overall tour length
     1326                //Tour.Length = new_length;
     1327
     1328                // Update the scores achieved by visiting this point
     1329                for (scoreCounter = (problem.ScoreCount - 1); scoreCounter >= 0; --scoreCounter) {
     1330                  tour.Scores[scoreCounter] -= problem.Points[tour.Path[tourPointCounter]].Score[scoreCounter];
     1331                  tour.Scores[scoreCounter] += problem.Points[visitablePoints[pointCounter]].Score[scoreCounter];
     1332                }
     1333
     1334                // Replace the old point by the new one
     1335                tour.Path.RemoveAt(tourPointCounter);
     1336                tour.Path.Insert(tourPointCounter, visitablePoints[pointCounter]);
     1337
     1338                // Update the overall tour length
     1339                tour.Length = CalcLength(problem, tour.Path);
     1340
     1341                // Re-run this optimization
     1342                optimizationDone = true;
     1343              }
     1344            }
     1345          }
     1346        }
     1347
     1348        if (!optimizationDone && (acceptNonParetoExchange == 0)) {
     1349          // If no optimization has been done, accept non dominant exchanges
     1350          // Non dominant exchanges will only be accepted 5 times to prevent infinite loops
     1351          optimizationDone = true;
     1352          acceptNonParetoExchange++;
     1353        } else if (optimizationDone && (acceptNonParetoExchange > 0)) {
     1354          // If an optimization has been done, do not accept non dominant exchange
     1355          acceptNonParetoExchange++;
     1356        }
     1357      }
     1358    }
     1359
     1360    private static double CalcLength(ProblemData problem, List<int> path) {
     1361      double length = 0.0;
     1362
     1363      for (int pointCounter = 1; pointCounter < path.Count; pointCounter++) {
     1364        length += problem.Edges[path[pointCounter - 1]][path[pointCounter]].Distance;
     1365      }
     1366      // Add the fixed penalty for every vertex except for the starting and ending vertex
     1367      if (path.Count > 1) {
     1368        if (path[path.Count - 1] == problem.TerminusPoint) length += ((path.Count() - 2.0) * problem.FixedPenalty);
     1369        else length += ((path.Count - 1.0) * problem.FixedPenalty);
     1370      }
     1371
     1372      return length;
     1373    }
     1374
     1375    #endregion
     1376
     1377    #region Path Relinking
     1378
     1379    private static int PathRelinking(ProblemData problem, List<TourData> tours, long startTime) {
     1380      int numberOfToursFound = 0;
     1381
     1382      // Sort the tours with regard to their scores
     1383      SortTours(tours);
     1384
     1385      for (int counterGuidingTour = 1; counterGuidingTour < tours.Count; counterGuidingTour++) {
     1386        TourData currentTour = tours[counterGuidingTour - 1];
     1387        TourData guidingTour = tours[counterGuidingTour];
     1388        numberOfToursFound += PathRelinkingStep(0, problem, tours, currentTour, guidingTour, startTime);
     1389      }
     1390
     1391      return numberOfToursFound;
     1392    }
     1393
     1394    private static void SortTours(List<TourData> tours) {
     1395      int numberTours = tours.Count;
     1396
     1397      // Sort the tours with regard to their scores
     1398      for (int counterTours = (numberTours - 1); counterTours >= 0; counterTours--) {
     1399        for (int counterSearch = 1; counterSearch <= counterTours; counterSearch++) {
     1400          if (tours[counterSearch].Scores[0] < tours[counterSearch - 1].Scores[0]) {
     1401            tours.Insert(counterSearch - 1, tours[counterSearch]);
     1402            tours.RemoveAt(counterSearch + 1);
     1403          }
     1404        }
     1405      }
     1406    }
     1407
     1408    private static int PathRelinkingStep(int level, ProblemData problem, List<TourData> tours, TourData currentTour, TourData guidingTour, long startTime) {
     1409      int numberOfToursFound = 0;
     1410      List<int> nodesToRemove = new List<int>();
     1411      List<int> nodesToInsert = new List<int>();
     1412      int numberOfNodesToRemove = FindNodesToRemove(currentTour, guidingTour, nodesToRemove);
     1413      int numberOfNodesToInsert = FindNodesToInsert(currentTour, guidingTour, nodesToInsert);
     1414
     1415      // If no other transformations are possible without reaching the guiding solution, return
     1416      if ((numberOfNodesToRemove <= 1) && (numberOfNodesToInsert <= 1)) {
     1417        return 0;
     1418      }
     1419
     1420      if (numberOfNodesToRemove != 0 && numberOfNodesToInsert != 0) {
     1421        // If too many combinations can be performed on this layer, draw one randomly
     1422        if ((numberOfNodesToRemove * numberOfNodesToInsert) < 16) {
     1423          // Nodes for removing and inserting are available
     1424          for (int counterRemove = 0; counterRemove < numberOfNodesToRemove; counterRemove++) {
     1425            for (int counterInsert = 0; counterInsert < numberOfNodesToInsert; counterInsert++) {
     1426              // Make a working copy of the current tour
     1427              TourData candidateTour = new TourData(currentTour);
     1428
     1429              // Perform the transformation step
     1430              for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     1431                candidateTour.Scores[counterScore] -= problem.Points[candidateTour.Path[nodesToRemove[counterRemove]]].Score[counterScore];
     1432                candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[counterInsert]]].Score[counterScore];
     1433              }
     1434              candidateTour.Path.RemoveAt(nodesToRemove[counterRemove]);
     1435              candidateTour.Path.Insert(nodesToRemove[counterRemove], guidingTour.Path[nodesToInsert[counterInsert]]);
     1436              candidateTour.Length = CalcLength(problem, candidateTour.Path);
     1437
     1438              // Locally optimize the modified tour
     1439              TourData tempTour = new TourData(candidateTour);
     1440              OptimizePath(problem, tempTour);
     1441
     1442              // If the tour is efficient, save it and increase the number of tours found
     1443              if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;
     1444
     1445              // Recursively perform all remaining steps after this one
     1446              if ((numberOfNodesToRemove > 1) || (numberOfNodesToInsert > 1)) {
     1447                numberOfToursFound += PathRelinkingStep((level + 1), problem, tours, candidateTour, guidingTour, startTime);
     1448              }
     1449            }
     1450          }
     1451        } else {
     1452          // Draw one combination randomly
     1453          int nodeToRemove = problem.MTR.Next(numberOfNodesToRemove - 1);
     1454          int nodeToInsert = problem.MTR.Next(numberOfNodesToInsert - 1);
     1455
     1456          // Make a working copy of the current tour
     1457          TourData candidateTour = currentTour;
     1458
     1459          // Perform the transformation step
     1460          for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     1461            candidateTour.Scores[counterScore] -= problem.Points[candidateTour.Path[nodesToRemove[nodeToRemove]]].Score[counterScore];
     1462            candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[nodeToInsert]]].Score[counterScore];
     1463          }
     1464          candidateTour.Path.RemoveAt(nodesToRemove[nodeToRemove]);
     1465          candidateTour.Path.Insert(nodesToRemove[nodeToRemove], guidingTour.Path[nodesToInsert[nodeToInsert]]);
     1466          candidateTour.Length = CalcLength(problem, candidateTour.Path);
     1467
     1468          // Locally optimize the modified tour
     1469          TourData tempTour = new TourData(candidateTour);
     1470          OptimizePath(problem, tempTour);
     1471
     1472          // If the tour is efficient, save it and increase the number of tours found
     1473          if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;
     1474
     1475          // Recursively perform all remaining steps after this one
     1476          if ((numberOfNodesToRemove > 1) || (numberOfNodesToInsert > 1)) {
     1477            numberOfToursFound += PathRelinkingStep((level + 1), problem, tours, candidateTour, guidingTour, startTime);
     1478          }
     1479        }
     1480      } else if (numberOfNodesToRemove != 0) {
     1481        // Only removing nodes is possible
     1482        for (int counter_remove = 0; counter_remove < numberOfNodesToRemove; counter_remove++) {
     1483          // Make a working copy of the current tour
     1484          TourData candidateTour = new TourData(currentTour);
     1485
     1486          // Perform the transformation step
     1487          for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     1488            candidateTour.Scores[counterScore] -= problem.Points[candidateTour.Path[nodesToRemove[counter_remove]]].Score[counterScore];
     1489          }
     1490          candidateTour.Path.RemoveAt(nodesToRemove[counter_remove]);
     1491          candidateTour.PathSize--;
     1492          candidateTour.Length = CalcLength(problem, currentTour.Path);
     1493
     1494          // Locally optimize the modified tour
     1495          TourData tempTour = new TourData(candidateTour);
     1496          OptimizePath(problem, tempTour);
     1497
     1498          // If the tour is efficient, save it and increase the number of tours found
     1499          if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;
     1500        }
     1501      } else if (numberOfNodesToInsert != 0) {
     1502        // Only inserting nodes is possible
     1503        for (int counterInsert = 0; counterInsert < numberOfNodesToInsert; counterInsert++) {
     1504          // Make a working copy of the current tour
     1505          TourData candidateTour = new TourData(currentTour);
     1506
     1507          // Perform the transformation step
     1508          for (int counterScore = 0; counterScore < problem.ScoreCount; counterScore++) {
     1509            candidateTour.Scores[counterScore] += problem.Points[guidingTour.Path[nodesToInsert[counterInsert]]].Score[counterScore];
     1510          }
     1511          candidateTour.Path.Insert((candidateTour.PathSize / 2), guidingTour.Path[nodesToInsert[counterInsert]]);
     1512          candidateTour.PathSize++;
     1513          candidateTour.Length = CalcLength(problem, candidateTour.Path);
     1514
     1515          // Locally optimize the modified tour
     1516          TourData tempTour = new TourData(candidateTour);
     1517          OptimizePath(problem, tempTour);
     1518
     1519          // If the tour is efficient, save it and increase the number of tours found
     1520          if (SaveCandidateTour(problem, tours, tempTour, startTime)) numberOfToursFound++;
     1521        }
     1522      }
     1523
     1524      return numberOfToursFound;
     1525    }
     1526
     1527    private static int FindNodesToRemove(TourData currentTour, TourData guidingTour, List<int> nodesToRemove) {
     1528      // Find all node to remove from the current tour
     1529      for (int counterNodes = 1; counterNodes < currentTour.PathSize; counterNodes++) {
     1530        bool nodeFound = false;
     1531        for (int counterSearch = 1; counterSearch < guidingTour.PathSize; counterSearch++) {
     1532          if (guidingTour.Path[counterSearch] == currentTour.Path[counterNodes]) {
     1533            nodeFound = true;
     1534            break;
     1535          }
     1536        }
     1537        if (!nodeFound) {
     1538          // Remember the position of the node that has to be removed
     1539          nodesToRemove.Add(counterNodes);
     1540        }
     1541      }
     1542      return nodesToRemove.Count;
     1543    }
     1544
     1545    private static int FindNodesToInsert(TourData currentTour, TourData guidingTour, List<int> nodesToInsert) {
     1546      // Find all node to insert into the current tour
     1547      for (int counterNodes = 1; counterNodes < guidingTour.PathSize; counterNodes++) {
     1548        bool nodeFound = false;
     1549        for (int counterSearch = 1; counterSearch < currentTour.PathSize; counterSearch++) {
     1550          if (currentTour.Path[counterSearch] == guidingTour.Path[counterNodes]) {
     1551            nodeFound = true;
     1552            break;
     1553          }
     1554        }
     1555        if (!nodeFound) {
     1556          // Remember the position of the node that has to be removed
     1557          nodesToInsert.Add(counterNodes);
     1558        }
     1559      }
     1560      return nodesToInsert.Count;
     1561    }
     1562
     1563    private static bool SaveCandidateTour(ProblemData problem, List<TourData> tours, TourData candidateTour, long startTime) {
     1564      bool candidateSaved = false;
     1565
     1566      if (candidateTour.Length <= problem.Constraints[0].TargetValue) {
     1567        bool processed = false;
     1568        int tourCounterMax = tours.Count - 1;
     1569        for (int tourCounter = tourCounterMax; tourCounter >= 0; --tourCounter) {
     1570          bool scoreGt = false;
     1571          bool scoreLt = false;
     1572          for (int scoreCounter = 0; scoreCounter < problem.ScoreCount; scoreCounter++) {
     1573            if (candidateTour.Scores[scoreCounter] > tours[tourCounter].Scores[scoreCounter]) {
     1574              scoreGt = true;
     1575            } else if (candidateTour.Scores[scoreCounter] < tours[tourCounter].Scores[scoreCounter]) {
     1576              scoreLt = true;
     1577            }
     1578          }
     1579
     1580          // If this tour equals an already existing one, skip it
     1581          if (candidateTour.Path == tours[tourCounter].Path) {
     1582            processed = true;
     1583            break;
     1584          }
     1585
     1586          // If the tour is dominated by an existing, skip it
     1587          if (scoreLt && !scoreGt) {
     1588            processed = true;
     1589            break;
     1590          }
     1591
     1592          // If the tour yields the same scores as an existing one, skip it
     1593          if (!scoreLt && !scoreGt) {
     1594            processed = true;
     1595            break;
     1596          }
     1597
     1598          // If the tour dominates an existing one, eliminate the existing one
     1599          if (!scoreLt && scoreGt) {
     1600            tours.RemoveAt(tourCounter);
     1601          }
     1602        }
     1603        if (!processed) {
     1604          // The tour is neither dominated by an existing one nor does it
     1605          // dominate an existing tour, so we assume it to be dominant
     1606          candidateTour.TimeOfAdding = CalculateDifference(startTime, DateTime.Now.Ticks);
     1607          tours.Add(candidateTour);
     1608          candidateSaved = true;
     1609        }
     1610      }
     1611      return candidateSaved;
     1612    }
     1613
     1614    #endregion
     1615
     1616    #region Helper
     1617    private static TimeSpan CalculateDifference(long startValue, long endValue) {
     1618      return TimeSpan.FromTicks(endValue - startValue);
     1619    }
     1620
     1621    #endregion
    31622  }
     1623
     1624  #region Data Structures
     1625
     1626  public class FeasiblePointVns {
     1627    public int Index;
     1628    public double Distance;
     1629    public List<int> Scores;
     1630  }
     1631
     1632  public enum Constraint {
     1633    Upperbound = 0,
     1634    Lowerbound = 1,
     1635    Maximize = 2,
     1636    Minimize = 3
     1637  }
     1638
     1639  public class ConstraintData {
     1640    public Constraint Type;           // 0...upper bound
     1641    // 1...lower bound
     1642    // 2...maximize
     1643    // 3...minimize
     1644    public int Target;            // Which score is affected by
     1645    // this constraint:
     1646    // 0...Time/Distance
     1647    // #...number of the score
     1648    public double TargetValue;        // The value that should
     1649    // (not) be reached
     1650  }
     1651
     1652  public class PointData {
     1653    public double PositionX;    // X-Position of the point
     1654    public double PositionY;    // Y-Position of the point
     1655
     1656    public List<int> Score;   // List of scores for this point
     1657    public List<int> Neighbors; // List of all points in the neighborhood
     1658  }
     1659
     1660  public class EdgeData {
     1661    public double Distance;       // Length of this edge
     1662
     1663    //vector<double> Pheromone;   // List of pheromones deposited
     1664    // on this edge
     1665  }
     1666
     1667  public class TourData {
     1668    public TourData() { }
     1669    public TourData(TourData other) {
     1670      Length = other.Length;
     1671      PathSize = other.PathSize;
     1672      Scores = new List<int>(other.Scores);
     1673      Path = new List<int>(other.Path);
     1674      TimeOfAdding = other.TimeOfAdding;
     1675    }
     1676
     1677    public double Length;       // Length of this tour
     1678    public int PathSize;
     1679
     1680    public List<int> Scores;    // Scores achieved by this tour
     1681    public List<int> Path;      // Indices of the vertices visited by this tour
     1682    public TimeSpan TimeOfAdding; // Time at which the solution was added
     1683  }
     1684
     1685  public class VnsData {
     1686    public int NumberOfIterations;        // Number of iterations to run
     1687    public int AcceptFrequency;           // How often "bad" solutions will be accepted
     1688    public double TresholdValue;          // Ratio that allows the system to accept
     1689    // Solutions that are not dominant but do
     1690    // not differ more than this from the actual
     1691    // solution
     1692    public TourData InitialTour;          // Initially created solution tour
     1693    public TourData ActualTour;           // Actually created neighborhood tour
     1694
     1695    public List<TourData> DominantTours;  // List containing all dominant tours
     1696  }
     1697
     1698  public class ProblemData {
     1699    public int StartingPoint;                 // Index of the starting point
     1700    public int TerminusPoint;                 // Index of the ending point
     1701    public int ConstraintCount;               // Number of constraints
     1702    public int ScoreCount;                    // Number of scores in the problem
     1703    public int PointCount;                    // Number of points in the problem
     1704    public bool MatrixGiven;                  // true if the distance matrix is given
     1705
     1706    public List<ConstraintData> Constraints;  // List of constraints
     1707    public List<PointData> Points;            // List of points
     1708    public List<List<EdgeData>> Edges;        // List of all edges (First index = origin, second index = target)
     1709
     1710    public MersenneTwister MTR;               // Mersenne Twister PRNG
     1711
     1712    //ACO_Data ACO;                           // All data needed by the ACO algorithm
     1713    public VnsData VNS;                       // All data needed by the VNS algorithm
     1714    public double FixedPenalty;               // User specified penalty for each visited vertex
     1715  }
     1716
     1717  #endregion
    41718}
Note: See TracChangeset for help on using the changeset viewer.