## 2 Overview of Multiobjective Path Problems and Algorithms
### Approximate Methods  
Given their difficulties, NP-hard optimization problems are often approached by approximate methods which work fast while looking for sets of solutions that approximate the efficient ones. Even if shortest path problems can be solved efficiently, when several objectives are considered or the solutions are subject to additional constraints, the instances become harder and, in such cases, exact methods may not be very successful. An early work concerning an approximate method for solving the MOSPP is [115], where the author proposes a fully polynomial time approximation scheme (FPTAS) to find an approximation to the set of efficient paths. The basic foundation of this algorithm is to use an upper bound on the cost of the paths for every OF, enabling the OF space to be divided into cells such that their size grows exponentially and applying an efficient exact pseudopolynomial algorithm to each cell, namely the algorithm in [12]. The work [116] also introduces a FPTAS for the multiobjective shortest path problem with non-negative and integer arc costs. The algorithm combines a labeling algorithm and a FPTAS proposed in an earlier work by [117]. More recently, [118] proposes an approximation method framework for solving the MOSPP based on three speeding up strategies for labeling algorithms. The authors present a comparison performance study of the proposed approximate methods with other approximate procedures and with exact algorithms, considering random and reference test networks in combinatorial optimization and real-type German power grid networks. Paper [119] addresses the dynamic MOSPP, which considers arc costs that may vary. It develops an exact algorithm under a FIFO assumption that is used as a starting point for an FPTAS for both the static MOSPP and its dynamic variant. Several heuristic and metaheuristic approaches have been used to solve some multiobjective problems that are formulated in the context of telecommunication network routing design, as illustrated in more detail in some references in Section 3. Here, we highlight some of these metaheuristics. Two resolution approaches of a multiobjective routing model based on simulated annealing and on tabu search are proposed and tested in [120]. Simulated annealing (SA) has been widely used to solve different optimization problems. It is based on an analogy with the annealing phenomenon in physics, which involves heating and then slowly cooling (in a controlled manner) a material, which will change its physical properties. This technique, in single objective problems, requires a fine tuning of its parameters, so that it may lead to approximate solutions to the optimal solution. Tabu search (TS) is also a widely used metaheuristic procedure in different optimization problems. It is a local neighborhood search technique. In single objective problems, it tries to diversify the areas of the solution space that are explored. This is achieved by an intelligent guidance into those areas by forbidding some moves and allowing the solutions to become worse (i.e., it is possible to escape local optima). Concerning simulated annealing approaches, next we add two references dedicated to MOPPs [121; 122]. These papers investigate an oriented spanning tree (OST)-based simulated annealing for solving the MOSPP as well as the multiobjective constrained shortest path problem, especially for those with non-linear OFs. The test results are compared with those obtained by a recent Evolutionary Algorithm (EA). Genetic algorithms and EAs are often used to solve multiobjective routing optimization problems. Some examples are in [123; 124; 125; 126]. These algorithms are based on the idea behind the evolution theory by [PERSON], such that the resolution procedure mimics the natural selection observed in nature. Different solutions (represented by chromosomes) are found through the application of operations of crossover and recombination, mutation, and selection.