cykl-rs is a Rust project implementing Lin-Kerninghan heuristics (LKH) algorithm for solving the travelling salesman problem and other related problems.
At the time of writing, two data structures, array and two-level list, are fully implemented with all operations [3], that are essential for building any heuristic algorithm:
get(id): returns a node for the given indexidsuccessor(a): returns a node that directly succeeds a nodeain the tour.predecessor(a): returns a node that directly preceeds a nodeain the tour.between(a, b, c): checks whetherbis between ofaandcin a forward traversal direction.flip(a, b, c, d): this is an operation used to rearrange the sequence of nodes in a tour. It breaks the edges(a, b)and(c, d), then forms new edges(a, c)and(b, d). This operation affects not only the four input nodes but also their neighbouring nodes.
On the algorithmic side, the library offers several k-opt methods for tour manipulation. They are move_2_opt (equivalent to the flip operation mentioned above), move_3_opt and move_4_opt. The method move_5_opt will be implemented soon.
For generating candidates and initial tours, the library can only offer at the moment the nearest-neighbour method. Other methods, especially alpha-nearness, will be implemented soon.
All metric functions to calculate edge weights between nodes are implemented in tspf, which is a parser for TSPLIB format.
The benchmark for two data structures is listed below. The unit for computation in all entries is nanosecond (ns).
| Array | TLL | |
|---|---|---|
| get | 0.716 | 0.697 |
| successor | 3.233 | 1.155 |
| predecessor | 0.757 | 0.708 |
| between | 0.218 | 3.12 |
| flip (case 1) (flip 99 nodes in one segment) |
228.04 | 107.07 |
| flip (case 2) (flip 100 nodes across two segments) |
255.66 | 13.648 |
| flip (case 3) (flip 900 nodes across multiple segments) |
2152.2 | 69.441 |
[1] S. Lin; B. W. Kernighan(1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. 21 (2): 498–516. doi:10.1287/opre.21.2.498.
[2] K. Helsgaun (2000). "An effective implementation of the Lin–Kernighan traveling salesman heuristic". European Journal of Operational Research. 126 (1): 106-130. doi:10.1016/S0377-2217(99)00284-2.
[3] M. Fredman et al. (1995). "Data Structures for Traveling Salesmen". J. Algorithms 18: 432-479. doi:10.1006/jagm.1995.1018.
[4] D. Sleator and R. Tarjan (1985). "Self-Adjusting Binary Search Trees" Journal of the ACM 32 (3): 652-686. doi:10.1145/3828.3835.
[5] M. Chrobak, T.Szymacha and A.Krawczyk (1990). "A data structure useful for finding Hamiltonian cycles". Theoretical Computer Science 71 (3): 419-424. doi:10.1016/0304-3975(90)90053-K.
[6] Z. Michaelwicz and D. Fogel (2004). "How to solve it: Modern Heuristics". Springer, 2nd Edition. Amazon.com.
[7] D. Applegate et al. "Finding Tours in the TSP". Forschungsinstitut für Diskrete Mathematik Report No. 99885, Universität Bonn. U. Waterloo.
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.