# An Improved Variable Neighborhood Search for the Reconfigurable Assembly Line Reconfiguring Problem
## 5 Proposed IVNS-RALRP
### Algorithm Framework  
VNS systematically explores different neighborhood structures, allowing it to escape local optima effectively. By switching between different neighborhoods, VNS can explore a broader search space than algorithms that rely on a single neighborhood structure. For certain specific combinatorial optimization problems, we can design specialized neighborhood structures based on the problem characteristics for VNS, thereby further enhancing its performance. So, we choose VNS as the algorithm framework. The basic component of the algorithm is basic VNS proposed by [PERSON] and [PERSON] in 1997 [22,23]. Firstly, it is necessary to select the set of neighborhood structures, generate the initial solution \(x\), choose the stopping condition, and complete the initialization of the algorithm. Subsequently, the main iterative process of VNS includes three parts: shaking, local search, and move or not. The current solution \(x\) in a certain neighborhood structure undergoes shaking to produce a temporary solution \(x^{\prime}\). A local search is performed on the temporary solution \(x^{\prime}\) to obtain a locally optimal solution \(x^{\prime\prime}\). Then, move or not is executed: if the locally optimal solution \(x^{\prime\prime}\) is better than the current solution \(x\), \(x^{\prime\prime}\) is taken as the current solution \(x\) to initiate a new search; otherwise, shaking is continued on \(x\) within other neighborhood structures. The entire iterative process continues until a stopping condition is met. The stopping condition may be, e.g., maximum CPU time allowed, maximum number of iterations, or maximum number of iterations between two improvements. Steps of the VNS are presented as follows:  
Figure 4: Data structure of assembly line. Figure 3: Data structure of product. * Initialization. Select the set of neighborhood structures \(\mathcal{N}_{k},k=1,\ldots,k_{\text{max}}\), that will be used in the search; find an initial solution \(x\); choose a stopping condition;
* Repeat the following until the stopping condition is met: 1. Set \(k\gets 1\); 2. Until \(k=k_{max}\), repeat the following steps: 1. Shaking. Generate a point \(x^{\prime}\) at random from the \(k\)th neighborhood of \(x\) (\(x^{\prime}\in\mathcal{N}_{k}(x)\)); 2. Local search. Apply some local search method with \(x^{\prime}\) as initial solution; denote with \(x^{\prime\prime}\) the so obtained local optimum; 3. Move or not. If this local optimum is better than the incumbent, move there (\(x\gets x^{\prime\prime}\)), and continue the search with \(\mathcal{N}_{1}(k\gets 1)\); otherwise, set \(k\gets k+1\). In RALRP, the sequence of operations in each solution must adhere to process precedence constraints. This method enhances the basic VNS by incorporating a legal check for these constraints. Each solution generated by the shaking process requires this legal check for process precedence constraint. If the constraints are satisfied, the next process proceeds; otherwise, the shaking process is repeated. Since the solution for RALRP involves both operation and resource dimensions, where resources are constrained by operations, the method first generates a partial solution through shaking that includes only operations. Subsequently, it employs local search to explore the solutions with resource. The detailed procedure of IVNS-RALRP is presented in Algorithm 1. 1. The first three lines initialize the problem. Line 1 initializes iteration for the algorithm. Line 2 computes the indegree of all operations of the product to facilitate legal check for process precedence constraint. Line 3 obtains an initial solution \(NAL\) as the current solution through the initialization algorithm. 2. Line 4 calculates the reconfiguration cost of the current solution \(NAL\) using the cost computation method. 3. Line 5 to 21 represent the iteration process of IVNS-RALRP, with the stopping condition being the maximum iteration. Line 6 counts the iteration. 4. Line 7 to 20 sequentially search \(k\)th neighborhood of the current solution \(NAL\). 5.