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 gr(fmt=:svg) repo_directory = TravelingSalesmanBenchmarks.repo_directory; data_directory = joinpath(repo_directory, "data");
Then load the dataset
cities = simple_parse_tsp(joinpath(data_directory, "att48.tsp"), verbose = false) N = length(cities) cost = [ ATT(cities[i], cities[j]) for i=1:N, j=1:N ]
48×48 Array{Int64,2}: 0 1495 381 2012 1157 990 … 1104 616 2162 488 753 1184 1495 0 1135 637 583 2207 2223 1957 1098 1727 1388 661 381 1135 0 1633 778 1163 1231 850 1790 640 591 810 2012 637 1633 0 886 2550 2526 2373 594 2138 1695 900 1157 583 778 886 0 1686 1680 1489 1025 1253 839 97 990 2207 1163 2550 1686 0 … 174 387 2468 528 856 1654 764 2056 971 2444 1565 235 386 153 2415 334 769 1545 178 1641 551 2175 1329 1015 1149 629 2338 565 911 1359 147 1590 457 2081 1210 845 961 470 2193 352 695 1226 1788 736 1412 444 636 2191 2149 2058 401 1826 1344 606 ⋮ ⋮ ⋱ ⋮ 261 1443 325 1901 1021 848 931 525 1988 320 495 1029 692 872 442 1467 768 1598 … 1671 1264 1766 1071 989 843 1525 504 1144 532 370 2019 1997 1846 698 1611 1164 370 1104 2223 1231 2526 1680 174 0 530 2405 622 842 1640 616 1957 850 2373 1489 387 530 0 2379 236 735 1477 2162 1098 1790 594 1025 2468 2405 2379 0 2152 1647 981 488 1727 640 2138 1253 528 … 622 236 2152 0 520 1242 753 1388 591 1695 839 856 842 735 1647 520 0 801 1184 661 810 900 97 1654 1640 1477 981 1242 801 0
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="att48.tsp") 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.
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("att48_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