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 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
//! The *solver* module contains basic building blocks for a metaheuristic among with the default //! implementation. //! //! # Metaheuristic //! //! A metaheuristic is a high-level algorithmic framework that provides a set of guidelines or strategies //! to develop heuristic optimization algorithms. Examples of metaheuristics include genetic/evolutionary //! algorithms, tabu search, simulated annealing, variable neighborhood search, (adaptive) large //! neighborhood search, ant colony optimization, etc. //! //! The default implementation can be roughly described as "*Multi-objective Parthenogenesis based //! Evolutionary Algorithm with Ruin and Recreate Mutation Operator*". //! //! # Multi-objective decision maker //! //! Most VRPs, frequently used to model real cases, are set up with a single objective (e.g. minimizing //! the cost of the solution), however the majority of the problems encountered in logistics industry, //! are multi-objective in nature as the complexity of real-life logistics planning often cannot be //! reduced to cost only. Such non-cost factors are: //! //! - **balancing work across multiple workers** //! - **minimization or maximization of fleet usage** //! - **minimization of unassigned jobs** //! //! In most of the cases, these additional factors are contradicting to the cost minimization //! objective which, in fact, leads to nontrivial multi-objective optimization problem, where no //! single solution exists that simultaneously optimizes each objective. //! //! That's why the concept of dominance is introduced: a solution is said to dominate another //! solution if its quality is at least as good on every objective and better on at least one. //! The set of all non-dominated solutions of an optimization problem is called the Pareto set and //! the projection of this set onto the objective function space is called the Pareto front. //! //! The aim of multi-objective metaheuristics is to approximate the Pareto front as closely as //! possible (Zitzler et al., 2004) and therefore generate a set of mutually non-dominated solutions //! called the Pareto set approximation. //! //! This library utilizes `NSGA-II` algorithm to apply Pareto-based ranking over population in order //! to find Pareto set approximation. However, that Pareto optimality of the solutions cannot be //! guaranteed: it is only known that none of the generated solutions dominates the others. //! In the end, the top ranked individual is returned as best known solution. //! //! This crate contains NSGA-II buildings blocks which can be found in [`nsga2`] module. //! //! [`nsga2`]: ../algorithms/nsga2/index.html //! //! # Evolutionary algorithm //! //! An evolutionary algorithm (EA) is a generic population-based metaheuristic optimization algorithm. //! This crate provides a custom implementation of EA which can be divided into the following steps: //! //! - **initialization**: on this step, an initial population is created using different construction //! heuristics. //! - **main loop begin**: enter an evolution loop //! - **selection**: an individual is selected from population. Best-fit individuals have more //! chances to be selected. //! - **mutation**: a mutation operator is applied to selected individual. Default implementation //! uses `ruin and recreate` principle described in next section. //! - **population adjustments**: new individual is added to population, then the population is //! sorted and shrinked to keep it under specific size limits with best-fit individuals and //! some intermediate. //! - **main loop end**: exit evolution loop when one of termination criteria are met. See [`termination`] //! module for details. //! //! As there is no crossover operator involved and offspring is produced from one parent, this algorithm //! can be characterized as parthenogenesis based EA. This approach eliminates design of feasible //! crossover operator which is a challenging task in case of VRP. //! //! [`termination`]: termination/index.html //! //! # Ruin and Recreate principle //! //! A **ruin and recreate** principle is introduced by [`Schrimpf et al. (2000)`] and key idea here //! is to ruin a quite large fraction of the solution and try to restore the solution as best as it //! is possible in order to get a new solution better than the previous one. Original algorithm can //! be described as a large neighborhood search that combines elements of simulated annealing and //! threshold-accepting algorithms, but this crate only reuses ruin/recreate idea as a mutation //! operator. //! //! Implementation blocks can be found in [`mutation`] module. //! //! [`Schrimpf et al. (2000)`]: https://www.sciencedirect.com/science/article/pii/S0021999199964136 //! [`mutation`]: mutation/index.html //! //! # Solver usage //! //! Check [`Builder`] and [`Solver`] documentation to see how to run VRP solver. //! //! [`Builder`]: ./struct.Builder.html //! [`Solver`]: ./struct.Solver.html //! extern crate rand; use crate::algorithms::nsga2::Objective; use crate::construction::heuristics::InsertionContext; use crate::construction::Quota; use crate::models::common::Cost; use crate::models::{Problem, Solution}; use hashbrown::HashMap; use std::any::Any; use std::sync::Arc; pub mod mutation; pub mod objectives; pub mod selection; pub mod termination; mod builder; pub use self::builder::Builder; mod evolution; use self::evolution::{EvolutionConfig, EvolutionSimulator}; mod population; pub use self::population::DominancePopulation; mod telemetry; pub use self::telemetry::{Metrics, Telemetry, TelemetryMode}; use std::cmp::Ordering; /// A key to store solution order information. pub const SOLUTION_ORDER_KEY: i32 = 100; /// A type which encapsulates information needed to perform solution refinement process. pub struct RefinementContext { /// Original problem definition. pub problem: Arc<Problem>, /// A population which tracks best discovered solutions. pub population: Box<dyn Population + Sync + Send>, /// A collection of data associated with refinement process. pub state: HashMap<String, Box<dyn Any + Sync + Send>>, /// A quota for refinement process. pub quota: Option<Arc<dyn Quota + Send + Sync>>, /// A refinement statistics. pub statistics: Statistics, } /// A refinement statistics to track evolution progress. pub struct Statistics { /// A number which specifies refinement generation. pub generation: usize, /// An improvement ratio from beginning. pub improvement_all_ratio: f64, /// An improvement ratio for last 1000 iterations. pub improvement_1000_ratio: f64, } /// Represents solution in population defined as actual solution. pub type Individual = InsertionContext; /// A trait which models a population with individuals (solutions). pub trait Population { /// Adds all individuals into the population, then sorts and shrinks population if necessary. /// Returns true if any of newly added individuals is considered as best known. fn add_all(&mut self, individuals: Vec<Individual>) -> bool; /// Adds an individual into the population. /// Returns true if newly added individual is considered as best known. fn add(&mut self, individual: Individual) -> bool; /// Gets nth individual from population. fn nth(&self, idx: usize) -> Option<&Individual>; /// Compares two solutions the same way as population does. fn cmp(&self, a: &Individual, b: &Individual) -> Ordering; /// Returns individuals within their rank sorted according their quality. fn ranked<'a>(&'a self) -> Box<dyn Iterator<Item = (&Individual, usize)> + 'a>; /// Returns population size. fn size(&self) -> usize; } impl RefinementContext { /// Creates a new instance of `RefinementContext`. pub fn new( problem: Arc<Problem>, population: Box<dyn Population + Sync + Send>, quota: Option<Arc<dyn Quota + Send + Sync>>, ) -> Self { Self { problem, population, state: Default::default(), quota, statistics: Statistics::default() } } } impl Default for Statistics { fn default() -> Self { Self { generation: 0, improvement_all_ratio: 0., improvement_1000_ratio: 0. } } } /// A Vehicle Routing Problem Solver based on evolutionary algorithm. pub struct Solver { /// A VRP problem definition. pub problem: Arc<Problem>, /// An evolution configuration. pub config: EvolutionConfig, } impl Solver { /// Solves a Vehicle Routing Problem and returns a _(solution, its cost)_ pair in case of success /// or error description, if solution cannot be found. /// /// # Examples /// /// The most simple way to run solver is to use [`Builder`](./struct.Builder.html) /// which has preconfigured settings: /// /// ``` /// # use vrp_core::models::examples::create_example_problem; /// # use std::sync::Arc; /// use vrp_core::solver::Builder; /// use vrp_core::models::Problem; /// /// // create your VRP problem /// let problem: Arc<Problem> = create_example_problem(); /// // build solver using builder with default settings /// let solver = Builder::new(problem).build()?; /// // run solver and get the best known solution within its cost. /// let (solution, cost, _) = solver.solve()?; /// /// assert_eq!(cost, 42.); /// assert_eq!(solution.routes.len(), 1); /// assert_eq!(solution.unassigned.len(), 0); /// # Ok::<(), String>(()) /// ``` pub fn solve(self) -> Result<(Solution, Cost, Option<Metrics>), String> { let (population, metrics) = EvolutionSimulator::new(self.config)?.run()?; // NOTE select the first best individual from population let (insertion_ctx, _) = population.ranked().next().ok_or_else(|| "cannot find any solution".to_string())?; let solution = insertion_ctx.solution.to_solution(self.problem.extras.clone()); let cost = self.problem.objective.fitness(insertion_ctx); Ok((solution, cost, metrics)) } }