Repository navigation
Releases
Releases · karmauh/TourKit
TourKit 0.1.0
First public release of TourKit: a dependency-free Swift package for the asymmetric traveling salesman problem (ATSP).
Highlights
HeuristicSolver: nearest neighbor construction, Or-opt and asymmetric 2-opt local search, and 30 double bridge restarts. 150 points take about 5 ms on an Apple M1 Pro; a time limit (2 s by default) returns the best tour found so far.ExactSolver: Held-Karp dynamic programming for proven optimal tours of up to 15 points by default.- Three tour shapes: closed, open, or ending at a chosen point, plus forbidden edges (
Double.infinity) in both solvers. - Swift 6: strict concurrency, typed throws,
Sendabletypes, cancellation support. - No dependencies, not even Foundation. iOS 16+, macOS 13+, Linux; Swift 6.2 or later.
Quality on TSPLIB
| Instance | Points | Best known | TourKit | Gap | Time |
|---|---|---|---|---|---|
| br17 | 17 | 39 | 39 | 0.00 % | 0.4 ms |
| ftv33 | 34 | 1286 | 1286 | 0.00 % | 1.1 ms |
| p43 | 43 | 5620 | 5620 | 0.00 % | 1.0 ms |
| ftv64 | 65 | 1839 | 1891 | 2.83 % | 2.1 ms |
| ft70 | 70 | 38673 | 39601 | 2.40 % | 3.5 ms |
| kro124p | 100 | 36230 | 39722 | 9.64 % | 5.3 ms |
| rbg443 | 443 | 2720 | 2739 | 0.70 % | 26.4 ms |
The heuristic gives no guarantee: single instances can be far from the optimum. Use ExactSolver when a proven optimum matters and the problem is small enough. See the README for details and the Benchmarks package to reproduce the table.
Installation
.package(url: "https://github.com/karmauh/TourKit", .upToNextMinor(from: "0.1.0"))While TourKit is below 1.0, a minor version may contain breaking changes, so .upToNextMinor is the safe range.
Full changelog: CHANGELOG.md