rapid_solve 0.1.7

This library provides a metaheuristic framework for solving combinatorial optimization problems.
Documentation 
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

//! This module contains the implementation of the [`SimulatedAnnealingSolver`] for the TSP, see
//! the [build] function for details.
//! ```ignore
//! pub fn build(tsp_instance: Arc<TspInstance>) -> SimulatedAnnealingSolver<TspTourWithInfo> {
//!     let node_count = tsp_instance.get_number_of_nodes();
//!     let average_distance: Distance = (0..node_count)
//!         .flat_map(|i| (0..node_count).filter_map(move |j| if i != j { Some((i, j)) } else { None }))
//!         .map(|(i, j)| tsp_instance.get_distance(i, j))
//!         .sum::<Distance>()
//!         / (node_count * (node_count - 1)) as Distance;
//!
//!     let acceptance_probability_function = Box::new(
//!         |current_objective_value: &ObjectiveValue,
//!          new_objective_value: &ObjectiveValue,
//!          temperature: Temperature| {
//!             if new_objective_value < current_objective_value {
//!                 1.0
//!             } else {
//!                 let current_total_distance = current_objective_value
//!                     .iter()
//!                     .next()
//!                     .unwrap()
//!                     .unwrap_float();
//!                 let new_total_distance = new_objective_value.iter().next().unwrap().unwrap_float();
//!                 ((current_total_distance - new_total_distance) / temperature).exp()
//!             }
//!         },
//!     );
//!
//!     let initial_temperature = average_distance;
//!
//!     let neighborhood = Arc::new(RotatedThreeOptNeighborhood::new(tsp_instance));
//!
//!     let objective: Arc<Objective<TspTourWithInfo>> =
//!         Arc::new(build_objective_for_tsp_tour_with_info());
//!
//!     SimulatedAnnealingSolver::initialize(
//!         neighborhood,
//!         objective,
//!         initial_temperature,
//!         0.9,
//!         acceptance_probability_function,
//!         Some(13), // random_seed
//!     )
//! }
//! ```
use crate::examples::tsp::tsp_instance::TspInstance;
use crate::examples::tsp::tsp_tour_with_info::neighborhood::RotatedThreeOptNeighborhood;
use crate::examples::tsp::tsp_tour_with_info::objective::build_objective_for_tsp_tour_with_info;
use crate::examples::tsp::tsp_tour_with_info::TspTourWithInfo;
use crate::examples::tsp::Distance;
use crate::heuristics::simulated_annealing::{SimulatedAnnealingSolver, Temperature};
use crate::objective::{Objective, ObjectiveValue};
use std::sync::Arc;

/// Builds a [`SimulatedAnnealingSolver`] for the TSP.
/// * The neighborhood is the [3-opt neighborhood][RotatedThreeOptNeighborhood], i.e., the neighborhood that consists of
/// all tours that can be obtained by applying the 3-opt operation.
/// * Since starting each neighborhood with the index (0, 1, 2) leads to back and forth moves,
/// the [`TspTour`][`super::super::tsp_tour::TspTour`] is wrapped in a [`TspTourWithInfo`] to store
/// the first index of the last move. The next move then starts with the first index one after the
/// first index of the previous move, which means that the backwards move appears very late in the
/// neighborhood iterator.
/// * The initial temperature is set to the average distance between two nodes.
/// * The acceptance probability function is an exponential function that accepts worse solutions
/// with a probability given by the formula e<sup>-∆f/T</sup>, where ∆f is the difference in
/// objective value and T is the current temperature.
/// * The cooling factor is set to 0.9.
/// * We set a random seed to have reproducible results.
pub fn build(tsp_instance: Arc<TspInstance>) -> SimulatedAnnealingSolver<TspTourWithInfo> {
    let node_count = tsp_instance.get_number_of_nodes();
    let average_distance: Distance = (0..node_count)
        .flat_map(|i| (0..node_count).filter_map(move |j| if i != j { Some((i, j)) } else { None }))
        .map(|(i, j)| tsp_instance.get_distance(i, j))
        .sum::<Distance>()
        / (node_count * (node_count - 1)) as Distance;

    let acceptance_probability_function = Box::new(
        |current_objective_value: &ObjectiveValue,
         new_objective_value: &ObjectiveValue,
         temperature: Temperature| {
            if new_objective_value < current_objective_value {
                1.0
            } else {
                let current_total_distance = current_objective_value
                    .iter()
                    .next()
                    .unwrap()
                    .unwrap_float();
                let new_total_distance = new_objective_value.iter().next().unwrap().unwrap_float();
                ((current_total_distance - new_total_distance) / temperature).exp()
            }
        },
    );

    let initial_temperature = average_distance;

    let neighborhood = Arc::new(RotatedThreeOptNeighborhood::new(tsp_instance));

    let objective: Arc<Objective<TspTourWithInfo>> =
        Arc::new(build_objective_for_tsp_tour_with_info());

    SimulatedAnnealingSolver::initialize(
        neighborhood,
        objective,
        initial_temperature,
        0.9,
        acceptance_probability_function,
        Some(13), // random_seed
    )
}

#[cfg(test)]
mod tests {
    use super::build;
    use crate::{
        examples::tsp::{
            tsp_instance::TspInstance, tsp_tour::TspTour, tsp_tour_with_info::TspTourWithInfo,
        },
        heuristics::Solver,
    };
    use std::sync::Arc;

    #[test]
    fn test_simulated_annealing() {
        let tsp_instance = Arc::new(TspInstance::new(vec![
            vec![0.0, 10.0, 15.0, 20.0],
            vec![10.0, 0.0, 35.0, 25.0],
            vec![15.0, 35.0, 0.0, 30.0],
            vec![20.0, 25.0, 30.0, 0.0],
        ]));
        let tsp_tour_with_infos =
            TspTourWithInfo::new(TspTour::new(vec![0, 1, 2, 3], tsp_instance.clone()), 0);

        let solver = build(tsp_instance.clone());

        let final_tour = solver.solve(tsp_tour_with_infos);
        assert_eq!(final_tour.unwrap().unwrap().get_nodes(), &vec![0, 1, 3, 2]);
    }

    #[test]
    fn test_simulated_annealing_large_instance() {
        let tsp_instance = Arc::new(
            TspInstance::from_tsplib_file("resources/tsp_test_instances/berlin52.tsp").unwrap(),
        );
        let tour = TspTour::from_instance_nearest_neighbor(tsp_instance.clone());
        let tour_with_infos = TspTourWithInfo::new(tour, 0);
        let solver = build(tsp_instance.clone());

        let local_opt_tour = solver.solve(tour_with_infos);

        assert_eq!(
            local_opt_tour.unwrap().unwrap().get_nodes(),
            &vec![
                0, 35, 38, 39, 37, 36, 33, 34, 48, 31, 44, 18, 40, 7, 8, 9, 42, 32, 11, 27, 26, 25,
                46, 12, 13, 51, 10, 50, 24, 3, 5, 14, 4, 23, 47, 45, 43, 15, 28, 49, 19, 22, 29, 1,
                6, 41, 20, 16, 2, 17, 30, 21
            ]
        );
    }
}