Abstract
The multiobjective shortest path problem (MSPP) consists of finding the best nondominated path linking two specified nodes in a network where k > 1 different criteria are considered for the arc costs. Solving the MSPP implies determining all the nondominated paths; there may be many such paths, making the selection process a very hard task to accomplish. A traditional way of dealing with such a difficulty is using a utility function where the parameters are aggregated with different weights. In this work, an alternative utility function based on the norm value associated with each path is considered. Two algorithms for solving the minimum-cost norm path problem are then proposed and some computational results are presented.
INTRODUCTION
The shortest path problem (SPP) is a well-known network optimization problem where one aims to determine the path that minimizes the sum of the arc weights (distance, cost, time, . . .). The SPP was initially proposed in the late 1950s [1, 18] and, since then, has been studied by many researchers (see [9, 10] for extensive bibliographies on the SPP).
Sometimes, a multiobjective formulation is needed, in which several parameters are associated with each arc, allowing the possibility of incorporating various criteria. The objectives can be defined as cost, distance, time, reliability [12] , accessibility [7] , capacity [17] , and others. For a review of the multiobjective shortest path problem (MSPP), the interested reader is referred to [6] .
Therefore, one intends to determine a path that minimizes simultaneously all the criteria under consideration. Usually, there is a conflict among the different criteria and such an ideal solution does not exist. The resolution of the MSPP turns into finding nondominated paths, that is, paths for which there is no other path with better values for all the criteria. The well-known labeling algorithm used for solving the SPP can be easily extended to the MSPP, allowing the determination of the full set of nondominated paths [3, 4, 11, 12, 14, 20] .
The MSPP may become hard to solve due to the ambiguity associated with the characterization of the optimal path. Hansen [12] proved that this problem is intractable because the number of nondominated solutions may increase exponentially with the number of nodes in the network. Taking into account this fact, several methods have been developed to select a "satisfactory" nondominated path for a specific instance. These methods include interactive procedures [5, 8] , utility functions [13, 19] , and approximation methods [21] .
A usual expression for the utility function is a weighted sum of the criteria, but it only allows us to determine supported nondominated solutions for the MSPP, that is, the extreme points of the convex hull of the set of feasible solutions for the MSPP. In this work, we propose a different expression based on the Euclidean norm of the cost for the MSPP (which also allows searching for unsupported nondominated solutions). In fact, the ideal solution would min-imize each one of the criteria, and if that solution exists, it will be the one closest to 0 ‫ޒ‬ k (the zero vector in ‫ޒ‬ k ), which means that it will be the solution with a minimum-cost norm value.
For random instances, it happens, in general, that there is not a significant difference between the solutions produced by the weighted sum and minimum norm procedures. Actually, they coincide very often. Nevertheless, instances may be identified where one may have a relevant difference between the solutions obtained by the two procedures. This is exhibited by the example presented in Figure 1 where (0, 10), (5.1, 5.1), and (10, 0) correspond to the values of the nondominated paths from node s to node t in the network. The weighted sum method will choose the first or the last solution, depending on the weights associated with each criterion. However, the solution with cost (5.1, 5.1) happens to be the one closest to 0 ‫ޒ‬ 2 but it will never be chosen by this method, regardless of the weights.
In this paper, we will address the problem of finding the path with a minimum-cost norm value and present two algorithms for solving it. One of the algorithms is based on the determination of the nondominated paths for the MSPP and the other is based on a ranking shortest path procedure. An example is shown and some computational experience is reported.
THE MSPP AND RELATED PROBLEMS
Let Ᏻ ϭ (ᏺ, Ꮽ, c) denote a network, where ᏺ ϭ {1, . . . , n} is the set of nodes and Ꮽ ʕ ᏺ ϫ ᏺ is the set of arcs; therefore, each arc is identified with a pair (i, j) with i, j ʦ ᏺ. The cost function is of the form c :
where k is the number of parameters (criteria) associated with each arc.
A path p between two nodes i, j ʦ ᏺ is an alternating sequence of nodes and arcs of the form p ϭ ͗i ϭ v 0 , a 1 , v 1 , . . . , a l , v l ϭ j͘, with v r ʦ ᏺ, r ϭ 0, . . . , l, and a r ϭ (v rϪ1 , v r ) ʦ Ꮽ, r ϭ 1, . . . , l. For simplicity, it can also be denoted by p ϭ ͗v 0 , v 1 , . . . , v l ͘ and, by convention, p ϭ ͗v 0 ͘ is assumed when l ϭ 0. The set of paths from i to j, i, j ʦ ᏺ, is denoted by ᏼ i, j . The set of all paths that can be defined in the network is denoted by ᏼ Ᏻ , that is,
Now, let us define the concept of concatenation of two paths, which will be used throughout this paper: It is important to mention that solving network optimization problems becomes an easy task whenever the following principle holds [2, 15] :
Optimality principle: Every optimal path is formed from optimal subpaths.
Note that if the optimality principle holds, then the labeling algorithm [3] guarantees the determination of an optimal solution.
Finally, let us point out that one looks for paths from an initial node s to a terminal node t of Ᏻ ϭ (ᏺ, Ꮽ, c), and to simplify the notation, we will use ᏼ instead of ᏼ s,t to denote the set of all paths from s to t.
The MSPP
This problem is defined on a network Ᏻ ϭ (ᏺ, Ꮽ, c) with a vector objective function
l , for l ʦ {1, . . . , k}. One aims to find the path from s to t that minimizes (simultaneously) all the components of f over the set ᏼ. However, as mentioned above, obtaining such a solution is very unlikely and the most common situation is to seek a set of nondominated or efficient paths formally defined as follows: The set of nondominated paths from i to j is denoted by Ᏸ i, j and only by Ᏸ when they are defined between s and t. These paths are the optimal solutions for the problem "min Յ ‫ޒ‬ k{ f(q) : q ʦ ᏼ}," where a generalized definition of minimum is used, since, in this case, Յ ‫ޒ‬ k is a partial order relation. The MSPP satisfies the optimality principle which can be stated, in this case, in the following way: Every nondominated path is formed from nondominated subpaths. Thus, using a labeling algorithm [3, 11, 12, 14, 20] , the nondominated solutions are easily obtained. Once these solutions have been obtained, we need to choose which ones satisfy the requirements of the specific instance. In this way, a labeling algorithm can be used to do the initial selection of paths from s to t, making easier the task of selecting a final solution.
The determination of all nondominated paths becomes a very hard task to accomplish when the number of such paths is too high (although each nondominated path is easily determined). Assuming that the determination of all the nondominated paths is possible, one still faces the problem of selecting the "best" final solution.
The Path with Minimum-cost Norm Value
Since we intend to minimize each one of the components of the objective function, a natural selection for the "best" solution will be picking the one which is "closer" to 0 ‫ޒ‬ k, that is, the path with a minimum-cost norm value.
The problem of finding such a path is defined on a network Ᏻ ϭ (ᏺ, Ꮽ, c) by considering the objective function f norm :
where f is the objective function of the MSPP. Thus, one seeks the path p* norm ʦ ᏼ such that
The following lemma allows us to reduce the solution space for the (minNorm) problem:
Proof. Since Ᏸ i, j ʕ ᏼ i, j , we only need to prove that the path with a minimum norm in ᏼ i, j is a nondominated path. Thus, let p be a path of
. . , k, where at least one of these inequalities is strict. So, it is obvious that ʈ f(q)ʈ Ͻ ʈ f( p)ʈ, which contradicts our assumption on p. Therefore, p must be a nondominated path.
■
In general, the (minNorm) problem does not satisfy the optimality principle, namely, the path with a minimum-cost norm value from s to t( p* norm ) may not be formed from minimum-cost norm subpaths from s to each node j ʦ p* norm . This is illustrated by the example shown in Figure  2 , where ͗1, 2, 4͘ is the optimal path with a minimum-cost norm value from 1 to 4. However, the subpath ͗1, 2͘ is not optimal from 1 to 2 since
We can say, in this example, that the order between the values of the path ͗1, 2͘ and ͗1, 3, 2͘ was reversed by concatenation with ͗2, 4͘. As we will show next, this can occur only for subpaths for which there is no dominance relationship.
The value ʈ f( p* sum )ʈ is a good approximation to ʈ f( p* norm )ʈ and the path p * sum may be considered as a good initial solution for the (minNorm) problem. In Table 1 , we present some empirical results averaged over 50 instances of each type. They show that, for random instances, p* norm and p* sum do not differ much from each other, in terms of the corresponding values. In fact, the last two columns of the table show that the gap between the values of f norm and f sum for p* norm and p * sum is less than 0.5%.
Nevertheless, theoretically, the value of ʈ f( p* sum )ʈ may be significantly different from ʈ f( p* norm )ʈ. The following theorem provides variation bounds for ʈ f( p* norm )ʈ in terms of f( p* sum ).
The condition given by this theorem depends on the labels a and b. In this work, we suggest keeping, for each node j ʦ ᏺ, the path with the minimum-cost norm among all the paths from s to j already determined. The label of this path will be the label a of the node j, decreasing, in this way, the probability of keeping new labels for this node. The complexity of this algorithm is, in the worst case, the same as that of the labeling algorithm. Theorem 3 allows us to avoid determining some nondominated labels, but it is difficult to estimate how many labels can be discarded. Algorithm 1 details the process described in this subsection.
Lemma 2. Let a and b be two elements of ‫ޒ(‬
Proof. First, let us note that ʈaʈ Ͻ ʈbʈ implies that there is at least one i ʦ {1, . . . , k} such that
there is (at least) one j ʦ {1, . . . , k} such that a j Ͼ b j , and this allows us to define the following vector c of ‫ޒ(‬ 0 ϩ ) k : c l ϭ 0, @l ʦ {1, . . . , k}‫{گ‬ j}, and
Thus,
We conclude that ʈa ϩ cʈ Ͼ ʈb ϩ cʈ. Finally, let us note that we are assuming that the units among the objectives are equivalent. If that is not the case, the cost for the arcs can be normalized as follows:
The Path with Minimum-cost Sum Value
We will be seen later, the algorithms described in Section 3 for solving the (minNorm) problem determine, as a first step, a path p* sum ʦ ᏼ such that
As shown next, such a solution can be easily obtained by solving an SPP in ‫ޒ‬ (this satisfies the optimality principle unless there is a cycle with negative cost).
where ᏼЈ is the set of paths from s to t in ᏳЈ, are equivalent.
Proof. Since the underlying graph of the networks Ᏻ and ᏳЈ is the same, then both networks have the same set of paths, that is,
, we conclude that both problems are equivalent.
Theorem 2.
Let p* norm and p * sum be the optimal solution for, respectively, the (minNorm) and (minSum) problems.
Proof. The inequality ʈ f( p* norm )ʈ Յ ʈ f( p * sum )ʈ is obvious since p * norm is the optimal solution for (minNorm). Now, let us consider the following problem:
By definition, p* norm is an optimal solution for (P1 ␤ ) with ␤ ϭ f sum ( p * norm ) and we can get a lower bound for (P1 ␤ ) by solving the following problem:
Using Lagrange multipliers, the optimal solution for
2 , and this proves the corollary.
■ Therefore, the best theoretical improvement on ʈ f( p* sum )ʈ is 
This value increases with the number of objectives, being approximately 30% in the biobjective case (k ϭ 2).
ALGORITHMS
In this section, we describe the two algorithms proposed in this work. Although both start with the determination of p* sum , they use different strategies for solving the (minNorm) problem. One is based on the labeling algorithm for the MSPP and the other one on a procedure to rank paths from s to t.
Labeling Algorithm
The labeling algorithm for the MSPP determines all the nondominated paths. Thus, taking into account Lemma 1 ( p* norm ʦ Ᏸ), one possible algorithm for the (minNorm) problem consists of the following two main steps:
1. Determine all the nondominated paths from s to t ( Ᏸ).
Choose from
Ᏸ the path p* norm with minimum cost.
This process avoids the direct determination of p * norm , which is harder to obtain because the (minNorm) problem does not satisfy the optimality principle, but it turns out to be inefficient when the number of nondominated paths is large. The complexity of the labeling algorithm depends on the number of nondominated paths, which is difficult to estimate. Henig [13] proposed the expression # Ᏸ ϭ log(#ᏼ) as a rough estimate of that number in the biobjective case. However, Hansen [12] showed that this number may grow exponentially with the number of nodes.
The algorithm proposed in this section is an adaptation of the labeling algorithm where the result stated by Corollary 1 is used to avoid the exhaustive determination of nondominated solutions. Recall that, by Corollary 1, if a and b are two nondominated labels at a specific node with ʈaʈ Ͻ ʈbʈ, then there exists c ʦ ‫ޒ(‬ 0 ϩ ) k such that ʈa ϩ cʈ Ͼ ʈb ϩ cʈ. However, that value for c may lead to a situation where ʈb ϩ cʈ is greater than an upper bound on the optimum value given by the norm of a known path from s to t. In this case, b is no longer considered in the searching procedure. In short, the algorithm has the following scheme:
1. Determine the path p* sum and let ␣ ϭ ʈ f( p * sum )ʈ. 2. Apply the labeling algorithm for the MSPP with an optimality condition which allows us to keep a new efficient label for a specific node, namely, suppose that a is a label of the node j already found and b is a new nondominated label of j created by the labeling algorithm. Then, b must be kept if there is c ʦ ‫ޒ(‬ 0 ϩ ) k such that ʈa ϩ cʈ Ͼ ʈb ϩ cʈ and ʈb ϩ cʈ Ͻ ␣.
The condition referred to in the second step is described in the following theorem: 
Proof. To simplify the proof of this theorem, let us note that the path which minimizes
Moreover, since b is a label of j, then every label b ϩ c of a path from s to t
Let be aЈ ϭ a ϩ ⌸*( j), bЈ ϭ b ϩ ⌸*( j), and xЈ with xЈ i ϭ x i 2 , i ϭ 1, . . . , k; a ϩ c and b ϩ c will be written as aЈ ϩ xЈ and bЈ ϩ xЈ, respectively. In this form, we want to know if
where xЈ depends on x. The optimal solution of problem (1) can be found using Lagrange multipliers. The restriction ʈbЈ ϩ xЈʈ 2 Յ ʈaЈ ϩ xЈʈ 2 needs to be written in the form h٪ ϭ 0, that is, h(x, y) ϭ ʈbЈ ϩ xЈʈ 2 ϩ y 2 Ϫ ʈaЈ ϩ xЈʈ 2 ϭ 0, for y ʦ ‫.ޒ‬ The optimal solution of this problem is obtained from the solutions of the following equations:
From
k does not satisfy Eq. (4). Thus, 0 and then y ϭ 0. From Eq. (2), the conditions on the components of x are
However, is feasible if
h(x, 0) ϭ 0} is obtained at one of these arrangements, so it is enough to verify if one of them satisfies ʈbЈ ϩ xЈʈ Յ ␣.
Ranking Algorithm
Now, we propose another algorithm, based on a ranking path procedure, to determine the minimum-cost norm path. The paths are ranked by a nondecreasing order of f sum ( p), p ʦ ᏼ. In this way, paths of the (minSum) problem are ranked until we can guarantee that the optimal solution of the (minNorm) problem has been found; see Algorithm 2. As shown in [16] , the complexity of this algorithm is ᏻ(m log(n) ϩ Kn), where K is the number of paths ranked (unknown in advance).
From Table 1 , we conclude that the optimal cost norm path values of (minNorm) and of (minSum) are "closer" to each other, in the general case. So, we should need to rank relatively few paths in the (minSum) problem to obtain the desired solution. As suggested by Figure 3 , the cost of p* sum produces a deep restriction in the region where the cost of the path p* norm can be found. Theorem 4 establishes a relation between the optimal paths p* sum and p * norm and gives a stopping condition to finish ranking the paths in the (minSum) problem. 
Proof. First, let us consider the following problem: max͕ f sum ͑q͒ : q ʦ ᏼ and ʈ f͑q͒ʈ ϭ ␤͖.
(P3 ␤ )
By definition, f sum ( p * norm ) is less than or equal to the value of an optimal solution for (P3 ␤ ) with ␤ ϭ ʈ f( p* norm )ʈ. We can get an upper bound for (P3 ␤ ) by solving the following problem:
Using again Lagrange multipliers, the optimal solution is 
EXAMPLE
In this section, the example given in Figure 4 (with k ϭ 3) is used to illustrate the algorithms described in the previous section.
Computing Ᏸ
As mentioned before, the (minNorm) problem can be solved by determining the full set of nondominated paths from s to t and then selecting the one with the least-cost norm. Computing Ᏸ is easily done by using, for example, a label-correcting algorithm [12] , building up a tree with the paths starting at s and leading to the other nodes of the network. Figure 5 shows how this procedure works for the given example, generating a tree where the dotted branches mean that the label of the corresponding path from s to, say, j is dominated by some other label already computed for a path linking s to the same node j. For this example, one finds four nondominated paths, with ͗1, 2, 4, 6͘ being the one with the minimum-cost norm while ͗1, 3, 4, 6͘ is the optimal solution for the (minSum) problem. Let us point out that, for this small example, a total of 14 labels were kept after applying the dominance test.
Algorithm 1
This algorithm corresponds to an enhancement of the labeling algorithm by incorporating the bounding test and the optimality condition stated in Theorem 3. For that, one needs to compute, as a first step, the values ⌸* l (i), i ϭ 1, 2, . . . , 6, l ϭ 1, 2, 3, shown in Table 2 . Also, p* sum is determined and ␣ ϭ ʈ f( p* sum )ʈ is used as an initial upper bound on the optimal value for (minNorm).
The search tree starts from node 1, labeled (0, 0, 0), generating the labels (5, 7, 4) and (5, 12, 0) for nodes 2 and 3, respectively. Following a FIFO rule, one looks now for an expansion of the path ͗1, 2͘ creating a new label (12, 8, 4) for node 3 and labeling, for the first time, node 4 with (11, 7, 8) .
Note that, so far, the bounding test has not been effective for any of the created labels. However, since there are two labels for node 3, the optimality condition of Theorem 3 can be applied taking a ϭ f(͗1, 3͘) ϭ ͌ 334 Ͻ ͌ 459 ϭ ʈ(17, 11, 7)ʈ ϭ ʈb ϩ ⌸*(3)ʈ, one may check if p* norm can be obtained from the path ͗1, 2, 3͘. According to Theorem 3, the array (5, 18.625, 3) is the smallest value for c such that ʈb ϩ cʈ Յ ʈa ϩ cʈ. However, ʈb ϩ cʈ ϭ ʈ(17, 26.625, 7)ʈ ϭ ͌ 1046.89 will then be greater than ␣, which discards the label as a potential element for the construction of p* norm .
The next label to be chosen is f(͗1, 3͘) ϭ (5, 12, 0), which generates the labels (9, 15, 0) for node 4 and (10, 12, 4) for node 5. The former label is canceled by the bounding test and the algorithm proceeds by looking for an expansion of the path ͗1, 2, 4͘. However, to illustrate the calculations of the optimality condition, we can verify that label b ϭ f(͗1, 3, 4͘) ϭ (9, 15, 0) does not satisfy it when compared with label a ϭ f(͗1, 2, 4͘) ϭ (11, 7, 8) . In fact, none of the three vectors obtained from Theorem 3, cЈ ϭ (22, 4, 3), cЉ ϭ (1, 4, 8.25) , and cٞ ϭ (Ϫ6.471, 4, 10.12), satisfy the optimality condition.
The full search tree built by the algorithm for the example is depicted in Figure 6 . One can see that a total of six labels were created and another five labels were computed but ignored after performing the tests.
Algorithm 2
In this case, the algorithm corresponds to using the optimality condition stated by Theorem 4 within the framework of the ranking algorithm presented in [16] . More precisely, the paths are ranked by increasing order of the corresponding f sum value until one gets a path p ʦ ᏼ such that f sum ( p) Ն ͌ k␣, where ␣ is the best value of f norm over the set of the computed paths.
In our example, the path q 1 ϭ p * sum ϭ ͗1, 3, 4, 6͘ is the first one to be produced by the algorithm with f sum (q 1 ) ϭ 32 and ␣ ϭ f norm (q 1 ) ϭ ͌ 470. From q 1 , the algorithm generates the following deviation paths: q 2 ϭ ͗1, 2, 4, 6͘, q 3 ϭ ͗1, 3, 5, 6͘, and q 4 ϭ ͗1, 3, 4, 5, 6͘. Among these, q 3 ( f sum (q 3 ) ϭ 33) is selected as the second shortest path and ␣ is updated to the value f norm (q 3 ) ϭ ͌ 405.
Then, q 5 ϭ ͗1, 3, 5, 2, 4, 6͘ is a new deviation path derived from q 3 and the third shortest path is obtained from the set {q 2 , q 4 , q 5 }, that is, q 2 ( f sum (q 2 ) ϭ 34) with f norm (q 2 ) ϭ ͌ 386, leading to a new updating of ␣. The ranking procedure generates two deviation paths from q 2 : q 6 ϭ ͗1, 2, 3, 4, 6͘ and q 7 ϭ ͗1, 2, 4, 5, 6͘. Now, the path q 6 ϭ ͗1, 2, 3, 4, 6͘ turns out to be the fourth shortest path with f sum (q 6 ) ϭ 39 Ͼ ͌ 3 ͌ 386, meaning that the algorithm stops with p* norm ϭ q 2 .
In this example, four paths were ranked and another three deviation paths were identified, with the ranking condition value being updated twice (see Fig. 7 ).
COMPUTATIONAL RESULTS
The algorithms were computationally tested on a set of instances generated over two types of networks and considering three different distributions for the costs assigned to the arcs. The computational experiments were carried out at CISUC (University of Coimbra), using a 266-MHz Pentium II biprocessor with 256 Mb of RAM.
The two types of networks considered for test instances are the following:
• Random: A Hamiltonian cycle is first randomly generated to guarantee connectivity of the graph. Then, the remain- ing m Ϫ n arcs are randomly generated with multiple arcs being excluded (n ϭ ͉ᏺ͉ and m ϭ ͉Ꮽ͉).
• Grid: The nodes correspond to the points of a square mesh with each one of them being linked to its nearest four neighbors. The initial node, s ϭ 1, is placed at the top-left corner while the terminal node, t ϭ n, is located at the bottom right corner.
Recall from Table 1 that the optimal paths for f sum and f norm are very close to each other for instances with a uniform distribution for the arc costs, regardless the type of network. Hence, to try out instances with a larger gap between those optimal values, two other distributions were considered for the costs. In fact, as can be seen in Table 3 , which shows the average results obtained with 50 instances of each type, the gap between the optimal paths for f sum and f norm significantly increases, for both types of networks, when "circular" or "cubic" distributions are used.
Thus, the following three cost distributions were studied:
• Uniform: The costs are randomly generated from the set {1, 2, . . . , 1000}.
• Cubic: For each arc (i, j), all but one of the components of its cost are zero. The index of the nonzero element is randomly chosen from the set {1, 2, . . . , k} and the corresponding cost is made equal to an integer in the interval [0.8 ϫ 1000/i, 1.2 ϫ 1000/i]. This means that ʈc i,j ʈ Ϸ 1000/i, @(i, j) ʦ Ꮽ, with a maximum deviation of plus or minus 20%. The initial and the terminal nodes are set equal to 1 and n, respectively.
• Circular: The cost components are randomly generated but satisfy the condition ʈc i,j ʈ ϭ 1000/i, @(i, j) ʦ Ꮽ. As in the previous case, s ϭ 1 and t ϭ n.
We note that the number of paths generated by the ranking procedure is also significantly increased when the "circular" and the "cubic" distributions are considered. This is shown in Table 4 , where, in particular, the number of ranked paths for the grid networks with a "cubic" distribution becomes too high for computational purposes. Tables 5-8 report computational results with the algorithms for the different test instances. All tables contain results based on the average CPU time (column sec) and the average memory (column Mb) required by the algorithms for solving 50 instances with the characteristics described in the respective table. Also, the number of created labels (column labels) is presented for the labeling algorithms, while the number of deviation paths determined (column paths) is exhibited for Algorithm 2-which corresponds, in such a way, to the number of labels generated by the labeling algorithms. Table 5 compares the label-correcting algorithm with the algorithms proposed here. It shows a drastic reduction in the number of determined labels when using Algorithm 1. Also, with the exception of grid networks with a "cubic" cost distribution, one can see that the number of paths generated by Algorithm 2 is usually smaller than is the number of labels generated by the labeling algorithms. Also, Table 5 indicates that the networks with a "cubic" cost distribution are the hardest to solve, due mainly to the large number of nondominated paths.
Tables 6 -8 refer to the computational experiments carried out with the new algorithms for different size instances, in terms of the number of nodes (n), the density (d), and the number of criteria (k). Table 6 reports on the results obtained when the number of nodes increases for the two types of networks and the different cost distributions, keeping d ϭ 4 and k ϭ 6. From this table, it is clear that the two algorithms are capable of tackling very large size random networks when the costs for the arcs are generated with a uniform or a circular distribution. In fact, all those instances were solved in less than 1 second of CPU time, with a slight superiority seen for Algorithm 2. The same is observed for square grid networks with uniform costs but with a much smaller number of nodes. Actually, n has to decrease even further when one considers a cubic distribution for both types of networks, to keep the same level of performance for the algorithms. In this case, Algorithm 2 failed for most of the instances and Algorithm 1 clearly becomes a more effective approach.
The two algorithms show the same kind of performance when one increases the density (Table 7) or the number of criteria (Table 8) , keeping a fixed number of nodes for the networks. However, with the exception of grid networks with a uniform cost distribution, Algorithm 2 appears to be more sensitive to changes in n, d, or k.
CONCLUSIONS
In this work, a utility function based on the Euclidean norm was proposed for the MSPP, leading to finding the path with a minimum-cost norm on a network, called the (minNorm) problem. Two algorithms for solving the (min- Norm) problem were presented and computationally tested. One of the algorithms is based on the labeling algorithm for the MSPP with an initial estimate for the optimal value produced by the solution of the (minSum) problem, which consists of determining the path with a minimum total sum of the criteria values. This algorithm integrates an optimality condition that allows removing a very large number of labels generated in the procedure (in general, about 95%). The second algorithm described in this paper produces a ranking of the paths until a stopping condition occurs. The new algorithms were computationally tested for two types of networks (random and grid) and three different distributions for the arc costs (uniform, circular, and cubic). The two algorithms proved to be very efficient for networks with a uniform or a circular distribution for the costs. The new labeling algorithm is able to find, in less than 1 second of CPU time, the optimal solution for most of the "cubic cost" instances. 

{'paper_id': '6544124', 'title': 'The determination of the path with minimum-cost norm value', 's2_url': 'https://api.semanticscholar.org/CorpusID:6544124', 'source': 'S2ORC'}