Info

The random descent and parallel tempering algorithms are applied to optimize the round trip. Don't know what random descent is? Read this. Never heard about parallel tempering? Read this.

This example demonstrates how to implement and solve a basic symmetric travelling salesman problem (TSP). The problem consists of finding the shortest round trip that visits a number of given cities, each exactly once, returning to the city where the tour started. For symmetric TSP, it is assumed that the travel distance from city a to b is equal to that from b to a. The input consists of a (symmetric) distance matrix containing the travel distance between each pair of cities. The goal is to find the optimal order in which to visit the cities so that the total travel distance is minimzed.

When defining a custom problem, the first step is to design the corresponding solution type. Here we create a `TSPSolution` class that models a solution to the TSP problem as a list of cities, in the order in which they are visited. Each of the N cities is represented by a unique number in [0, N-1]. In JAMES, it is required that all solution types extend the abstract `Solution` class, which has three required abstract methods to implement:

1. `Solution copy()`: creates a deep copy of the solution. It is important that the returned copy is of exactly the same type as the original solution. As it is allowed to confine the return type to a subtype when overriding a method, we may set it to `TSPSolution` here. In this example, the list of cities is copied and wrapped in a new `TSPSolution`.
2. `boolean equals(Object)`: the default reference-based implementation from `Object` has been erased so that it is required to provide an appropriate equality check for every defined solution type. It is important that solutions are compared based on their contents (value-based) to guarantee correct behaviour of all optimization algorithms. In this example, the list of cities is compared (given that the other object is also a `TSPSolution`).
3. `int hashCode()`: as always, it is required to provide a hash code computation in line with the custom equality definition. Here, a hash code is inferred from the list of cities.
A method `swapCities(i, j)` is also provided, to swap the two cities at the given positions. This will be used later to modify solutions during optimization.

```public class TSPSolution extends Solution {

// list of cities in the order in which they are visited
private List<Integer> cities;

public TSPSolution(List<Integer> cities){
this.cities = cities;
}

public List<Integer> getCities(){
return cities;
}

// swap the i-th and j-th city in the round trip
public void swapCities(int i, int j){
Collections.swap(cities, i, j)
}

@Override
public TSPSolution copy() {
return new TSPSolution(new ArrayList<>(cities));
}

@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final TSPSolution other = (TSPSolution) obj;
return Objects.equals(this.cities, other.cities);
}

@Override
public int hashCode() {
return Objects.hashCode(cities);
}

}
```

We can now define the problem. The framework includes a `Problem` interface, which is parameterized on the solution type, in this case our newly introduced `TSPSolution`. The problem is responsible for evaluating and validating solutions, as well as generating random solutions, which are for example used as the default initial solutions of applied local searches. To facilitate problem specification, a predefined `GenericProblem` is provided, which is composed of data, an objective (for evaluation), possibly some constraints (for validation) and a random solution generator. A generic problem is parameterized on both the solution and data type. It is advised to use this class when defining new problems, instead of directly implementing the `Problem` interface, as demonstrated in this example.

Modelling constraints

The basic TSP problem which is solved here does not have any constraints. To learn about modelling constraints in JAMES, see examples 2A and 2B.

Data is stored in a separate class and accessed by the other problem components to evaluate, validate and generate random solutions. For our basic TSP problem, the data consists of a (symmetric) distance matrix containing the travel distance between each pair of cities. The numbers assigned to the cities correspond to the row and column indices in this matrix. The data type of a problem is not confined in any way, i.e. it is not required to implement a certain interface or extend an (abstract) class. Here, we create a `TSPData` class that wraps the travel distance matrix. Methods are provided to retrieve the distance between two cities and the number of cities.

```public class TSPData {

// travel distance matrix
private double[][] dist;

public TSPData(double[][] dist) {
this.dist = dist;
}

// get travel distance between two cities
public double getDistance(int from, int to){
return dist[from][to];
}

// retrieve number of cities
public int getNumCities(){
return dist.length;
}

}
```

The objective is used to evaluate solutions generated during optimization. It also informs the search whether the computed values are to be maximized or minimized. To provide the objective, implement the `Objective` interface, which is parameterized on the solution and data type of the problem. Here, a solution is evaluated by computing the total travel distance resulting from visiting the cities in the order specified in the solution. The computed value is wrapped in a `SimpleEvaluation`. Since the travel distance is to be minimized, the method `isMinimizing()` returns `true`.

Evaluation type

For many problems, it is sufficient to wrap the computed value in a `SimpleEvaluation` as shown in this example. To understand when and why it may be necessary to define a custom evaluation type, see example 1C.
```public class TSPObjective implements Objective<TSPSolution, TSPData>{

public Evaluation evaluate(TSPSolution solution, TSPData data) {
// compute sum of travel distances
List<Integer> cities = solution.getCities();
int n = cities.size();
double totalDistance = 0.0;
for(int i=0; i<n; i++){
int fromCity = cities.get(i);
int toCity = cities.get((i+1)%n);
totalDistance += data.getDistance(fromCity, toCity);
}
// wrap in simple evaluation
return SimpleEvaluation.WITH_VALUE(totalDistance);
}

public boolean isMinimizing() {
return true;
}

}
```

By default, all local searches in JAMES start from a random solution. It is therefore required to specify how such random solutions are to be obtained, by implementing the `RandomSolutionGenerator` interface. Again, this interface is parameterized on the solution and data type of the problem. It contains a single method `create(rnd, data)` to create a random solution, using the given source of randomness and the problem data. The implementation can be compactly defined as a Java 8 lambda expression, as shown below. To create a random solution for our TSP problem, a list with all city numbers [0, N-1] is constructed, shuffled and wrapped in a `TSPSolution` object.

Info

For some problems, it may not be possible to generate random solutions. A custom initial solution should then be provided when applying a local search. See example 3.

Info

The method `create(rnd, data)` takes a random generator as its first argument, which should be used as the source of randomness. Each search has a dedicated random generator, which is passed to the problem when requesting a random solution. If desired, a search's random generator can be customized with `search.setRandom(rnd)`.
```RandomSolutionGenerator<TSPSolution, TSPData> rsg = (r,d) -> {
// create random permutation of cities
List<Integer> cities = new ArrayList<>();
int n = d.getNumCities();
for(int i=0; i<n; i++){
}
Collections.shuffle(cities, r);
// create and return TSP solution
return new TSPSolution(cities);
};
```

We can now combine all components in a `GenericProblem`.

```// define distance matrix (e.g. read from file)
double[][] dist = ...

// create data
TSPData data = new TSPData(dist);
// create objective
TSPObjective obj = new TSPObjective();
// create random solution generator
RandomSolutionGenerator<TSPSolution, TSPData> rsg = ... // see before

// wrap in generic problem
Problem<TSPSolution> problem = new GenericProblem<>(data, obj, rsg);
```

To be able to apply the available neighbourhood searches we have to provide at least one neighbourhood for the new `TSPSolution` type. Here we create a neighbourhood that reverses a subsequence of cities in a given solution, by performing a series of swaps. This is often referred to as a 2-opt move in the context of (symmetric) TSP. All distances except the two at the border of the reversed subsequence are retained. The latter two are replaced by two other distances.

First, provide the corresponding move by implementing the `Move` interface with solution type `TSPSolution`. This interface has two methods: one to apply the move and one to undo it after it has been applied to a solution. This specific move can be undone by again reversing the subsequence with the exact same code as for applying the move.

```public class TSP2OptMove implements Move<TSPSolution> {

// city positions i,j between which the path is reversed as follows:
// ... - (a) - (c_1) - (c_2)   - ... - (c_n-1) - (c_n) - (b) - ...
//               i                                 j
//  =>
// ... - (a) - (c_n) - (c_n-1) - ... - (c_2)   - (c_1) - (b) - ...
//               i                                 j
private final int i, j;

public TSP2OptMove(int i, int j) {
// check
if(i == j){
throw new IllegalArgumentException("Error: i and j should be distinct positions.");
}
// store
this.i = i;
this.j = j;
}

public int getI(){
return i;
}

public int getJ(){
return j;
}

@Override
public void apply(TSPSolution solution) {
// reverse subsequence of cities
int start = i;
int stop = j;
int n = solution.getCities().size();
int reversedLength;
if(i < j){
reversedLength = j-i+1;
} else {
reversedLength = n - (i-j-1);
}
int numSwaps = reversedLength/2;
for(int k=0; k<numSwaps; k++){
solution.swapCities(start, stop);
start = (start+1) % n;
stop = (stop-1+n) % n;
}
}

@Override
public void undo(TSPSolution solution) {
// undo by reversing again
apply(solution);
}

}
```

Then, create the neighbourhood itself by implementing the `Neighbourhood` interface, again with solution type `TSPSolution`. A neighbourhood has two methods: one to create a random move and one to obtain a list of all possible moves. Here, both methods create moves of type `TSP2OptMove`.

Info

The method `getRandomMove(solution, rnd)` takes a random generator as its second argument, which should be used as the source of randomness. Each search has a dedicated random generator, which is passed to the neighbourhood when requesting a random move. If desired, a search's random generator can be customized with `search.setRandom(rnd)`.
```public class TSP2OptNeighbourhood implements Neighbourhood<TSPSolution>{

public TSP2OptMove getRandomMove(TSPSolution solution, Random rnd) {
// pick two distinct random positions i,j in the round trip
int n = solution.getCities().size();
int i = rnd.nextInt(n);
int j = rnd.nextInt(n-1);
if(j >= i){
j++;
}
// return 2-opt TSP move that reverses path from position i to j
return new TSP2OptMove(i, j);
}

public List<TSP2OptMove> getAllMoves(TSPSolution solution) {
// generate a 2-opt TSP move for every pair of positions i,j
int n = solution.getCities().size();
List<TSP2OptMove> moves = new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i != j){
}
}
}
return moves;
}

}
```

It is strongly advised (although optional) to also specify an efficient delta evaluation as part of the objective, exploiting the knowledge that a new solution is obtained by reversing a subsequence in the previous solution. This can be done by overriding the method `evaluate(move, curSolution, curEvaluation, data)` in the objective. Without this custom delta evaluation, moves are evaluated by applying them to the current solution, followed by a full evaluation, and finally undoing the applied move. The delta evaluation provided here is of course much more efficient. This will cause the applied neighbourhood searches to run significantly faster.

```public class TSPObjective implements Objective<TSPSolution, TSPData>{

// see before ...

@Override
public Evaluation evaluate(Move move, TSPSolution curSolution, Evaluation curEvaluation, TSPData data){

// check move type
if(!(move instanceof TSP2OptMove)){
throw new IncompatibleDeltaEvaluationException("Delta evaluation in TSP objective expects move of type TSP2OptMove.");
}
// cast move
TSP2OptMove move2opt = (TSP2OptMove) move;
// get bounds of reversed subsequence
int i = move2opt.getI();
int j = move2opt.getJ();
// get number of cities
int n = data.getNumCities();

if((j+1)%n == i){
// special case: entire round trip reversed
return curEvaluation;
} else {
// get current total travel distance
double totalDistance = curEvaluation.getValue();
// get current order of cities
List<Integer> cities = curSolution.getCities();

// get crucial cities (at boundary of reversed subsequence)
int beforeReversed = cities.get((i-1+n)%n);
int firstReversed = cities.get(i);
int lastReversed = cities.get(j);
int afterReversed = cities.get((j+1)%n);

// account for dropped distances
totalDistance -= data.getDistance(beforeReversed, firstReversed);
totalDistance -= data.getDistance(lastReversed, afterReversed);

// account for new distances
totalDistance += data.getDistance(beforeReversed, lastReversed);
totalDistance += data.getDistance(firstReversed, afterReversed);

// return updated travel distance
return SimpleEvaluation.WITH_VALUE(totalDistance);
}

}

// see before ...

}
```

Applying an optimization algorithm is now done in exactly the same way as for subset selection problems (see subset selection examples). After the problem has been created, it is passed to a search that attempts to find a round trip with minimum total travel distance using the provided 2-opt neighbourhood. Example code is shown below for the basic random descent as well as the advanced parallel tempering algorithms.

A random descent search is simple, fast and does not have any additional parameters.

```// create random descent search with TSP neighbourhood
LocalSearch<TSPSolution> randomDescent = new RandomDescent<>(problem, new TSP2OptNeighbourhood());
// set maximum runtime
long timeLimit = ...
// attach listener (see example 1A)

// start search
randomDescent.start();

// print results
if(randomDescent.getBestSolution() != null){
System.out.println("Best round trip: " + randomDescent.getBestSolution().getCities());
System.out.println("Best round trip travel distance: " + randomDescent.getBestSolutionEvaluation());
} else {
System.out.println("No valid solution found...");
}

// dispose
randomDescent.dispose();
```

To be able to escape from local optima, more advanced techniques such as parallel tempering might be needed. When using the parallel tempering algorithm, it is important to set an appropriate temperature range (also see examples 1C and 2A) taking into account the scale of the evaluations. In particular, the probability to accept an inferior move is determined based on the ratio of the difference in evaluation (delta) and the temperature of the system. Here, the scale of the expected deltas depends on that of the distances between cities. Therefore, temperatures are scaled according to the average travel distance between each city and the closest other city. Alternatively, we could have rescaled the distances.

The (unscaled) temperature range was refined to [10-8, 0.6] using the analysis workflow, based on experiments with a number of TSPLIB instances. A detailed demonstration of how this can be done, for a different problem (core subset selection), is provided in example 5A.

```// set temperature range, scaled according to average
// distance between cities and their nearest neighbours
double scale = computeAvgNearestNeighbourDistance(data);
double minTemp = scale * 1e-8;
double maxTemp = scale * 0.6;
// create parallel tempering search with TSP neighbourhood
int numReplicas = 10;
ParallelTempering<TSPSolution> parallelTempering = new ParallelTempering<>(
problem,
new TSP2OptNeighbourhood(),
numReplicas, minTemp, maxTemp
);
```

The average travel distance between cities and their closest neighbour is easily computed.

```double computeAvgNearestNeighbourDistance(TSPData data){
int n = data.getNumCities();
double sum = 0.0;
for(int i=0; i<n; i++){
double min = Double.MAX_VALUE;
for(int j=0; j<n; j++) {
double dist = data.getDistance(i, j);
if(dist > 0.0 && dist < min){
min = dist;
}
}
sum += min;
}
return sum/n;
}
```

Running the parallel tempering search is now done in exactly the same way as for the random descent search. However, it is able to find much better solutions, i.e. round trips with a much lower total travel distance.

The complete source code of this example is available on GitHub, including some additional code to read the input from a text file. You can also download a ZIP file that contains the Java sources of all examples, a compiled JAR (including all dependencies) as well as some input files for in case you want to run any of the examples. To run this example, execute

```\$ java -cp james-examples.jar org.jamesframework.examples.tsp.TSP <inputfile> <runtime>
```

from the command line. The first line of the input file contains a single integer value (possibly surrounded by whitespace) that indicates the number of cities N. The remainder of the file contains the entries of the lower triangular part of an N × N symmetric distance matrix (row-wise without diagonal entries), separated by whitespace and/or newlines. The runtime is given in seconds.

The example input files correspond to instances gr17, gr48, gr120 and pa561, respectively, from the TSPLIB benchmark set.