A scenario-based framework for supply planning under uncertainty: stochastic programming versus robust optimization approaches

Abstract

In this paper we analyze the effect of two modelling approaches for supply planning problems under uncertainty: two-stage stochastic programming (SP) and robust optimization (RO). The comparison between the two approaches is performed through a scenario-based framework methodology, which can be applied to any optimization problem affected by uncertainty. For SP we compute the minimum expected cost based on the specific probability distribution of the uncertain parameters related to a set of scenarios. For RO we consider static approaches where random parameters belong to box or ellipsoidal uncertainty sets in compliance with the data used to generate SP scenarios. Dynamic approaches for RO, via the concept of adjustable robust counterpart, are also considered. The efficiency of the methodology has been illustrated for a supply planning problem to optimize vehicle-renting and procurement transportation activities involving uncertainty on demands and on buying costs for extra-vehicles. Numerical experiments through the scenario-based framework allow a fair comparison in real case instances. Advantages and disadvantages of RO and SP are discussed.

1 Introduction

In this paper we analyze the effect of two modelling approaches, stochastic programming (SP) and robust optimization (RO), to a supply planning problem under uncertainty. Stochastic programming and robust optimization are considered two alternative techniques to deal with uncertain data both in a single period and in a multi-period decision making process. The main difficulty associated with the former is the need to provide the probability distribution functions of the underlying stochastic parameters. This requirement creates a heavy burden to the user because in many real-world situations, such information is unavailable or hard to obtain (see for example Birge and Louveaux 2011; Ruszczyński and Shapiro 2003). On the other side RO addresses the uncertain nature of the problem without making specific assumptions on probability distributions: the uncertain parameters are assumed to belong to a deterministic uncertainty set. The drawback of this approach is the potentially strong dependence of the solution on the rather arbitrarily chosen uncertainty set. RO adopts a min-max approach that addresses uncertainty by guaranteeing the feasibility and optimality of the solution against all instances of the parameters within the uncertainty set (Bertsimas et al. 2011; Dupačová 1998). A vast literature about the hypotheses that have to be imposed on the structure of the uncertainty set in order to have computationally tractable problems are available, see Bertsimas and Sim 2004; Soyster 1973 for polyhedral uncertainty sets and Ben-tal and Nemirovski (1999); Ben-Tal et al. (2004); Ghaoui and Lebret (1997); Ghaoui et al. (1998) for ellipsoidal uncertainty sets. The original RO model deals with static problems where all the decision variables have to be determined before any of the uncertain parameters are realized. This is not the typical situation in most problems that are multi-period in nature, and where a decision at any period can and should account for data realizations in previous periods. An extension of robust optimization to a dynamic framework was analyzed in Ben-tal and Nemirovski (1999); Ben-Tal et al. (2004); Ben-tal et al. (2009); Bertsimas and Goyal (2012); Bertsimas and Caramanis (2010); Bertsimas and Goyal (2010) and many others via the concept of adjustable robust counterpart (ARC) and affinely adjustable robust counterpart (AARC), where part of the decision variables, the so-called adjustable variables, have to be determined after a portion of the uncertain data is realized. In the case of AARC the dependence of the adjustable variables on the realized data is represented by an affine function. The introduction of AARC is motivated by the fact that in most of the cases the ARC approach is computationally intractable.

Comparing SP and RO methods considering a cost-based approach is somehow unilateral. The philosophy of the two approaches to deal with uncertainty is completely different indeed. The RO approach is well-suited to the cases where the optimizer wants to hedge the result against all imaginable outcomes of the uncertain events. Such methods can be successfully implemented usually only in the cases where the hedging against rare events is cheap or at least at low cost with respect to possible consequences. On the other side, the SP approach includes the probabilistic information about the events into consideration. As a consequence, less probable events are counted only with small weights implying less conservative and, in many cases, cheaper solutions. As drawback, we have a risk of appearance of rare but expensive events which can result in high actual costs if such an “unhappy” event is realized.

To make a fair comparison between the above approaches we consider a scenario-based framework, which does not just compare the different solution approaches in terms of costs; it compares the costs of implementing the non-adjustable (or first-stage) solutions obtained using the information available up to now, with SP or RO. The adjustable variables are then determined when the uncertainty is revealed by solving a deterministic problem. This heuristic methodology allows also to overcome the typical problem of computational intractability of ARC and can be applied to any optimization problem affected by uncertainty.

The efficiency of the methodology has been illustrated on a supply planning problem to optimize vehicle-renting and procurement transportation activities to satisfy demand in several destinations out of several origins. Uncertainty on demands and cost of extra vehicles is considered. The problem consists in determining the number of vehicles to book, at the end of each time period, from each plant of the set of suppliers, to replenish a certain good at factories in order to minimize the total cost, given by the sum of the transportation costs from origin to destinations (including the discount for vehicles booked but not used) and the cost of buying units of product from external sources in case of inventory shortage at the destinations. We formulate and solve the problem as a two-stage stochastic programming model and as robust optimization models with different uncertainty sets where scenarios of demand and buying costs are built on historical data.

Since the demand of goods is in general highly affected by the economic conditions, a reliable forecast and reasonable estimates of probability distributions are difficult to obtain. Furthermore, the supply-planning company would avoid to negotiate the quantity of vehicles with the suppliers every time period, being immunized against every possible demand realization allowing to save a lot of operational activities. This motivates us to consider besides the SP approach, also RO approaches and to quantify the value (or extra-cost) of RO guarantees. First we consider static approaches where the uncertain parameters belong to box or box-ellipsoidal uncertainty sets, and then dynamic approaches, via the concept of ARC with scenario generated uncertainty set and scenario-based framework methodology. A robust solution at the tactical level allows to find a feasible solution for the operational planning problem for each possible realization of demand in the uncertainty set considered.

Both SP and RO allow to determine the nonadjustable variables, i.e., the number of vehicles to book at the end of each time period, using the information available at that time. As new information on demand and buying costs from external sources become available, the adjustable (or recourse) decision variables have to be determined. We describe five strategies for updating the adjustable variables given the values of the already determined values of the nonadjustable variables. The methodology allows to quantify the cost saving of the SP approach compared to the RO, as well as the value of a more conservative strategy avoiding a negotiation of the number of vehicles every period with the suppliers or third-party service providers (3PL). Numerical experiments through the scenario-based framework allow a fair comparison in real instances inspired by a gypsum replenishment problem of an Italian cement factory producer.

The paper is organized as follows: Sect. 2 introduces basic concepts about stochastic and robust optimization. A scenario-based framework used to compare the two approaches is presented in Sect. 3 while Sect. 4 describes the supply planning problem. Section 5 discusses the two-stage stochastic programming formulation, robust formulations and the scenario based framework for comparison. Finally, Sect. 6 discusses the numerical results. Conclusions follow.

2 Stochastic versus robust optimization: basic facts and notations

We consider the uncertain linear optimization problem

$$\begin{aligned} \left\{ \min _{x} \left\{ c^{T} x + o:\ Ax \le h\right\} \right\} _{(c,o,A,h)\in \mathcal {U}}\ , \end{aligned}$$

(1)

as a collection of linear optimization problems with data varying in a given uncertainty set $\mathcal {U}$ where $x \in \mathbb {R}^{n}_{+}$ is the vector of non-negative decision variables, $c \in \mathbb {R}^n$ and $o\in \mathbb {R}$ are the coefficients of the objective function, $A\in \mathbb {R}^{m \times n}$ is the constraint matrix, and $h\in \mathbb {R}^{m}$ is the right hand side vector.

Let us introduce a scenario based stochastic programming formulation of problem (1).

Let us consider:

• A finite set $\zeta ^s$, $s\in \mathscr {S}=\left\{ 1,\ldots ,S\right\}$ of realizations (or scenarios) of a random event $\zeta$ which affects the data varying in $\mathcal {U}$. The random process $\zeta$ is defined on a probability space $(\Xi ,\mathscr {F},P)$ with support $\Xi$ and given probability distribution P on the $\sigma$-algebra $\mathscr {F}$.

• A partitioning of the decision variable $x=[u ; v^1;\ldots ; v^S]$, where $u\in \mathbb {R}^{n_1}_{+}$ represents the first-stage decision which has to be taken without full information on the random event $\zeta$. When full information is received on the realization of the random vector, then, second-stage or recourse actions $v^s\in \mathbb {R}^{n_2}_{+}$, $s=1,\ldots ,S$ are taken. Throughout this paper, we use “;” for adjoining elements in a column.

• A partitioning of vector cost $c=[p;P^1 q^1;\ldots ;P^S q^S]$, where $p\in \mathbb {R}^{n_1}$ is the first stage cost, $q^s\in \mathbb {R}^{n_2}$, $s=1,\ldots ,S$, is the second stage cost and $P^s$ is the probability of scenario $s=1,\ldots ,S$.

• A partitioning of matrix A as follows:

  $$\begin{aligned} A=\left[ \begin{array}{c|ccc} \tilde{A} &{} &{} \mathbf {0} &{}\\ \hline T^1 &{} W &{} &{}\\ \vdots &{} &{} \ddots &{} \\ T^S &{} &{} &{} W \end{array}\right] \ , \end{aligned}$$

  where $\tilde{A}\in \mathbb {R}^{m_1 \times n_1}$ is a deterministic matrix, $T^s \in \mathbb {R}^{m_2\times n_1}$, $s=1,\ldots ,S$ are called technology matrices, $W\in \mathbb {R}^{m_2 \times n_2}$ is the matrix of fixed recourse, and $\mathbf {0}$ the null matrix of dimension $m_1 \times S n_2$.

• The partitioning of right hand side vector $h=[\tilde{h};h^1;\ldots ;h^S]$, where $\tilde{h}\in \mathbb {R}^{m_1}$ is a deterministic right hand side vector and $h^s\in \mathbb {R}^{m_2}$, $s=1,\ldots ,S$ are stochastic right hand side terms.

Definition 1

The two-stage linear stochastic problem with fixed recourse, is formulated as follows:

$$\begin{aligned}&\! \min _{u,v^1,\ldots ,v^S} p^{T} u + \sum _{s=1}^{S}P^s \left( {q^s}^{T} v^s \right) + o \nonumber \\&\text {s.t. } \tilde{A} u\le \tilde{h},\nonumber \\&\qquad T^s u + W v^s\le h^s,\quad s=1,\ldots , S,\nonumber \\&\qquad u \ge 0,\quad v^{s}\ge 0,\quad s=1,\ldots ,S. \end{aligned}$$

(2)

We note that o usually does not appear in SP problems, however it is reported for the sake of consistency of notation with the RO formulation.

Let us introduce the robust optimization counterpart of problem (1). We assume that the uncertainty set $\mathcal {U}$ is parametrized in an affine way by the perturbation vector $\zeta =[\zeta _1; \ldots ; \zeta _L]$ in a given perturbation set Z:

$$\begin{aligned} \mathcal {U}=\left\{ [c;o;A;h]=[\bar{c};\bar{o};\bar{A};\bar{h}] + \sum _{\ell =1}^L\zeta _\ell [c_\ell ;o_\ell ;A_\ell ;h_\ell ]: \zeta \in Z \subset \mathbb {R}^{L} \right\} \ , \end{aligned}$$

(3)

where $[c_\ell ;o_\ell ;A_\ell ;h_\ell ]$ represent basic perturbations from the nominal data $[\bar{c};\bar{o};\bar{A};\bar{h}]$.

Definition 2

The Robust Counterpart of the uncertain linear optimization problem (1) is formulated as follows

$$\begin{aligned} \min _{x}\left\{ \sup _{(c,o,A,h)\in \mathcal {U}}c^{T} x + o:\ Ax \le h,\ (c,o,A,h)\in \mathcal {U}\right\} , \end{aligned}$$

(4)

that is minimizing the worst total cost over all feasible solutions.

Problem (4) can be equivalently formulated as

$$\begin{aligned} \min _{x,w}\left\{ w:\ c^{T} x -w\le - o,\ Ax \le h,\ \forall (c,o,A,h)\in \mathcal {U}\right\} . \end{aligned}$$

(5)

Notice that if x is a feasible solution of (4), then x remains feasible when we extend the uncertainty set $\mathcal {U}$ to its convex hull $Conv(\mathcal {U})$.

We consider tractable formulations of the robust problem (5) with uncertainty set $\mathcal {U}$ computationally tractable, that is solvable in polynomial time with a specific description of the uncertainty set. There are three well known formulations of RO problems in literature; these are given by Ben-tal and Nemirovski (2000); Ben-tal et al. (2009); Bertsimas and Sim (2004) and Soyster (1973). They all share the advantage that minimal assumptions about the nature of the uncertainties have to be made and they differ in the ways the uncertainty sets are represented. More specifically, the formulations by Soyster (1973) and by Bertsimas and Sim (2004) use polyhedral uncertainty sets, while the formulation by Ben-tal and Nemirovski (1999); Ben-Tal et al. (2004); Ghaoui and Lebret (1997); Ghaoui et al. (1998) considers an ellipsoidal uncertainty set, transforming the original LP problem into a second order cone programming (SOCP) problem.

Among possible formulations we consider the case of box uncertainty sets and ellipsoidal uncertainty sets. To show the construction of the uncertainty sets we focus on a single uncertain linear inequality:

$$\begin{aligned} \left\{ a^{T} x \le h \right\} _{(a,h)\in \mathcal {U}}\ . \end{aligned}$$

(6)

The tractable formulation of $\mathcal {U}$ through a box uncertainty set is given by

$$\begin{aligned} a^{T} x\le h,\,\forall [a;h]\!\in \!\left\{ \! [\bar{a};\bar{h}]\!+\!\sum _{\ell =1}^L\zeta _\ell [a^\ell ;h^\ell ]:\, \zeta \!=\![\zeta _1;\ldots ;\zeta _L]\!\in \!\mathbb {R}^L,\, \Vert \zeta \Vert _{\infty }\le 1\!\right\} , \end{aligned}$$

(7)

where $\Vert \cdot \Vert _{\infty }$ is the infinity norm, while the formulation through an ellipsoidal uncertainty set is given by

$$\begin{aligned} a^{T} x\le h,\;\forall [a;h]\in \left\{ [\bar{a};\bar{h}]+\sum _{\ell =1}^L\zeta _\ell [a^\ell ;h^\ell ]\;:\; \zeta =[\zeta _1;\ldots ;\zeta _L]\in \mathbb {R}^L,\, \Vert \zeta \Vert _{2}\le \Omega \right\} , \end{aligned}$$

(8)

where $\Vert \cdot \Vert _{2}$ is the Euclidean norm and $\Omega$ the radius.

As shown in Ben-tal et al. (2009) (8) can be written as

$$\begin{aligned} \left[ (\bar{h}-\bar{a}^{T} x )/\Omega ; h^1 - {a^{1}}^{T} x;\dots ;h^L - {a^{L}}^{T} x \right] \in \mathscr {LC}_{L+1}, \end{aligned}$$

(9)

where $\mathscr {LC}_{L+1} =\left\{ t= \left[ t_0;t_1;\ldots ;t_L\right] \in \mathbb {R}^{L+1}: t_0 \ge \left\| t_1;\ldots ;t_L\right\| _2\right\} \ ,$ is the second order (or Lorentz) cone of $\mathbb {R}^{L+1}$, so that (8) is equivalent to

$$\begin{aligned} \Omega \sqrt{\sum _{\ell =1}^L([a^\ell ]^{T} x - h^\ell )^2}\le \bar{h} - \bar{a}^{T} x. \end{aligned}$$

(10)

Let us consider a random vector [a; h] defined by

$$\begin{aligned}{}[a;h]=[\bar{a};\bar{h}]+\sum _{\ell =1}^L\zeta _\ell [a^\ell ;h^\ell ], \end{aligned}$$

(11)

where

$$\begin{aligned} \zeta _1,\ldots ,\zeta _L: \text{ zero } \text{ mean } \text{ independent } \text{ random } \text{ variables } \text{ with } \text{ values } \text{ in } [-1,1]. \end{aligned}$$

(12)

The following result holds true (see Corollary 2.3.2. in Ben-tal et al. 2009):

Proposition 1

If [a; h] is the random vector given by (11), (12) and x is a solution of (9) then

$$\begin{aligned} \text{ Prob }\left\{ \ a^Tx > h\right\} \le e^{-\frac{\Omega ^2}{2}}. \end{aligned}$$

(13)

We note that the above result holds for any probability distribution for the random vector $\zeta =[\zeta _1;\ldots ;\zeta _L]$ that satisfies (12). Let us denote by $\mathcal{P}$ the family of all probability distributions that satisfy (12) and consider the ambiguous chance constraint where $\varepsilon \in (0; 1)$ is a prespecified small tolerance:

$$\begin{aligned} \forall P\in \mathcal{P}\quad {\text{ Prob }}_{\zeta \sim P}\left\{ \zeta \; : \; \bar{a}^{T} x+\sum _{\ell =1}^L\zeta _\ell [a^\ell ]^{T} x\,>\,\bar{h}+\sum _{\ell =1}^L\zeta _\ell h^\ell \right\} \le \varepsilon . \end{aligned}$$

(14)

We note that the relation between $\epsilon$ and $\Omega$ is $\Omega = \sqrt{\ln \epsilon ^{-2}}.$

The above problem is called an ambiguous chance constraint because we do not have any knowledge about the probability distribution P except the fact that it belongs to the class $\mathcal{P}$ and we have uncertainty in the particular realization of the data (given its distribution). From Proposition 1 it follows that any x satisfying the second order cone constraint (9) is a solution of (14).

All decision variables described above in case of RO approaches represent here and now decisions, i.e., decisions that are taken before the actual data reveals itself. This is too restrictive since in reality there may be situations in which the decisions must adjust themselves to the actual data. To model adjustability of the variables we can proceed as follows: $\forall \, j\le n$ we suppose that $x_j$ is dependent on a portion of the data $(c,o,A,h)\in \mathcal {U}$, i.e.

$$\begin{aligned} x_j=X_j(\pi _j(\zeta )),\quad j=1,\ldots ,n, \end{aligned}$$

(15)

where the uncertain data are denoted by $\zeta =(c,o,A,h)$, $\pi _j$ describes a portion of the uncertain data by a suitable linear mapping on $\zeta$, and $X_j$ are decision rules to be chosen. We can now replace problem (5) with the usage of the new decision rules $X_j$ as follows:

$$\begin{aligned} \min _{\left\{ X_j(\cdot )\right\} _{j=1}^n,w}\left\{ w:\ c(\zeta )^{T} X(\zeta ) -w\le - o(\zeta ),\ A(\zeta ) X(\zeta ) \le h(\zeta ),\, \zeta \in \mathcal {U}\right\} \ , \end{aligned}$$

(16)

where $X(\zeta )=[X_1(\pi _1(\zeta ));\ldots ;X_n(\pi _n(\zeta ))]$. The robust optimization problem (16) is called adjustable robust counterpart (ARC).

We consider:

• the case of fixed recourse, i.e. for every adjustable variable all its coefficients in the objective function and the left hand side of the constraints are certain;

• a scenario-generated uncertainty set described as a convex hull of finitely many scenarios $\zeta ^s$, $s=1,\ldots ,S$.

Assuming that $x=\left[ u; v(\zeta )\right]$, where u refers to the here-and-now variables (non-adjustable) and v refers to the wait-and-see (adjustable) variables, (16) becomes

$$\begin{aligned} \min _{u,v(\zeta ),w}\!\!\left\{ \!w\!:\! p(\zeta )^{T}u\! +\! q^{T}\! v(\zeta ) \!-\! w \! \le \! - o(\zeta ),\ T(\zeta ) u \!+\! W \! v(\zeta ) \le \! h(\zeta ),\ \zeta \!\in \! Conv\left\{ \zeta ^1,\ldots ,\zeta ^S\!\right\} \!\right\} \end{aligned}$$

(17)

where $p(\zeta ), T(\zeta ),o(\zeta ),h(\zeta )$ are affine in $\zeta$.

The following theorem holds (see Ben-tal et al. 2009):

Theorem 1

Under the assumption of fixed recourse and scenario-generated uncertainty set described above, the ARC (17) is equivalent to the computationally tractable problem

$$\begin{aligned} \min _{u,\left\{ v^s\right\} _{s=1}^S,w}\left\{ \!w: \! p(\zeta ^s)^{T}u\! + \!q^{T} v^s\! - \!w \!\le \!- o(\zeta ^s),\! T(\zeta ^s) u \!+\! W v^s \le h(\zeta ^s),\; s=1,\ldots ,S\!\right\} \end{aligned}$$

(18)

and their optimal values are equal. Moreover, if $\bar{w}$, $\bar{u}$, $\left\{ \bar{v}^s\right\} _{s=1}^{S}$ is a feasible solution to (18), then the pair $\bar{w}$, $\bar{u}$ augmented by the decision rule for the adjustable variables

$$\begin{aligned} v(\zeta )= \sum _{s=1}^{S}\lambda _s(\zeta )\bar{v}^s, \end{aligned}$$

(19)

form a feasible solution to the ARC. Here $\lambda (\zeta )=[\lambda _1(\zeta );\ldots ;\lambda _S(\zeta )]$ is a nonnegative vector with the unit sum of entries such that

$$\begin{aligned} \zeta =\sum _{s=1}^{S}\lambda _s(\zeta )\zeta ^s. \end{aligned}$$

(20)

The assumption of fixed recourse is essential, since without it the ARC may become intractable (see Ben-Tal et al. 2004). However, from a practical point of view, Eq. (20) is not easily satisfied unless the number of scenarios S becomes extremely large.

3 A scenario based framework for comparison of modelling approaches under uncertainty

In this section we propose a scenario based framework for comparison of stochastic programming and robust optimization approaches. The framework can be applied to any optimization problem affected by uncertainty.

We introduce the following notation:

• $\mathbf {M_1}$ is the stochastic optimization problem (2);

• $\mathbf {M_2}$ is the robust optimization problem (5) with box constraints as in (7);

• $\mathbf {M_3}$ is the robust optimization problem (5) with ellipsoidal constraints as in (8);

• $\mathbf {M_4}$ is the computationally tractable robust optimization problem (18).

Let

$$\begin{aligned} \hat{\Delta } = \left\{ \hat{\zeta }^1,\hat{\zeta }^2,\ldots ,\hat{\zeta }^{S}\right\} , \end{aligned}$$

(21)

be a given set of scenarios of the uncertain parameters $\zeta$ eventually obtained by historical data. We consider a set of indices

$$\begin{aligned} \bar{\mathscr {S}}=\left\{ 1,\ldots ,\bar{S}\right\} \subset \mathscr {S}, \end{aligned}$$

(22)

with cardinality $\bar{S}<S$. For each such $\tau =\bar{S},\ldots ,S-1$ we compute the quantities

$$\begin{aligned} \bar{\zeta }^{\tau }=\frac{1}{\tau }\sum _{s=1}^{\tau } \hat{\zeta }^s,\quad \text { and } \quad \max _{s=1,\ldots ,\tau }\left\| \hat{\zeta }^{s} - \bar{\zeta }^{\tau }\right\| _2 \ , \end{aligned}$$

(23)

which represent respectively the nominal term and basic perturbation term in (7) and (8).

For each $\tau =\bar{S},\ldots ,S-1$ we find the optimal first stage, or nonadjustable decision variables solutions $u^*$, of the corresponding optimization problem $\mathbf {M_m},\;\mathbf {m}=\mathbf {1},\ldots ,\mathbf {4}$, using only the information contained in the vectors

$$\begin{aligned} \hat{\zeta }^1,\hat{\zeta }^2,\ldots ,\hat{\zeta }^{\tau }. \end{aligned}$$

(24)

Assume now that the vectors $\hat{\zeta }^{\tau +1}$ become available. Then we can solve the optimization problem

$$\begin{aligned} \min _{w,v}\left\{ w:\ {p(\hat{\zeta }^{\tau +1})}^{T}u^{*}\! +\! q^{T} v \!- \!w \!\le \!- o(\hat{\zeta }^{\tau +1}), T(\hat{\zeta }^{\tau +1}) u^{*} \!+\! W v \le h(\hat{\zeta }^{\tau +1})\right\} , \end{aligned}$$

(25)

to obtain the adjustable variables $v^{*}$ . The optimal value of the objective function in (25) is denoted by $\mathbf {{cost}}_{\mathbf {m},\tau }$. It represents the optimal cost of the problem with the adjustable strategy considered in this section when using method $\mathbf {M_m}$ for determining the nonadjustable variables. If the optimization problem is infeasible we set $\mathbf {{cost}}_{\mathbf {m},\tau }=\infty$.

We also consider the following adjustable robust optimization problem according to Theorem 1:

• $\mathbf {M_5}$:

  • (a) Solve the computationally tractable optimization problem (18) using only the information (24);

  • (b) Solve the optimization problem

    $$\begin{aligned} \min _{\lambda }\varphi ^{\tau }(\lambda ):=\min _{\lambda }\left\| \zeta \!- \!\sum _{s=1}^{\tau }\lambda _s(\zeta )\zeta ^s\right\| ^2,\ \sum _{s=1}^{\tau }\lambda _s=1,\quad \lambda _s\ge 0, \end{aligned}$$

    (26)

    with $\zeta =\hat{\zeta }^{\tau +1}$;

  • (c) For each $\tau =\bar{S},\ldots ,S-1$ define the adjustable variables as in (19).

This method has the advantage that the adjustable variables are obtained by solving only the very simple optimization problem (26). However, this method only works if the optimal objective function of the latter problem $\varphi ^\tau \left( \lambda \left( \hat{\zeta }^{\tau +1}\right) \right)$ is equal to zero. In this case the optimal cost given by this method, $\mathbf {{cost}}_{\mathbf {5},\tau }$, is equal to the optimal value of the objective function (18). If $\varphi ^\tau \left( \lambda \left( \hat{\zeta }^{\tau +1}\right) \right) >0$ we set $\mathbf {{cost}}_{\mathbf {5},\tau }=\infty$.

Of course, when $\hat{\zeta }^{\tau +1}$ become available we can also solve the optimization problem

$$\begin{aligned} \min _{u,v,w}\left\{ w:\ p(\zeta )^{T}u + q^{T} v -w \le - o(\zeta ), T(\zeta ) u + W v \le h(\zeta )\right\} , \end{aligned}$$

(27)

with $\zeta =\hat{\zeta }^{\tau +1}$. However, this optimization problem, corresponding to the well-known Wait-and-See problem (WS) in SP, determines the optimal values of both the adjustable and nonadjustable variables, while in our setting the nonadjustable variables have to be determined before the $\hat{\zeta }^{\tau +1}$ become available. We denote by $\mathbf {{cost}}_{\tau }$ the optimal value of the objective function (27).

We finally compare methods $\mathbf {M_m},\;\mathbf {m}=\mathbf {1},\ldots ,\mathbf {5}$ by considering the aggregated costs:

$$\begin{aligned} \mathbf {{cost}}_{\mathbf {m}}:= \sum _{\tau =\bar{S}}^{S-1} \mathbf {{cost}}_{\mathbf {m},\tau },\quad \mathbf {m}=\mathbf 1 ,\ldots ,\mathbf 5 . \end{aligned}$$

(28)

The same for the wait-and-see problem, WS (27), $\mathbf {cost}:= \sum _{\tau =\bar{S}}^{S-1} \mathbf {{cost}}_{\tau }.$

4 Supply planning under uncertainty

In this section we shortly review the literature of supply planning under uncertainty and we describe the problem considered to illustrate the efficiency of the scenario based framework methodology.

4.1 Literature review

Freight transportation (Crainic and Laporte 1997) is one of todays’ most important logistic activities that influences the performance of many other economic activities. The two most important factors for having high performance level are the economic efficiency and the service quality. The former relates to the facts that those firms that make use of freight transportation service want to move the right amount of goods at the best cost. The latter highlights the importance of the quality of service, i.e. being able to satisfy clients demand of a good eventually avoiding inventory costs. Bolstering one almost certainly causes the other to suffer: for example, if one lowers his/her inventory to reduce costs, it will become difficult to meet varying customer demand. If one increases safety stock to meet peak demands, one could wind up with a great deal of excess inventory with nowhere to sell it, see Simchi-Levi and Simchi-Levi (2004). Traditionally, two prevailing supply chain strategies have dominated the industry: push and pull. However, new technologies, have enabled the creation of a third strategy, a hybrid push-pull model that offers the best of both worlds without their corresponding disadvantages, see Simchi-Levi and Simchi-Levi (2003).

The problem of transporting goods or resources from a set of supply points (production plants) to a set of demand points (destination factories or customers) is an important component of the planning activity of a manufacturing firm. A particular case is given by the so-called single-sink transportation problem, in which a single retailer is served by a set of suppliers. This problem has been extensively studied, in particular when the total cost is given by the sum of a variable transportation cost and a fixed charge cost to use the supplier (Alidaee and Kochenberger 2005; Lamar and Wallace 1997; Lamar et al. 1990; Maggioni et al. 2009). Critical parameters such as customer demands, row material prices and resource capacity are quite uncertain in real problems. An important issue is then represented by the decision on quantities to acquire and store at each destination factory before actual demands reveal themselves. This is involved in the tactical planning (Crainic and Laporte 1997) of the firm supply chain operations. In this paper we are dealing with a tactical planning problem of a firm supply chain operations, where decision on quantities to acquire and store at each destination factory before actual demands reveal themselves have to be chosen. Detailed information on the capacity of transportation vehicles, capacity of origin plants and destination warehouse are given. See Crainic and Laporte (1997) and Graves et al. (1993) for differences among planning levels, strategic, tactical and operational ones. Example of strategic models are those for designing physical networks and their evolutions, for location of the main facilities of a plant, for resource acquisition, for defining tariff policies. They usually involve long-term investment decision and strategic policies and they deal with planning at international, national and regional levels. Tactical planning problems modeling works over a medium term horizon for a rational and efficient allocation of existing resources in order to enhance the performance of the whole system. They usually incorporate seasonal changes in the data and not daily information: vehicle routing models belong to this class of models. On the other hand, the notion of cost is central to the operational planning model and it may have different components related to different events that may happen at the decision time (scarcity of goods at the origin, full capacity at destinations, delay, risk, etc.) see Graves et al. (1993).

The significance of uncertainty has prompted a number of works addressing random parameters in tactical level supply chain planning involving distribution of raw material and products (see for example Chen et al. 2014; Cheung and Powell 1996; Cooper and LeBlanc 1997; Crainic and Laporte 1997; Powell and Topaloglu 2003; Simchi-Levi 2014; Solyali et al. 2001; Landeghem and Vanmaele 2002; Yu and Li 2000). Nowadays firms are engaged in a continuous procurement process and collaboration with their supply chain partners. The firm regularly orders products from suppliers in a given area according to inventory, forecasted demand and inventory policy (Crainic et al. 2014). Firms may negotiate directly with carriers but very often they deal with a third-party logistic service provider (3PL) (Marasco 2008). In the recent past, 3PL, also referred to as logistics outsourcing (e.g. Knemeyer et al. 2003; Maltz and Ellram 1997; Marasco 2008; Razzaque and Sheng 1998), has received considerable attention due to a steadily increasing number of companies across industry sectors using third-party providers for the management of their logistics operations (e.g. Lieb and Bentz 2004, 2005; Lieb and Miller 2002; Lieb and Randall 1999). The functions performed by the third party can encompass the entire logistics process or selected activities within that process (Coyle et al. 2003; Lieb 1992). The 3PL combines goods into containers or trucks ensuring shipping usually with a fixed schedule. The firm needs to book in advance sufficient capacity to satisfy the demand leading to a negotiation with 3PL to reserve the necessary number of trucks. Usually the agreement between the firm and 3PL is made under uncertainty without full information about the demand of goods. Extra vehicles must be then purchased at a much higher cost than the initial one.

4.2 Problem description

We consider a supply planning problem to optimize vehicle-renting and transportation procurement activities to satisfy demand in several destinations out of several origins. Uncertainty on the demands and on the costs of extra vehicles is considered.

The logistic system is organized as follows: a set of suppliers, each of them composed by a set of plants (origins) has to satisfy the demand of a certain good from a set of factories (destinations) belonging to the same producer. The demand at the destination factory is considered stochastic. We assume a uniform fleet of vehicles with fixed capacity and we allow only full-load shipments. Shipments are performed by booking a number of capacitated vehicles in advance, before the demand is revealed. When the demand becomes known, the number of used vehicles is determined and there is an option to discount vehicles booked but not actually used. The cancellation fee is given as a proportion of the transportation costs. If the quantity shipped from the suppliers using the booked vehicles is not enough to satisfy the demand at destination factory, residual product is purchased from an external company at a higher price, which is considered stochastic as well. The problem is to determine the number of vehicles to book from each plant of the set of suppliers to replenish the good at factory in order to minimize the total cost for the producer of good, given by the sum of the transportation costs from origins to destinations.

4.3 Notation

We adopt the following notation.

Sets:

$$\begin{aligned}&\,\, \mathscr {K} = \{k:k=1,\ldots ,K\} \,\, \text {set of suppliers};\\&\,\, \mathscr {O}_k = \{i:i=1,\ldots ,O_k\} \,\, \text {set of plant locations of supplier } k\in \mathscr {K};\\&\,\, \mathscr {D} = \{j:j=1,\ldots ,D\} \,\, \text {set of destination factories}; \end{aligned}$$

Deterministic parameters:

$t_{ijk}$,:

unit transportation cost from supplier $i\in \mathscr {O}_k, k\in \mathscr {K}$ to plant $j\in \mathscr {D}$;

q,:

vehicle capacity;

$g_j$,:

maximum capacity which can be booked at the customer $j\in \mathscr {D}$;

$v_k$,:

maximum requirement capacity of supplier $k\in \mathscr {K}$;

$r_k$,:

minimum requirement capacity of supplier $k\in \mathscr {K}$;

$l_j^{0}$,:

initial inventory of product at customer $j\in \mathscr {D}$;

$\alpha$,:

cancellation discount.

Uncertain or stochastic parameters:

$d_{j}$,:

demand of customer j $\in \mathscr {D}$;

$b_{j}$,:

buying cost from external sources for customer j $\in \mathscr {D}$.

Variables:

$x_{ijk}$,:

number of vehicles booked from supplier $i\in \mathscr {O}_k$, $k\in \mathscr {K}$ to plant $j\in \mathscr {D}$,

(nonadjustable or first stage decision variables);

$z_{ijk}$,:

number of vehicles actually used from supplier $i\in \mathscr {O}_k$, $k\in \mathscr {K}$ to plant $j\in \mathscr {D}$,

(adjustable or second stage decision variables);

$y_j$,:

volume of product to purchase from an external source normalized by q, for

plant $j\in \mathscr {D}$, (adjustable or second stage decision variables).

To simplify the notation it is convenient to introduce the vectors

$$\begin{aligned}&d=\left( d_j\right) _{j\in \mathscr {D}}\in \mathbb {R}^D,\quad b=\left( b_j\right) _{j\in \mathscr {D}}\in \mathbb {R}^D,\quad y=\left( y_j\right) _{j\in \mathscr {D}}\in \mathbb {R}^D,\\&x=\mathrm{vec}\left( x_{ijk}, i\in \mathscr {O}_k, k\in \mathscr {K},j\in \mathscr {D}\right) ,\quad z =\mathrm{vec} \left( z_{ijk}, i\in \mathscr {O}_k, k\in \mathscr {K},j\in \mathscr {D}\right) . \end{aligned}$$

It is easily seen that $x,z\in \mathbb {R}^m$, with $\;m=D\sum _{k=1}^KO_k$.

4.4 Objective function and constraints

The objective function of the uncertain optimization problem is of the form

$$\begin{aligned} f(x,y,z;b)=f_1(x)+f_2(x,y,z;b), \end{aligned}$$

(29)

where

$$\begin{aligned} f_1(x)=q \sum _{k=1}^{K}\sum _{i=1}^{O_k}\sum _{j=1}^D t_{ijk} x_{ijk} \end{aligned}$$

(30)

denotes the booking costs of the vehicles, while

$$\begin{aligned} f_2(x,y,z;b)= q\sum _{j=1}^D b_j\,y_j\! - \! \alpha q \!\sum _{k=1}^{K}\sum _{i=1}^{O_k}\!\sum _{j=1}^D t_{ijk}\! \left( x_{ijk}\! -\! z_{ijk} \right) , \end{aligned}$$

(31)

represents the cost of recourse actions, consisting of buying good from external sources ($q y_j$) and canceling unwanted vehicles. We note that $f_1$ involves only deterministic parameters and nonadjustable, or first stage decision variables, while $f_2$ also involves uncertain or stochastic parameters as well as adjustable or second stage decision variables.

We have the following constraints for our optimization problem. Constraint

$$\begin{aligned} \mathscr {C}_1(x): \quad q \sum _{k=1}^{K}\sum _{i=1}^{O_k} x_{ijk} \le g_j,\quad j \in \mathscr {D}, \end{aligned}$$

(32)

guarantees that for each destination $j\in \mathscr {D}$ the number of booked vehicles does not exceed $g_j/q$ inducing thus an upper bound on the total number of vehicles. We impose the constraint

$$\begin{aligned} \mathscr {C}_2(z): \quad r_k \le q \sum _{i\in O_k}\sum _{j=1}^D z_{ijk} \le v_k ,\quad k \in \mathscr {K}, \end{aligned}$$

(33)

to ensures that the number of vehicles serving supplier k does not exceed the production capacity $v_{k}$ of supplier $k\in \mathscr {K}$ and satisfies the lowest requirement capacity $r_k$ established in the contract. In order to ensure that the j-customer’s demand is satisfied we also impose the following constraint

$$\begin{aligned} \mathscr {C}_3(y,z;d): \quad l_j^{0} + q \left( \sum _{k=1}^{K}\sum _{i=1}^{O_k} z_{ijk} + y_j \right) - d_j \ge 0, \quad j \in \mathscr {D}. \end{aligned}$$

(34)

The inequality constraint

$$\begin{aligned} z\le x, \end{aligned}$$

(35)

guarantees that the number of vehicles actually used is at most equal to the number booked in advance. We will always impose nonnegativity constraints on the vectors y, x, z,

$$\begin{aligned} y\ge 0,\; x\ge 0,\;z\ge 0, \end{aligned}$$

(36)

and in some cases integrality constraints on the vectors x and z, i.e.,

$$\begin{aligned} x \in \mathbb {N}^m,\;\;z \in \mathbb {N}^m, \end{aligned}$$

(37)

where $\mathbb {N}$ is the set of natural numbers.

If the vectors b and d were known the optimization problem presented above would be a simple linear programming problem. However, in our application b and d are uncertain. In the next section we will deal with this problem by using a stochastic programming model and several robust optimization models.

5 Models for the supply planning problem under uncertainty

5.1 A two stage stochastic optimization model

In this section we introduce a two-stage stochastic optimization model for the problem described above. Our approach is based on a set of scenarios

$$\begin{aligned} \mathscr {S} = \{s:s=1,\ldots ,S\}, \end{aligned}$$

and the following parameters and variables related to it:

$P^s$,:

probability of scenario $s\in \mathscr {S}$;

$d_{j}^s$,:

demand of customer j at scenario $s\in \mathscr {S}$;

$b_{j}^s$,:

buying cost from external sources for customer j at scenario $s\in \mathscr {S}$;

$z_{ijk}^s$,:

number of vehicles actually used from supplier $i\in \mathscr {O}_k$, $k\in \mathscr {K}$ to plant $j\in \mathscr {D}$,

at scenario $s\in \mathscr {S}$ (second stage decision variables);

$y_j^s$,:

volume of product to purchase from an external source normalized by q,

for plant $j\in \mathscr {D}$, at scenario $s\in \mathscr {S}$ (second stage decision variables).

As in Sect. 4.3 we introduce the vectors

$$\begin{aligned}&d^s=\left( d_j^s\right) _{j\in \mathscr {D}},\quad b^s=\left( b_j^s\right) _{j\in \mathscr {D}},\quad y^s=\left( y_j\right) _{j\in \mathscr {D}},\quad z^s = \left( z_{ijk}^s\right) _{ i\in \mathscr {O}_k, k\in \mathscr {K},j\in \mathscr {D}}. \end{aligned}$$

In the two-stage (one-period) case, we get the following mixed-integer stochastic programming model with recourse:

$$\begin{aligned} \text{ SP }&\min _{x,\{y^s,z^s\}_{s\in \mathscr {S}}}\; f_1(x)+ \sum _{s=1}^{S}P^s\left( f_2(x,y^s,z^s,b^s)\right) \end{aligned}$$

(38)

$$\begin{aligned}&s.t. \quad&\mathscr {C}_1(x),\;\; \mathscr {C}_2(z^s),\;\mathscr {C}_3(y^s,z^s;d^s),\; s\in \mathscr {S},\end{aligned}$$

(39)

$$\begin{aligned}&x\in \mathbb {N}^m,\;\;z^s\in \mathbb {N}^m,\; z^s\le x,\;y^s\ge 0,\; s\in \mathscr {S}. \end{aligned}$$

(40)

From now on we will refer to problem (38)–(40) as the two-stage stochastic programming problem (SP) for the supply planning problem.

5.2 Robust optimization models

In this section we introduce several robust formulations (RO) for the problem described above. These formulations are of particular interest in the case it is impossible, or not practical, to give reasonable estimates of probability distributions for the random parameters given by the demand of a certain good at factories and the cost of buying from external sources. Moreover, some LP-relaxations of RO formulations can be solved in polynomial time and have theoretical guarantees for the quality of the solution none of which is true for the SP formulations.

We consider different selections of the uncertainty set for the objective function and constraints involving the uncertain demands and buying costs. More precisely we assume that $b\in \mathscr {U}_b$ and $d\in \mathscr {U}_d$ for some uncertainty sets $\mathscr {U}_b\subset \mathbb {R}^{D}$ and $\mathscr {U}_d\subset \mathbb {R}^{D}$. For any such uncertainty sets the robust optimization formulation of our problem becomes

$$\begin{aligned} \text{ RO }&\min _{w,x,y,z}\; w \end{aligned}$$

(41)

$$\begin{aligned}&\text { s.t. }\;&w \ge f(x,y,z;b),\;\forall b\in \mathscr {U}_{b} \end{aligned}$$

(42)

$$\begin{aligned}&\mathscr {C}_1(x), \mathscr {C}_2(z), \mathscr {C}_3(y,z;d), \;\forall d\in \mathscr {U}_{d}\end{aligned}$$

(43)

$$\begin{aligned}&x\in \mathbb {N}^m,\;\;z\in \mathbb {N}^m,\; z\le x,\;y\ge 0, \end{aligned}$$

(44)

where the auxiliary variable w has been introduced.

5.2.1 Box uncertainty

We assume that the cost vector b belongs to the uncertainty set

$$\begin{aligned} \mathscr {U}_{b, box,L} = \left\{ \bar{b}+\sum _{\ell =1}^L\zeta _\ell b^\ell \;:\; \zeta =[\zeta _1;\ldots ;\zeta _L]\in \mathbb {R}^L,\, \Vert \zeta \Vert _{\infty }\le 1\right\} , \end{aligned}$$

(45)

where $b^1,\ldots ,b^L$ are vectors representing basic perturbations of the average vector cost $\bar{b}$, which is considered fixed. If we choose $L=D$ and the perturbation vectors

$$\begin{aligned} b^\ell =\rho _2F_\ell e^\ell ,\quad \ell =1,\ldots ,D, \end{aligned}$$

(46)

where $e^\ell$ is the $\ell$-th vector from the standard basis of $\mathbb {R}^D$ then $y^Tb^\ell =\rho _2F_\ell y_\ell$, with the positive number $F_\ell$ representing the uncertainty scale and $\rho _2>0$ the uncertainty level.

With the choice (46) the uncertainty set (45) coincides with the simple box

$$\begin{aligned} \mathscr {U}_{b, box} = \left\{ b\in \mathbb {R}^{D}: |b_j - \bar{b}_j|\le \rho _2 F_{j}, \ j\in \mathscr {D}\right\} . \end{aligned}$$

(47)

Of course, for other choices of the perturbation vectors we get different results.

Similarly, we assume that the demand vector d belongs to an uncertainty set of the form

$$\begin{aligned} \mathscr {U}_{d, box,L} = \left\{ \bar{d}+\sum _{\ell =1}^L\zeta _\ell \, d^\ell \;:\; \zeta =[\zeta _1;\ldots ;\zeta _L]\in \mathbb {R}^L,\, \Vert \zeta \Vert _{\infty }\le 1\right\} , \end{aligned}$$

(48)

for given perturbation vectors $d^1,\ldots ,d^L$. As above, it is easily seen that with the choice

$$\begin{aligned} L=D,\quad d^\ell =\rho _1G_\ell e^\ell ,\; \ell =1,\ldots ,D, \end{aligned}$$

(49)

the uncertainty set $\mathscr {U}_{d, box,L}$ reduces to the simple box

$$\begin{aligned} \mathscr {U}_{d, box} = \left\{ d\in \mathbb {R}^{D}: |d_j - \bar{d}_j|\le \rho _1 G_{j}, \ j\in \mathscr {D}\right\} . \end{aligned}$$

(50)

We clearly have $\max _{d\in \mathscr {U}_{d, box}}d_j=\bar{d}_j+\rho _1 G_{j}$. Using the uncertainty sets (47) and (50) for the uncertain vectors b and d, and considering the vector $G=\left( G_j\right) _{j\in \mathscr {D}}$, the robust formulation (41)–(44) of our problem can be written as the following linear mixed-integer problem:

$$\begin{aligned} \text{ RO-box }&\min _{w,x,y,z}\; w \end{aligned}$$

(51)

$$\begin{aligned}&\text { s.t. }\;&w - f(x,y,z;\bar{b})\ge \sum _{j=1}^D q \rho _2 F_j y_j \end{aligned}$$

(52)

$$\begin{aligned}&\mathscr {C}_1(x), \mathscr {C}_2(z), \mathscr {C}_3(y,z;\bar{d}+\rho _1G),\end{aligned}$$

(53)

$$\begin{aligned}&x\in \mathbb {N}^m,\;\;z\in \mathbb {N}^m,\; z\le x,\;y\ge 0, \end{aligned}$$

(54)

We note that the above model is very conservative. Indeed let us assume that

$$\begin{aligned} \zeta _1,\ldots ,\zeta _L:\text{ zero } \text{ mean } \text{ independent } \text{ random } \text{ variables } \text{ in } \text{ the } \text{ interval } [-1,1] , \end{aligned}$$

(55)

and let us consider the random vectors

$$\begin{aligned} b=b(\zeta )=\bar{b}+\sum _{\ell =1}^D\zeta _\ell \, b^\ell ,\quad d=d(\zeta )=\bar{d}+\sum _{\ell =1}^D\zeta _\ell \, d^\ell , \end{aligned}$$

(56)

where the perturbation vectors $b^\ell$ and $d^\ell$ are given by (46) and (49) respectively. Consider a feasible solution of the RO problem (51)-(54). Then

$$\begin{aligned} {\text{ Prob }}_{\zeta \sim P}\left\{ \zeta : \,w \ge f(x,y,z,b(\zeta ))\right\} \!=\!1, \end{aligned}$$

(57)

and

$$\begin{aligned} {\text{ Prob }}_{\zeta \sim P}\left\{ \zeta \, : \,\mathscr {C}_3(y,z,d(\zeta ))\right\} =1 , \end{aligned}$$

(58)

for any probability distribution P that is compatible with (55). This certitude of constraints satisfaction will result in a high cost for the optimal solution of the RO problem (51)–(54).

5.2.2 Box-ellipsoidal uncertainty

In this subsection we study the case were the uncertainty set for the buying costs is given by

$$\begin{aligned} \mathscr {U}_{b,ell} = \left\{ \bar{b}+\sum _{\ell =1}^L\zeta _\ell \, b^\ell \;:\; \zeta =[\zeta _1;\ldots ;\zeta _L]\in \mathbb {R}^L,\, \Vert \zeta \Vert _{2}\le \Omega \right\} , \end{aligned}$$

(59)

and the uncertainty set for the demand vector d is the box (50).

Using the Cauchy–Schwarz inequality, we obtain, for a given y

$$\begin{aligned} \max _{b\in \mathscr {U}_{b,ell}} y^T b=y^T\bar{b}+\max _{\Vert \zeta \Vert _2\le \Omega }\sum _{\ell =1}^L\zeta _\ell (y^T b^\ell )=y^T\bar{b}+ \Omega \sqrt{\sum _{l=1}^L (y^T b^\ell )^2}\quad \ . \end{aligned}$$

(60)

By choosing the perturbation vectors as in (46) we obtain the following RO model with box and ellipsoidal uncertainty set:

$$\begin{aligned} \text{ RO-ell }&\min _{w,x,y,z}\; w \end{aligned}$$

(61)

$$\begin{aligned}&\text { s.t. }\;&w - f(x,y,z;\bar{b})\ge \Omega \cdot \sqrt{\sum _{j=1}^D (q \rho _2 F_j y_j)^2} \end{aligned}$$

(62)

$$\begin{aligned}&\mathscr {C}_1(x), \mathscr {C}_2(z), \mathscr {C}_3(y,z;\bar{d}+\rho _1G),\end{aligned}$$

(63)

$$\begin{aligned}&x\in \mathbb {N}^m,\;\;z\in \mathbb {N}^m,\; z\le x,\;y\ge 0. \end{aligned}$$

(64)

The nonlinear constraint (62) is a second order cone constraint, so that the above optimization problems is a SOCP. Notice that if we relax the integrality constraints on x and z, the SOCP problem can be solved in polynomial time.

Consider again the random vectors $b(\zeta )$ and $d(\zeta )$ from (56). By virtue of Proposition 1 it follows that for any feasible solution of the RO problem (61)–(64) we have

$$\begin{aligned} {\text{ Prob }}_{\zeta \sim P}\left\{ \zeta \; : \; w \ge f(x,y,z;b(\zeta )) \right\} \ge 1-e^{-\frac{\Omega ^2}{2}} , \end{aligned}$$

(65)

for all probability distributions P that are compatible with (55). Since we are using the same box uncertainty for the demand, (58) is also satisfied. From the Cauchy-Schwarz inequality we have

$$\begin{aligned} \sum _{j=1}^D q \rho _2 F_j y_j\le \sqrt{D}\sqrt{\sum _{j=1}^D (q \rho _2 F_j y_j)^2}. \end{aligned}$$

(66)

If follows that if $\Omega \ge \sqrt{D}$ then for any feasible solution of the RO problem (61)–(64) we have the stronger probability result (57). This certitude of constraint satisfaction will result in a high cost for the optimal solution of the RO problem (61)–(64).

5.2.3 Adjustable robust optimization

In the robust optimization models considered in Sects. 5.2.1 and 5.2.2, all the variables are treated in the same way, while in the two-stage stochastic programming model the variables $x_{ijk}$ are considered first stage decision variables and the variables $y_j$ and $z_{ijk}$ are considered second stage (recourse) variables. This means that the variables $x_{ijk}$ are to be determined “here and now”, before the actual data “reveals itself”. On the other hand, once the uncertain data are known the variables $y_j$, $z_{ijk}$ should be able to adjust themselves by means of some decision rules $Y_j(\cdot )$ and $Z_{ijk}(\cdot )$. Therefore the decision variables $x_{ijk}$ are called nonadjustable variables while the decision variables $y_j$ and $z_{ijk}$ are called adjustable variables. In the following we relax the integrality in all the decision variables and we assume that decision rules $Y_j(\cdot )$ and $Z_{ijk}(\cdot )$ are affine function of their arguments. In the case with integer adjustable variables more subtle approaches are needed (e.g. Bertsimas and Georghiou 2014, 2015; Hanasusanto et al. 2015).

In developing an adjustable robust optimization model for our problem we will follow the simple model described in Ben-tal et al. (2009), where, however, it is assumed that all the coefficients of the adjustable variables are certain. This is not the case for our problem where the coefficients $b_j$ of the adjustable variables $y_j$ are uncertain. We will circumvent this difficulty by assuming as before that the cost vector b belongs to the ellipsoidal uncertainty set $\mathscr {U}_{b,ell}$ (59). We have seen that in this case, with the choice (46), our cost constraint can be written under the form (62). This is no longer a linear constraint, but a second order cone constraint. On the other hand we assume that the demand vector d belongs to the scenario-generated uncertainty set

$$\begin{aligned} \mathscr {U}_{d,\hat{\Delta } } = \left\{ \sum _{s=1}^S\lambda _s\hat{d}^s\; : \; \lambda \in \mathscr {L}\right\} , \end{aligned}$$

(67)

where,

$$\begin{aligned} \mathscr {L}=\left\{ \lambda =[\lambda _1;\ldots ;\lambda _S]\in \mathbb {R}^S\; : \; \lambda _1\ge 0, \ldots ,\lambda _S\ge 0,\;\sum _{s=1}^S\lambda _s=1\right\} , \end{aligned}$$

(68)

and $\hat{\Delta }$ is a given set of scenarios

$$\begin{aligned} \hat{\Delta }=\left\{ \hat{d}^1,\hat{d}^2,\ldots ,\hat{d}^S\right\} . \end{aligned}$$

(69)

In our applications $\hat{\Delta }$ is obtained from historical data.

Let us denote by $u=x$ the vector composed of all “here and now” decision variables $x_{ijk}$, and by $v=[y;z]$ the vector composed of all adjustable decision variables $y_j$, $z_{ijk}$. We consider also the vector of decision rules

$$\begin{aligned} V(\cdot )=\left[ Y_1(\cdot );\ldots ;Y_D(\cdot );\text{ vec }\left( Z_{ijk}(\cdot ), i \in \mathscr {O}_k,\, k \in \mathscr {K},\, j \in \mathscr {D}\right) \,\right] . \end{aligned}$$

Since decision rules $Y_j(\cdot )$ and $Z_{ijk}(\cdot )$ are assumed to be affine, so is $V(\cdot )$. The deterministic constraints of our problem are:

$$\begin{aligned} \mathscr {C}(u,v):\quad \mathscr {C}_1(x),\; \mathscr {C}_2(z),\;z\le x,\;x\ge 0,\;y\ge 0,\;z\ge 0, \end{aligned}$$

(70)

while our uncertain constraints are given by:

$$\begin{aligned} \widetilde{\mathscr {C}}(u,v,w;b,d):\quad w \ge f(x,y,z;b),\; \mathscr {C}_3(y,z;d). \end{aligned}$$

(71)

With the above notation our problem can be written as:

$$\begin{aligned} \mathscr {R}=\min _{w,u,v}\left\{ w\; :\; \mathscr {C}(u,v), \widetilde{\mathscr {C}}(u,v,w;b,d), \forall b\in \mathscr {U}_{b,ell} ,\forall d\in \mathscr {U}_{d,\hat{\Delta } }\right\} . \end{aligned}$$

For the choice (46) the infinite set of constraints $w \ge f(x,y,z;b), \forall b\in \mathscr {U}_{b,ell}$ reduces to the deterministic single second-order cone constraint (62). In this case the uncertain constraints of our problem become

$$\begin{aligned} \widehat{\mathscr {C}}(u,v,w;d):\quad w - f(x,y,z;\bar{b})\ge \Omega \sqrt{\sum _{j=1}^D (q \rho _2 F_j y_j)^2 },\;\; \mathscr {C}_3(y,z;d). \end{aligned}$$

(72)

Therefore, our problem can be written equivalently, (see (17)) as:

$$\begin{aligned} \mathscr {R}:\quad \min _{w,u,v}\left\{ w\; :\; \mathscr {C}(u,v),\widehat{\mathscr {C}}(u,v,w;d),\; \forall d\in \mathscr {U}_{d,\hat{\Delta } }\right\} . \end{aligned}$$

(73)

According to (16) the adjustable version of this problem is

$$\begin{aligned} \mathscr {A}: \quad \min _{w,u,V(\cdot )}\left\{ w\; :\; \mathscr {C}(u,V(d)), \widehat{\mathscr {C}}(u,V(d),w;d) ,\forall d\in \mathscr {U}_{d,\hat{\Delta } }\right\} , \end{aligned}$$

(74)

where the minimum is taken for all decision rules $V(\cdot )$ that are affine functions of their arguments. According to Theorem 1 we show below that this adjustable version is equivalent to the following tractable optimization problem (see (18))

$$\begin{aligned} \mathscr {Q}: \quad \min _{w,u,\left\{ v^s \right\} _1^S}\left\{ w\; :\; \mathscr {C}(u,v^s), \widehat{\mathscr {C}}(u,v^s,w;\hat{d}^s),\; s=1,\ldots ,S \right\} . \end{aligned}$$

(75)

The equivalence is understood in the sense that the optimal values of $\mathscr {A}$ and $\mathscr {Q}$ are equal and that any feasible solution of $\mathscr {Q}$ can be augmented to a feasible solution of $\mathscr {A}$. More specifically let $\hat{w},\hat{u},\left\{ \hat{v}^s \right\} _1^S$ be a feasible solution of $\mathscr {Q}$ and consider a vector $d\in \mathscr {U}_{d,\hat{\Delta } }$. Then there is a vector $\lambda (d)=[\lambda _1(d);\ldots ;\lambda _S(d)]\in \mathscr {L}$ such that

$$\begin{aligned} d=\sum _{s=1}^S\lambda _s(d)\hat{d}^s, \end{aligned}$$

(76)

and the adjustable variables are defined by the decision rule

$$\begin{aligned} v=\hat{V}(d):=\sum _{s=1}^S\lambda _s(d)\hat{v}^s. \end{aligned}$$

(77)

The feasibility of $\hat{w},\hat{u},\left\{ \hat{v}^s \right\} _1^S$ means that the following constraints are satisfied

$$\begin{aligned} \mathscr {C}(\hat{u},\hat{v}^s), \widehat{\mathscr {C}}(\hat{u},\hat{v}^s,\hat{w};\hat{d}^s),\quad s=1,\ldots ,S. \end{aligned}$$

(78)

From (32), (33) and (70) it follows that the constraints $\mathscr {C}(u,v)$ are linear inequality constraints, while $\widehat{\mathscr {C}}(u,v,w;d)$ are convex constraints, because the left hand side of the inequality in (72) is linear while the right-hand-side can be written as $\Vert H y\Vert$ where H is the diagonal matrix with entries $\Omega q \rho _2 F_j$. Therefore if (78) is satisfied, then $\hat{w},\hat{u},\hat{V}(\cdot )$ is feasible for $\mathscr {A}$. In particular, this proves that the optimal solution of $\mathscr {A}$ is less than or equal to the optimal solution of $\mathscr {Q}$. To prove the reverse inequality, we remark that if $(w,u,V(\cdot ))$ is feasible for $\mathscr {A}$, then $w,u,\left\{ V(\hat{d}^s) \right\} _1^S$ is clearly feasible for $\mathscr {Q}$.

In conclusion, in order to solve our adjustable robust optimization model we first find the optimal solution

$$\begin{aligned} x^*=\left( x^*_{ijk}\right) ,\;y^{*\,s}=\left( y^{*\,s}_j\right) ,\;z^{*\,s}= \left( z^{*\,s}_{ijk}\right) , \quad s \in \mathscr {S} \end{aligned}$$

(79)

of the tractable second order cone optimization problem

$$\begin{aligned} \text{ trSOCP }&\min _{x,\{y^s,z^s\}_{s\in \mathscr {S}}}\; \quad w \end{aligned}$$

(80)

$$\begin{aligned}&s.t. \quad&w - f(x,y^s,z^s;\bar{b})\ge \Omega \cdot \sqrt{\sum _{j=1}^D (q \rho _2 F_j y_j^s)^2},\; s \in \mathscr {S}, \end{aligned}$$

(81)

$$\begin{aligned}&\mathscr {C}_1(x),\;\; \mathscr {C}_2(z^s),\;\mathscr {C}_3(y^s,z^s;\hat{d}^s),\; s\in \mathscr {S},\end{aligned}$$

(82)

$$\begin{aligned}&0\le z^s\le x,\;y^s\ge 0,\; s\in \mathscr {S}. \end{aligned}$$

(83)

When the uncertain demand d reveals itself we try to find a vector $\lambda (d)=[\lambda _1(d);\ldots ;\lambda _S(d)]\in \mathscr {L}$ satisfying (76) by solving the following optimization problem in $\lambda$

$$\begin{aligned} \min _{\lambda \in \mathscr {L}}\;\varphi (\lambda ):=\min _{\lambda \in \mathscr {L}}\sum _{j=1}^D\left( d_j-\sum _{s=1}^S\lambda _s\hat{d}^s_j\right) ^2\, . \end{aligned}$$

(84)

The optimal value of the objective function is equal to zero, i.e., $\varphi (\lambda (d))=0$, if and only if $d\in \mathscr {U}_{d,\hat{\Delta } }$. In this case the adjustable variables are given by

$$\begin{aligned} y_j^*=\sum _{s=1}^S\lambda _s(d)y^{*\,s}_j, \; z^{*}_{ijk}=\sum _{s=1}^S\lambda _s(d) z^{*\,s}_{ijk} \quad i \in \mathscr {O}_k,\, k \in \mathscr {K},\, j \in \mathscr {D}. \end{aligned}$$

(85)

From the above considerations it follows that

$$\begin{aligned} x^*_{ijk},\; y^{*}_j,\;z^{*}_{ijk}, \quad i \in \mathscr {O}_k,\, k \in \mathscr {K},\, j \in \mathscr {D}, \end{aligned}$$

(86)

is an optimal solution of the robust adjustable optimization problem (74). This is no longer the case when $\varphi (\lambda (d))>0$. As noted in Sect. 3, the scenario-generated uncertainty set $\mathscr {U}_{d,\hat{\Delta } }$ from (67) is usually “too small” to be of much interest. Nevertheless, as shown in the next section the values

$$\begin{aligned} x^*_{ijk},\quad i \in \mathscr {O}_k,\, k \in \mathscr {K},\, j \in \mathscr {D}, \end{aligned}$$

(87)

could be used to find a solution of our supply planning problem even when $d\notin \mathscr {U}_{d,\hat{\Delta } }$.

5.2.4 Scenario based framework for the supply planning problem under uncertainty

In this subsection we compare the performance of the various methods in the scenario based framework described in Sect. 3. For our specific application those methods become:

• $\mathbf {M_1}$ is the stochastic optimization problem SP (38)–(40);

• $\mathbf {M_2}$ is the RO problem with box constraints RO-box (51)–(54);

• $\mathbf {M_3}$ is the RO problem with ellipsoidal constraints RO-ell (61)–(64);

• $\mathbf {M_4}$ is the second order cone optimization problem trSOCP (80)–(83).

As in (69), let $\hat{\Delta } = \left\{ \hat{d}^1,\hat{d}^2,\ldots ,\hat{d}^{S}\right\}$ be a given set of demand scenarios of dimension D from historical data. We consider a set of indices (22). For each $\tau =\bar{S},\ldots ,S-1$ we compute the quantities $\bar{d}^{\tau }=\frac{1}{\tau }\sum _{s=1}^{\tau } \hat{d}^s,\quad \rho _1^{\tau } G_j^{\tau } = \max _{s=1,\ldots ,\tau } |\hat{d}_j^s -\bar{d}_j^{\tau }|, \; j\in \mathscr {D}.$

If we do not have historical data for the cost vectors, but we know a D-dimensional vector $\bar{b}$ of average costs, we can generate a set of vectors $\hat{B}=\left\{ \hat{b}^1,\hat{b}^2,\ldots ,\hat{b}^{S}\right\} ,$ with components $\hat{b}_j^s$ obtained by sampling from a uniform distribution in the interval $\left[ \bar{b}_j - \sigma \cdot \bar{b}_j ,\bar{b}_j + \sigma \cdot \bar{b}_j \right]$ with a given deviation level of $\sigma$. For each $\tau =\bar{S},\ldots ,S-1$ we compute $\rho _2^{\tau } F_j^{\tau } = \max _{s=1,\ldots ,\tau } |\hat{b}_j^s -\bar{b}_j^{\tau }|, \; j\in \mathscr {D}.$ For each $\tau =\bar{S},\ldots ,S-1$ and for each of the methods $\mathbf {M_1},\ldots , \mathbf {M_4}$ described in Sect. 3 we find the optimal solution of the corresponding optimization problem using only the information contained in the vectors

$$\begin{aligned} \hat{d}^1,\hat{d}^2,\ldots ,\hat{d}^{\tau },\quad \hat{b}^1,\hat{b}^2,\ldots ,\hat{b}^{\tau }. \end{aligned}$$

(88)

From this optimal solution we obtain the nonadjustable decision variables $x^*$. They are determined by using only the information contained in (88). Assume now that the vectors $\hat{d}^{\tau +1},\hat{b}^{\tau +1}$ become available. Then we can solve the optimization problem

$$\begin{aligned}&\min _{y,z} f\left( x^*,y,z;\hat{b}^{\tau +1}\right) \end{aligned}$$

(89)

$$\begin{aligned}&\text { s.t. }\;&\mathscr {C}_2(z), \mathscr {C}_3(y,z;\hat{d}^{\tau +1}),\end{aligned}$$

(90)

$$\begin{aligned}&z\in \mathbb {N}^m,\; z\le x^*,\;y\ge 0. \end{aligned}$$

(91)

to obtain the adjustable variables $y^{*}, z^{*}$.

We will also consider method $\mathbf {M_5}$ which now consists in the following steps:

• $\mathbf {M_5}$:

  • (a) Solve the optimization problem (80)–(83) using only the information (88);

  • (b) Solve the optimization problem (84) with $S=\tau$ and $d=\hat{d}^{\tau +1}$;

  • (c) If $\varphi (\lambda (d))=0$, define the adjustable variables as in (85).

6 Numerical results

In this section we discuss numerical results for stochastic and robust modelling approaches applied to the supply planning problem described in Sects. 4 and 5. The instance considered comes from a real case of gypsum replenishment in Italy provided by the primary Italian cement producer. The logistic system is composed of 24 suppliers with multiple plants and 15 destinations. The models aim to find, for each plant of the 24 suppliers, the number of vehicles to be booked for replenishing gypsum in order to minimize the total cost.

Deterministic and stochastic parameters values for the problem are reported in Tables 11, 12 and 13 in the Appendix. Table 11 lists the set of suppliers $\mathscr {K}$ and the set of their plants $\mathscr {O}_k, \ k \in \mathscr {K}$. The list of destinations (cement factories) are shown in Table 12 with relative emergency costs, unloading capacities and variation of demand $\rho _1 G_j$, and buying costs $\rho _2 F_j$, $j\in \mathscr {D}$.

Table 13 refers to the minimum and maximum requirement capacity of supplier $k \in \mathscr {K}$. We suppose to have an initial inventory level $l_j^0=0$ at all the destinations $j\in \mathscr {D}$ and to use vehicles with fixed capacity $q=31$ tons. The cancellation fee $\alpha$ is fixed to the value of 0.7.

Equiprobable scenarios of gypsum demand $\hat{\Delta } = \left\{ \hat{d}^1,\hat{d}^2,\ldots ,\hat{d}^{S}\right\}$ are built on historical data, using all the weekly values in March, April, May and June of the years 2011, 2012 and 2013 for a total number of $S=48$ realizations. Having no historical data for the buying costs, equiprobable scenarios $\hat{B}=\left\{ \hat{b}^1,\hat{b}^2,\ldots ,\hat{b}^{S}\right\}$ have been generated sampling from a uniform distribution in the interval $\left[ \bar{b}_j - \sigma \cdot \bar{b}_j ,\bar{b}_j + \sigma \cdot \bar{b}_j \right]$ with a given deviation level of $\sigma =20\%$. In order to make a fair comparison between RO and SP methodologies, the same deviation level is used also for the RO methodology.

All the models (SP and RO) are modeled in AMPL and solved using the CPLEX 12.5.1.0. solver or MOSEK 7.1.0.58 solver for RO model with ellipsoidal constraint. The computations have been performed on a 64-bit machine with 12 GB of RAM and a 2.90 GHz Intel i7 processor. Summary statistics of the adjusted problems derived for our test-case are reported in Table 1.

Table 1 Summary statistics of the solution approaches (SP versus static RO)

Table 2 Optimal first-stage solutions of the stochastic model SP with mixed-integer variables

First-stage solutions of the stochastic mixed-integer model (SP) are reported in Table 2. Results show that the demand of all 15 destinations is satisfied by ordering vehicles from the set of suppliers for a total of 141 vehicles and a total cost of 107,244.67. The SP model forces the company to buy from external sources only in high demand scenarios as recourse action.

Similar results are obtained also for larger number of scenarios. Figure 1 shows the in-sample stability of the optimal SP function value for an increasing number of scenarios (Kaut and Wallace 2007). For $S\ge 200$ the stability is reached, where the scenarios have been generated by a uniform distribution in the range provided by the minimum and maximum values from historical data.

Fig. 1

In-sample stability of SP model with all continuous variables

Before to proceed with the comparison between SP and RO models, we analyze the advantage of having the information about future demand and buying cost. This is provided by the well-known Expected Value of Perfect Information EVPI, (Birge and Louveaux 2011; Maggioni et al. 2014, 2016):

$$\begin{aligned} EVPI = SP - WS = 107{,}244.67 - 84{,}472.21 = 22{,}772.46 \end{aligned}$$

(92)

given by the difference between the stochastic cost and the wait-and-see cost WS. Figure 2 shows the objective function values of the deterministic problems solved separately over each scenario $(\hat{d}^s,\hat{b}^s)\in \hat{\Delta } \times \hat{B}.$

Fig. 2

Optimal objective function values of deterministic programs with mixed-integer variables with full knowledge of demand and buying cost. The costs refer to the 48 scenarios obtained from historical data

Since the gypsum demand is highly affected by the economic conditions of the public and private medium and large-scale construction sector, a reliable forecast and reasonable estimates of probability distributions are difficult to obtain. This is the main reason that leads us to consider also robust optimization approaches. In the following we consider:

• static approaches with uncertainty parameters belonging respectively to box, ellipsoidal uncertainty sets or mixture of them;

• dynamic approaches, via the concept of tractable adjustable robust counterpart and scenario based framework.

Table 3 Optimal normalized volume $y_{j}$ for destination plant $j\in \mathscr {D}$ for the static robust mixed-integer optimization model with box constraints (column 2), of the corresponding continuous version (column 3) and box-ellipsoidal optimization model with $\Omega =2.75$ (column 4)

We first consider the robust optimization model with box uncertainty, (51)–(54). Boxes for demand and buying cost are built in compliance with the 48 historical data used to generate SP scenarios. See again Table 12 for variation of demand $\rho _1 G_j$ and buying costs $\rho _2 F_j$, $j\in \mathscr {D}$.

The static RO-box approach is very conservative having a total cost about $365\%$ larger than the SP expected cost. Table 3 (column 2) reports the optimal solutions of the mixed-integer robust problem with box constraints given by the normalized volume $y_{j}$ for destination plant $j\in \mathscr {D}$, while Table 4 gives number of booked vehicles $x_{ijk}$ from plant $i\in \mathscr {O}_k$ of supplier k to destination $j\in \mathscr {D}$.

Table 4 Optimal solution of the RO-box model

Due to the upper bound constraint on the number of booked vehicles and largest demand to be satisfied, the model forces the company to buy from external sources. This happens for almost all the destinations, with exception of dest5 and dest13 where the demand is fully satisfied by the orders $x_{ijk}$. On the other hand, the demand of dest3, dest12 and dest15 are satisfied only by external orders $y_j>0$ with a consequent larger cost.

The choice of the box uncertainty set is preferable only if the feasibility of all the constraints is highly required which would be the case if the company prefers to keep the same contract with the suppliers (or 3PL) and still being immunized against every possible realization of random demand in the box.

One can try to use a different uncertainty set in order to get a less conservative outcome. We show the results obtained by using a box-ellipsoidal uncertainty set which, as mentioned in Sect. 5.2.2, requires the solution of a second-order cone program with integer constraints. The current MOSEK solver version 7.1.0.58 finds that the robust mixed-integer second-order cone formulation RO-ell described in Sect. 5.2.2 is infeasible. Although the problem may be feasible, MOSEK cannot find it. This is the main reason that made us relax the integrality constraints on $x_{ijk}$ and $z_{ijk}$ for all second-order cone formulations. To have a fair comparison we have then relaxed the integrality constraints in all the other formulations.

Total costs of the static RO-ell model are shown in Fig. 3 (dashed line) with the probability of satisfaction (dotted line) of the second order cone constraint (62) for increasing values of the parameter $0\le \Omega \le 3.873$ (see Proposition 1). Notice that the strongest probability satisfaction (57) is verified for $\Omega \ge \sqrt{15}=3.873$ since in the test-case considered the number of destinations is $D=15$. The results show that for $\Omega =0$, the total cost of the static RO-ell approach is 343,849.19, the same than the static RO-box model with average buying cost $\bar{b}_j$ and box constraint requirement for the demand $d_j$. As $\Omega$ increases to 2.75 the total cost reaches approximately the same value, 381,520.16, for the box model case with a probability of constraint satisfaction close to one. Notice that the optimal cost of the RO-ell model is only 114.74 lower than the box model, where the probability of constraint satisfaction is exactly one. On the other hand, the solution of the static RO-ell model with $\Omega =\sqrt{D}= 3.873$ is guaranteed to satisfy the second order cone constraint with probability one. This fact has been remarked at the end of Sect. 5.2.2. For $\Omega =\sqrt{D}= 3.873$ the ellipsoidal uncertainty set $\mathscr {U}_{b,ell}$, given by (59) and (46), includes the box uncertainty set $\mathscr {U}_{b, box}$ defined in (47). Therefore the static RO-ell gives a cost that is $13\,575$ larger than RO-box. CPU times are negligible (0.2028 CPU seconds) compared to the SP problem with 200 scenarios (114.13 CPU seconds).

Fig. 3

Total cost given by RO-ell with all continuous variables for increasing values of $\Omega$ (dashed line) and probability of satisfaction (dotted line) of constraint (62)

For a comparative analysis, Tables 6 and 3 (column 4) report the solution variables $x_{ijk}$ and $y_j$ in the case of the static box-ellipsoidal robust approach with $\Omega =2.75$ whereas Tables 5 and 3 (column 3) refer to the optimal solutions of the static box case with continuous variables. While the two approaches have approximately the same total costs, their solution strategies show some differences: the box-ellipsoidal solution does not make any order except for dest12, deciding to satisfy their maximum demand by external sources $y_{12}=22.10$. On the other side the box solution does not make any order both for dest3 and dest12, and buys from external sources. The box solution tries to satisfy the demand of dest1, dest5, dest6, dest7, dest8, dest10, and dest13 only by booking vehicles $x_{ijk}$ from the set of suppliers while the box-ellipsoidal solution requires for all the destinations, with exception of dest13, to buy from external sources.

Table 5 Optimal solution given by RO-box with all continuous variables

Table 6 Optimal solution of RO-ell with $\Omega =2.75$ and all continuous variables

Fig. 4

Adjustable total costs $\mathbf {{cost}}_{\mathbf {1},\tau },\ldots ,\mathbf {{cost}}_{\mathbf {4},\tau }$ obtained by solving model (89)–(91) with all continuous variables using the nonadjustable decision variables $x_{ijk}^{*}$ given by methods $\mathbf {M_1},\ldots ,\mathbf {M_4}$, for an increasing value of $\tau =24,\ldots ,47$. Results are compared with the cost of the problem where a full information on the realization of vectors b and d is available ($\mathbf {{cost}}_{\tau }=WS_{\tau }$)

Table 7 Optimal value of the objective function (89) with the adjustable strategy where method $\mathbf {M_1},\ldots ,\mathbf {M_5}$ is used to determine the nonadjustable variables $x_{ijk}^{*}$

In order to make a fair comparison with the SP methodology, we compute total costs via the scenario based framework proposed in Sect. 5.2.3. Our methodology allows us to understand the cost saving of the SP approach when compared to RO, and to quantify the value of a more conservative strategy which does not require a negotiation with third-party providers every week, but keeps the same solution strategy for longer periods. For this purpose, we consider a subset $\bar{\mathscr {S}}=\left\{ 1,\ldots ,24\right\} \subset \mathscr {S}$ of scenarios from the 48 historical data. For each $\tau =24,\ldots ,47$ and for each method $\mathbf {M_1},\dots ,\mathbf {M_5}$, we compute nonadjustable decision variables $x_{ijk}^{*}$ using only the information contained in $\hat{d}^1,\hat{d}^2,\ldots ,\hat{d}^{\tau },\quad \hat{b}^1,\hat{b}^2,\ldots ,\hat{b}^{\tau }$. When vectors $\hat{d}^{\tau + 1},\hat{b}^{\tau +1}$ become available, we solve model (89)–(91) fixing the nonadjustable decision variables $x_{ijk}^{*}$ just obtained, allowing to determine the adjustable decision variables $y^{*}_j,z_{ijk}^{*}$. The adjustable total costs $\mathbf {{cost}}_{\mathbf {1},\tau },\ldots ,\mathbf {{cost}}_{\mathbf {5,\tau }}$ and $\mathbf {{cost}}_{\tau }$ are shown in Fig. 4 and results are listed in Table 7. Last line reports the aggregated cost $\mathbf {{cost}_{m}}$, $\mathbf {m}=\mathbf {1},\ldots ,\mathbf {5}$ over 24 weeks. The results provide an important information to the firm about the cost saving in case of SP or RO solution procedures are implemented in practice over 6 months: SP approach allows a saving of $35.04\%$ compared to RO-box, $22.10\%$ compared to RO-ell ($\Omega =2.75$) and $20.77\%$ compared to the computationally tractable problem trSOCP. Nevertheless, RO solutions are immunized over all realization of uncertain parameters allowing to the company to keep the same contract for longer periods without the necessity of a weekly negotiation and an adjustment of the plan when the booked vehicles are not sufficient. Only in case the observations of demands and costs in $\tau + 1$ are worse than their history up to $\tau$, should the RO solution strategy also be renegotiated. However this would be not the case when $(\hat{d}^{\tau + 1},\hat{b}^{\tau +1})$ corresponds to an extremely bad scenario: the results are shown in Table 8 where we can see the better performance of RO approaches with respect to SP allowing a saving of $3.32\%$.

On the other hand, the adjustable RO approach $\mathbf {{M}_{5}}$ is no longer implementable since $\varphi ^\tau \left( \lambda \left( \bar{d}^{\tau +1}\right) \right) >0$ and consequently $\mathbf {{cost}}_{\mathbf {5},\tau }=\infty$ for $\tau =24,\dots ,47$.

As expected the lowest cost is given by the wait-and see WS problem allowing a saving of $38.19\%$ compared to SP, since a full information on the realization of vectors b and d is available.

Table 8 Optimal value of the objective function (89) with the adjustable strategy where method $\mathbf {M_1},\ldots ,\mathbf {M_5}$ is used to determine the nonadjustable variables $x_{ijk}^{*}$ in case of worst scenario $(\hat{d}^{\tau + 1},\hat{b}^{\tau +1})=(\bar{d}_j + \gamma _j \cdot \bar{d}_j,\bar{b}_j + \sigma \cdot \bar{d}_j)$, $j\in \mathscr {D}$

Total CPU time, in seconds, spent in solving the optimization problems $\mathbf {M_m}$, $\mathbf {m}=\mathbf {1},\ldots ,\mathbf {5}$ and (89)–(91) including the possible infeasibility detection of the latter, are reported in Table 9. Results show the higher computational complexity of the SP approach $\mathbf {M_1}$ and the adjustable approaches $\mathbf {M_4}$ and $\mathbf {M_5}$ as compared to the robust box constrained problem $\mathbf {M_2}$ or the robust box-ellipsoidal constrained problem $\mathbf {M_3}$.

Table 9 Total CPU time, in seconds, spent in solving the optimization problems $\mathbf {M_m}$, $\mathbf {m}=\mathbf {1},\ldots ,\mathbf {5}$

Fig. 5

Adjustable total costs $\mathbf {{cost}}_{\mathbf {1},\tau },\ldots ,\mathbf {{cost}}_{\mathbf {4},\tau }$ obtained by solving model (89)–(91) using the nonadjustable decision variables $x_{ijk}^{*}$ respectively given by methods $\mathbf {M_1},\ldots ,\mathbf {M_4}$, for an increasing value of $\tau =24,\ldots ,47$. Results are averaged over 2000 simulations randomly generated by a Monte Carlo procedure

We finally validate the performance of the approaches $\mathbf {M_1},\ldots ,\mathbf {M_5}$ over 2000 simulations randomly generated by a Monte Carlo procedure. Uncertain buying cost values are obtained by sampling from a uniform distribution in the interval $\left[ \bar{b}_j - \sigma \cdot \bar{b}_j ,\bar{b}_j + \sigma \cdot \bar{b}_j \right] ,\ j\in \mathscr {D}$, with a given deviation level of $\sigma =20\%$. Uncertain demand values are obtained by sampling from a uniform distribution in the interval $\left[ \bar{d}_j - \gamma _j \cdot \bar{d}_j ,\bar{d}_j + \gamma _j \cdot \bar{d}_j \right] ,\ j\in \mathscr {D}$ with $\gamma _j=\max _{s=1,\ldots ,48} \hat{d}_j^s -\bar{d}_j, \; j\in \mathscr {D}$ (see Table 12). Total costs over 24 weeks over 2000 simulations are reported in Table 10 and shown in Fig. 5. The numerical results show that the SP approach allows a saving of $19.88\%$ compared to RO-box, $12.69\%$ compared to RO-ell and $11.07\%$ compared to computationally tractable robust formulation trSOCP. Again, the adjustable method $\mathbf {M_5}$ is not implementable.

Table 10 Total cost of optimization problems $\mathbf {M_m}$, $\mathbf {m}=\mathbf {1},\ldots ,\mathbf {5}$ and (89)–(91) over 24 weeks over 2000 simulations randomly generated by a Monte Carlo procedure

7 Conclusions

In this paper we have analyzed the effect of two modelling approaches, stochastic programming (SP) and robust optimization (RO) for a supply planning problem under uncertainty. The problem has been formulated and solved both via a two-stage stochastic programming and robust optimization models with different uncertainty sets.

The goal of SP is to compute the minimum expected cost based on the specific probability distribution of the uncertain parameters based on a set of scenarios.

For RO we have firstly considered static approaches with random parameters belonging to box or ellipsoidal uncertainty sets in compliance with the data used to generate scenarios for SP, and secondly dynamic approaches, via the concept of adjustable robust counterpart ARC.

The choice of the box uncertainty set is preferable only if the feasibility of all the constraints is highly required, but this certainty of constraint satisfaction results in a higher cost. A less conservative outcome has been obtained with a box-ellipsoidal uncertainty set that requires the solution of a second-order cone program SOCP. The main advantage of the considered RO formulations, is that they can be solved in polynomial time and theoretical guarantees for the quality of the solution are provided, which is not the case with the aforementioned SP formulation.

A scenario based framework methodology for a fair comparison between SP and RO has been proposed, which can be applied to any optimization problem affected by uncertainty.

The efficiency of the methodology has been illustrated for a supply planning problem to optimize vehicle-renting and transportation activities involving uncertainty on demands and buying costs for extra-vehicles. The methodology allows to understand what is the cost saving of the SP approach when compared to the RO approach and to quantify the value of a more conservative strategy which does not require a negotiation with suppliers or third-party providers every week.

Appendix

See Tables 11, 12 and 13.

Table 11 Set of suppliers $\mathscr {K}$ and set of their plants ${O}_k, \ k \in \mathscr {K}$

Table 12 List of destinations (cement factories) with relative expected emergency costs $\bar{b}_j$, maximum capacities which can be booked $g_j$, $j \in \mathscr {D}$ and values of deviation for defining the box constraints for demand (50) and buying cost (47)

Table 13 Minimum $r_k$ and average maximum $v_k$ requirement capacity of supplier $k \in \mathscr {K}$