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

//! This module contains the implementation of the [`ThresholdAcceptingSolver`] for the TSP. See
//! the [build] function for details.
//! ```ignore
//! pub fn build(tsp_instance: Arc<TspInstance>) -> ThresholdAcceptingSolver<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 initial_threshold = ObjectiveValue::new(vec![BaseValue::Float(average_distance)]);
//!
//!     let neighborhood = Arc::new(RotatedThreeOptNeighborhood::new(tsp_instance));
//!
//!     let objective: Arc<Objective<TspTourWithInfo>> =
//!         Arc::new(build_objective_for_tsp_tour_with_info());
//!
//!     ThresholdAcceptingSolver::initialize(neighborhood, objective, initial_threshold, 0.9)
//! }
//! ```
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::threshold_accepting::ThresholdAcceptingSolver;
use crate::objective::{BaseValue, Objective, ObjectiveValue};
use std::sync::Arc;

/// Builds a [`ThresholdAcceptingSolver`] 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 threshold is set to the average distance between two nodes.
/// * The threshold is reduced by 0.9 whenever a worse neighbor is accepted.
pub fn build(tsp_instance: Arc<TspInstance>) -> ThresholdAcceptingSolver<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 initial_threshold = ObjectiveValue::new(vec![BaseValue::Float(average_distance)]);

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

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

    ThresholdAcceptingSolver::initialize(neighborhood, objective, initial_threshold, 0.9)
}

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

    use super::build;

    #[test]
    fn test_threshold_accepting() {
        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_basic_local_search_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, 21, 17, 16, 2, 44, 18, 40, 7, 8, 9, 32, 42, 14, 4, 5, 3, 27, 26, 25, 46, 12, 13,
                51, 10, 50, 11, 24, 45, 47, 23, 37, 36, 39, 38, 35, 34, 33, 43, 15, 28, 49, 19, 22,
                20, 41, 6, 1, 29, 30, 31, 48
            ]
        );
    }
}