Traveling Salesman Problem

A Traveling Salesman Problem appoximation with simulated annealing.

Usage

cargo run --release [algorithm] [input mode]

• Algorithms: choose between annealing and brute-force. The project is focused on simulated annealing but the brute force method is included as a comparison.
• Input modes: use random [city count] to generate a random number of cities or input to read the cities from standard input (some examples are included in the examples directory).

Example (simulated annealing on 40 random cities):

cargo run --release annealing random 40

Example (simulated annealing on a circle of 50 cities generated by the gen_circle.py script):

./examples/gen_circle.py 50 | cargo run --release annealing input

Dependencies

Because the Rust standard library does not include a random number generator, the rand crate is used for the random number generation.

Visualization

The visualization code is included as an optional Cargo feature visualize using the speedy2d library. You can this feature by running the code with the --features visualize option and appending v(isualize) as arguement.

Examples:

cargo run --release --features visualize annealing rand 40 visualize
cargo run --release --features visualize brute-force rand 12 visualize

Use the following keys to control the visualization:

• Space Pause
• S Slower speed
• F Faster speed
• N Toggle show numbers
• P Toggle show samples

Visualization screenshots: