LINGO的TSP的实现

最短路径LINGO源代码：MODEL: SETS: CITY / 1. 33/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): DIST, ! The distance matrix; X; ! X( I, J) = 1 if we use link I, J; ENDSETS DATA: !Distance matrix, it need not be symmetric; DIST =0.0 127.4 1208.5 1770.0 292.2 507.0 691.5 989.2 1244.3 1238.2 1300.1 1034.4 1887.4 1424.3 422.1 683.1 1157.0 1427.3 2113.2 2693.4 1804.7 2152.5 2653.0 1094.6 1486.2 1690.1 3638.2 2320.8 487.4 1141.7 2956.6 2200.8 2252.6 127.4 0.0 1086.9 1794.4 304.8 534.4 665.6 970.6 1225.7 881.4 1150.3 937.6 1765.9 1311.2 325.3 654.7 1072.2 1454.2 2095.1 2675.2 1829.2 2070.2 3634.9 1119.0 1468.2 1664.8 3579.5 2273.9 599.2 1205.6 3196.1 2111.6 2234.5 1208.5 1086.9 0.0 1708.4 1096.1 1346.5 1734.8 2039.9 2295.0 296.1 173.7 456.4 765.7 732.7 840.8 955.5 840.0 1088.3 1402.7 2029.8 1069.0 1846.1 2346.6 1386.9 2035.1 2274.7 4222.8 1887.5 1596.4 1596.1 3921.3 1514.2 1585.5 1770.0 1794.4 1708.4 0.0 1470.0 1283.0 2429.8 2734.8 2989.9 1396.4 1605.9 1241.4 1774.9 1212.2 1545.2 1140.9 868.4 893.0 1313.7 1428.5 311.7 372.1 880.2 683.0 981.1 1191.1 2395.7 923.4 1645.3 1433.2 2876.7 1472.6 1441.5 292.2 304.8 1096.1 1470.0 0.0 240.8 966.8 1271.8 1526.9 914.7 1176.6 910.9 1790.7 1164.7 298.6 406.2 887.7 1203.7 1936.6 2424.8 1521.1 1883.9 2384.4 811.0 1243.3 1447.2 3395.3 2054.4 503.9 935.4 2925.9 1933.8 1964.5 507.0 534.4 1346.5 1283.0 240.8 0.0 1185.9 1490.9 1746.0 1077.7 1341.5 1004.6 1847.4 1284.8 526.7 432.5 937.7 1220.7 1861.5 2441.7 1318.7 1657.5 2163.2 608.6 1048.3 1252.2 3200.4 2082.1 436.6 740.5 2730.9 2024.0 2000.9 691.5 665.6 1734.8 2429.8 966.8 1185.9 0.0 380.4 585.6 1547.0 1798.7 1594.4 2414.3 2005.8 982.1 1362.6 1795.6 2111.0 2751.9 3332.0 2478.7 2791.2 3291.7 1768.6 2163.0 2366.9 4315.1 2972.4 1164.7 1855.2 3845.7 2839.5 2891.2 989.2 970.6 2039.9 2734.8 1271.8 1490.9 380.4 0.0 258.1 1839.4 2091.0 1886.8 2706.6 2298.2 1274.5 1655.0 2088.0 2403.4 3044.3 3624.4 2771.1 3083.5 3584.0 2061.0 2351.9 2548.5 4463.2 3264.8 1334.0 2064.1 3812.1 3131.8 3183.6 1244.3 1225.7 2295.0 2989.9 1526.9 1746.0 585.6 258.1 0.0 2107.2 2358.8 2154.6 2974.4 2565.9 1542.2 1922.7 2355.7 2671.1 3312.0 3892.1 3038.8 3351.3 3851.8 2328.7 2723.1 2927.1 4875.2 3532.5 1517.7 2331.8 3987.0 3399.6 3451.4 1238.2 881.4 296.1 1396.4 914.7 1077.7 1547.0 1839.4 2107.2 0.0 276.7 163.6 910.8 579.3 636.8 665.7 535.2 869.9 1356.7 1954.2 1680.4 1638.9 2148.1 1100.2 1722.5 1958.7 3907.7 1744.9 1502.9 1698.9 3615.3 1436.0 1513.4 1300.1 1150.3 173.7 1605.9 1176.6 1341.5 1798.7 2091.0 2358.8 276.7 0.0 408.4 634.0 547.3 901.5 934.7 724.6 907.8 1276.6 1853.6 1858.2 1665.0 2174.1 1367.0 1989.3 2175.0 4121.0 1720.5 1758.4 1945.8 3828.6 1335.3 1412.7 1034.4 937.6 456.4 1241.4 910.9 1004.6 1594.4 1886.8 2154.6 163.6 408.4 0.0 943.5 434.5 626.9 570.6 379.6 724.0 1210.8 1787.8 1514.1 1483.3 1992.4 911.5 1540.1 1776.3 3725.2 1599.0 1441.0 1601.6 3432.8 1269.5 1346.9 1887.4 1765.9 765.7 1774.9 1790.7 1847.4 2414.3 2706.6 2974.4 910.8 634.0 943.5 0.0 569.9 1518.4 1421.9 917.9 901.3 865.0 1444.3 2051.5 1585.6 2094.7 1644.4 2272.9 2509.1 4458.1 1423.4 2292.4 2369.5 4165.7 858.1 973.1 1424.3 1311.2 732.7 1212.2 1164.7 1284.8 2005.8 2298.2 2565.9 579.3 547.3 434.5 569.9 0.0 1053.8 857.5 353.5 339.2 781.6 1358.5 1487.1 1144.7 1653.8 1080.0 1708.5 1944.7 3893.7 1200.2 1728.0 1805.1 3601.3 840.3 945.3 422.1 325.3 840.8 1545.2 298.6 526.7 982.1 1274.5 1542.2 636.8 901.5 626.9 1518.4 1053.8 0.0 436.9 843.1 1166.7 1815.0 2391.9 1603.7 1846.2 2355.3 892.5 1445.5 1646.1 5395.1 2041.7 915.2 1224.5 3125.1 1882.1 1957.4 683.1 654.7 955.5 1140.9 406.2 432.5 1362.6 1655.0 1922.7 665.7 934.7 570.6 1421.9 857.5 436.9 0.0 539.0 800.4 1448.6 2025.6 1188.7 1479.9 1989.0 477.5 1099.8 1336.0 3284.9 1675.4 876.8 1037.3 2992.6 1611.4 1591.0 1157.0 1072.2 840.0 868.4 887.7 937.7 1795.6 2088.0 2355.7 535.2 724.6 379.6 917.9 353.5 843.1 539.0 0.0 345.5 985.9 1566.5 1143.1 1087.2 1618.8 731.4 1382.6 1622.2 3219.5 1203.7 1376.9 1365.0 3223.2 1089.9 1113.8 1427.3 1454.2 1088.3 893.0 1203.7 1220.7 2111.0 2403.4 2671.1 869.9 907.8 724.0 901.3 339.2 1166.7 800.4 345.5 0.0 661.8 1280.9 1194.8 837.3 1337.8 950.7 1633.2 1872.8 3230.2 869.0 1614.6 1584.3 3442.5 806.4 789.7 2113.2 2095.1 1402.7 1313.7 1936.6 1861.5 2751.9 3044.3 3312.0 1356.7 1276.6 1210.8 865.0 781.6 1815.0 1448.6 985.9 661.8 0.0 590.5 1658.9 992.3 1326.0 1593.3 2279.8 2519.4 3535.0 556.6 2257.2 2226.9 4085.1 163.3 131.6 2693.4 2675.2 2029.8 1428.5 2424.8 2441.7 3332.0 3624.4 3892.1 1954.2 1853.6 1787.8 1444.3 1358.5 2391.9 2025.6 1566.5 1280.9 590.5 0.0 1710.8 1060.6 1226.7 2107.5 2407.3 2618.1 3435.7 474.0 2878.4 2855.1 4302.8 641.9 573.5 1804.7 1829.2 1069.0 311.7 1521.1 1318.7 2478.7 2771.1 3038.8 1680.4 1858.2 1514.1 2051.5 1487.1 1603.7 1188.7 1143.1 1194.8 1658.9 1710.8 0.0 676.2 899.9 712.9 854.3 964.3 2088.8 1242.7 1685.6 1434.6 2696.7 1821.7 1791.7 2152.5 2070.2 1846.1 372.1 1883.9 1657.5 2791.2 3083.5 3351.3 1638.9 1665.0 1483.3 1585.6 1144.7 1846.2 1479.9 1087.2 837.3 992.3 1060.6 676.2 0.0 507.5 1050.5 1355.0 1565.8 2648.3 558.9 2012.8 1802.8 3250.6 1150.1 1098.3 2653.0 3634.9 2346.6 880.2 2384.4 2163.2 3291.7 3584.0 3851.8 2148.1 2174.1 1992.4 2094.7 1653.8 2355.3 1989.0 1618.8 1337.8 1326.0 1226.7 899.9 507.5 0.0 1562.2 1765.8 1976.7 2213.1 770.6 2544.1 2309.8 3661.4 1541.0 1402.4 1094.6 1119.0 1386.9 683.0 811.0 608.6 1768.6 2061.0 2328.7 1100.2 1367.0 911.5 1644.4 1080.0 892.5 477.5 731.4 950.7 1593.3 2107.5 712.9 1050.5 1562.2 0.0 646.0 885.5 2833.7 1602.7 963.6 634.8 2493.1 1736.4 1719.6 1486.2 1468.2 2035.1 981.1 1243.3 1048.3 2163.0 2351.9 2723.1 1722.5 1989.3 1540.1 2272.9 1708.5 1445.5 1099.8 1382.6 1633.2 2279.8 2407.3 854.3 1355.0 1765.8 646.0 0.0 215.1 2129.8 1921.7 1112.4 430.0 1903.1 2439.3 2416.2 1690.1 1664.8 2274.7 1191.1 1447.2 1252.2 2366.9 2548.5 2927.1 1958.7 2175.0 1776.3 2509.1 1944.7 1646.1 1336.0 1622.2 1872.8 2519.4 2618.1 964.3 1565.8 1976.7 885.5 215.1 0.0 1915.6 2129.0 1312.7 605.7 1734.4 2677.2 2654.1 3638.2 3579.5 4222.8 2395.7 3395.3 3200.4 4315.1 4463.2 4875.2 3907.7 4121.0 3725.2 4458.1 3893.7 5395.1 3284.9 3219.5 3230.2 3535.0 3435.7 2088.8 2648.3 2213.1 2833.7 2129.8 1915.6 0.0 2979.2 3263.6 2519.0 2646.5 3760.5 3611.0 2320.8 2273.9 1887.5 923.4 2054.4 2082.1 2972.4 3264.8 3532.5 1744.9 1720.5 1599.0 1423.4 1200.2 2041.7 1675.4 1203.7 869.0 556.6 474.0 1242.7 558.9 770.6 1602.7 1921.7 2129.0 2979.2 0.0 2522.3 2367.3 3815.1 720.5 632.6 487.4 599.2 1596.4 1645.3 503.9 436.6 1164.7 1334.0 1517.7 1502.9 1758.4 1441.0 2292.4 1728.0 915.2 876.8 1376.9 1614.6 2257.2 2878.4 1685.6 2012.8 2544.1 963.6 1112.4 1312.7 3263.6 2522.3 0.0 635.0 2479.3 2462.0 2438.9 1141.7 1205.6 1596.1 1433.2 935.4 740.5 1855.2 2064.1 2331.8 1698.9 1945.8 1601.6 2369.5 1805.1 1224.5 1037.3 1365.0 1584.3 2226.9 2855.1 1434.6 1802.8 2309.8 634.8 430.0 605.7 2519.0 2367.3 635.0 0.0 2078.4 2370.7 2354.0 2956.6 3196.1 3921.3 2876.7 2925.9 2730.9 3845.7 3812.1 3987.0 3615.3 3828.6 3432.8 4165.7 3601.3 3125.1 2992.6 3223.2 3442.5 4085.1 4302.8 2696.7 3250.6 3661.4 2493.1 1903.1 1734.4 2646.5 3815.1 2479.3 2078.4 0.0 4227.9 4221.2 2200.8 2111.6 1514.2 1472.6 1933.8 2024.0 2839.5 3131.8 3399.6 1436.0 1335.3 1269.5 858.1 840.3 1882.1 1611.4 1089.9 806.4 163.3 641.9 1821.7 1150.1 1541.0 1736.4 2439.3 2677.2 3760.5 720.5 2462.0 2370.7 4227.9 0.0 72.5 2252.6 2234.5 1585.5 1441.5 1964.5 2000.9 2891.2 3183.6 3451.4 1513.4 1412.7 1346.9 973.1 945.3 1957.4 1591.0 1113.8 789.7 131.6 573.5 1791.7 1098.3 1402.4 1719.6 2416.2 2654.1 3611.0 632.6 2438.9 2354.0 4221.2 72.5 0.0 ; ENDDATA !The model:Ref. Desrochers & Laporte, OR Letters, Feb. 91; N = SIZE( CITY); MIN = SUM( LINK: DIST * X); FOR( CITY( K): ! It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1; ! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1; ! Weak form of the subtour breaking constraints; ! These are not very powerful for large problems; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K); ! Make the Xs 0/1; FOR( LINK: BIN( X); ! For the first and last stop we know.; FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1);END结果如下： Global optimal solution found. Objective value: 19652.10 Objective bound: 19652.10 Infeasibilities: 0.1894781E-14 Extended solver steps: 33863 Total solver iterations: 2189844 Variable Value N 33.00000 U( 1) 0.000000 U( 2) 4.000000 U( 3) 11.00000 U( 4) 23.00000 U( 5) 32.00000 U( 6) 31.00000 U( 7) 3.000000 U( 8) 1.000000 U( 9) 2.000000 U( 10) 10.00000 U( 11) 12.00000 U( 12) 9.000000 U( 13) 13.00000 U( 14) 14.00000 U( 15) 5.000000 U( 16) 6.000000 U( 17) 8.000000 U( 18) 15.00000 U( 19) 16.00000 U( 20) 19.00000 U( 21) 24.00000 U( 22) 22.00000 U( 23) 21.00000 U( 24) 7.000000 U( 25) 28.00000 U( 26) 27.00000 U( 27) 25.00000 U( 28) 20.00000 U( 29) 30.00000 U( 30) 29.00000 U( 31) 26.00000 U( 32) 17.00000 U( 33) 18.00000 DIST( 1, 1) 0.000000 DIST( 1, 2) 127.4000 DIST( 1, 3) 1208.500 DIST( 1, 4) 1770.000 DIST( 1, 5) 292.2000 DIST( 1, 6) 507.0000 DIST( 1, 7) 691.5000 DIST( 1, 8) 989.2000 DIST( 1, 9) 1244.300 DIST( 1, 10) 1238.200 DIST( 1, 11) 1300.100 DIST( 1, 12) 1034.400 DIST( 1, 13) 1887.400 DIST( 1, 14) 1424.300 DIST( 1, 15) 422.1000 DIST( 1, 16) 683.1000 DIST( 1, 17) 1157.000 DIST( 1, 18) 1427.300 DIST( 1, 19) 2113.200 DIST( 1, 20) 2693.400 DIST( 1, 21) 1804.700 DIST( 1, 22) 2152.500 DIST( 1, 23) 2653.000 DIST( 1, 24) 1094.600 DIST( 1, 25) 1486.200 DIST( 1, 26) 1690.100 DIST( 1, 27) 3638.200 DIST( 1, 28) 2320.800 DIST( 1, 29) 487.4000 DIST( 1, 30) 1141.700 DIST( 1, 31) 2956.600 DIST( 1, 32) 2200.800 DIST( 1, 33) 2252.600 DIST( 2, 1) 127.4000 DIST( 2, 2) 0.000000 DIST( 2, 3) 1086.900 DIST( 2, 4) 1794.400 DIST( 2, 5) 304.8000 DIST( 2, 6) 534.4000 DIST( 2, 7) 665.6000 DIST( 2, 8) 970.6000 DIST( 2, 9) 1225.700 DIST( 2, 10) 881.4000 DIST( 2, 11) 1150.300 DIST( 2, 12) 937.6000 DIST( 2, 13) 1765.900 DIST( 2, 14) 1311.200 DIST( 2, 15) 325.3000 DIST( 2, 16) 654.7000 DIST( 2, 17) 1072.200 DIST( 2, 18) 1454.200 DIST( 2, 19) 2095.100 DIST( 2, 20) 2675.200 DIST( 2, 21) 1829.200 DIST( 2, 22) 2070.200 DIST( 2, 23) 3634.900 DIST( 2, 24) 1119.000 DIST( 2, 25) 1468.200 DIST( 2, 26) 1664.800 DIST( 2, 27) 3579.500 DIST( 2, 28) 2273.90