newTSP: Generate a TSP problem environment
In xegaSelectGene: Selection of Genes and Gene Representation Independent Functions

newTSP

R Documentation

Generate a TSP problem environment

Description

newTSP() generates the problem environment for a traveling salesman problem (TSP).

Usage

newTSP(D, Name, Cities = NA, Solution = NA, Path = NA)

Arguments

`D`	A `n` x `n` distance matrix.
`Name`	The name of the problem environment.
`Cities`	The names of the cities.
`Solution`	Solution of problem (if known). Default: `NA`
`Path`	Optimal permutation of cities (if known). As integer vector. Default: `NA`.

Details

newTSP() provides several local permutation improvement heuristics: a greedy path of length k starting from city i, the best greedy path of length k, a random 2-Opt-move, and a sequence of random 2-Opt moves. They help to find bounds for the TSP or to implement special purpose mutation operators.

Value

A problem environment for the TSP.

$name() a string with the name of the environment
$cities() a vector length n of city names.
$dist() the n x n distance matrix between n cities.
$genelength() the size of the permutation n. E.g. for a TSP: the number of cities.
$f(permutation, gene, lF, tour=TRUE) the fitness function of the TSP. If tour==FALSE, the path length is computed (without the cost from city n to city 1).

With a permutation of size n as argument.
$show(p) shows tour through the cities in path p with its cost.
$greedy(startPosition, k) computes a k-step greedy minimal cost path beginning at the city start. For k+1=n the greedy solution gives an upper bound for the TSP.
$kBestGreedy(k, tour=TRUE) computes the best greedy subtour with k+1 cities. For tour=FALSE, the best greedy subpath with k+1 cities is computed.
$rnd2Opt(permutation, maxTries=5) returns a permutation improved by a single random 2-Opt-move after at most maxTries=5 attempts.
$LinKernighan(permutation, maxTries=5, show=FALSE) returns the best permutation found after several random 2-Opt-moves with at most maxTries=5 attempts. The loop stops after the first 2-Opt-move which does not improve the solution.
$solution() known optimal solution.
$path() known optimal round trip.
$max() FALSE.
$globalOptimum() a named list with the following elements:
- $param the optimal permutation.
- $value the known optimal solution.
- $is.minimum TRUE.

Examples

a<-matrix(0, nrow=15, ncol=15)
a[1,]<- c(0, 29, 82, 46, 68, 52, 72, 42, 51,  55,  29,  74,  23,  72,  46)
a[2,]<- c(29,  0, 55, 46, 42, 43, 43, 23, 23,  31,  41,  51,  11,  52,  21)
a[3,]<- c(82, 55,  0, 68, 46, 55, 23, 43, 41,  29,  79,  21,  64,  31,  51)
a[4,]<-c(46, 46, 68,  0, 82, 15, 72, 31, 62,  42,  21,  51,  51,  43,  64)
a[5,]<-c(68, 42, 46, 82,  0, 74, 23, 52, 21,  46,  82,  58,  46,  65,  23)
a[6,]<-c(52, 43, 55, 15, 74,  0, 61, 23, 55,  31,  33,  37,  51,  29,  59)
a[7,]<-c(72, 43, 23, 72, 23, 61,  0, 42, 23,  31,  77,  37,  51,  46,  33)
a[8,]<-c(42, 23, 43, 31, 52, 23, 42,  0, 33,  15,  37,  33,  33,  31,  37)
a[9,]<-c(51, 23, 41, 62, 21, 55, 23, 33,  0,  29,  62,  46,  29,  51,  11)
a[10,]<-c(55, 31, 29, 42, 46, 31, 31, 15, 29,  0,  51,  21,  41,  23,  37)
a[11,]<-c(29, 41, 79, 21, 82, 33, 77, 37, 62,  51,   0,  65,  42,  59,  61)
a[12,]<-c(74, 51, 21, 51, 58, 37, 37, 33, 46,  21,  65,   0,  61,  11,  55)
a[13,]<-c(23, 11, 64, 51, 46, 51, 51, 33, 29,  41,  42,  61,   0,  62,  23)
a[14,]<-c(72, 52, 31, 43, 65, 29, 46, 31, 51,  23,  59,  11,  62,   0,  59)
a[15,]<-c(46, 21, 51, 64, 23, 59, 33, 37, 11,  37,  61,  55,  23,  59,   0)
lau15<-newTSP(a, Name="lau15")
lau15$name()
lau15$genelength()
b<-sample(1:15, 15, FALSE)
lau15$f(b)
lau15$f(b, tour=TRUE)
lau15$show(b)
lau15$greedy(1, 14)
lau15$greedy(1, 1)

xegaSelectGene documentation built on April 16, 2025, 5:12 p.m.