Travelling salesman problem

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

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 7.0 reaches a gap of 1% after 1 minute.

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

use io;

/* Reads 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();
}

/* Declares 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;
}

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


/* Writes 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\python27\
python tsp.py instances\br17.atsp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python tsp.py instances/br17.atsp
########## tsp.py ##########

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:

    #
    # Reads instance data 
    #

    file_it = iter(read_elem(sys.argv[1]))

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

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

    #
    # Declares 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.
    distance_array = model.array(distance_weight)

    # Minimize the total distance
    dist_selector = model.function(lambda i: model.at(distance_array, cities[i-1], cities[i]))
    obj = (model.sum(model.range(1, nb_cities), dist_selector)
            + model.at(distance_array, cities[nb_cities - 1], cities[0]));
    model.minimize(obj)

    model.close()

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

    ls.solve()

    #
    # Writes the solution in a file
    #
    if len(sys.argv) >= 3:
        # Writes 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\localsolver.dll.lib
tsp instances\br17.atsp
Compilation / Execution (Linux)
g++ tsp.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o tsp
./tsp instances/br17.atsp
/********** tsp.cpp **********/

#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

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

    // Vector of distance between two cities
    vector<vector<lsint> > distanceWeight;

    // LocalSolver.
    LocalSolver localsolver;

    // Decision variables.
    LSExpression cities;

    // Objective
    LSExpression obj;

    /* Reads 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
        distanceWeight.resize(nbCities);
        for(int i = 0; i < nbCities; i++) {
            distanceWeight[i].resize(nbCities);
            for (int j = 0; j < nbCities; j++) {
                infile >> distanceWeight[i][j];
            }
        }       
    }

    void solve(int limit) {
        // Declares 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 for the distance matrix in order to be able to 
        // access it with "at" operators.
        LSExpression distanceArray = model.array();
        for(int i = 0; i < nbCities; i++){
            LSExpression row = model.array(distanceWeight[i].begin(), distanceWeight[i].end());
            distanceArray.addOperand(row);
        }

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

        model.minimize(obj);

        model.close();

        // Parameterizes the solver.
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);

        localsolver.solve();

        
    }

    // Writes 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 << "Error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Tsp.cs /reference:localsolvernet.dll
Tsp instances\br17.atsp
/********** Tsp.cs **********/

using System;
using System.IO;
using localsolver;

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

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

    // Solver.
    LocalSolver localsolver;

    // Decision variables
    LSExpression cities;

    // Objective
    LSExpression obj;

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

    // Reads 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);
            distanceWeight = new long[nbCities][];
            for (int i = 0; i < nbCities; i++)
            {
                distanceWeight[i] = new long[nbCities];
                for (int j = 0; j < nbCities; j++)
                    distanceWeight[i][j] = long.Parse(matrixText[i * nbCities + j]);
            }
        }
    }

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

    void Solve(int limit)
    {
        // Declares 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 distanceArray = model.Array(distanceWeight);

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

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

        // Parameterizes the solver.
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();
    }

    // Writes 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] : "300";

        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_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Tsp instances/br17.atsp
/********** Tsp.java **********/

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[][] distanceWeight;

    // LocalSolver.
    private LocalSolver localsolver;

    // Decision variables.
    private LSExpression cities;

    // Objective
    private LSExpression obj;

    // Reads 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
            distanceWeight = new long[nbCities][nbCities];
            for(i = 0; i < nbCities; i++) {
                for (int j = 0; j < nbCities; j++) {
                    distanceWeight[i][j] = input.nextInt();
                }
            }
        }
    }

    private void solve(int limit) {
        localsolver = new LocalSolver();

        // Declares 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 distanceArray = model.array(distanceWeight);

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

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

        // Parameterizes the solver. 
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);

        localsolver.solve();
    }

    // Writes 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: 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 {
            Tsp model = new Tsp();
            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