1 unstable release
0.1.1  Sep 14, 2024 

0.1.0 

#317 in Algorithms
322 downloads per month
2MB
4.5K
SLoC
ibnbattuta: A Rust Library for Solving the Travelling Salesman Problem (TSP)
ibnbattuta
is a powerful, flexible, and extensible Rust library designed to solve the Travelling Salesman Problem (
TSP) using various algorithms, including exact, heuristic, and metaheuristic methods. The library is designed to handle
both small and large instances of TSP efficiently and is optimized for parallel processing, making it suitable for
performance benchmarking across multiple solvers.
Features

Exact Algorithms:
 BellmanHeldKarp
 BranchandBound
 Brute Force

Heuristic Algorithms:
 Nearest Neighbor
 2Opt Local Search
 3Opt Local Search
 LinKernighan Heuristic

Metaheuristic Algorithms:
 Ant Colony System (ACS) and Ant System (AS)
 Genetic Algorithm (GA)
 Simulated Annealing (SA)
 RedBlack Ant Colony System (RBACS)
 Hybrid ACS and 2Opt (ACS2Opt, RBACS2Opt, etc.)

TSP Parser:
 Supports parsing
.tsp
files (TSPLIB format) for loading TSP instances.
 Supports parsing

Parallel Processing:
 Uses the
rayon
crate for multithreaded execution, allowing for efficient benchmarking and parallel computations.
 Uses the
Installation
Add the following to your Cargo.toml
:
[dependencies]
ibn_battuta = "0.1.0"
Then, in your Rust code:
use ibn_battuta::algorithms::utils::Solver;
use ibn_battuta::parser::TspBuilder;
Usage
Example: Running Benchmarks on Multiple Solvers
The following example demonstrates how to benchmark multiple TSP solvers in parallel:
use ibn_battuta::algorithms::utils::Solver;
use ibn_battuta::algorithms::*;
use ibn_battuta::parser::TspBuilder;
use rayon::prelude::*;
use std::sync::{Arc, Mutex};
use std::fs::OpenOptions;
use std::time::Duration;
fn main() {
// List of solvers to benchmark
let solvers = vec![
Solver::NearestNeighbor,
Solver::TwoOpt,
Solver::SimulatedAnnealing,
Solver::GeneticAlgorithm,
Solver::AntColonySystem,
Solver::RedBlackAntColonySystem,
];
// Parameters for each solver
let params = vec![
vec![], // NN
vec![], // 2Opt
vec![1000.0, 0.999, 0.0001, 1000.0, 100.0], // SA
vec![100.0, 5.0, 0.7, 0.01, 500.0], // GA
vec![0.1, 2.0, 0.1, 0.9, 1000.0, 15.0], // ACS
vec![0.1, 2.0, 0.1, 0.2, 0.9, 1000.0, 15.0], // RBACS
];
// Number of threads to use
let num_threads = 8;
// TSP instances to benchmark
let instances = vec![
TspInstance { path: "data/tsplib/eil51.tsp".to_string(), best_known: 426.0 },
TspInstance { path: "data/tsplib/berlin52.tsp".to_string(), best_known: 7542.0 },
];
// CSV file to save results
let csv_file = Arc::new(Mutex::new(create_csv_file("BenchmarkResults.csv")));
run_parallel_benchmarks(&instances, &solvers, ¶ms, num_threads, csv_file);
}
fn create_csv_file(filename: &str) > std::fs::File {
OpenOptions::new().write(true).create(true).truncate(true).open(filename).expect("Unable to create file")
}
Supported Algorithms
Exact Algorithms
These algorithms find the optimal solution but may take a long time for large instances:
 BellmanHeldKarp: Solves TSP using dynamic programming.
 BranchandBound: Optimizes through branching decisions and bounds.
 Brute Force: Exhaustively searches all possible tours (not recommended for large instances).
Heuristic Algorithms
These algorithms find good (but not necessarily optimal) solutions quickly:
 Nearest Neighbor: Constructs a solution by iteratively choosing the nearest city.
 2Opt and 3Opt: Local search algorithms that iteratively swap edges to reduce the total tour cost.
 LinKernighan: A more advanced local search heuristic based on 2opt and 3opt moves.
Metaheuristic Algorithms
These algorithms use more complex strategies to search the solution space:
 Ant Colony System (ACS): Uses artificial ants to build solutions based on pheromone trails.
 Genetic Algorithm (GA): Evolves a population of solutions through crossover and mutation.
 Simulated Annealing (SA): Gradually cools down a solution, allowing worse moves to escape local optima.
 RedBlack Ant Colony System (RBACS): A variant of ACS with red and black pheromone trails for more robust search.
 Hybrid Methods: Combines metaheuristics with 2Opt (e.g., ACS2Opt, RBACS2Opt).
Contributing
Contributions to ibnbattuta
are welcome! Please submit issues or pull requests via GitHub.
License
This project is licensed under the MIT License.
Acknowledgments
This project is inspired by the work of various TSP solvers and metaheuristics, and is named after the famous explorer Ibn Battuta, representing the spirit of exploring optimal solutions in vast solution spaces.
Special thanks to the authors of the following libraries and tools:
 TSPLIB: Used for benchmarking TSP instances.
 teeline: Used as a reference for implementing exact algorithms.
 tspfrs: Used as base for the parser implementation, with modifications to accommodate for needs of this library.
Particular thanks to the authors of the following papers :
 Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization.
 Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for the TravelingSalesman Problem.
 Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study.
 Helsgaun, K. (2000). An Effective Implementation of the LinKernighan Traveling Salesman Heuristic.
 Reinelt, G. (1991). TSPLIB  A Traveling Salesman Problem Library.
 Gambardella, L. M., Dorigo, M., & Blum, C. (1999). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.
 Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents.