Artur Alves Pessoa

Luigi Di

Puglia Pugliese
email: luigi.dipugliapugliese@unical.it

Francesca Guerriero
email: francesca.guerriero@unical.it§michael.poss@hds.utc.fr

Michael Poss

Robust constrained shortest path problems under budgeted uncertainty

Keywords: Constrained shortest path, Robust optimization, Budgeted uncertainty, Dynamic programming, NP-hard

. We apply classical techniques to show that the problem with capacity constraint can be solved in pseudo-polynomial time. However, we prove that the problem with time windows is N P-hard in the strong sense when Γ is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudo-polynomial when Γ is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty.

Introduction

Let G = (N, A) be a directed graph with two special nodes o and d, κ : A → R + be a cost function and r : A → Z + be a weight function that represents the resource consumption along each arc of G. The resource constrained shortest path problem looks for the shortest path (according to cost κ) from o to d that satisfies the resource constraint(s), which can be, for instance, capacity constraints or time windows. Namely, a capacity constraint considers an upper bound W ∈ Z + on the resource available on a path, and imposes that any feasible path p satisfies

w(p) ≤ W, (1)
where w(p) = a∈p r a . The shortest path problem with capacity constraint is denoted by CSP . Differently from the capacity constraint, time windows must be satisfied at each node pertaining to

The shortest path problem with time windows is denoted by T W SP . One can define similarly problems with multiple capacity constraints and/or time window constraints. To keep simple notations, we disregard these generalizations in the following and consider a unique resource constraint. One can readily extend the algorithms presented in this paper to problems that contain multiple resource constraints. The literature on constrained shortest path problems is very broad. Providing an exhaustive account of the papers published on the topic would be beyond the scope of this work, and we rather redirect the interested reader to the surveys [START_REF] Irnich | Shortest Path Problems with Resource Constraints[END_REF][START_REF] Puglia Pugliese | A survey of resource constrained shortest path problems: Exact solution approaches[END_REF] and the references therein.

Constrained shortest paths problem are N P-hard [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], however, in the weak sense since pseudopolynomial algorithms exist. Indeed, early papers propose dynamic programming algorithms for these problems (e.g. [START_REF] Joksch | The shortest route problem with constraints[END_REF]), based on states defined by the current node, the resource consumption, and the cost consumption. An important dynamic programming algorithm that is often regarded as one of the most efficient (e.g. [START_REF] Jaumard | A two-phase resource constrained shortest path algorithm for acyclic graphs[END_REF]) is the label-setting algorithm from [START_REF] Desrochers | A generalized permanent labelling algorithm for the shortest path problem with time windows[END_REF]. Denoting B = max i∈N (b i -b i +1) and using appropriate data structure, [START_REF] Desrochers | A generalized permanent labelling algorithm for the shortest path problem with time windows[END_REF] show that the worst-case running time of the label-setting algorithm for solving T W SP is O(|A|B). Similarly, the worst-case running time of the algorithm applied to CSP is O(|A|W ). When costs and/or resource consumptions are allowed to take negative values, the optimal solutions may contain cycles. Forbidding such cycles leads to the problem called Elementary Resource Constrained Shortest Path Problem (ERCSP ), N P-hard in the strong sense [START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF]. In this work, we focus on problems with positive costs and resource consumptions and avoid the burden of forbidding cycles. Nevertheless, the algorithms proposes herein could be adapted to solve the robust versions of the ERCSP .

In this paper, we consider uncertain versions of the above problems and consider that r is not known with precision. Instead, we suppose that the weights are uncertain parameters that can take any value in a given uncertainty set U ⊂ Z |A| + , which we assume to be finite. Given a fixed r ∈ U, we redefine the values of w(p) and t j (p) as w(p, r) and t j (p, r), respectively, to mark the dependency on uncertain parameter r. In the uncertain context, we impose that constraints (1) and (2) be satisfied for all r ∈ U, that is w(p, r) ≤ W, r ∈ U,

and t j (p, r) ≤ b ij , j = 1, . . . , l, r ∈ U.

We denote the associated optimization problems by U-CSP and U-T W SP , respectively.

Remark 1. The recent literature on robust optimization [START_REF] Ben-Tal | Robust optimization[END_REF] very often considers convex uncertainty sets, such as polytopes, which may seem different from our assumption that U is finite. Nevertheless, one readily sees that, because w(p, r) and t(p, r) are convex functions of r, it is equivalent to consider U or its convex hull conv(U). Namely, constraints (3) and (4) are satisfied for all r ∈ U if and only if they are satisfied for all r ∈ conv(U).

By enforcing resource constraints for all r ∈ U, our approach falls into the framework of robust optimization, a celebrated approach to handle optimization problems in the presence of uncertainty [START_REF] Ben-Tal | Robust optimization[END_REF][START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]. In [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Bertsimas | The price of robustness[END_REF], Bertsimas and Sim study budgeted uncertainty sets, denoted by U Γ herein, that control with positive number Γ the number of uncertain parameters that can deviate simultaneously from their means to their peak values. The nice properties enjoyed by set U Γ have led to a very large use of budgeted uncertainty for discrete optimization problems under uncertainty. Two important such properties are related to the computational complexity and probabilistic guarantee offered by the robust model.

Complexity

The robust problems very often belong to the same complexity class as their deterministic counterpart. This is true, for instance, for robust combinatorial optimization problems under cost uncertainty. In fact, prior to this paper, no one had came up with a robust combinatorial optimization problem under budgeted uncertainty that does not belong to the complexity class of its deterministic counterpart.

Probabilistic guarantee If the uncertain parameters of an optimization problem are random variables, the constraints of the problem become probabilistic constraints. Under some conditions, any solution to the associated robust optimization problem under uncertainty set U Γ satisfies the probabilistic constraints with a guarantee that depends on Γ (see also [START_REF] Bertsimas | The price of robustness[END_REF]).

Recent works have seek to improve these properties. For instance, [START_REF] Álvarez-Miranda | A note on the bertsimas & sim algorithm for robust combinatorial optimization problems[END_REF] and [START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF] study how to generalize the complexity results of [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] to combinatorial optimization problems with uncertainty in the constraints and integer variables, respectively, while [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF][START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF] discuss how the probabilistic guarantee can be improved by allowing Γ to depend on the decision variables, yielding variable budgeted uncertainty, denoted U γ in what follows.

While the robust shortest path problem has been investigated in several works (see [START_REF] Aissi | Min-max and min-max regret versions of combinatorial optimization problems: A survey[END_REF][START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Catanzaro | Reduction approaches for robust shortest path problems[END_REF], among others), we are not aware of previous works on robust approaches for the constrained shortest path problem. The closely related vehicle routing problem under uncertainty has, on the contrary, been the subject of several studies. The problem with a robust capacity constraint has been first investigated by Sungur et al. in [START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing[END_REF] who study conditions under which robust versions of the capacitated vehicle routing problem (CVRP) can be solved through methods similar to the ones used for the deterministic version of the CVRP. More recently, Gounaris et al. present in [START_REF] Gounaris | The robust capacitated vehicle routing problem under demand uncertainty[END_REF] study more refined robust approaches for the CVRP, including the use of affine decision rules and the extension of rounded capacity inequalities to the robust case. The interest in the robust VRP with time windows is more recent. In [START_REF] Agra | Layered formulation for the robust vehicle routing problem with time windows[END_REF], the authors present an extended formulation that can be dualized using classical tools of robust optimization [START_REF] Bertsimas | The price of robustness[END_REF]. The authors pursue their work in [START_REF] Agra | The robust vehicle routing problem with time windows[END_REF] where they present more subtle formulations, based on implicit formulations and adjustable robust optimization, that are tackled through decomposition algorithms.

Contributions and structure of the paper To our knowledge, this paper is the first to study the computational complexity for problems U-CSP and U-T W SP . In particular, the main contribution of the paper is two-fold:

1. We prove that U Γ -T W SP is N P-hard in strong sense, contrasting with the pseudo-polynomial algorithms that can be devised for U Γ -CSP .

2. We propose a label-setting algorithm for U Γ -T W SP that is exponential in Γ. Numerical results show the effectiveness of the algorithm.

We show in Section 4 that the problems are N P-hard in the strong sense for uncertainty sets of unbounded cardinalities. In view of this difficulty, we turn then to budgeted uncertainty sets, known to enjoy easier robust counterparts than arbitrary uncertainty sets. We recall the definition of budgeted uncertainty and its recent extension to variable uncertainty in Section 2.2, yielding problems U Γ -CSP and U Γ -T W SP (budgeted uncertainty), and U γ -CSP and U γ -T W SP (variable budgeted uncertainty).

Section 3 is devoted to U Γ -CSP and U γ -CSP . In particular, we define an algorithm based on the solution of |A| + 1 deterministic CSP by employing similar techniques to those developed in [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF][START_REF] Álvarez-Miranda | A note on the bertsimas & sim algorithm for robust combinatorial optimization problems[END_REF][START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF]. We show then in Section 4 that U Γ -T W SP is N P-hard in the strong sense even when G is a directed and acyclic graph, the mean weight vector r = 0, and b = 0, which highlights a fundamental difference between U Γ -CSP and U Γ -T W SP . Our proof is based on a reduction from the independent set problem. This result exhibits for the first time a combinatorial optimization problem that admits a pseudo-polynomial algorithm whose robust version (with budgeted uncertainty) is N Phard in the strong sense.

We present in Section 5 a label-setting algorithm based on that proposed in [START_REF] Desrochers | A generalized permanent labelling algorithm for the shortest path problem with time windows[END_REF]. We pay a particular attention to the generalization of dominance rules. On one hand, the resulting algorithm is pseudo-polynomial when Γ is fixed. On the other hand, it has an exponential worst-case running-time when Γ is part of the input data. The proposed label-setting algorithms are evaluated by considering instances inspired by the scientific literature. We report in Section 6 a detailed accounting of the numerical results. The goals of our numerical experiments for the U Γ -T W SP are two-fold. First, they assess the effectiveness of the label-setting algorithm based on the defined robust labels for U Γ -T W SP and U γ -T W SP . Second, they show that a reduction in the price of robustness can be obtained when using variable budgeted uncertainty instead of the classical budgeted uncertainty. The paper ends with Section 7, where we give conclusions and final remarks.

2 Uncertainty set 2.1 N P-hardness for general uncertainty sets When U is reduced to a singleton, U-CSP and U-T W SP reduce to the deterministic counterparts. Otherwise, the problems can be seen as deterministic problems that contain multiples capacity or time windows constraints, one for each value of r in U. When the cardinality of U is bounded by a small constant, U-CSP and U-T W SP could therefore be solved in pseudo-polynomial time using, for instance, the classical label-setting algorithm. However, the running-time of such algorithms is exponential in the cardinality of U, making them impractical for solving problems with uncertainty sets of large cardinalities. One can wonder whether different efficient approaches could exist to solve these problems under arbitrary uncertainty sets. The next result answers by the negative, showing that U-CSP and U-T W SP are N P-hard in the strong sense when the cardinality of U is unbounded. The proof consists in reducing the robust knapsack problem (U-KP ) to U-CSP . A similar proof can be devised to reduce U-KP to U-T W SP . ROBUST KNAPSACK PROBLEM (U-KP )

Input: Set {1, . . . , m} of items, set V ⊂ Z m + of weights w, profit vector c ∈ R m + , capacity D.
Task: Find a subset of items I ⊆ {1, . . . , m} of maximum profit such that Proof. Problem U-KP is N P-hard in the strong sense, see Theorem 4.5 from [START_REF] Talla Nobibon | Complexity results and exact algorithms for robust knapsack problems[END_REF]. Given an instance to U-KP , the corresponding instance of U-CSP is built as follows. First, we compute c * = max 1≤i≤m c i . Then, we consider the directed graph with m + 1 nodes and 2m arcs described in Figure 1. For each pair of nodes {i -1, i}, let -----→ (i -1, i) and (i -1, i) -----→ denote the top and bottom arc, respectively. The instance of the U-CSP looks for a path from 0 to m in the graph from Figure 1 with W = D, κ--→ i-1i = c * and r--→ i-1i = 0 for each i ∈ {1, . . . , m}, κ i-1i

i∈I w i ≤ D for all w ∈ V. 0 m 1 (c * , 0) (c * , 0) (c * -c 1 , w 1 ) (c * -c m , w m ) (c * -c 2 , w 2 ) (c * , 0)
--→ = c * -c i and r i-1i

--→ = w i for each i ∈ {1, . . . , m}. Accordingly, supposing that bottom arcs have smaller indexes than top arcs, U = V × (0, . . . , 0). Then, for any positive integer K, we see that the optimal solution cost to U-KP is equal to K if and only if the optimal solution cost to U-CSP is equal to mc * -K.

The above result suggests that problems U-CSP and U-T W SP can be quite hard to solve exactly for arbitrary uncertainty sets. This is not very surprising as it is well known that many robust versions of combinatorial optimization problems become N P-hard in the presence of uncertainty [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]. In the following, we thus focus on special uncertainty sets, U Γ and U γ , known to often lead to robust optimization problems with computational complexities similar to the complexities of their deterministic counterparts. These sets are defined formally in the next subsection.

Budgeted uncertainty and probabilistic guarantee

To avoid the difficulty often present in robust combinatorial optimization (such as Theorem 1), Bertsimas and Sim introduced in [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] a particular type of uncertainty sets, called budgeted uncertainty, whose conservatism can be adjusted through a budget parameter Γ ∈ R + .

Budgeted uncertainty set U Γ considers nominal value r a and peak value r a + ra for each a ∈ A. Whenever Γ is integer, each vector r ∈ U Γ has up to Γ of its components equal to their peak values while the other components are equal to their nominal values. If Γ is fractional, a vector in U Γ is formed of up to Γ peak values plus a component a equal to r a + (Γ -Γ )r a , the rest of the components being at their nominal values. The set is defined formally as follows:

U Γ ≡    r ∈ R |A| ∃S, Ŝ ⊆ A, a ∈ A\(S ∪ Ŝ), | Ŝ| ≤ Γ, S ∩ Ŝ = ∅, S ∪ Ŝ ∪ {a } = A : ra =   ra a ∈ S ra + ra a ∈ Ŝ ra + (Γ -Γ )ra a = a      . ( 5
)
Notice that although we define U Γ as a finite set, it is often described as a polytope in the literature (see Remark 1). In what follows, we study the complexity of U-CSP and U-T W SP under budgeted uncertainty, yielding problems U Γ -CSP and U Γ -T W SP . We include in our study the consideration of variable budgeted uncertainty that improves over the probabilistic guarantee offered by U Γ .

Let ra = r a + η a ra be the random variable associated with parameter r a and suppose that η a , a ∈ A, are arbitrary random variables independently and symmetrically distributed in [-1, 1]. Bertsimas and Sim [START_REF] Bertsimas | The price of robustness[END_REF] construct different functions δ : R 2 → R such that any vector x that satisfies the robust constraint a∈A r a x a ≤ h, for all r ∈ U Γ , also satisfies

P a∈A ra x a > h ≤ δ(Γ, |A|). (6)
Hence, given a probability level ∈ (0, 1), choosing Γ such that δ(Γ, |A|) ≤ ensures that probabilistic constraint P a∈A r a x a > h ≤ be satisfied. This is a very strong result since robust constraints are significantly easier to handle than individual probabilistic constraints. We refer to Appendix A for an example of function δ. Remark 2. Bound (6) is not directly applicable to time windows inequalities (2) because the latter are non-linear. Nevertheless, we can linearize these inequalities by replacing each occurrence of max(X, Y ) hidden in notation t j (p) by one inequality with X and one inequality with Y . Doing so recursively yields a set of linear inequalities equivalent to non-linear inequalities (2). The same transformation can be applied to the probabilistic constraints that involve random vector r, which yields a set of linear probabilistic constraints, each of which approximated by a robust constraint through bound (6).

Recently, [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] has noticed that the bound provided by ( 6) can be improved when x is binary by considering a more general model of uncertainty. We sketch below how this can be done and redirect the interested reader to [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] for details. The author of [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] shows that (6) can be changed to

P a∈A ra x a > h ≤ δ(Γ, |x|), (7)
where |x| = a∈A x a is the cardinality of x. Inequality [START_REF] Bertsimas | The price of robustness[END_REF] tells us that the value of Γ can be changed according to the cardinality of x while ensuring the same level of probability protection. This observation led [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] to introduce a new model of uncertainty, called variable budgeted uncertainty, where the fixed value of Γ is replaced by the non-decreasing function γ : {0, 1, . . . , |A|} → R + . Coming back to our shortest path problem, variable budgeted uncertainty adjusts the level of conservatism according to the cardinality of the path considered. For a path p ⊆ A from o to d, the point-to-set mapping

U γ : Z ⇒ R |A| is defined as U γ (|p|) ≡    r ∈ R |A| ∃S, Ŝ ⊆ A, a ∈ A\(S ∪ Ŝ), | Ŝ| ≤ γ(|p|), S ∩ Ŝ = ∅, S ∪ Ŝ ∪ {a } = A : ra =   ra a ∈ S ra + ra a ∈ Ŝ ra + (γ(|p|) -γ(|p|) )ra a = a      . ( 8
)
When γ(k) = Γ for each k ∈ {0, 1, . . . , |A|}, U γ (x) reduces to U Γ . However, it has been shown in [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF][START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF] that U γ is in general less conservative than U Γ . A measure of conservatism of a robust model is its price of robustness, that is, the increase in solution cost when imposing a probabilistic protection with a specified guarantee > 0. The reduction in the price of robustness offered by model U γ is particularly significant when the cardinality of the optimal solution is small in comparison to the total number of variables of the problem. This is the case for the shortest path problem since an optimal solution typically contains O(N ) variables while the number of arcs can be as large as O(N 2 ). Remark 3. In view of the above discussion, one way to choose Γ is to follow probabilistic bound δ(Γ, |A|) used in constraint [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF]. Unfortunately, this is likely to yield values of Γ that are greater than the cardinality of the optimal solution. We have argued that function γ avoids this problem. However, the resulting optimization problem may be more complex than the one using a constant Γ. An alternative is to refine the choice of Γ by computing an upper bound U B on the cardinality of the longest path from o to d that satisfies the resource constraint. Then, Γ would be defined in accordance with δ(Γ, U B). Notice that computing an exact upper bound may be as difficult as solving the robust constrained shortest path, so that we should restrict ourselves to bounds U B on the longest path that can be computed easily.

3 Complexity of U Γ -CSP and U γ -CSP We consider in this section U γ -CSP and show how it can be solved in pseudo-polynomial time. The results presented in what follows are obtained by applying tools similar to those described in [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF]Section 3]. However, their importance should not be undervalued since they show that U γ -CSP is pseudo-polynomial, and therefore, belongs to the same complexity class as its deterministic counterpart. In contrast, we show in the next section that U Γ -T W SP is N P-hard in the strong sense.

One of the major result of [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] shows that combinatorial optimization problems with cost uncertainty and uncertainty polytope U Γ can be addressed by solving n + 1 deterministic problems (where n is the number of binary variables). The authors of [START_REF] Álvarez-Miranda | A note on the bertsimas & sim algorithm for robust combinatorial optimization problems[END_REF][START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF] have recently shown how the aforementioned result can be extended to a robust constraint under uncertainty polytope U Γ . Combining ideas from [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF] and [START_REF] Álvarez-Miranda | A note on the bertsimas & sim algorithm for robust combinatorial optimization problems[END_REF][START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF], we see easily that combinatorial problems with one robust constraint under uncertainty point-to-set mapping U γ (assuming γ affine) can be solved by solving n + 1 deterministic problems.

Theorem 2. Let Y ⊆ {0, 1} |I| be the feasibility set of a combinatorial optimization problem and γ be the affine function defined by reals γ 0 and γ 1 through γ(y) = γ 0 + γ 1 i∈I y i . Moreover, let κ ∈ R |I| be a cost vector, b ∈ R, and r be an uncertain vector taking values in U γ (y). Without loss of generality, suppose that indices are ordered such that r1 ≥ r2 ≥ . . . ≥ r|I| and let r|I|+1 be 0. Then, the optimal solution to

min i∈I κ i y i : i∈I r i y i ≤ b ∀r ∈ U γ (y), y ∈ Y
is equal to the optimal solution of min l∈{1,...,|I|+1} Z l where

Z l =    min i∈I κ i y i : i∈I (r i + γ 1 rl )y i + l j=1 (r j -rl )y j + ≤ b -γ 0 rl , y ∈ Y    , for l = 1, . . . , |I| + 1.

Proof. The proof follows closely the line of the proof of [4, Lemma 2], replacing Γ by γ(y).

There are two differences between Theorem 2 and [4, Lemma 2]. First, and most importantly, the fact that γ is an affine function rather than a constant leads the presence of terms γ 1 rl y i in the constraints of Z l . Second, we cannot reduce the number of problems to be solved as done in [START_REF] Álvarez-Miranda | A note on the bertsimas & sim algorithm for robust combinatorial optimization problems[END_REF], because γ is in general not integer-valued.

We formulate next U γ -CSP as an integer linear program with one linear robust constraint. Let x ∈ {0, 1} |A| be a vector of optimization variables stating which arcs belong to the solution, and let X ⊂ {0, 1} |A| contain all vectors x that correspond to paths from o to d. With these variables, U γ -CSP can be cast as

min a∈A κ a x a s.t. a∈A r a x a ≤ W, r ∈ U γ (x) (9)
x ∈ X .

Applying Theorem 2 to problem (9) yields the results below.

Corollary 1. If γ is affine, U γ -CSP can be handled by solving |A| + 1 problems CSP with modified weights.

The above result implies that U γ -CSP can be solved in pseudo-polynomial time. It is interesting to notice that Corollary 1 can be applied both to U Γ -CSP and U γ -CSP and that the resulting computational complexity is the same. This is a surprisingly positive result given that model U γ relies upon more complex mathematical tools and often leads to difficulties absent with the use of U Γ (see [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] for details). When the appropriated data structures are used, CSP can be solved by the label-setting algorithm in O(|A|W ) if there are no zero weights [START_REF] Desrochers | A generalized permanent labelling algorithm for the shortest path problem with time windows[END_REF], yielding the following corollary.

Corollary 2. If γ is affine, U γ -CSP can be solved in O(|A| 2 W ).
Notice that whenever γ is not affine, we can still solve U γ -CSP in pseudo-polynomial time, albeit at a higher computational cost. Let CSP ≤ k and U Γ -CSP ≤ k be defined as CSP and U Γ -CSP , respectively, with the additional restriction that feasible paths cannot contain more than k arcs, for 0 ≤ k ≤ |N |, and Γ = γ(k). Clearly, the label-setting algorithm applied to CSP ≤ k with the appropriate data structure has a running-time of O(|A|W |N |). Moreover, Theorem 2 can be applied to U Γ -CSP ≤ k so that the problem can be solved in

O(|A| 2 W |N |). Theorem 3. U γ -CSP can be solved in O(|A| 2 W |N | 2 )
for any non-decreasing function γ.

Proof. Let opt(P ) be the optimal solution cost of optimization problem P . The proof results from equality opt

(U γ -CSP ) = min k=1,...,|N | opt(U Γ -CSP ≤ k ), (10)
which has been proved in [22, (19)] for combinatorial optimization problems under cost uncertainty.

Unfortunately, the approach used in this section cannot be used to provide pseudo-polynomial algorithms for U γ -T W SP . The reason is that time windows restrictions are expressed through |N | non-linear constraints, instead of a single linear constraint as it is the case for U γ -CSP . The issue has been discussed in [START_REF] Agra | Layered formulation for the robust vehicle routing problem with time windows[END_REF] where the authors propose an extended linear programming formulation for U Γ -T W SP using additional binary variables and a number of robust constraints that is quadratic in |N |. Since the formulation from [START_REF] Agra | Layered formulation for the robust vehicle routing problem with time windows[END_REF] contains many robust constraints, applying Theorem 2 to that formulation would enable us to solve U Γ -T W SP by solving more than O |A| |N | 2 problems T W SP , instead of the O(|A|) involved in Corollary 1. This approach would hardly be of any practical use.

Complexity of U Γ -T W SP and U γ -T W SP

We show in this section that the decision version of a simplification of U Γ -T W SP is N P-complete in the strong sense. Namely, we consider the robust path with deadlines, obtained from the decision version of U Γ -T W SP by looking for a path with zero nominal travel time that satisfies the upper time windows (hence we suppose r = 0 and b = 0); we also suppose that the graph is acyclic.

ROBUST PATH WITH DEADLINES (U Γ -P D)

Input: A directed and acyclic graph D = (N, A) with corresponding ra for each a ∈ A and b i for each i ∈ N , and a positive integer Γ.

Question: There exists a path p = (i 0 , i 1 , . . . , i l ) in D starting at o ∈ N (i 0 = o) and ending at

d ∈ N (i l = d) such that max a∈S ra S ⊆ (i 0 , i 1 , . . . , i h ), |S| ≤ Γ ≤ b i h , for each h = 1, . . . , l?
Our proof is based on reducing the decision version of the independent set problem to U Γ -P D. It is well-known that the former problem is N P-complete in the strong sense (e.g. [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]).

INDEPENDENT SET (IS)

Input: An undirected graph G = (V, E) and a positive integer K.

Question: There exists W ⊆ V such that |W | ≥ K and {i, j} W for each {i, j} ∈ E ?

0 n p 1 p 2n-1 p 2 p 2n 1 n + 1 n + 2 n + m p 2n+1 p 2n+2 p 2n+m p 3 p 4 2
Figure 2: Reduction from the independent set problem to U Γ -P D.

Theorem 4. U Γ -P D is N P-complete in the strong sense.

Proof. First, we show that U Γ -P D belongs to N P. For that, the feasibility of a path p = (i 0 , i 1 , . . . , i l ) must be checked in polynomial time. This is true because, for each h = 1, . . . , l, the time window constraint on i h needs to be checked only for a single S containing min(h, Γ) arcs, with largest values of ra . Next, we show that IS can be reduced to U Γ -P D.

Given an instance to IS with |V | = n nodes and |E| = m edges, we show next how to build an instance for U Γ -P D. Graph D is described on Figure 2 where p i represents a directed path that contains m + 1 arcs for each i ∈ {1, . . . , 2n} and n arcs for each i ∈ {2n + 1, . . . , 2n + m}. Moreover, o = 0, d = n + m and Γ = n(m + 1). In what follows we denote the k-th arc of p i by a(i, k) and the elements of E by {e 1 , . . . , e m }.

One sees immediately that any path p from o to d must contain all paths p 2n+i for i ∈ {1, . . . , m}. Furthermore, for each i ∈ {1, . . . , n}, path p contains either p 2i or p 2i-1 . Hence, there are 2 n different paths in D from o to d, which is as many as the number of different subsets of V . The correspondence between subsets of V and paths in D works as follows. Let W ⊆ V be a subset of V and let p W be the path in D associated to W . Then, for each i ∈ {1, . . . , n}, path p W contains p 2i if i ∈ W and path p W contains p 2i-1 otherwise. We can describe concisely p W by introducing function W defined as follows:

W (i) = 2i if i ∈ W and W (i) = 2i -1 otherwise, for each i ∈ {1, . . . , n}. Hence, p W = p W (1) ∪ p W (2) ∪ . . . ∪ p W (n) ∪ p 2n+1 ∪ . . . ∪ p 2n+m .
We explain next how to choose parameters r and b such that the deadline constraints imposed to p W are equivalent to the constraints of IS imposed to W . Namely, we choose these parameters such that constraint max

a∈S ra S ⊆ p W (1) ∪ p W (2) ∪ . . . ∪ p W (n) , |S| = n(m + 1) ≤ b n (11)
written for p W is equivalent to |W | ≥ K and constraints

max a∈S ra S ⊆ p W (1) ∪ . . . ∪ p W (n) ∪ p 2n+1 ∪ . . . ∪ p 2n+h , |S| = n(m + 1) ≤ b n+h (12)
written for p W are equivalent to e h = {i, j} W , for each h = 1, . . . , m. Notice that in ( 11) and ( 12), |S| = n(m + 1) has been used instead of |S| ≤ n(m + 1) because all components of r are positive and the paths considered in [START_REF] Puglia Pugliese | A survey of resource constrained shortest path problems: Exact solution approaches[END_REF] and [START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF] contain not less than n(m + 1) arcs. Our construction below is made in two steps. First, we impose restrictions on r and b which ensure that the corresponding deadline constraints translate exactly into the constraints of IS. To this end we introduce additional parameters µ, ν, and σ h for each h ∈ {1, . . . , m} to be specified later. Second, we provide in Appendix B an example of vector (µ, ν, σ, r, b) that satisfies the restrictions and that is composed of polynomial functions of n, m, and K.

Constraint [START_REF] Puglia Pugliese | A survey of resource constrained shortest path problems: Exact solution approaches[END_REF] The number of arcs of subpath p W (1) ∪ p W (2) ∪ . . . ∪ p W (n) is equal to n(m + 1), so that the unique choice of S in the maximization is the full subpath p W (1) ∪ p W (2) ∪ . . . ∪ p W (n) . Hence, [START_REF] Puglia Pugliese | A survey of resource constrained shortest path problems: Exact solution approaches[END_REF] becomes

n i=1 m+1 k=1 ra( W (i),k) ≤ b n . ( 13
)
Let r and b n be such that

m+1 k=1 ra(2i,k) = µ, i ∈ {1, . . . , n}, m+1 k=1 ra(2i-1,k) = µ + 1, i ∈ {1, . . . , n}, b n = nµ + n -K. (14)
Plugging ( 14) into (13), we obtain that p W cannot contain more than n -K paths of the form p 2i-1 for i ∈ {1, . . . , n}, which is equivalent to

|V \ W | ≤ n -K, or more simply, |W | ≥ K.
h-th constraint of [START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF] We propose next restrictions on r and b such that the maximization in the lhs of the h-th constraint in [START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF] becomes

n i=1 m+1 k=h+1 ra( W (i),k) + 2n+h i=2n+1 n k=1 ra(i,k) . ( 15
)
One readily checks that the following set of constraints yields the desired [START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF] ra(i,k) < ra(j,k+1) , i, j ∈ {1, . . . , 2n}, k ∈ {1, . . . , m}, ν > ra(i,m) , i ∈ {1, . . . , 2n}, ν = ra(i,k) , i ∈ {2n + 1, . . . , 2n + m}, k ∈ {1, . . . , n}.

Once the lhs of the h-th constraint of ( 12) has been turned to [START_REF] Goetzmann | Optimization over integers with robustness in cost and few constraints[END_REF], we impose the following additional restrictions to obtain the desired deadline constraint

m+1 k=h+1 r(2i,k) = σ h + 1, if e h is adjacent to vertex i, σ h , otherwise. , i ∈ {1, . . . , n}, m+1 k=h+1 r(2i-1,k) = σ h , i ∈ {1, . . . , n}, b n+k = 1 + nσ h + hnν. (17)
Plugging restrictions ( 16) and ( 17) into the h-th constraint of ( 12), we obtain that p W cannot contain more than a single subpath p 2i such that i is adjacent to edge e h . Hence, the number of vertices in W adjacent to e h must not be greater than 1, which is equivalent to {i, j} W for e h = {i, j}.

Since U Γ -P D is a special case of the decision problem associated to U Γ -T W SP , we obtain immediately the following result, which contrasts with the pseudo-polynomial algorithms proposed for U Γ -CSP in the previous section.

Corollary 3. U Γ -T W SP and U γ -T W SP are N P-hard in the strong sense.

Label-setting algorithm

We show in this section how to extend the classical labels used in dynamic programming and labelsetting algorithms (e.g. [START_REF] Desrochers | A generalized permanent labelling algorithm for the shortest path problem with time windows[END_REF]) to the case of uncertain weights. We focus on the definition of robust labels and discuss dominance rules in case of budgeted uncertainty. Our description is presented for time windows; one can readily modify the algorithms presented below to a capacity constraint instead of time windows. Notice, however, that the computational complexity of the algorithm presented below is exponential in Γ, which is in accordance with the N P-hardness of U Γ -T W SP .

In Section 5.1, we sketch the label-setting algorithm, recall how labels are defined in the deterministic setting and how dominance applies. We refer the interested reader to [START_REF] Boland | Accelerated label setting algorithms for the elementary resource constrained shortest path problem[END_REF], among others, for a detailed description of the algorithm. In Section 5.2, we consider set U Γ and suppose that Γ is integer. If it is not the case, we can always round up Γ to obtain a slightly more conservative model. In the (unlikely) situation where the fractional part of Γ really matters, one can always extend the algorithm described next in a way similar to the dynamic programming algorithms described in [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF]. In Section 5.3, we consider U γ . In the following, we denote the cost of any path p shortly by κ(p) = a∈p κ a .

Deterministic labels

We outline next the basic principles of the label-setting algorithm for T W SP . For each path p from node o to node i, the classical label-setting algorithm considers label (κ(p), t |p| (p)) that records the cost of the path and its arrival time at node i. To avoid constructing all labels, the algorithm selects and extends labels in a special order. Two sets of labels are considered: permanent labels and non-permanent labels. At each iteration, the algorithm selects the smallest non-permanent label according to the lexicographical order and mark the label as permanent. Then, for each direct descendant of the node associated to the current label, we create a new non-permanent label and check whether it satisfies the time-windows and is not dominated by a permanent label. If one of the condition fails to hold, the label is immediately removed from the set of non-permanent labels. The algorithm ends when the next selected label corresponds to d.

A crucial phase in the label-setting algorithm is the removal of dominated labels, which reduces significantly the total number of labels searched in the course of the algorithm. Given two labels y and y associated to paths p and p ending at the same node, we say that label y is dominated by label y if the following condition holds: if path p belongs to an optimal solution of T W SP , then path p belongs to an optimal solution of T W SP . Dominated labels can be discarded from the search that occurs during the label-setting algorithm. The next result is well-known and is presented without proof.

Lemma 1. Consider the T W SP and let y = (κ, t) and y = (κ , t ) be two labels associated to paths p and p ending at the same node. Assume the following conditions are verified:

1. κ ≤ κ 2. t ≤ t
3. and at least one inequality is strict.

Then, label y is dominated by label y.

Robust labels

Next, we consider robust time windows constraints (4) recalled below for uncertainty set

U Γ t j (p, r) ≤ b ij , j = 1, . . . , l, r ∈ U Γ , ( 18
)
where p = (i 0 , i

and extend the label through arc (i, j) with the classical formula

κ(p) + κ ij , max(b i , t |p| (p, r 1 ) + r 1 ij ), . . . , max(b i , t |p| (p, r s ) + r s ij ) . (20)
Using labels [START_REF] Joksch | The shortest route problem with constraints[END_REF] and appropriate data structures, one can solve U Γ -T W SP by the label-setting algorithm in solution time O(s|A|B s ), where s = Γ k=1 |A| k . We show below how to reduce the solution time to O(Γ|A|B Γ+1 ) by using a more compact description of the labels. Notice that this is a significant improvement since Γ is always much smaller than s. To be more precise, this improvement leads to pseudo-polynomial algorithms when Γ is fixed, which happens in applications where we are interested to be protected only against a small number of deviations, regardless to the size of the instances. However, if we choose Γ according to probabilistic guarantees, then Γ ∈ O(|A| 1/2 ) (see [START_REF] Bertsimas | The price of robustness[END_REF][START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF]). In the latter case, the resulting computing time of the label-setting algorithm would be O(|A| 3/2 B O(|A| 1/2 ) ) which is not polynomial, although asymptotically smaller than O(s|A|B s ).

Remark 4. The author of [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF] has shown how generic dynamic programming algorithms for combinatorial optimization problems can be extended to the robust versions of the problems when only costs are uncertain and the uncertainty set is U Γ . His work shows that the number of states of the robust dynamic programming algorithms needs only to be multiplied by Γ, and therefore, polynomial algorithms stay polynomial in the robust case. This is in sharp contrast with the robust label-setting algorithm presented herein, which multiplies the number of labels by B Γ+1 . Unfortunately, the approach of [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF] cannot be applied to the problems studied in this paper because herein the uncertainty lies in the constraints while only costs are uncertain in [START_REF] Poss | Robust combinatorial optimization with variable cost uncertainty[END_REF].

Before explaining how the running-time can be decreased to O(Γ|A|B Γ+1 ), we present without proof the well-known extension of Lemma 1 to multiple-resource label [START_REF] Joksch | The shortest route problem with constraints[END_REF].

Lemma 2. Consider the U Γ -T W SP and let y = (κ, t 1 , . . . , t s ) and y = (κ , t 1 , . . . , t s ) be two labels associated to paths p and p ending at the same node. Assume the following conditions are verified:

1. κ ≤ κ 2. t j ≤ t j , for each j = 1, . . . , s

and at least one inequality is strict.

Then, label y is dominated by label y.

The key idea to reduce the running-time of the robust label-setting algorithm is based on rewriting time windows [START_REF] Jaumard | A two-phase resource constrained shortest path algorithm for acyclic graphs[END_REF] as max

r∈U Γ t j (p, r) ≤ b ij , j = 1, . . . , l. ( 21
)
Our objective is to define robust labels that contain only the necessary information to test whether the current path is feasible when considering its maximum travel time over U Γ . Rather than considering all possible travel times r ∈ U Γ that could be used along path p = (i 0 , . . . , i l ) from o = i 0 to i = i l , we can define the label attached to node i and path p as

κ(p), τ 0 l (p), . . . , τ Γ l (p) , (22)
where, for each j = 1, . . . , l, τ g j (p) is defined as the maximum arrival at node i j when considering up to g ∈ {0, . . . , Γ} deviations when g ≤ |p| and is equal 0 otherwise, that is,

τ g j (p) = max r∈U g t j (p, r), for each g ∈ {0, . . . , min(|p|, Γ)}, 0, for each g ∈ {|p| + 1, . . . , Γ}. ( 23
)
Then, we extend the label through arc (i, k), generating a new label for node k = i l+1 , with formula

       κ = κ(p) + κ ij , τ 0 l+1 = max b j , τ 0 l (p) + r ij ), τ g l+1 = max b j , τ g-1 l (p) + r ij + rij , τ g l (p) + r ij ), for each g ∈ {1, . . . , ḡ}, τ ḡ+1 l+1 = max b j , τ ḡ-1 l (p) + r ij + rij ), (24)
where ḡ = min |p|, Γ -1) and the extended label is feasible if τ ḡ+1 is less than or equal to b j . It is easy to see by induction that extending label (0, 0 . . . , 0), that corresponds to the empty path, iteratively through formula ( 24) leads exactly to definition [START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing[END_REF]. One readily sees that the solution time of the label-setting algorithm based on label ( 22) is reduced to O(Γ|A|B Γ+1 ) since these labels contain Γ + 1 resources and their extension through new arcs can be done in O(Γ) with the help of formula [START_REF] Talla Nobibon | Complexity results and exact algorithms for robust knapsack problems[END_REF]. Finally, the next result states the new robust dominance rule.

Lemma 3. Consider the U Γ -T W SP and let z = (κ, τ 0 , . . . , τ Γ ) and z = (κ , τ 0 , . . . , τ Γ ) be two labels associated to paths p and p ending at the same node. Assume the following conditions are verified:

1. κ ≤ κ 2. τ j ≤ τ j , for each j = 0, . . . , Γ

3. and at least one inequality is strict.

Then, label z is dominated by label z.

Proof. We prove the result by contradiction. Namely, suppose that p belongs to an optimal solution to U Γ -T W SP , denoted p , while p does not belong to an optimal solution to U Γ -T W SP . Consider then path p * = p ∪ (p \p ). One readily sees that path p * is optimal, yielding a contradiction.

Variable budgeted uncertainty

Let us now address the case of variable budgeted uncertainty U γ -T W SP . Again, we suppose that γ is an integer-valued function, and if this is not case, we consider instead the rounded function γ . Notice that while the rounded function γ is non-decreasing (because γ is non-decreasing), γ is usually not affine. This is fortunately not a requirement for the algorithm described in this section.

The difference between U Γ -T W SP and U γ -T W SP is that the budget of uncertainty against which the solution must be protected depends on the cardinality of the solution. Hence, we define variable robust labels as robust labels to which we append the cardinality of the current path k = |p|, that is, (κ, τ 0 , . . . , τ Γ , k), where τ g is defined as before (Eq. ( 23)) for each g ∈ {0, . . . , Γ}. Then, we extend labels through arc (i, j) similarly to formula [START_REF] Talla Nobibon | Complexity results and exact algorithms for robust knapsack problems[END_REF], and increasing k by one unit.

With variable budgeted uncertainty, smaller paths suffer less deviations than longer ones. Namely, to check the feasibility of label (κ, τ 0 , . . . , τ Γ , k), we only need to check that time windows are satisfied by τ g for g = γ(k) . In opposition, the check for robust labels must be done for g = Γ for classical robust labels. This implies that smaller paths must be preferred over longer ones, as formalized in the lemma below. Lemma 4. Consider the U γ -T W SP and let w = (κ, τ 0 , . . . , τ Γ , k) and w = (κ , τ 0 , . . . , τ Γ , k ) be two labels associated to paths p and p ending at the same node. Assume the following conditions are verified:

1. κ ≤ κ 2. τ j ≤ τ j , for each j = 0, . . . , Γ 3. k ≤ k 4. and at least one inequality is strict.

Then, label w is dominated by label w.

Proof. The proof follows directly from the fact that γ is non-decreasing.

One readily sees that the classical label-setting algorithm can be applied to variable robust labels. With appropriated data structures, the complexity of the resulting algorithm is O(Γ|A||N |B γ(|N |)+1 ).

Computational experiments

We present next our numerical assessment of the algorithms discussed in the paper for problems U Γ -T W SP and U γ -T W SP . The proposed solution approaches have been coded in JAVA and our numerical experiments have been carried out on an Intel(R) Core(TM) i7 CPU M 620, 2.67 GHz, 4 GB RAM machine, under microsoft operating system. The experimental results underline that the robust version of the T W SP is not much harder to solve than its deterministic counterpart. Furthermore, the results show that, while the dynamic programming approach for U γ -T W SP requires more computational effort than for solving U Γ -T W SP , U γ -T W SP provides cheaper optimal solution than U Γ -T W SP . More details about the computational results are reported in what follows. First, we describe the instances used to assess the behavior of the proposed dynamic programming approaches. Then, we discuss the numerical results. [START_REF] Dumitrescu | Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem[END_REF].

Our experiments are based on the grid networks from Class 6 used in [START_REF] Dumitrescu | Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem[END_REF]. The characteristic of these networks are reported in Table 1. For each network, we generate a set of different instances by varying the values of Γ (or γ) and ρ = ra /r a as follows. Ratio ρ takes each value in {0.5, 0.6, 0.7, 0.8, 0.9, 1}. For the value of Γ, we consider two sets of instances S1 and S2 defined below.

Generating time windows

We describe next how we generate b and b such that all instances always have a feasible solution. We let T and T represent the shortest paths trees with respect to r + r and r, respectively. We let p denote the path from node o to node d in T and the width of Instances S1 The set contains instances with no connections to the probabilistic bounds discussed in Section 2.2. To build these instances, we let Γ take each value in {3, 6, 12, 25, 50}. These values are such that the cardinality of the optimal paths are less than Γ.

Instances S2 The set contains instances for which γ and Γ are generated according to the probabilistic bounds. Namely, we compute function γ for each probability level in {0.01, 0.05, 0.1} following the construction outlined in Appendix A. For Γ, we compute first an upper bound U B on the longest feasible path for the problem and then set Γ = γ(U B), see Remark 3. Bound U B is computed as follows: for each node in i ∈ V , we let r i be the value of the lowest resource arc outgoing from i, r i = min (i,j)∈A r ij , and we sort the nodes in V by non-decreasing values of r. Then,

U B is equal to max U B∈Z+ U B : U B i=1 r i ≤ b U B .
Table 2 reports the values of U B and the time needed to compute the bounds for the T W SP . The values of Γ are shown in the last three columns for different values of .

Price of robustness In our results, we report the optimal solution cost for the deterministic problems, while the solution costs for robust problems are provided under the form of prices of robustness. The latter can be computed as follows PoR = opt(P ) -opt(T W SP ) opt(T W SP ) ,

where opt(P ) is the optimal solution cost of problem P ∈ {U Γ -T W SP, U γ -T W SP }. PoR represents the additional cost required to obtain solutions robust with a prescribed guarantee. Notice, however, that in real applications this cost is significantly smaller than the cost needed to repair the deterministic solutions that become infeasible in the presence of uncertainty.

Numerical results

Our computational results are presented in Tables 345where we provide the solution times in seconds, numbers of generated labels, solution costs, and prices of robustness. Since for set S2 we have a unique value of Γ, each row of Table 5 shows the average results over ρ only. Each row of Table 4 averages the results for the different values of ρ and Γ.

Instances in S1 The computational results for instances in S1 are presented in Tables 3 and4. Table 3 provides average results for T W SP and U Γ -T W SP taken over the different values of ρ and Γ, while Table 4 shows the variations observed for the different values of Γ. We see that for the instances tested, U Γ -T W SP does not seem much harder to solve that T W SP . This may be surprising given the exponential (in Γ) worst-case running time of the robust label-setting algorithm. However, the label-setting algorithm is well-known for generating only a subset of all possible labels. Still, Table 4 confirms that increasing Γ tends to increase solution times, which is particularly visible when Γ changes from 12 to 25 or 50. Another observation one can make is that widening time windows increases the difficulty of solving all problems, and that the increase in solution times is more marked for U Γ -T W SP than for T W SP . Indeed, comparing w = 40 with w = 100, the average solution times for the T W SP are multiplied by 1.7 while they are multiplied by 2.9 for the U Γ -T W SP . This, again, can easily be explained by the larger dimension of the labels in the robust case, which makes more room for creating more labels when time windows are widened. Regarding the optimal solution costs (and the related prices of robustness), the results show that, as expected, increasing the value of Γ raises the price of robustness, while widening time windows reduces the price of robustness.

Instances in S2 Table 5 shows that the robust T W SP with variable budgeted uncertainty is more difficult to solve than U Γ -T W SP . Indeed, the computational cost of the label-setting algorithm for solving the U γ -T W SP is, on average, 1.52 times higher than the time required for solving the U Γ -T W SP (see Table 3). This behavior is justified by the number of generated labels. Indeed, the labels generated when solving U γ -T W SP are 1.54 times higher than that processed by the labelsetting algorithm to solve U Γ -T W SP . The higher number of labels is due to the fact that the feasibility check is done for a subset of the element of the labels. It follows, that unfeasible labels for the U Γ -T W SP are feasible for the U γ -T W SP . The table also shows that model U γ -T W SP leads to significant reduction in the price of robustness obtained by model U Γ -T W SP .

T W SP

Concluding remarks

In this paper, we have addressed a variant of the constrained shortest path problem. In particular, we have assumed that the resource consumption is not known with precision, rather, it belongs to an uncertainty set. We have proved that the problem is N P-hard in the strong sense for unbounded uncertainty sets. To overcome this issue, we have considered the budgeted uncertainty set and the variable budgeted uncertainty set. Indeed, the considered sets have been successfully applied to combinatorial optimization problems, and in many cases, the complexity of the robust counterparts are similar to the complexity of the deterministic problem.

We have analyzed two types of resource constraints, that is, time windows and capacity. We have proved that the latter version of the problem can be solved in pseudo-polynomial time, thus, the robust version maintains the complexity of the deterministic counterpart. Interestingly, the complexity of the robust version of the time windows shortest path problem increases. Indeed, we have proved it is N P-hard in the strong sense, using a reduction from the independent set problem. This is the first example of a weakly N P-hard combinatorial optimization problem whose robust version (under budgeted uncertainty) is N P-hard in the strong sense.

A dynamic programming-based solution approach has been devised in order to solve the problems at hand. Robust labels have been defined and the well-known dominance relations have been extended to address the robustness. The developed label-setting algorithm has been tested by considering instances inspired from the scientific literature. Several scenarios have been considered in order to assess the behavior of the proposed solution strategy. The computational results underline the effectiveness of the algorithm in solving the robust version of the time windows shortest path problem with budgeted uncertainty set. In addition, we have shown that using the variable budgeted uncertainty set a reduction in the price of robustness is observed.

It is worth observing that the defined label-setting algorithm is able to solve the robust shortest path problem with capacity constraint. However, speed up techniques have to be considered, that is, use of lower and upper bounds on both the cost and the resource consumption and pre-processing procedures in order to reduce the dimension of the networks by removing nodes and arcs. The extension of the proposed dynamic programming-based solution approach to the problem with capacity constraint is an interesting subject of future investigation.

Figure 1 :

 1 Figure 1: Reduction from the knapsack problem to U-CSP .

  time windows is denoted by w (and set to value in {40, 100, 200}). The values of b i and b i are set according to the following rule    b i = Ti -w; b i = Ti , for each i ∈ p, b i = Ti -w; b i = Ti , for each i ∈ p and rand < 0.5, b i = Ti ; b i = Ti + w, for each i ∈ p and rand ≥ 0.5, (25)where Ti and Ti are the costs of the paths from o to i in T and T , respectively, and rand is chosen randomly through the uniform distribution [0, 1].

  1 , . . . , i l ), and l = |p|. The naive approach to U Γ -T W SP would express the problem as a shortest path problem with |U Γ | time-windows constraints, one for each r ∈ U Γ . Defining s = |U Γ | and U Γ = {r 1 , . . . , r

s }, the naive approach would associate to node i and each path p from o to i a label with s resources, κ(p), t |p| (p, r 1 ), . . . , t |p| (p, r s ) ,

Table 1 :

 1 Characteristics of the test problems proposed in

	6.1 Test problems
	test	nodes	arcs density
	G1	625	2400	3.84
	G2	2500	9800	3.92
	G3	5625	22200	3.95
	G4	15625	62000	3.97
	G5	22500	89400	3.97
	G6	30625 121800	3.98
	G7	40000 159200	3.98

Table 2 :

 2

	γ(U B)

Computation of U B and Γ for ∈ {0.01, 0.05, 0.1}.

Table 3 :

 3 Average computational results for the instances belonging to set S1.

	U Γ -T W SP

Table 4 :

 4 Average computational results for each value of Γ when solving the instances belonging to the set S1.

			T W SP			U Γ -T W SP			U γ -T W SP
	test problems time #labels	cost	|p|	time #labels PoR %	|p|	time	#labels PoR %	|p|
	0.01	G1 0.02	159.83	4427.00	48.00	0.01	108.50	7.30	48.00	0.05	261.50	4.96	48.00
		G2 0.17	318.00	8707.00	98.33	0.20	489.00	12.60	98.00	0.61	1323.33	10.69	98.00
		G3 0.47	442.33 12663.67 148.00	1.22 1388.00	7.57 148.00	3.09	3108.17	5.35 148.00
		G4 2.50	851.67 21675.33 246.00	7.78 3127.33	8.00 245.00	21.24	7358.00	5.59 245.00
		G5 3.95	912.83 15226.33 293.33 14.64 4034.17	6.16 293.00	40.11	9551.67	5.30 293.00
		G6 6.50 1086.00 24798.00 340.00 51.04 9271.33	10.03 339.00 124.94 20666.50	6.52 339.00
		G7 9.54 1213.83 22215.33 392.33 39.25 4929.17	8.78 392.00 360.57 15381.50	6.42 392.00
	AVG	3.31	712.07 15673.24 223.71 16.31 3335.36	8.63 223.29	78.66	8235.81	6.40 223.29
	0.05	G1 0.02	159.83	4427.00	48.00	0.02	141.33	7.25	48.00	0.03	257.83	4.88	48.00
		G2 0.17	318.00	8707.00	98.33	0.22	455.00	12.12	98.00	0.44	984.50	10.24	98.00
		G3 0.47	442.33 12663.67 148.00	1.26 1218.83	6.29 148.00	1.95	2059.33	3.63 148.00
		G4 2.50	851.67 21675.33 246.00	7.64 2750.83	7.42 245.00	14.33	5335.83	5.15 245.00
		G5 3.95	912.83 15226.33 293.33 12.63 3092.50	5.92 293.00	23.81	5901.17	4.58 293.00
		G6 6.50 1086.00 24798.00 340.00 37.52 6324.83	8.80 339.00	70.92 12058.33	6.06 339.00
		G7 9.54 1213.83 22215.33 392.33 34.54 4316.00	7.75 392.00	80.05 10176.50	5.70 392.00
	AVG	3.31	712.07 15673.24 223.71 13.41 2614.19	7.93 223.29	27.36	5253.36	5.75 223.29
	0.1	G1 0.02	159.83	4427.00	48.00	0.02	144.83	6.22	48.00	0.03	226.17	4.88	48.00
		G2 0.17	318.00	8707.00	98.33	0.21	441.00	11.57	98.00	0.41	899.50	9.72	98.00
		G3 0.47	442.33 12663.67 148.00	1.04 1039.83	5.91 148.00	1.57	1661.00	2.56 148.00
		G4 2.50	851.67 21675.33 246.00	6.57 2210.67	5.80 245.00	12.13	4039.00	4.46 245.00
		G5 3.95	912.83 15226.33 293.33 10.58 2517.67	5.50 293.00	19.15	4417.33	4.36 293.00
		G6 6.50 1086.00 24798.00 340.00 29.03 4934.33	8.14 339.00	46.49	8107.50	5.52 339.00
		G7 9.54 1213.83 22215.33 392.33 28.48 3580.33	7.34 392.00	57.93	7778.50	5.15 392.00
	AVG	3.31	712.07 15673.24 223.71 10.85 2124.10	7.21 223.29	19.67	3875.57	5.24 223.29

Table 5 :

 5 Average computational results for the instances belonging to set S2.

A Probabilistic bounds

Bertismas and Sim [START_REF] Bertsimas | The price of robustness[END_REF] present various examples of bounds δ(Γ, |A|). In our computational results, we use bound

where ν = (Γ + |A|)/2 and µ = ν -ν . From (26), we see that the smallest value of Γ such that the resource constraint are satisfied with probability 1 -is given by the solution of minimization problem min Γ s.t. δ(Γ, |A|) ≤ ,

which can be solved by a bisection method. We can then compute γ in two steps. First, we compute function Γ : {1, . . . , |A|} → Γ by solving (27) when |A| is replaced by k which takes any value in {1, . . . , |A|}. Then, we compute an affine upper-bounding approximation of the resulting function.

The reader is redirected to [START_REF] Poss | Robust combinatorial optimization with variable budgeted uncertainty[END_REF] for more details on a similar construction.

B Existence of a solution (µ, ν, σ, r, b) to ( 14), [START_REF] Gounaris | The robust capacitated vehicle routing problem under demand uncertainty[END_REF], and

Let r be defined as follows. For each i ∈ {1, . . . , n} and k ∈ {2, . . . , m}, we have

and for each i ∈ {1, . . . , n}, we have ra(2i-1,1) = 2, and

k) = 4(k -1), for each k ∈ {2, . . . , m + 1} and i ∈ {1, . . . , n}. Parameters µ and σ follow from these definitions. Namely,

for each h ∈ {1, . . . , m} and µ = σ 1 + 1. Then we must fix ν to any integer greater than 4(m -1) + 1. Finally, deadlines b n and b n+h for each h ∈ {1, . . . , m} are chosen according to the equations in ( 14) and [START_REF] Irnich | Shortest Path Problems with Resource Constraints[END_REF], respectively, while other deadlines can be set, for instance, to n(µ + 1).