tsp.md

解TSP旅行商问题

给定中国\(34\)个城市的GEO坐标，如下：


北京,天津,上海,重庆,拉萨,乌鲁木齐,银川,呼和浩特,南宁,哈尔滨,长春,沈阳,石家庄,太原,西宁,济南,郑州,南京,合肥,杭州,福州,南昌,长沙,武汉,广州,台北,海口,兰州,西安,成都,贵阳,昆明,香港,澳门


[39.92,116.46],[39.13,117.2],[31.22,121.48],[29.59,106.54],[29.97,91.11],[43.77,87.68],[38.47,106.27],[40.82,111.65],[22.84,108.33],[45.75,126.63],[43.88,125.35],[41.8,123.38],[38.03,114.48],[37.87,112.53],[36.56,101.74],[36.65,117],[34.76,113.6],[32.04,118.78],[31.86,117.27],[30.26,120.19],[26.08,119.3],[28.68,115.89],[28.21,113],[30.52,114.31],[23.16,113.23],[25.05,121.5],[20.02,110.35],[36.03,103.73],[34.27,108.95],[30.67,104.06],[26.57,106.71],[25.04,102.73],[22.2,114.1],[22.13,113.33]

其最优解是\(15704\)。

local print = require('package.print').print
local plt = require 'package.plot'
local mol = libminoptlab

local city = {{39.92, 116.46}, {39.13, 117.2}, {31.22, 121.48}, {29.59, 106.54}, {29.97, 91.11}, {43.77, 87.68},
              {38.47, 106.27}, {40.82, 111.65}, {22.84, 108.33}, {45.75, 126.63}, {43.88, 125.35}, {41.8, 123.38},
              {38.03, 114.48}, {37.87, 112.53}, {36.56, 101.74}, {36.65, 117}, {34.76, 113.6}, {32.04, 118.78},
              {31.86, 117.27}, {30.26, 120.19}, {26.08, 119.3}, {28.68, 115.89}, {28.21, 113}, {30.52, 114.31},
              {23.16, 113.23}, {25.05, 121.5}, {20.02, 110.35}, {36.03, 103.73}, {34.27, 108.95}, {30.67, 104.06},
              {26.57, 106.71}, {25.04, 102.73}, {22.2, 114.1}, {22.13, 113.33}}
local cityname = {
		"北京","天津","上海","重庆","拉萨","乌鲁木齐","银川","呼和浩特","南宁","哈尔滨","长春","沈阳","石家庄","太原","西宁",
"济南","郑州","南京","合肥","杭州","福州","南昌","长沙","武汉","广州","台北","海口","兰州","西安","成都","贵阳","昆明","香港","澳门"
}

local best, fbest = mol.tspsolve(city, "GEO")

print({
    fbest = fbest,
    best = best
})

local img = {}
local len = #best

for i = 1, len - 1 do
    table.insert(img,
        plt.line({{{city[best[i]][2], city[best[i + 1]][2]}, {city[best[i]][1], city[best[i + 1]][1]}}}, {nil}, {}, {{
            text = {
                args = {city[best[i]][2], city[best[i]][1], string.format('%s[%s]', cityname[best[i]], cityname[best[i + 1]])},
                kwargs = {}
            }
        }}))
end
table.insert(img,
    plt.line({{{city[best[#best]][2], city[best[1]][2]}, {city[best[#best]][1], city[best[1]][1]}}}, {nil}, {}, {{
        text = {
            args = {city[best[len]][2], city[best[len]][1], string.format('%s[%s]', cityname[best[len]], cityname[best[1]])},
            kwargs = {}
        }
    }}))

local fw = plt.framework(111, '中国34个城市的旅行商问题', {'x', 'y'})
plt.show({{fw, img}})