Traveling Salesman Problem implemented in dignea. Uses a IntFloat representation where the solutions are integers in a permutation-based approach and the fitness is a float with the cost of a travel. More...

#include <TSP.h>

Inheritance diagram for TSP:

Public Member Functions
	TSP ()
	Creates a default TSP object. More...

	TSP (const int &numberOfVars)
	Creates a TSP object with a predefined number of cities. More...

	TSP (const int &numberOfVars, const vector< coords > &coordinates)
	Creates a TSP object with a predefined number of cities and the coordinates for each one. More...

	TSP (const string &pathToInstance)
	Creates a TSP object which loads the data from the filesystem. More...

	TSP (TSP const *other)
	Creates a TSP copying the information from other instance. More...

float	getUpperLimit (int i) const override
	Get the upper bound of the search space. In this case the upper bound is the number of variables minus one since the starting city is duplicated at the end of the travel. More...

int	getOptimizationDirection (const int i) const override
	Get the optimization direction. Only for dimension = 0 and returns Minimize. More...

float	getLowerLimit (int i) const override
	Get the lower bound of the search space (1). More...

string	getName () const override
	Get the name of the problem. More...

const vector< vector< float > > &	getDistances () const
	Get the matrix of distances between each city in the instance. More...

const vector< coords > &	getPoints () const
	Get the points of the instances as coordinates. More...

const std::string	getPathToInstance () const
	Get the path to the instance if used. More...

void	evaluate (IntFloatSolution &solution) const override
	Evaluates a solution to the TSP. More...

bool	evaluateConstraints (IntFloatSolution &solution) const override
	Evaluates whether a solution is feasible of not regarding to the TSP formulation. More...

IntFloatSolution	createSolution () const override
	Creates and return a random solution for the TSP. More...

IntFloatSolution	createSolution (ParallelPRNG &engine) const override
	Creates and return a random solution for the TSP. More...

void	readData (const string &path) override
	Reads the instance information from the filesystem. More...

json	to_json () const override
	Creates and return the JSON representation of the TSP problem. More...

Public Member Functions inherited from Problem< IntFloatSolution >
	Problem ()
	Creates a new Problem with all parameters to zero. More...

	Problem (const int &numberOfVars, const int &numberOfObjectives, const int &nCons)
	Construct a new Problem with all the given parameters. More...

	Problem (const Problem *copy)

virtual void	readData (const std::string &path)=0
	Method to read problem information from the given path. This method must be implemented in the subclasses. More...

int	getNumberOfVars () const
	Get the number of variables (dimension) of the problem. More...

void	setNumberOfVars (int nVars)
	Sets the number of variables (dimension) of the problem. More...

int	getNumberOfObjs () const
	Get the number of objectives of the problem. More...

void	setNumberOfObjs (int nObjs)
	Sets the number of objectives to the problem. More...

int	getNumberOfCons () const
	Get the number the constraint of the problem. More...

void	setNumberOfCons (int nCons)
	Sets the number of constraint of the problem. More...

Protected Member Functions
void	computeDistances ()
	Computes the distance from each point to the other in the instance.

Protected Attributes
std::string	pathToInstance

vector< coords >	points

vector< vector< float > >	distances

Protected Attributes inherited from Problem< IntFloatSolution >
int	numberOfVars

int	numberOfObjs

int	numberOfCons

Detailed Description

Traveling Salesman Problem implemented in dignea. Uses a IntFloat representation where the solutions are integers in a permutation-based approach and the fitness is a float with the cost of a travel.

Constructor & Destructor Documentation

◆ TSP() [1/5]

TSP::TSP ( )

Creates a default TSP object.

Construct a new TSP::TSP object.

◆ TSP() [2/5]

TSP::TSP ( const int & numberOfVars )

explicit

Creates a TSP object with a predefined number of cities.

Construct a new TSP::TSP object.

Parameters

numberOfVars	Cities in include in the instance
numberOfVars

◆ TSP() [3/5]

TSP::TSP	(	const int &	numberOfVars,
		const vector< coords > &	coordinates
	)

explicit

Creates a TSP object with a predefined number of cities and the coordinates for each one.

Construct a new TSP::TSP object.

Parameters

numberOfVars
coordinates

◆ TSP() [4/5]

TSP::TSP ( const string & path )

Creates a TSP object which loads the data from the filesystem.

Parameters

pathToInstance

Crea una instancia del TSP a partir de la instancia en el directorio recibido

Parameters

pathTo

◆ TSP() [5/5]

TSP::TSP ( TSP const * tsp )

Creates a TSP copying the information from other instance.

Construct a new TSP::TSP object.

Parameters

other
tsp

Member Function Documentation

◆ createSolution() [1/2]

IntFloatSolution TSP::createSolution ( ) const

overridevirtual

Creates and return a random solution for the TSP.

Creates a new solution for the TSP.

Returns: IntFloatSolution

Implements Problem< IntFloatSolution >.

◆ createSolution() [2/2]

IntFloatSolution TSP::createSolution ( ParallelPRNG & engine ) const

overridevirtual

Creates and return a random solution for the TSP.

Creates a solution for the TSP using a Parallel RNG.

Deprecated:

Returns

Parameters

engine

Returns: IntFloatSolution

Implements Problem< IntFloatSolution >.

◆ evaluate()

void TSP::evaluate ( IntFloatSolution & solution ) const

overridevirtual

Evaluates a solution to the TSP.

Parameters

solution

Metodo de evaluacion de una solucion al problema KP

Parameters

solution

Implements Problem< IntFloatSolution >.

◆ evaluateConstraints()

bool TSP::evaluateConstraints ( IntFloatSolution & solution ) const

overridevirtual

Evaluates whether a solution is feasible of not regarding to the TSP formulation.

Evaluates whether the solution does not contain a point more than once Also checks that the solution starts and ends in the first city (aka point 0)

Parameters

solution

Returns: True if the solution is feasible, false otherwise.

Parameters

solution

Returns: true; false

Implements Problem< IntFloatSolution >.

◆ getDistances()

const vector<vector<float> >& TSP::getDistances ( ) const

inline

Get the matrix of distances between each city in the instance.

Returns: Vector of vectors of float with all distances

◆ getLowerLimit()

float TSP::getLowerLimit ( int i ) const

overridevirtual

Get the lower bound of the search space (1).

Gets lower limit for TSP. In this case it's fixed to 1.

Parameters

i

Returns

Parameters

i

Returns: float

Implements Problem< IntFloatSolution >.

◆ getName()

string TSP::getName ( ) const

inlineoverridevirtual

Get the name of the problem.

Returns: A string with the TSP acronym

Implements Problem< IntFloatSolution >.

◆ getOptimizationDirection()

int TSP::getOptimizationDirection ( const int i ) const

overridevirtual

Get the optimization direction. Only for dimension = 0 and returns Minimize.

Parameters

i

Returns

Implements Problem< IntFloatSolution >.

◆ getPathToInstance()

const std::string TSP::getPathToInstance ( ) const

inline

Get the path to the instance if used.

Returns: String with the location of the filesystem of the instance

◆ getPoints()

const vector<coords>& TSP::getPoints ( ) const

inline

Get the points of the instances as coordinates.

Returns: Vector of coordinates

◆ getUpperLimit()

float TSP::getUpperLimit ( int i ) const

overridevirtual

Get the upper bound of the search space. In this case the upper bound is the number of variables minus one since the starting city is duplicated at the end of the travel.

Gets upper limit for TSP which it's the amount of available cities in the instance.

Parameters

i

Returns

Parameters

i

Returns: float

Implements Problem< IntFloatSolution >.

◆ readData()

void TSP::readData ( const string & path )

override

Reads the instance information from the filesystem.

Parameters

path

Método para leer un fichero de instancia del KP. La estructura esperada del fichero es la siguiente: nItems Q w0 p0 w1 p1 ... wn-1 pn-1

Parameters

path

◆ to_json()

json TSP::to_json ( ) const

overridevirtual

Creates and return the JSON representation of the TSP problem.

Returns

Generates a JSON object with the information of the KP problem

Returns

Reimplemented from Problem< IntFloatSolution >.

Member Data Documentation

◆ distances

vector<vector<float> > TSP::distances

protected

Distance matrix

◆ pathToInstance

std::string TSP::pathToInstance

protected

Path to the instance file

◆ points

vector<coords> TSP::points

protected

Coordinates of cities (points)

The documentation for this class was generated from the following files:

include/dignea/problems/TSP.h
src/dignea/problems/TSP.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TSP() [1/5]

◆ TSP() [2/5]

◆ TSP() [3/5]

◆ TSP() [4/5]

◆ TSP() [5/5]

Member Function Documentation

◆ createSolution() [1/2]

◆ createSolution() [2/2]

◆ evaluate()

◆ evaluateConstraints()

◆ getDistances()

◆ getLowerLimit()

◆ getName()

◆ getOptimizationDirection()

◆ getPathToInstance()

◆ getPoints()

◆ getUpperLimit()

◆ readData()

◆ to_json()

Member Data Documentation

◆ distances

◆ pathToInstance

◆ points