1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

//! Find an approximate solution to the Travelling Salesman Problem using Simulated Annealing
//!
//! For more information, please see the
//! [metaheuristics::simulated_annealing](https://www.alfie.wtf/rustdoc/metaheuristics/metaheuristics/simulated_annealing/)
//! documentation.
//!
//!# Examples
//!
//!```
//!extern crate time;
//!extern crate travelling_salesman;
//!
//!fn main() {
//!  let tour = travelling_salesman::simulated_annealing::solve(
//!    &[
//!       (27.0, 78.0),
//!       (18.0, 24.0),
//!       (48.0, 62.0),
//!       (83.0, 77.0),
//!       (55.0, 56.0),
//!    ],
//!    time::Duration::seconds(1),
//!  );
//!
//!  println!("Tour distance: {}, route: {:?}", tour.distance, tour.route);
//!}
//!```
extern crate metaheuristics;

use rand::thread_rng;
use time::{Duration};

use super::{
    get_distance_matrix,
    get_route_distance,
    Tour,
    TravellingSalesman,
};

/// Returns an approximate solution to the Travelling Salesman Problem using Simulated Annealing
///
/// `cities` is an array slice, containing `(x,y)` tuple coordinates for each city.
///
/// `runtime` is a `time::Duration`, specifying how long to spend searching for a solution.
///
/// Returns a `travelling_salesman::Tour` struct, representing the approximate solution found.
///
/// For more information, please see the
/// [metaheuristics::simulated_annealing](https://www.alfie.wtf/rustdoc/metaheuristics/metaheuristics/simulated_annealing/)
/// documentation.
///
///```
///extern crate time;
///extern crate travelling_salesman;
///
///fn main() {
///  let tour = travelling_salesman::simulated_annealing::solve(
///    &[
///       (27.0, 78.0),
///       (18.0, 24.0),
///       (48.0, 62.0),
///       (83.0, 77.0),
///       (55.0, 56.0),
///    ],
///    time::Duration::seconds(1),
///  );
///
///  println!("Tour distance: {}, route: {:?}", tour.distance, tour.route);
///}
///```
pub fn solve(cities: &[(f64, f64)], runtime: Duration) -> Tour {
    let mut tsp = TravellingSalesman {
        distance_matrix: &get_distance_matrix(cities),
        rng:             &mut thread_rng(),
    };

    let best_candidate = metaheuristics::simulated_annealing::solve(&mut tsp, runtime);

    Tour {
        distance: get_route_distance(tsp.distance_matrix, &best_candidate.route),
        route:    best_candidate.route,
    }
}