1. Home
2. Examples
3. Travelling salesman problem (2)

Example 4B: The travelling salesman problem (2)

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 solution type for permutation problems

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

}

A generic permutation problem

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.

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

}

Permutation neighbourhood and corresponding move

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.

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

}

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

}

TSP Data and objective

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

}

Optimizing the round trip

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

Other permutation problems

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.

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