{"action":"created","issue":{"url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/1","repository_url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl","labels_url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/1/comments","events_url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/1/events","html_url":"https://github.com/evanfields/TravelingSalesmanHeuristics.jl/pull/1","id":150447145,"number":1,"title":"Simulated annealing heuristic","user":{"login":"evanfields","id":10092265,"avatar_url":"https://avatars.githubusercontent.com/u/10092265?v=3","gravatar_id":"","url":"https://api.github.com/users/evanfields","html_url":"https://github.com/evanfields","followers_url":"https://api.github.com/users/evanfields/followers","following_url":"https://api.github.com/users/evanfields/following{/other_user}","gists_url":"https://api.github.com/users/evanfields/gists{/gist_id}","starred_url":"https://api.github.com/users/evanfields/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/evanfields/subscriptions","organizations_url":"https://api.github.com/users/evanfields/orgs","repos_url":"https://api.github.com/users/evanfields/repos","events_url":"https://api.github.com/users/evanfields/events{/privacy}","received_events_url":"https://api.github.com/users/evanfields/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2016-04-22T19:00:08Z","updated_at":"2016-05-18T17:34:16Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/pulls/1","html_url":"https://github.com/evanfields/TravelingSalesmanHeuristics.jl/pull/1","diff_url":"https://github.com/evanfields/TravelingSalesmanHeuristics.jl/pull/1.diff","patch_url":"https://github.com/evanfields/TravelingSalesmanHeuristics.jl/pull/1.patch"},"body":"Initial code for a simulated annealing approach. At least on small instances, this simulated annealing approach works *very* poorly compared to the nearest neighbor and cheapest insertion approaches. \r\n\r\nThe cooling schedule is a simple exponential decay, which is nice because computing temperatures requires only a single multiplication per iteration. But, this schedule seems to get too cold too quickly.\r\n\r\n- [x] write tests covering simulated annealing\r\n    - simple tests are now implemented\r\n- [ ] compare performance on larger instances, non-Euclidean (even non-metric) instances, etc\r\n    - In rare Euclidean instances, the simulated annealing heuristic finds better solutions than the repetitive nearest neighbor heuristic. The full 2-opt procedure is time consuming for large instances, and it seems that some of the benefit of SA is that it can do a partial 2-opt procedure. It's not clear that SA is the right tool if one wishes to perform 2-opt improvements without exhaustively testing all improvements; perhaps it would be better to run the regular 2-opt procedure on a clock, only loop through all pairs of possible swaps k times, etc.\r\n- [ ] tune cooling schedule\r\n\r\nThis is only worth merging if it can be tuned so that at least on same categories of TSP instances it's competitive with the existing heuristics."},"comment":{"url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/comments/220101335","html_url":"https://github.com/evanfields/TravelingSalesmanHeuristics.jl/pull/1#issuecomment-220101335","issue_url":"https://api.github.com/repos/evanfields/TravelingSalesmanHeuristics.jl/issues/1","id":220101335,"user":{"login":"evanfields","id":10092265,"avatar_url":"https://avatars.githubusercontent.com/u/10092265?v=3","gravatar_id":"","url":"https://api.github.com/users/evanfields","html_url":"https://github.com/evanfields","followers_url":"https://api.github.com/users/evanfields/followers","following_url":"https://api.github.com/users/evanfields/following{/other_user}","gists_url":"https://api.github.com/users/evanfields/gists{/gist_id}","starred_url":"https://api.github.com/users/evanfields/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/evanfields/subscriptions","organizations_url":"https://api.github.com/users/evanfields/orgs","repos_url":"https://api.github.com/users/evanfields/repos","events_url":"https://api.github.com/users/evanfields/events{/privacy}","received_events_url":"https://api.github.com/users/evanfields/received_events","type":"User","site_admin":false},"created_at":"2016-05-18T17:34:15Z","updated_at":"2016-05-18T17:34:15Z","body":"I'm going to go ahead and merge this shortly. For finding decent paths the existing heuristics are still better, but with a bit of tuning and specifying the path to start annealing from, SA can be useful for additional path improvement. \r\n\r\nI haven't added SA to the heuristics in `solve_tsp` since it tends to be a bit slower and a bit worse than the other heuristics. Also, it requires much more tuning.\r\n\r\nGiven the speed and quality of the SA paths, I suspect the costs of using this simulated annealing code about reach the point where using Gurobi etc would be a better option. But not everybody has access to those and perhaps this code will be useful to someone."}}