This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.

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 prodived come from the TSPLib asymmetric TSP databate. 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.

You can find at the end of this page a table with the known optimal results on the asymmetric TSPLib database. On average, LocalSolver 5.5 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;

    // Distance of the arc reaching the ith city 
    distance[0] <- distanceWeight[cities[nbCities - 1]][cities[0]];
    distance[i in 1..nbCities - 1] <- distanceWeight[cities[i - 1]][cities[i]];

    // Minimize the total distance
    obj <- sum[i in 0..nbCities - 1](distance[i]);

    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: city[i] is the index of the ith city in the tour
    city = model.list(nb_cities) 

    # All cities must be visited
    model.constraint(model.count(city)==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()
    for i in range(nb_cities):
        distance_array.add_operand(model.array(distance_weight[i]))

    # Distance of the arc reaching the ith city
    distance = [None]*nb_cities
    distance[0] = model.at(distance_array, city[nb_cities-1], city[0])
    for i in range(1,nb_cities):
        distance[i] = model.at(distance_array, city[i-1], city[i])

    # Minimize the total distance
    obj = model.sum(distance)
    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 city.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(fileName.c_str());
        if (!infile.is_open()) {
            cerr << "File " << fileName << " cannot be opened." << endl;
            exit(1);
        }
        // The input files follow the TSPLib "explicit" format.
        char str[400];
        char * pch;
        while (true) {
            infile >> str;
            pch = strtok (str, " :");
            if  (strcmp(pch, "DIMENSION") == 0){
                infile >> str;
                pch = strtok (str, " :");
                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];
            }
        }
        infile.close();
    }

    void solve(int limit) {
        try {

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

            // Distance of the arc reaching the ith city 
            vector<LSExpression> distance(nbCities);
            distance[0] = model.at(distanceArray, cities[nbCities-1], cities[0]);
            for(int i = 1; i < nbCities; i++){
                distance[i] = model.at(distanceArray, cities[i-1], cities[i]);
            }

            // Minimize the total distance
            obj = model.sum(distance.begin(), distance.end());  
            model.minimize(obj);

            model.close();

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

            localsolver.solve();

        } catch (const LSException& e) {
            cout << "LSException:" << e.getMessage() << endl;
            exit(1);
        }
    }

    /* Writes the solution in a file */
    void writeSolution(const string& fileName) {
        ofstream outfile(fileName.c_str());
        if (!outfile.is_open()) {
            cerr << "File " << fileName << " cannot be opened." << endl;
            exit(1);
        }
        outfile << obj.getValue() << endl;
        LSCollection citiesCollection = cities.getCollectionValue();
        for (int i = 0; i < nbCities; i++) {
            outfile << citiesCollection[i] << " ";
        }
        outfile << endl;
        outfile.close();
    }
};
int main(int argc, char** argv) {
    if (argc < 2) {
        cout << "Usage: tsp inputFile [outputFile] [timeLimit]" << endl;
        exit(1);
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "5";

    Tsp model;
    model.readInstance(instanceFile);
    model.solve(atoi(strTimeLimit));
    if(solFile != NULL)
        model.writeSolution(solFile);
    return 0;
}
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
	int nbCities;

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

	// LocalSolver.
    LocalSolver localsolver;

	// Decision variables.
	LSExpression cities;

    // Objective
	LSExpression obj;

    /* Reads instance data. */
    void readInstance(String fileName) {
        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();
                }
		    }
            input.close();
                        
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    void solve(int limit) {
        try {
            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();
            for(int i = 0; i < nbCities; i++){
                LSExpression row = model.array(distanceWeight[i]);
                distanceArray.addOperand(row);
            }
	
			// As the operator [] is not overloaded, create the explicit list of cities
            LSExpression[] explicitCities = new LSExpression[nbCities];
            for(int i = 0; i < nbCities; i++){
                explicitCities[i] = model.at(cities, i);
			}

			// Distance of the arc reaching the ith city 
			LSExpression[] distance = new LSExpression[nbCities];
            distance[0] = model.at(distanceArray, explicitCities[nbCities-1], explicitCities[0]);
			for(int i = 1; i < nbCities; i++){
                distance[i] = model.at(distanceArray, explicitCities[i-1], explicitCities[i]);
			}

            // Minimize the total distance
			obj = model.sum(distance);
			model.minimize(obj);

            model.close();

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

            localsolver.solve();

        } catch (LSException e) {
            System.out.println("LSException:" + e.getMessage());
            System.exit(1);
        }

    }

    /* Writes the solution in a file */
    void writeSolution(String fileName) {
        try {
            BufferedWriter output = new BufferedWriter(new FileWriter(fileName));

		    output.write(obj.getValue() + "\n");
            LSCollection citiesCollection = cities.getCollectionValue();
            for (int i = 0; i < nbCities; i++) {
                output.write(citiesCollection.get(i) + " ");
            }
            output.write("\n");
            output.close();
	    } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
    
    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.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";

        Tsp model = new Tsp();
        model.readInstance(instanceFile);
        model.solve(Integer.parseInt(strTimeLimit));
        if(outputFile != null) {
            model.writeSolution(outputFile);
        }
    }

}
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.
            while (true) 
            {
                string[] splitted = input.ReadLine().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 ()
    {
        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();
        for(int i = 0; i < nbCities; i++)
        {
            LSExpression row = model.Array(distanceWeight[i]);
            distanceArray.AddOperand(row);
        }

		// Distance of the arc reaching the ith city 
		LSExpression[] distance = new LSExpression[nbCities];
        distance[0] = distanceArray[cities[nbCities-1], cities[0]];
		for(int i = 1; i < nbCities; i++)
        {
            // distanceArray[a, b] is a shortcut for accessing the multi-dimensional array
            // distanceArray with an at operator. Same as model.At(distanceArray, a, b)
            distance[i] = distanceArray[cities[i-1], cities[i]];
		}

        // Minimize the total distance
		obj = model.Sum(distance);
		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]");
            System.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);
        }
    }


}

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