## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.1 Apo--A Posteriori Aggregation of Preferences Methods
The approach is based on the use of the Choquet integral in the context of a multicriteria decision aid method (see [60]), which can model both relative importance and interactions between criteria. The paper introduces Choquet dominance rules [61] which replace the Pareto dominance, integrated within the algorithm by [12]. In [20], the authors present an analysis and a comparison of the performance of three label-setting algorithms that use heuristic information for improving their efficiency, namely, the procedures MOA and NAMOA referred to above, and the algorithm in [16]. The related paper [26] presents a lower-bound-set calculation procedure for the biobjective shortest path problem to be used for improving the computational efficiency of label-setting algorithms. The method is based on a standard dichotomic search that provides increasingly precise lower-bound sets. The work in [22] develops two speedup measures for the algorithm presented in [12] using a well-defined stopping condition enabling the search to be terminated as soon as all efficient paths are found and searching the network bidirectionally. That is, dividing the search procedure into a forward search initiated at the origin node and a backward search initiated at the destination node. Paper [23] develops a parallelized version of a label-setting algorithm for the MOSPP, enabling the calculation of the whole efficient solution set. The procedure is based on the generalization of a priority queue (designated as Pareto queue) for a multiobjective optimization purpose. The authors concluded that the implementation of the developed parallelized algorithm for the biobjective problem yields to an asymptotically lower computational load than the previous sequential type algorithms. Paper [25] explores the possibility of strengthening the search when the portion of the Pareto front considered to be interesting for further exploration can be initially bounded. A dimensionality reduction technique is applied to label-setting algorithms, which reduces the number of dominance checks. Tests on the application of this technique to problems with three to five objectives are performed; significant reductions in time requirements were obtained. The work [27] addresses the BOSPP and introduces a label-setting algorithm with a dynamic update of the Pareto front. Different exploration strategies are proposed. Paper [30] extends the ripple-spreading algorithm proposed in [62] for the single-objective shortest path problem of the MOSPP. The ripple-spreading algorithm is an exact method based on labeling, with an approach similar to the pulse algorithm [63] but which defines search areas for each node in order to limit the computation, instead of guiding it recursively. The new algorithm calculates all the efficient paths. In [29], a label-setting algorithm is introduced for finding a minimal complete set of efficient paths for the MOSPP. The new algorithm is called the Multiobjective Dijkstra Algorithm (MDA). The size of the priority queue used to store the node labels is bounded by the number of nodes in the graph. The new management of the labels allows us to parallelize some of the subroutines. Paper [32] follows up this work, and it equips the MDA with A*-like techniques, with the goal of discarding uninteresting subpaths to be explored at early stages of the algorithm. A key issue is how to store the subpaths. Moreover, the priority queue used in the MDA is combined with a lazy management of paths outside the queue. An exact algorithm for the MOSPP is developed in [31]. The described algorithm seeks to improve upon a label-correcting algorithm by enabling the removal of unnecessary nodes from the graph and by dynamically updating the bounds for the costs of partial paths. The work in [34] describes an original algorithmic combination for a one node-to-many nodes MOSPP seeking to achieve a fast solution search.