Gams Travelling Salesman Problem Model
Essay Preview: Gams Travelling Salesman Problem Model
Report this essay
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);tabled(i,j) distance$include “TR_15cities.txt”;binary variablesx(i,j);positive variablesu(i)variableopt;EquationsTotalDistanceAssignmentConstraint_1(j)AssignmentConstraint_2(i)Initialize_USubSetConstraint_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 2000000000IBM ILOG CPLEX Jul 4, 2010 23.5.1 WIN 18414.18495 VS8 x86/MS WindowsCplex 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 solutionFixed MIP status(1): optimalProven optimal solution.MIP Solution: 5161.000000 (9748 iterations, 965 nodes)Final Solve: 5161.000000 (0 iterations)Best possible: 5161.000000Absolute gap: 0.000000
Relative gap: 0.000000We reached the best possible solution by using constraint (6) in a very short time interval. 2.c.SOLUTION: 1 2 3 4 5 61 1.0003 1.0007 1.0008 1.00012 1.00014 1.000+ 7 8 9 10 11 124 1.0006 1.0009 1.00010 1.00013 1.00015 1.000+ 13 14 152 1.0005 1.00011 1.0002.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);tabled(i,j) distance$include “TR_81cities.txt”;binary variablesx(i,j); positive variablesu(i);variableopt;EquationsTotalDistanceAssignmentConstraint_1(j)AssignmentConstraint_2(i)Initialize_USubSetConstraint_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;