# A Survey on Variable Neighborhood Search for Sustainable Logistics
## 2 VNS: Concept, Versions, and Extensions  
VNS is a metaheuristic proposed by [PERSON] in 1995 [3], whose key idea was to apply systematic changes in the neighborhood structure during search. The metaheuristic framework was first formalized in 1997 in joint works with [PERSON] [4; 5]. The principles of this metaheuristic were established in 2001 [6]. VNS has played an important role in the field of metaheuristics and its applications [7; 8; 9]. This metaheuristic and its versions have been applied to a large series of optimization problems and most logistic problems since the beginning of the century [9; 10]. These versions appear considering variations of their components and the inclusion of another ingredient in the framework [11]. It has three main components: a shaking method, an improvement procedure, and a neighborhood change strategy [7]. The main versions are the Basic VNS (BVNS), the Reduced VNS (RVNS), the Variable Neighborhood Descent (VND), the General VNS (GVNS), and the Adaptive VNS (AVNS). The BVNS proposal consists of using a series of neighborhood structures to shake the incumbent solution, a local search to improve it, and the sequential change strategy for the neighborhood structure. Each neighborhood structure is given by a specific set of moves that can be applied to a solution; the neighborhood of that solution is constituted by the solutions that can be obtained by applying one of these moves. The shaking of a solution consists of selecting a random solution from its neighborhood. The sequential strategy consists of selecting the next neighborhood structure of the series if there is no improvement in the best solution found so far and starting with the first structure of the series otherwise. Therefore, starting from the initial solution as the current solution, the procedure shakes and applies the local search to the current. The change strategy is applied until no improvement in the best solution is obtained with the last structure of the series. RVNS is a very simple proposal that consists of excluding the improvement step in BVNS [7]. An RVNS method is obtained when no local search is applied after shaking the current solution, i.e., selecting the next neighborhood structure of the series if the shaking solution does not improve the best solution found so far and starting with the first structure of the series otherwise. VND is the variant that appears by applying the core VNS idea of a sequential change in the neighborhood structure to a neighborhood-based local search. GVNS is one of the most widely used versions of VNS [7]. This variant is obtained from BVNS, using a VND as the improvement step. The series of neighborhoods used in the shaking phase and in the VND could be the same, but usually they are different because their purposes are different. Different versions of VNS appear by considering variations of these proposals and the inclusion of another ingredient in the framework [11]. As a result of the current tendency, the relevance of Artificial Intelligence (AI) approaches in science and technology has the effect of using adaptive tools in optimization search [8]. AVNS is the result of the incorporation of an adaptive mechanism into some of the components of a VNS, mainly in the way of ordering the neighborhoods or when they are selected. The first explicit proposals of an AVNS are in [12; 13]. From the BNS, the AVNS obtained consists of using an adaptive mechanism in the shaking phase by favoring moves or neighborhoods according to their success within the search. This approach is used in sustainable logistics in [14; 15; 16; 17; 18]. A second way is to select the neighborhood for the improvement procedure, usually in a VND, based on its performance during the search process that is applied to sustainable logistics in [19; 20; 21]. The adaptation strategy can be applied in a GVNS in both the shaking phase and improvement phase and is used in sustainable logistics by [22], but most articles use it only in the shaking phase of the GVNS [23; 24; 25].