1. Home
2. Examples
3. Travelling salesman problem

Example 4A: The travelling salesman problem

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.

Designing a solution type

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

}

Problem specification

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.

Providing the data

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

Specifying the objective

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.

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

}

Random solution generation

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.

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

Combining problem components

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

Providing a neighbourhood and corresponding move

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.

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

}

Efficient delta evaluation

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

}

Optimizing the round trip

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.

Full source code

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.

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