ptsp.gms : Traveling Salesman Problem Instance solved with explicit Permutation Enumeration

**Description**

In this model, we use specific GAMS option syntax to compute all permutations of the cities. We compute the cost for each permutation and by that find the optimal tour. Since the number of permutations grows exponentially, this is not a good idea for larger instances, but it demonstrates the GAMS feature that produces all permutations of a set. Keywords: traveling salesman problem, complete enumeration, GAMS language features

**Reference**

- GAMS Development Corporation, Formulation and Language Example.

**Small Model of Type :** GAMS

**Category :** GAMS Model library

**Main file :** ptsp.gms **includes :** br17.inc

```
$title Traveling Salesman Problem Instance solved with explicit Permutation Enumeration (PTSP,SEQ=374)
$onText
In this model, we use specific GAMS option syntax to compute all
permutations of the cities. We compute the cost for each permutation
and by that find the optimal tour. Since the number of permutations
grows exponentially, this is not a good idea for larger instances, but
it demonstrates the GAMS feature that produces all permutations of a
set.
Keywords: traveling salesman problem, complete enumeration,
GAMS language features
$offText
$include br17.inc
$if not set N $set N 7
$ifE %N%>17 $abort Maximum number of cities is 17
Set i(ii) 'subset of cities' / i1*i%N% /;
Alias (i,j,k);
$eval pmax fact(card(i))
Set
p 'all permutations of cities' / p1*p%pmax% /
m(p,ii,ii) 'actual permutations';
* Let GAMS produce all permutations:
option m > i;
Set bestTour(i,i);
Scalar pObj, bestObj / inf /;
* Iterate through permutations and compute cost of the permutation/tour
loop(p,
pObj = 0;
loop((i,j)$m(p,i,j), pObj = pObj + sum(m(p,i++1,k), c(j,k)););
if(pObj < bestObj,
bestTour(i,j) = m(p,i,j);
bestObj = pObj;
);
);
display bestObj, bestTour;
```