Package es.urjc.etsii.grafo.TSP.model

Class TSPSolution

java.lang.Object
es.urjc.etsii.grafo.solution.Solution<TSPSolution,TSPInstance>
es.urjc.etsii.grafo.TSP.model.TSPSolution
public class TSPSolution extends Solution<TSPSolution,TSPInstance>
This class represents a solution of the problem. A solution is represented by an array of size n, being n the number of locations (cities, facilities, etc.) of the problem. The index represent the order in which the location contained at that position of the array will be visited.

Example: an instance with 5 locations, each location with an id [0,4] and a route 3 -> 1 -> 4 -> 0 -> 2 (-> 3) is represented as follows: Index 0 1 2 3 4 Value [ 3 ][ 1 ][ 4 ][ 0 ][ 2 ]

The total distance is considered the objective function value of the solution.

  • Constructor Details

    • TSPSolution

      public TSPSolution(TSPInstance ins)
      Initialize solution from instance
      Parameters:
      ins - instance of the problem

    • TSPSolution

      public TSPSolution(TSPSolution s)
      Clone constructor
      Parameters:
      s - Solution to clone

  • Method Details

    • cloneSolution

      public TSPSolution cloneSolution()
      Description copied from class: Solution
      Clone the current solution. Deep clone mutable data or you will regret it.
      Specified by:
      cloneSolution in class Solution<TSPSolution,TSPInstance>
      Returns:
      A deep clone of the current solution

    • getDistance

      public double getDistance()
      Get the current solution score. The difference between this method and recalculateScore is that this result can be a property of the solution, or cached, it does not have to be calculated each time this method is called
      Returns:
      current solution score as double

    • setScore

      public void setScore(double distance)
      Set the current solution score.

    • recalculateScore

      public double recalculateScore()
      Recalculate solution score, sometimes is faster than incrementally calculating it. This method is also used in the solution validator to verify that the solution is correct.
      Returns:
      current solution score as double

    • toString

      public String toString()
      Generate a string representation of this solution. Used when printing progress to console, show as minimal info as possible
      Specified by:
      toString in class Solution<TSPSolution,TSPInstance>
      Returns:
      Small string representing the current solution

    • setOrderOfLocation

      public void setOrderOfLocation(int order, int location)
      Sets in which position (or order) a location will be visited.
      Parameters:
      order - position in which the location will be visited
      location - location

    • shuffleRoute

      public void shuffleRoute()
      Shuffle route

    • swapLocationOrder

      public void swapLocationOrder(int pi, int pj)
      Swap classical move: Swap the position in the route of two locations, given its actual positions. Example: actual route : [a,b,c,d,e,f], pi = 0, pj= 1, resultant route= [b,a,c,d,e,f] Example: actual route : [a,b,c,d,e,f], pi = 1, pj= 4, resultant route= [a,e,c,d,b,f] When the operation is performed, the objective function (this.distance) is updated
      Parameters:
      pi - actual position of the location
      pj - desired position

    • insertLocationAtPiInPj

      public void insertLocationAtPiInPj(int pi, int pj)
      Insert classical move: Deletes a location from and array (given its position) and inserts it in the specified position. Example: actual route : [a,b,c,d,e,f], pi = 0, pj= 1, resultant route= [b,a,c,d,e,f] Example: actual route : [a,b,c,d,e,f], pi = 1, pj= 4, resultant route=[a,c,d,e,b,f] Example: actual route : [a,b,c,d,e,f], pi = 5 pj= 3, resultant route= [a,b,c,f,d,e] When the operation is performed, the objective function (this.distance) is updated
      Parameters:
      pi - actual position of the location
      pj - desired position

    • getLocation

      public int getLocation(int position)
      Get the position what is visited in a given position of the route
      Parameters:
      position - position of the route
      Returns:
      location id

    • getDistanceContribution

      public double getDistanceContribution(int pos)
      Get the contribution (i.e. the distance to the previous and next location on the route) of a location (given its position). The location is not inserted at that position, it only calculates and returns the value.
      Parameters:
      pos - position of the route
      Returns:
      the distance

    • getDistanceContribution

      public double getDistanceContribution(int pos, int loc)
      Get the contribution (i.e. the distance to the previous and next location on the route) if it was placed at a specific position on the route. The location is not inserted at that position, it only calculates and returns the value.
      Parameters:
      pos - position of the route
      loc - location to calculate the distance to next location
      Returns:
      the distance

    • getDistanceContributionToPreviousLocation

      public double getDistanceContributionToPreviousLocation(int pos)
      Get the distance to the previous location
      Parameters:
      pos - position of the route
      Returns:
      the distance

    • getDistanceContributionToPreviousLocation

      public double getDistanceContributionToPreviousLocation(int pos, int loc)
      Get the distance to the previous location if it was placed at a specific position on the route. The location is not inserted at that position, it only calculates and returns the value.
      Parameters:
      pos - position of the route
      loc - location to calculate the distance to next location
      Returns:
      the distance

    • getDistanceContributionToNextLocation

      public double getDistanceContributionToNextLocation(int pos)
      Get the distance to the next location
      Parameters:
      pos - position of the route
      Returns:
      the distance

    • getDistanceContributionToNextLocation

      public double getDistanceContributionToNextLocation(int pos, int loc)
      Get the distance to the next location if it was placed at a specific position on the route. The location is not inserted at that position, it only calculates and returns the value.
      Parameters:
      pos - position of the route
      loc - location to calculate the distance to next location
      Returns:
      the distance