## 2 Problem Statement
### Existing Methodologies to Generate Alternate Routes  
Several techniques to evaluate the number of alternate routes and solve the corridor planning problem have been described in the existing literature. The iterative penalty method [7] assigns penalty parameters to graph arcs once they are selected to be part of a candidate solution. This method is initially proposed for road design, but it has also been used for routing hazardous materials [16], among other applications. In [8], the gateway shortest path (GSP) method based on a constrained shortest path problem is introduced. The Global Positioning System (GPS) generates the shortest route between two points without passing through points known as gateways. GPS allows the identification of different acceptable alternative paths with less computational effort concerning penalty methods. The k-shortest-path algorithm [17] and the near-shortest path method [18] are two methods generating a set of lower-cost paths based on small variations of their initial solution.  
Furthermore, the k-differentiated-path (kDP) algorithm proposed in [19] uses a minimax approach to find k-differentiated-shortest paths that are relatively different from one another, but not necessarily disjoint. On the other hand, the p-dispersion algorithm in [20] first creates a broad set of candidate routes, and then it selects a subset of them using a dispersion model, maximizing the minimum difference between any pair of selected routes. In [21], the authors locate corridors as a collection of adjacent polygons based on a quantitative criterion measuring the corridor length. This method selects one corridor to cross the polygons using the Dijkstra algorithm. In contrast, in [9], the authors use multiple gateways to generate more complex paths. This approach is similar to the GPS method, except for allowing that the route uses more than one gateway. Other proposed strategies use parallel computing to run their procedures, such as the kth-shortest path and the near-shortest path method [22; 23]. The main disadvantage of these methods is that the needed time to reach an optimal solution grows exponentially as the problem size increases [24].  
An alternative to deal with these problems is applying some non-deterministic heuristic capable of generating near-optimal solutions in a reasonable computation time. In [25; 26; 27; 28; 29], the authors use genetic algorithms (GAs) to optimize two and three-dimensional highway alignments. These approaches only differ in the objective function elements, such as right-of-way cost, travel-time cost, earthwork cost, structure cost, and socioeconomic cost. This formulation is also used by [30; 31] to solve the rail transit alignment problem. In [32], a parallel GA to solve the intercity railway alignment problem is used. In [6], a multi-objective GA, named MOGADOR, for solving the general corridor alignment problem is applied, and the authors in [33; 34] also use a multi-objective GA to solve the highway alignment problem. On the other hand, scarce application of other heuristics for the corridor planning problem has been described in the existing literature, such as the tabu search for alignment of forest roads [35] and simulated annealing [36], particle swarm optimization [37], and ant colony optimization [38] for the highway alignment problem.