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.

`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.

`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); } }

`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.

- Example input file (17 cities)
- Example input file (48 cities)
- Example input file (120 cities)
- Example input file (561 cities)

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