arion/
routing.rs

1use crate::vehicle::Vehicle;
2use crate::location::Location;
3use crate::route::Route;
4use crate::errors::InfeasableProblem;
5use itertools::Itertools;
6
7pub struct UnsolvedProblem { 
8    vehicles: Vec<Vehicle>,
9    destinations: Vec<Location>,
10}
11
12impl UnsolvedProblem { 
13    pub fn new(vehicles: Vec<Vehicle>, destinations: Vec<Location>) -> Self { 
14        UnsolvedProblem { 
15            vehicles, 
16            destinations
17        }
18    }
19
20    pub fn initial_solution(self) -> Result<SolvedProblem, InfeasableProblem> { 
21        if !self.solvable() { 
22            return Err(InfeasableProblem)
23        }
24
25        let mut routes: Vec<Route> = Vec::new();
26        let mut destinations = self.destinations;
27        let mut vehicles = self.vehicles;
28
29        destinations.sort_by(|a, b| b.cmp(a));        
30        vehicles.sort_by(|a, b| b.cmp(a));        
31        
32        for vehicle in vehicles {
33            let mut route = Route::new(vehicle);
34
35            let mut remainder = Vec::new();
36            for destination in destinations.into_iter() { 
37                
38                if destination.demand <= route.vehicle.capacity { 
39                    dbg!(&route.vehicle);
40                    route.vehicle.capacity -= destination.demand;
41                    route.destinations.push(destination)
42                } else { 
43                    remainder.push(destination)
44                }
45            }
46            destinations = remainder;
47
48            routes.push(route)
49        }
50
51        dbg!(&routes);
52
53        Ok(SolvedProblem::new(routes))
54    }
55
56    /// https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing
57    /// Order the items from largest to smallest.
58    /// Open a new empty bin, bin #1.
59    /// For each item from largest to smallest, find the first bin into which the item fits, if any.
60    /// If such a bin is found, put the new item in it.
61    /// Otherwise, open a new empty bin put the new item in it.
62    pub fn solvable(&self) -> bool {
63        let mut demands: Vec<i64> = self.destinations.iter().map(|location| &location.demand).copied().collect();
64        let mut capacities: Vec<i64> = self.vehicles.iter().map(|vehicle| &vehicle.capacity).copied().collect();
65
66        demands.sort_by(|a, b| b.cmp(a));
67        capacities.sort_by(|a, b| b.cmp(a));
68        
69        let mut put_in_bin: bool;
70        for demand in demands { 
71            put_in_bin = false;
72            for capacity in capacities.iter_mut() { 
73                dbg!(&demand, &capacity);
74                if demand <= *capacity { 
75                    *capacity -= demand;
76                    put_in_bin = true;
77                    break;
78                }
79            }
80            if !put_in_bin { 
81                return false
82                }
83        }
84        true
85    }
86}
87
88pub struct SolvedProblem { 
89    routes: Vec<Route>,
90}
91
92impl SolvedProblem { 
93    pub fn new(routes: Vec<Route>) -> SolvedProblem { 
94        SolvedProblem { 
95            routes: routes
96        }
97    }
98    
99    pub fn intra_two_opt(mut self) -> SolvedProblem { 
100        fn two_opt(route: &mut Route) {
101            let n_nodes = 2;
102            let mut best_cost = route.cost();
103            for i in 0..route.destinations.len()-(n_nodes-1) {
104                let mut candidate_route_destinations = route.destinations.clone();
105                candidate_route_destinations.swap(i, i+n_nodes);
106                
107                std::mem::swap(&mut route.destinations, &mut candidate_route_destinations);
108                let cost = route.cost();
109                if cost < best_cost { 
110                    best_cost = cost;
111                } else {
112                    std::mem::swap(&mut route.destinations, &mut candidate_route_destinations);
113                }
114            }
115         }
116
117        for route in self.routes.iter_mut() { 
118            two_opt(route)
119        }
120
121        self
122    }
123
124    pub fn intra_three_opt(mut self) -> SolvedProblem { 
125        fn three_opt(route: &mut Route) { 
126            let n_nodes: usize = 3;
127            let mut best_cost = route.cost();
128
129            let route_len = route.destinations.len();
130            for i in 0..route_len-(n_nodes-1) {
131                for j in i..route_len-(n_nodes-2) { 
132                    for k in j..route_len {
133                        let index = [i,j,k];
134                        let options = index.iter().permutations(3);
135                        'options: for option in options { 
136                            let i2 = *option[0]; // vec length should be 3 for 3-opt
137                            let j2 = *option[1]; // vec length should be 3 for 3-opt
138                            let k2 = *option[2]; // vec length should be 3 for 3-opt
139
140                            let mut candidate_route_destinations = route.destinations.clone();
141                            candidate_route_destinations.swap(i, i2);
142                            candidate_route_destinations.swap(j, j2);
143                            candidate_route_destinations.swap(k, k2);
144
145                            std::mem::swap(&mut route.destinations, &mut candidate_route_destinations);
146                            let cost = route.cost();
147                            if cost < best_cost { 
148                                best_cost = cost;
149                                break 'options;
150                            } else {
151                                std::mem::swap(&mut route.destinations, &mut candidate_route_destinations);
152                            }
153                        }
154                    }
155                }
156            }
157        }
158        for route in self.routes.iter_mut() { 
159            three_opt(route)
160        }
161
162        self
163    }
164
165
166}
arion/routing.rs

arion/
routing.rs
