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ΒΆ

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.

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;

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

if (inFileName == nil) throw usage;

// The input files follow the TSPLib "explicit" format
while (true) {
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[i in 0...nbCities][j in 0...nbCities] = 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, 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_12_0/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)

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

with localsolver.LocalSolver() as ls:
#
#

# 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\localsolver120.lib
tsp instances\br17.atsp
Compilation / Execution (Linux)
g++ tsp.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -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;

ifstream infile;
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());
}

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

{
{
// 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
.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.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_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/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;
}

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