Traveling Salesman (TSP)

Principles learned

  • Add a list decision variable

  • Access the list elements with an “at” operator

  • Constrain the number of elements in the list with operator “count”

  • Access a multi-dimensional array with an “at” operator

  • Get the value of a list variable

Problem

../_images/tsp.svg

The traveling salesman problem is defined as follows: given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. The distance from node i to node j and the distance from node j to node i may be different.

Download the example


Data

The instances provided come from the TSPLib asymmetric TSP database. They follow the TSPLib explicit format. The number of cities is defined after the keyword “DIMENSION:” and the full distance matrix is defined after the keyword “EDGE_WEIGHT_SECTION”.

Program

This LocalSolver model is based on a list variable constrained to contain all cities. The ith element of the list variable corresponds to the index of the ith city visited in the tour. From this list we can directly obtain the distance between each pair of consecutive cities in the list plus the closing arc (from last city to first city). Note that we use here the 2-dimensional ‘at’ operator z <- A[x][y] defining z as the element (x,y) of matrix A, where x and y are integer expressions. This operator allows defining virtually any non-linear relationship between three variables x,y,z. We also use a function to apply the sum operator over the whole range of cities.

You can find at the end of this page a table with the known optimal results on the asymmetric TSPLib database. On average, LocalSolver 9.0 reaches a gap of 0.8% after 1 minute.

Execution:
localsolver tsp.lsp inFileName=instances/br17.atsp [lsTimeLimit=] [solFileName=]
use io;

/* Read instance data */
function input() {
    local usage = "Usage: localsolver tsp.lsp "
            + "inFileName=inputFile [lsTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;
    local inFile = io.openRead(inFileName);

    // The input files follow the TSPLib "explicit" format
    while (true) {
        local str = inFile.readln();
        if (str.startsWith("DIMENSION:")) {
            local dim = str.trim().split(":")[1];
            nbCities = dim.toInt();
        } else if (str.startsWith("EDGE_WEIGHT_SECTION")) {
            break;
        }
    }

    // Distance from i to j
    distanceWeight[0..nbCities - 1][0..nbCities - 1] = inFile.readInt();
}

/* Declare the optimization model */
function model() {
    // A list variable: cities[i] is the index of the ith city in the tour
    cities <- list(nbCities); 

    // All cities must be visited
    constraint count(cities) == nbCities;

    // Minimize the total distance
    obj <- sum(1..nbCities-1, i => distanceWeight[cities[i - 1]][cities[i]])
            + distanceWeight[cities[nbCities - 1]][cities[0]];

    minimize obj;
}

/* Parametrize the solver */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 5;  
}


/* Write the solution in a file */
function output() {
    if (solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println(obj.value);
    for [c in cities.value] 
        solFile.print(c, " ");
    solFile.println();
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python tsp.py instances\br17.atsp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_11_5/bin/python
python tsp.py instances/br17.atsp
import localsolver
import sys

if len(sys.argv) < 2:
    print("Usage: python tsp.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)


def read_elem(filename):
    with open(filename) as f:
        return [str(elem) for elem in f.read().split()]


with localsolver.LocalSolver() as ls:
    #
    # Read instance data
    #
    file_it = iter(read_elem(sys.argv[1]))

    # The input files follow the TSPLib "explicit" format
    for pch in file_it:
        if pch == "DIMENSION:":
            nb_cities = int(next(file_it))
        if pch == "EDGE_WEIGHT_SECTION":
            break

    # Distance from i to j
    dist_matrix_data = [[int(next(file_it)) for i in range(nb_cities)]
                        for j in range(nb_cities)]

    #
    # Declare the optimization model
    #
    model = ls.model

    # A list variable: cities[i] is the index of the ith city in the tour
    cities = model.list(nb_cities)

    # All cities must be visited
    model.constraint(model.count(cities) == nb_cities)

    # Create a LocalSolver array for the distance matrix in order to be able
    # to access it with "at" operators
    dist_matrix = model.array(dist_matrix_data)

    # Minimize the total distance
    dist_lambda = model.lambda_function(lambda i:
                                        model.at(dist_matrix, cities[i - 1], cities[i]))
    obj = model.sum(model.range(1, nb_cities), dist_lambda) \
        + model.at(dist_matrix, cities[nb_cities - 1], cities[0])
    model.minimize(obj)

    model.close()

    # Parameterize the solver
    if len(sys.argv) >= 4:
        ls.param.time_limit = int(sys.argv[3])
    else:
        ls.param.time_limit = 5

    ls.solve()

    #
    # Write the solution in a file
    #
    if len(sys.argv) >= 3:
        # Write the solution in a file
        with open(sys.argv[2], 'w') as f:
            f.write("%d\n" % obj.value)
            for c in cities.value:
                f.write("%d " % c)
            f.write("\n")
Compilation / Execution (Windows)
cl /EHsc tsp.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver115.lib
tsp instances\br17.atsp
Compilation / Execution (Linux)
g++ tsp.cpp -I/opt/localsolver_11_5/include -llocalsolver115 -lpthread -o tsp
./tsp instances/br17.atsp
#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>

using namespace localsolver;
using namespace std;

class Tsp {
public:
    // Number of cities
    int nbCities;

    // Vector of distance between two cities
    vector<vector<int>> distMatrixData;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variables
    LSExpression cities;

    // Objective
    LSExpression obj;

    /* Read instance data */
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        // The input files follow the TSPLib "explicit" format
        string str;
        char* pch;
        char* line;

        while (true) {
            getline(infile, str);
            line = strdup(str.c_str());
            pch = strtok(line, " :");
            if (strcmp(pch, "DIMENSION") == 0) {
                getline(infile, str);
                line = strdup(str.c_str());
                pch = strtok(NULL, " :");
                nbCities = atoi(pch);
            } else if (strcmp(pch, "EDGE_WEIGHT_SECTION") == 0) {
                break;
            }
        }

        // Distance from i to j
        distMatrixData.resize(nbCities);
        for (int i = 0; i < nbCities; ++i) {
            distMatrixData[i].resize(nbCities);
            for (int j = 0; j < nbCities; ++j) {
                infile >> distMatrixData[i][j];
            }
        }
    }

    void solve(int limit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // A list variable: cities[i] is the index of the ith city in the tour
        cities = model.listVar(nbCities);

        // All cities must be visited
        model.constraint(model.count(cities) == nbCities);

        // Create a LocalSolver array in order to be able to access it with "at" operators
        LSExpression distMatrix = model.array();
        for (int i = 0; i < nbCities; ++i) {
            LSExpression row = model.array(distMatrixData[i].begin(), distMatrixData[i].end());
            distMatrix.addOperand(row);
        }

        // Minimize the total distance
        LSExpression distLambda =
            model.createLambdaFunction([&](LSExpression i) { return model.at(distMatrix, cities[i - 1], cities[i]); });
        obj = model.sum(model.range(1, nbCities), distLambda) + model.at(distMatrix, cities[nbCities - 1], cities[0]);

        model.minimize(obj);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /* Write the solution in a file */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << obj.getValue() << endl;
        LSCollection citiesCollection = cities.getCollectionValue();
        for (int i = 0; i < nbCities; ++i) {
            outfile << citiesCollection[i] << " ";
        }
        outfile << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: tsp inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "5";
    try {
        Tsp model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Tsp.cs /reference:localsolvernet.dll
Tsp instances\br17.atsp
using System;
using System.IO;
using localsolver;

public class Tsp : IDisposable
{
    // Number of cities
    int nbCities;

    // Vector of distance between two cities
    long[][] distMatrixData;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variables
    LSExpression cities;

    // Objective
    LSExpression obj;

    public Tsp()
    {
        localsolver = new LocalSolver();
    }

    // Read instance data
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            // The input files follow the TSPLib "explicit" format
            string line;
            while ((line = input.ReadLine()) != null)
            {
                string[] splitted = line.Split(':');
                if (splitted[0].Contains("DIMENSION"))
                    nbCities = int.Parse(splitted[1]);
                else if (splitted[0].Contains("EDGE_WEIGHT_SECTION"))
                    break;
            }

            string[] matrixText = input
                .ReadToEnd()
                .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            distMatrixData = new long[nbCities][];
            for (int i = 0; i < nbCities; ++i)
            {
                distMatrixData[i] = new long[nbCities];
                for (int j = 0; j < nbCities; ++j)
                    distMatrixData[i][j] = long.Parse(matrixText[i * nbCities + j]);
            }
        }
    }

    public void Dispose()
    {
        if (localsolver != null)
            localsolver.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        LSModel model = localsolver.GetModel();

        // A list variable: cities[i] is the index of the ith city in the tour
        cities = model.List(nbCities);

        // All cities must be visited
        model.Constraint(model.Count(cities) == nbCities);

        // Create a LocalSolver array for the distance matrix in order to be able to access it with "at" operators
        LSExpression distMatrix = model.Array(distMatrixData);

        // Minimize the total distance
        LSExpression distLambda = model.LambdaFunction(i => distMatrix[cities[i - 1], cities[i]]);
        obj = model.Sum(model.Range(1, nbCities), distLambda) + distMatrix[cities[nbCities - 1], cities[0]];

        model.Minimize(obj);
        model.Close();

        // Parametrize the solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.Solve();
    }

    /* Write the solution in a file */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(obj.GetValue());
            LSCollection citiesCollection = cities.GetCollectionValue();
            for (int i = 0; i < nbCities; ++i)
                output.Write(citiesCollection.Get(i) + " ");
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Tsp inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "30";

        using (Tsp model = new Tsp())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac Tsp.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Tsp instances\br17.atsp
Compilation / Execution (Linux)
javac Tsp.java -cp /opt/localsolver_11_5/bin/localsolver.jar
java -cp /opt/localsolver_11_5/bin/localsolver.jar:. Tsp instances/br17.atsp
import java.util.*;
import java.io.*;
import localsolver.*;

public class Tsp {
    // Number of cities
    private int nbCities;

    // Vector of distance between two cities
    private long[][] distMatrixData;

    // LocalSolver
    private final LocalSolver localsolver;

    // Decision variables
    private LSExpression cities;

    // Objective
    private LSExpression obj;

    private Tsp(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            // The input files follow the TSPLib "explicit" format
            String str = new String();
            String[] pch = new String[2];
            int i = 0;
            while (true) {
                str = input.nextLine();
                pch = str.split(":");
                if (pch[0].compareTo("DIMENSION") == 0) {
                    nbCities = Integer.parseInt(pch[1].trim());
                    System.out.println("Number of cities = " + nbCities);
                } else if (pch[0].compareTo("EDGE_WEIGHT_SECTION") == 0) {
                    break;
                }
            }

            // Distance from i to j
            distMatrixData = new long[nbCities][nbCities];
            for (i = 0; i < nbCities; ++i) {
                for (int j = 0; j < nbCities; ++j) {
                    distMatrixData[i][j] = input.nextInt();
                }
            }
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // A list variable: cities[i] is the index of the ith city in the tour
        cities = model.listVar(nbCities);

        // All cities must be visited
        model.constraint(model.eq(model.count(cities), nbCities));

        // Create a LocalSolver array for the distance matrix in order to be able to
        // access it with "at" operators
        LSExpression distMatrix = model.array(distMatrixData);

        // Minimize the total distance
        LSExpression distLambda = model
            .lambdaFunction(i -> model.at(distMatrix, model.at(cities, model.sub(i, 1)), model.at(cities, i)));
        obj = model.sum(model.sum(model.range(1, nbCities), distLambda),
            model.at(distMatrix, model.at(cities, nbCities - 1), model.at(cities, 0)));

        model.minimize(obj);
        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /* Write the solution in a file */
    void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
            output.println(obj.getValue());
            LSCollection citiesCollection = cities.getCollectionValue();
            for (int i = 0; i < nbCities; ++i) {
                output.print(citiesCollection.get(i) + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java Tsp inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "5";

        try (LocalSolver localsolver = new LocalSolver()) {
            Tsp model = new Tsp(localsolver);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}

Known optimal solutions

The known optimal solutions of the asymmetric instances of the TSPLib are listed below:

Instance

Optimum

br17

39

ft53

6905

ft70

38673

ftv33

1286

ftv35

1473

ftv38

1530

ftv44

1613

ftv47

1776

ftv55

1608

ftv64

1839

ftv70

1950

ftv170

2755

kro124

36230

p43

5620

rbg323

1326

rbg358

1163

rbg403

2465

rbg443

2720

ry48p

14422