# 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¶

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

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

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[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)

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

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

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

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

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

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