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:
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
.
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
).
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.
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.
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
.
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.
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++){ cities.add(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
.
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){ moves.add(new TSP2OptMove(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 = ... randomDescent.addStopCriterion(new MaxRuntime(timeLimit, TimeUnit.SECONDS)); // attach listener (see example 1A) randomDescent.addSearchListener(new ProgressSearchListener()); // 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.