We will use TravelingSalesmanExact
to compute the exact cost and compare to the estimated best costs found by TravelingSalesmanHeuristics
with various settings of quality
. First we load the packages:
using TravelingSalesmanExact, GLPK using TravelingSalesmanHeuristics using TravelingSalesmanExact: ATT, euclidean_distance using TravelingSalesmanBenchmarks using Plots using Random gr(fmt=:svg)
Plots.GRBackend()
Then we generate a cost matrix by taking a matrix uniformly at random and symmetrizing it, with a fixed seed for reproducibility:
Random.seed!(758) N = 50 cost = 100*rand(N, N) cost = (cost + transpose(cost) )/2
50×50 Array{Float64,2}: 22.8248 41.3445 53.5929 39.1792 35.2913 … 47.2814 44.6921 63.09 45 41.3445 13.1004 73.5235 55.3009 21.3577 7.21117 7.95262 43.62 36 53.5929 73.5235 94.3781 15.3588 32.0469 22.1608 32.8762 53.04 74 39.1792 55.3009 15.3588 6.4889 57.6645 23.1055 45.7339 48.58 97 35.2913 21.3577 32.0469 57.6645 35.839 26.109 37.426 48.69 61 35.9583 55.201 39.093 38.341 78.4554 … 81.0471 67.1443 61.32 85 46.3519 62.3843 62.3551 71.7588 57.538 43.3942 31.7907 56.28 28 28.4214 66.4843 12.7711 60.2753 69.8672 55.1447 64.1496 34.32 35 78.6491 39.8221 63.9344 23.893 64.0864 51.8869 83.0205 76.81 73 13.229 59.8764 51.2916 8.1257 45.1743 33.4251 70.3754 48.01 71 ⋮ ⋱ 41.5839 39.6921 64.83 68.6766 63.3925 58.7033 77.5336 14.92 28 81.0534 50.161 28.101 62.3008 64.0195 43.4937 48.3701 52.13 26 5.4622 79.1732 11.1337 57.0497 44.1113 49.1062 64.2019 34.71 3 21.392 62.2546 66.2069 56.8905 26.1311 14.1168 79.7081 24.71 7 32.5348 43.5087 50.4695 37.2779 50.1287 … 73.0339 15.687 42.78 62 42.6627 36.5543 47.0154 67.1887 73.7858 42.773 19.8238 76.37 81 47.2814 7.21117 22.1608 23.1055 26.109 97.7158 55.2536 35.30 3 44.6921 7.95262 32.8762 45.7339 37.426 55.2536 80.0741 44.91 38 63.0945 43.6236 53.0474 48.5897 48.6961 35.303 44.9138 60.74 65
Note that this is a very odd cost matrix for a TSP problem, since e.g. the diagonal is non-zero, although it is symmetric.
Now we will compute an optimal tour and cost, and plot these versus those found by the tsp_solve
function of TravelingSalesmanHeuristics
.
t_exact, c_exact = get_optimal_tour(cost, with_optimizer(GLPK.Optimizer)) c(q) = solve_tsp(cost; quality_factor = q)[2] qs = range(10, stop = 100, step = 10) plot(qs, c, xlabel="quality", ylabel="Cost", label="solve_tsp 1", title="random symmetric cost matrix") for j = 2:5 plot!(qs, c, label="solve_tsp $j") end hline!([c_exact], label="Exact cost")
We've run tsp_solve
five times for each quality, since the cost will vary from run to run due to the randomness of the heuristics. It seems like the heuristics do not perform that well, but I believe that is due to the pathological cost matrix, which likely violates some assumptions of the heuristics.
These benchmarks are a part of the TravelingSalesmanBenchmarks.jl repository, found at: https://github.com/ericphanson/TravelingSalesmanBenchmarks.jl, based on the weave
branch of DiffEqBenchmarks.
To locally run this tutorial, do the following commands:
using TravelingSalesmanBenchmarks
TravelingSalesmanBenchmarks.weave_file("random_50_symmetric_cost_vs_quality.jmd")
Computer Information:
Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
OS: macOS (x86_64-apple-darwin14.5.0)
CPU: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, broadwell)
Environment:
JULIA_EDITOR = "/Applications/Visual Studio Code.app/Contents/Frameworks/Code Helper.app/Contents/MacOS/Code Helper"
Package Information:
Status: `/Users/eh540/Dropbox (Personal)/LinkedFolders/Julia/dev/TravelingSalesmanBenchmarks/Project.toml`
[a93c6f00-e57d-5684-b7b6-d8193f3e46c0] DataFrames 0.17.1
[60bf3e95-4087-53dc-ae20-288a0d20c6a6] GLPK 0.9.1
[2e9cd046-0924-5485-92f1-d5272153d98b] Gurobi 0.6.0
[7073ff75-c697-5162-941a-fcdaad2a7d2a] IJulia 1.18.1
[91a5bcdd-55d7-5caf-9e0b-520d859cae80] Plots 0.24.0
[737fac7d-4440-55ef-927e-002196e95561] TravelingSalesmanExact 0.3.2
[8c8f4381-2cdd-507c-846c-be2bcff6f45f] TravelingSalesmanHeuristics 0.3.1
[44d3d7a6-8a23-5bf8-98c5-b353f8df5ec9] Weave 0.9.0
[ddb6d928-2868-570f-bddf-ab3f9cf99eb6] YAML 0.3.2
[b77e0a4c-d291-57a0-90e8-8db25a27a240] InteractiveUtils
[d6f4376e-aef5-505a-96c1-9c027394607a] Markdown
[44cfe95a-1eb2-52ea-b672-e2afdf69b78f] Pkg
[de0858da-6303-5e67-8744-51eddeeeb8d7] Printf
[9a3f8284-a2c9-5f02-9a11-845980a1fd5c] Random
[10745b16-79ce-11e8-11f9-7d13ad32a3b2] Statistics