#### Info

The parallel tempering algorithm is applied to optimize the round trip. Don't know what parallel tempering is? Read this.

This example reconsiders the travelling salesman problem from example 4A. TSP is actually a permutation problem: the goal is to find the best permutation of cities so that visiting them in this order yields the lowest possible total travel distance. Part of the implementation for TSP will likely be the same for various other permutation problems. In that respect, it may be useful to design generic components that can be reused for any permutation problem. TSP can then be implemented by plugging in the necessary data and objective.

All reusable permutation problem components defined here have been made available in the JAMES extensions module.

A permutation problem consists of finding an optimal order of a list of items. Thus, a solution indicates a specific order of these items. We will assume that every item is identified with a unique integer ID. This assumption is imposed later when defining a generic permutation problem, by restricting the allowed data type (see below). A `PermutationSolution` reflects an ordered list of these IDs. Its implementation is very similar to that of the `TSPSolution` from example 4A.

```public class PermutationSolution extends Solution {

// ordered sequence of IDs
private List<Integer> order;

public PermutationSolution(List<Integer> order) {
this.order = order;
}

public List<Integer> getOrder(){
return order;
}

public int size(){
return order.size();
}

public void swap(int i, int j){
int tmp = order.get(i);
order.set(i, order.get(j));
order.set(j, tmp);
}

@Override
public PermutationSolution copy() {
return new PermutationSolution(new ArrayList<>(order));
}

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

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

}
```

Now we can define a generic, reusable permutation problem. It extends `GenericProblem`, fixing the solution type to `PermutationSolution` and the data type to any implementation of the `IntegerIdentifiedData` interface (also used for subset problems). The latter imposes that every item in the data set is assigned a unique integer ID, as assumed by the solution representation (see before).

A default random solution generator is set when creating a permutation problem. Its implementation is very similar to that of the random solution generator from example 4A. The IDs of the items in the data set are retrieved from the data object. Since the `RandomSolutionGenerator` interface has a single method `create(rnd, data)` it can be compactly specified as a Java 8 lambda expression, as shown here.

#### Info

The method `create(rnd, data)` of `RandomSolutionGenerator` 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 solutionn. If desired, a search's random generator can be customized with `search.setRandom(rnd)`.
```public class PermutationProblem<DataType extends IntegerIdentifiedData> extends GenericProblem<PermutationSolution, DataType>{

public PermutationProblem(DataType data, Objective<? super PermutationSolution, ? super DataType> objective) {
// pass data and objective to super class; specify random solution generator
super(data, objective, (r,d) -> {
// create list with all IDs
List<Integer> ids = new ArrayList<>(d.getIDs());
// shuffle IDs
Collections.shuffle(ids, r);
// create and return permutation solution
return new PermutationSolution(ids);
});
}

}
```

To be able to apply neighbourhood searches to solve permutation problems, we need to provide at least one neighbourhood for the newly defined `PermutationSolution`. Here we create a `ReverseSubsequenceNeighbourhood` and corresponding move, similar to the `TSP2OptNeighbourhood` and move introduced in example 4A.

#### Info

The extensions module contains several permutation neighbourhoods among which this `ReverseSubsequenceNeighbourhood`. Of course, custom neighbourhoods can also be defined when needed for specific permutation problems.
```public class ReverseSubsequenceMove implements Move<PermutationSolution>{

// first and last position of subsequence that will be reversed
private int from, to;

public ReverseSubsequenceMove(int from, int to) {
this.from = from;
this.to = to;
}

public int getFrom(){
return from;
}

public int getTo(){
return to;
}

@Override
public void apply(PermutationSolution solution) {
int start = from;
int stop = to;
int n = solution.size();
// reverse subsequence by performing a series of swaps
// (works cyclically when start > stop)
int reversedLength;
if(start < stop){
reversedLength = stop-start+1;
} else {
reversedLength = n - (start-stop-1);
}
int numSwaps = reversedLength/2;
for(int k=0; k<numSwaps; k++){
solution.swap(start, stop);
start = (start+1) % n;
stop = (stop-1+n) % n;
}
}

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

}
```

#### 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 ReverseSubsequenceNeighbourhood implements Neighbourhood<PermutationSolution>{

public ReverseSubsequenceMove getRandomMove(PermutationSolution solution, Random rnd) {
int n = solution.size();
// check: move possible
if(n < 2){
return null;
}
// pick two random, distinct positions
int i = rnd.nextInt(n);
int j = rnd.nextInt(n-1);
if(j >= i){
j++;
}
// generate move
return new ReverseSubsequenceMove(i, j);
}

@Override
public List<ReverseSubsequenceMove> getAllMoves(PermutationSolution solution) {
// initialize list
List<ReverseSubsequenceMove> moves = new ArrayList<>();
int n = solution.size();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i != j){
moves.add(new ReverseSubsequenceMove(i, j));
}
}
}
return moves;
}

}
```

The generic permutation problem components can now be used to implement and solve TSP. We simply define the data and objective and wrap these in a `PermutationProblem`. As in example 4A, the data contains the distance matrix. It now implements the `IntegerIdentifiedData` interface, as required by the permutation problem definition. The IDs assigned to each city correspond to the row and column indices in the distance matrix and are automatically inferred.

```public class TSPData implements IntegerIdentifiedData {

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

// set of IDs
private final Set<Integer> ids;

public TSPData(double[][] dist) {
// infer IDs
ids = new HashSet<>();
for(int i=0; i<dist.length; i++){
ids.add(i);
}
// store distance matrix
this.dist = dist;
}

@Override
public Set<Integer> getIDs() {
return ids;
}

// get travel distance from the given city to the given other city
public double getDistance(int from, int to){
return dist[from][to];
}

}
```

The objective evaluates a permutation solution by computing the total travel distance of the round trip that visits cities in the order in which they occur in the permutation. The implementation is almost identical to that of the objective from example 4A. It also includes an efficient delta evaluation for the applied move type. The solution type is set to `PermutationSolution` and the data type to `TSPData`.

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

public Evaluation evaluate(PermutationSolution solution, TSPData data) {
// compute sum of travel distances
List<Integer> cities = solution.getOrder();
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 Evaluation evaluate(Move move, PermutationSolution curSolution, Evaluation curEvaluation, TSPData data){

// check move type
if(!(move instanceof ReverseSubsequenceMove)){
throw new IncompatibleDeltaEvaluationException("Delta evaluation in "
+ "TSP objective expects move of type ReverseSubsequenceMove.");
}
// cast move
ReverseSubsequenceMove move2opt = (ReverseSubsequenceMove) move;
// get bounds of reversed subsequence
int from = move2opt.getFrom();
int to = move2opt.getTo();
// get number of cities
int n = curSolution.size();

if((to+1)%n == from){
// 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.getOrder();

// get crucial cities (at boundary of reversed subsequence)
int beforeReversed = cities.get((from-1+n)%n);
int firstReversed = cities.get(from);
int lastReversed = cities.get(to);
int afterReversed = cities.get((to+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);
}

}

public boolean isMinimizing() {
return true;
}

}
```

We can apply a parallel tempering algorithm in the same way as in example 4A. The problem is now a `PermutationProblem` that contains the TSP data and objective. The generic `ReverseSubsequenceNeighbourhood` is used, which corresponds to a 2-opt neighbourhood in the context of TSP.

```// create distance matrix (e.g. read from a file)
double[][] dist = ...
// create data
TSPData data = new TSPData(dist);
// create objective
TSPObjective obj = new TSPObjective();

// wrap data and objective in a permutation problem
PermutationProblem<TSPData> problem = new PermutationProblem<>(data, obj);

// 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 neighbourhood that reverses a subsequence (2-opt move)
int numReplicas = 10;
ParallelTempering<PermutationSolution> parallelTempering = new ParallelTempering<>(
problem,
new ReverseSubsequenceNeighbourhood(),
numReplicas, minTemp, maxTemp
);

// set maximum runtime
long timeLimit = ...
parallelTempering.addStopCriterion(new MaxRuntime(timeLimit, TimeUnit.SECONDS));
// attach listener (see example 1A)
parallelTempering.addSearchListener(new ProgressSearchListener());

// start search
parallelTempering.start();

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

// dispose
parallelTempering.dispose();
```

The average travel distance between each city and its closest neighbour is easily computed, which is used as scale factor for the temperatures (see example 4A to understand why).

```double computeAvgNearestNeighbourDistance(TSPData data){
Set<Integer> ids = data.getIDs();
double sum = 0.0;
for(int id1 : ids){
double min = Double.MAX_VALUE;
for(int id2 : ids) {
double dist = data.getDistance(id1, id2);
if(dist > 0.0 && dist < min){
min = dist;
}
}
sum += min;
}
int n = ids.size();
return sum/n;
}
```

The advantage of this approach over that from example 4A is that, with very little additional effort, other permutation problems can now also be defined and solved using the provided solution type, problem class and neighbourhood(s). These reusable components have been added to the JAMES extensions module. Source code is found on GitHub.

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.tsp2.TSP2 <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.