## 3 Simulated Annealing Approach for the Corridor Planning Problem
For improving the search procedure, diverse neighborhood structures are used, allowing found approximate solutions, adjusted to the complexity and nature of the problem [49]. Algorithm 1, shows the procedure to locate a near-optimal corridor. In this algorithm, \(s_{i}\) is the initial solution, \(m\) is the counter increasing until reaching the Markov chain length (\(L_{markov}\)) defining the Metropolis cycle. \(P_{tam}\) is the size of a partial route where a random segment is altered, and \(s_{opt}\) is the optimal solution found by the algorithm. \(T_{0}\) is the control parameter in SA, \(T_{i}\) is the stopping criterion, and \(\beta\)is the control coefficient. In this algorithm, lines 1-3 point out that a randomly created solution is accepted as the initial solution if it is inside the corridor. The SA external cycle is shown in lines 5-23. In particular, lines 6-21 represent the Metropolis cycle: First, lines 7-10 describe the creation of an alternative solution, in which all nodes must be inside the corridor. If a segment of the path has some node outside the corridor, it is modified with the variable \(P_{tam}\) (lines 8-9), until the entire route is within the corridor. Then, line 11 computes the difference in energy cost. Finally, the acceptance criteria is shown in lines 12-20. Line 22 indicates the updated criterion for the temperature control parameter. At the end of the external cycle, the best solution is returned as the algorithm solution. SA can distribute optimized routes along the corridor, which is only possible with other algorithms if they modify their search procedure. The SA algorithm can generate alternate routes close to the shortest one in the corridor with optimized costs when solving the optimization model presented in relations (1)-(5). Since the SA algorithm generates local optimal solutions, it can find one or more optimal global solutions, where some can be the same found by deterministic procedures such as the Dijkstra procedure, since the problem may have more than one global optimal solution. The SA-based algorithm proposed in this work seeks the optimal global route and finds a variety of optimized local optimal routes meeting the restriction of being inside the corridor. The use of SA is a simpler alternative to find optimized routes within a corridor, independently of the shortest route, which gives a choice of alternative optimized routes for a pipeline installation if the shorter one is challenging to use in the corridor for various unforeseen reasons. The corridor planning problem solved in this work is encoded in a rectangular mesh of \(n\) rows and \(m\) columns, where each node connects with eight neighboring nodes with constant distance. The search space is determined based on the number of nodes in the network, \(z=n\ x\ m\), such as it is \(8^{2}\)[50]. However, the mesh contour conditions should be considered to determine the total number of feasible routes connecting the origin and destination nodes. If reverse walks are restricted, the search domain is reduced to \(8\times 7^{2}\)[51]. The initial solution used by the SA algorithm is created using the cumulative penalty costs matrix, where indices correspond with the point coordinates. The rectangular mesh is generated using the universal transversal Mercator (UTM) system. A greedy uninformed search procedure is used to create the initial solution encoded by two integer-valued vectors containing the coordinates of the nodes being part of the route. Figure 1 shows a candidate solution representing a path between (0,0) and (5,5) points. The mechanism to find neighboring solutions builds pseudo-random paths between two points selected at random in the current solution. The search for alternatives routes uses a matrix of visited nodes to avoid using those that have been part of previous solutions. This procedure applies the following steps:  
1. Randomly select a point \(r_{1}\) from \(s\). 2. Randomly select a second point \(r_{2}\) from \(s\).