China
Africa
Explore chapters and articles related to this topic
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
The most widely studied VRPs are the capacitated VRP and the VRP with time windows (VRPTW). Variable neighborhood search (VNS) is a meta-heuristic based on the idea of systematically changing the neighborhood structure during the search. VNS systematically exploits the following observation: A local optimum with respect to one neighborhood structure is not necessary as for another.A global optimum is a local optimum with respect to all possible neighborhood structures.For many problems, local optima with respect to one or several neighborhoods are relatively close to each other.
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Intelligent Autonomy of Uavs, 2018
The most widely studied VRPs are the capacitated VRP and the vehicle routing problem with time windows (VRPTW). Variable neighborhood search (VNS) is a meta-heuristic based on the idea of systematically changing the neighborhood structure during the search. VNS systematically exploits the following observation:A local optimum with respect to one neighborhood structure is not necessary as for another.A global optimum is a local optimum with respect to all possible neighborhood structures.For many problems local optima with respect to one or several neighborhoods are relatively close to each other.
Methodology
Published in Tolga Bektaş, Freight Transport and Distribution, 2017
Variable neighbourhood search (VNS) is an extension of the VND where, prior to applying local search with a given operator Oi in the set (O1, O2,…,Om), a shake mechanism is invoked, which randomly selects a solution in the neighbourhood of Oi. The enumeration through the list of operators and the way that the search restarts are as in VND.
Multi-objective optimization for multi-depot heterogeneous first-mile transportation system considering requests’ preference ranks for pick-up stops
Published in Transportmetrica A: Transport Science, 2023
Jingxuan Ren, Wenzhou Jin, Weitiao Wu
The NSGA II (a fast and elitist genetic multi-objective algorithm) is a variant of the genetic algorithm used to solve multi-objective problems by introducing non-dominated sorting, Pareto solutions, and crowd distance (Deb et al. 2002). This leads to the adaptability of NSGA II to a wide range of realistic problems using customised encoding and decoding methods (Psychas et al. 2014; Psychas, Marinaki, and Marinakis 2015; Haas and Bekhor 2017; Wang, Ma, and Xu 2020; Gharib, Ghomi, and Jolai 2021). To exploit the promising areas identified by the population-based NSGA II, methods can be introduced to improve the solution quality of NSGA II. Variable neighbourhood search (VNS), a metaheuristic method for solving problems by searching the distant neighbourhood, is one of the methods that can be easily customised to exploit promising areas based on the problem characteristics (Hansen and Mladenović 1997; Hansen and Mladenović 2001; Jabir, Panicker, and Sridharan 2017; Shao, Xu, and Huang 2020). The hybrid of NSGA II and VNS has been shown to be effective and efficient in the vehicle routing problem and other highly related problems (Psychas et al. 2014; Psychas, Delimpasi, and Marinakis 2015; Psychas et al. 2017; Vanneschi, Henriques, and Castelli 2017; Masri, Krichen, and Guitouni 2019).
Scheduling in a flexible job shop followed by some parallel assembly stations considering lot streaming
Published in Engineering Optimization, 2022
Fatemeh Daneshamooz, Parviz Fattahi, Seyed Mohammad Hassan Hosseini
According to the summary of previous studies, no attempt has been made to jointly consider an FJSP with parallel assembly stages and a lot streaming technique. Hence, in this article the considered problem will be solved with the aim of minimizing the maximum completion time. The FJSP is a much more complex version of the JSP, so the FJSP is strongly NP hard (Yazdani, Amiri, and Zandieh 2010). This problem will be made more complex by adding a parallel assembly stage and lot streaming technique to the FJSP. Owing to the complexity of the considered problem, finding the optimal or near-optimal solutions will be a challenge, especially in a limited time, for medium- and large-sized instances. The variable neighbourhood search (VNS) algorithm is one of the metaheuristic algorithms, which are based on the systematic changes of the neighbourhood in the search space. The VNS algorithm is able to search different parts of the solution space by the use of different neighbourhood structures, so that it can be released from the trap of local optima. This algorithm is known to be effective because of its simple implementation and the quality of the solution. Therefore, in this article, two hybrid metaheuristic algorithms based on the VNS algorithm are presented. The first one is a two-level self-adaptive parallel variable neighbourhood search (TLSAPVNS) and the second is a two-level self-adaptive variable neighbourhood search (TLSAVNS) algorithm. Both algorithms are based on two levels of decisions. A VNS based on an integrated approach is also presented.
A hybrid algorithm combining genetic algorithm and variable neighborhood search for process sequencing optimization of large-size problem
Published in International Journal of Computer Integrated Manufacturing, 2020
Yabo Luo, Yuling Pan, Cunrong Li, Hongtao Tang
Variable Neighborhood Search (VNS) is a commonly used method to decompose a complex solution space into multiple simple subspaces to reduce the complexity of the solution, and there are many research results in some fields. For example, in solving mathematical problems, Sevkli and Hamza (2019) propose two novel models based on VNS algorithm to solve Sudoku puzzles, in which, four neighborhood structures are proposed and implemented by using different local search improvement strategies. For the mathematical problem of graphical model energy minimization (Ouali et al. 2020), an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration is proposed. For computing graph separators (Sánchez-Oro, Mladenović, and Duarte 2017), a new heuristic algorithm based on the VNS methodology for computing vertex separators is proposed, and computational results show that the proposed procedure obtains the optimum solution in all of the small and medium instances, and high-quality results in large instances. In addition to solving mathematical problems, VNS also has some applications in the routing scheduling problem. For example, a two-stage VNS algorithm for the consistent vehicle routing problem (ConVRP) is presented and tested (Xu and Cai 2018). For the integrated location routing scheduling problem, a skewed general variable neighborhood search-based heuristic is proposed and the proven optimal solution in a significant number of cases is provided (Macedo et al. 2015).