Gams Travelling Salesman Problem Model

1. STRATEGY & FORMULATION:

In order not to deal with excessive number of constraints, we skipped the constraint (4) directly, which is more trustable, but includes so many constraints. Because of the fact that the constraint, which is found by  Desrochers and Laporte, is a stronger version of the Miller-Tucker-Zemlin(MTZ), we used constraint (6) in order to solve Travelling Salesman Problem(TSP) for the given data. As one can see in below, we defined a new decision variable u(i), which indicates the sequence in which the city i is visited.

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

2. TSP WITH 15 CITIES:

2.a.CODE:

*****************************************************

*This is the code for TSP with 15 cities.

*****************************************************

set i /1*15/;

alias  (i,j);

table

d(i,j) distance

$include "TR_15cities.txt";

binary variables

x(i,j);

positive variables

u(i)

variable

opt;

Equations

TotalDistance

AssignmentConstraint_1(j)

AssignmentConstraint_2(i)

Initialize_U

SubSetConstraint_6(i,j) ;

TotalDistance..

opt =E= SUM(i, SUM(j, d(i,j)*x(i,j) ) );

AssignmentConstraint_1(j)..

SUM(i, x(i,j) ) =E= 1 ;

AssignmentConstraint_2(i)..

SUM(j, x(i,j) ) =E= 1 ;

Initialize_U..

u('1') =E= 1;

* We initialiazed the city 1 as the first city.

SubSetConstraint_6(i,j)$(ord(i) gt 1 and ord(j) gt 1)..

u(i) - u(j) + 14 * x(i,j) + 12 * x(j,i) =L= 13;

MODEL IE413_TSP /ALL/;

 option optcr = 0.0 ;

*We used the option in order to decrease the tolerance to 0.

SOLVE IE413_TSP MINIMIZING opt USING MIP;

DISPLAY   opt.l, x.l, x.m, u.l;

 2.b.S O L V E      S U M M A R Y:

 MODEL   IE413_TSP                           OBJECTIVE  opt

 TYPE    MIP                                         DIRECTION  MINIMIZE

 SOLVER  CPLEX                               FROM LINE  67

**** SOLVER STATUS                     1 Normal Completion        

**** MODEL STATUS                      1 Optimal                  

**** OBJECTIVE VALUE                     5161.0000

 RESOURCE USAGE, LIMIT                  1.574      1000.000

 ITERATION COUNT, LIMIT                      9748    2000000000

IBM ILOG CPLEX   Jul  4, 2010 23.5.1 WIN 18414.18495 VS8 x86/MS Windows

Cplex 12.2.0.0, GAMS Link 34

GAMS/Cplex licensed for continuous and discrete problems.

Cplex MIP uses 1 of 8 parallel threads. Change default with option THREADS.

MIP status(101): integer optimal solution

Fixed MIP status(1): optimal

Proven optimal solution.

MIP Solution:                                 5161.000000    (9748 iterations, 965 nodes)

Final Solve:                                  5161.000000    (0 iterations)

Best possible:                                5161.000000

Absolute gap:                                    0.000000

Relative gap:                                    0.000000

We reached the best possible solution by using constraint (6) in a very short time interval.

2.c.SOLUTION:

        1           2           3           4           5           6

1                                                                    1.000

3                                            1.000

7                                                        1.000

8        1.000

12                   1.000

14                               1.000

+           7           8           9          10          11          12

4                    1.000

6                                                                    1.000

9        1.000

10                               1.000

13                                                       1.000

15                                           1.000

+          13          14          15

2                                1.000

5        1.000

11                   1.000

2.d.MAP:

[pic 6]

3. TSP WITH 81 CITIES:

3.a.CODE:

*This is the code for TSP with 81 cities.

*****************************************************

set i /1*81/;

alias  (i,j);

table

d(i,j) distance

$include "TR_81cities.txt";

binary variables

x(i,j);

 positive variables

u(i);

variable

opt;

Equations

TotalDistance

AssignmentConstraint_1(j)

AssignmentConstraint_2(i)

Initialize_U

SubSetConstraint_6(i,j);

TotalDistance..

opt =E= SUM(i, SUM(j, d(i,j)*x(i,j) ) );

AssignmentConstraint_1(j)..

SUM(i, x(i,j) ) =E= 1 ;

AssignmentConstraint_2(i)..

SUM(j, x(i,j) ) =E= 1 ;

Initialize_U..

u('1') =E= 1;

SubSetConstraint_6(i,j)$(ord(i) gt 1 and ord(j) gt 1)..

u(i) - u(j) + 80 * x(i,j) + 78 * x(j,i) =L= 79;