## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.1 Apo--A Posteriori Aggregation of Preferences Methods
Although there is a dependence on the data structures used in the implementation of the algorithms, it was concluded in [6; 17; 51] that, in general, label correcting methods are faster than label setting methods, the main reason resulting from the fact that label setting involves the extraction of the label with minimal cost from the set of temporary labels. This task can be completed either by maintaining the set of labels sorted, or by simply selecting the minimal element in the set at every extraction, and both are demanding operations that have to be repeated several times. Furthermore, following [6], node selection can be more advantageous than label selection taking into account that it allows setting several paths terminating at node \(j\) whenever an arc \((i,j)\) is being analyzed. Still, the authors in [6] concluded that label-setting and label-correcting methods are the ones with the best performances for most of the instances that these authors evaluated and that the two-phase methods can be competitive with other resolution procedures for the BOSPP. This was concluded after the test of different implementation strategies for each calculation phase, whereas the ranking method using a \"near shortest path\" procedure (a dynamic programming type procedure) performed poorly. In particular, a ranking approach recurring to a \"near shortest path\" procedure (alternately identifying nondominated supported solutions and searching within duality gaps) and the two-phase method, investigating different methods for solving the problems arising in phases 1 and 2, were tested. It also investigates the two-phase method considering ranking in phase 2. The addressed near-shortest path method was adapted from the algorithm in [55], enabling the enumeration of all near-shortest loopless paths assuming the network has non-negative arc costs, meaning those with a cost that does not exceed the minimum with a tolerance \(\epsilon\in\mathbb{R}^{+}\). Next, we summarize more recent or particularly relevant references on labeling methods for MOSPPs. In [8], a generalization of the single objective shortest path algorithm in [56] is presented, considering two objectives. A generalization of [PERSON]'s algorithm is presented in [12], considering more than two objectives. In the proposed method, the lexicographically lowest label is selected in the set of temporary labels, so that it corresponds to an efficient path. A label correcting algorithm with a form of label generation is described in [13], similarly to the single-objective shortest path problem proposed by [57; 58]. The works in [15; 19] extend the so-called heuristic search algorithm A* to the multiobjective case: the algorithm Multi-Objective A* (MOA) and the algorithm New Approach to Multi-Objective A* (NAMOA), respectively. The A* algorithm is a path finding method which combines the traditional labeling with a heuristic function that estimates the remaining cost of the path to the terminal node [59]. MOA also uses a labeling method complemented by a node expansion strategy that is guided by a heuristic for the cost of partial paths. NAMOA is based on MOA, but it dynamically uses the cost of the efficient paths found by the algorithm to update the partial solutions that should still be expanded. Label correcting/setting methods for the MOSPP are investigated in [17]. This work proposes new label-selection and also several node-selection strategies and presents computational experiments. It reports instances of the problem where label selection is the best strategy and others where node selection performs better. Furthermore, it reports that label setting is superior for some instances, whereas label correcting performs better for others. A label-setting algorithm that uses a preference model built a priori for calculating efficiently the exact preferred solutions for the multiobjective shortest path problem is described in [43].