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

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;