A hybrid approach for uncertain multi-criteria bilevel programs with a supply chain competition application

Abstract

The goal of this paper is going to present a hybrid approach to solve multi-criteria bilevel optimization models with uncertain parameters in the objective functions. In reality, the player can not provide the weights to the objectives exactly. Since to assert the correct weight for objective is difficult, ambiguity is often not absent in the weights given by the player. Therefore, each player (leader or follower) usually has to choose a weight of his objective from a given set. Then, we proposed a robust optimization approach to copy with this situation, where each player obtains his strategy by minimizing his worst-case weighted sum objective over the given weight region. We note that the worst-case implies the maximization of the weights. The corresponding reformulation is presented with the different choice of weights. By an application in supply chain optimization with the consideration of both supply and demand uncertainties, the usefulness of the proposed method is shown. The comparison with the existed approach is also presented.

Keywords

Uncertain multi-criteria programs bilevel optimization robust Pareto supply chain

1 Introduction

Multi-criteria programs, which have multiple conflicting objectives, have been extensively studied [1 –3]. Since no unique solution which minimizes all objective functions simultaneously exists, we must decide which objective to improve. Hence the concept of optimality has to be replaced by the concept of Pareto optimality [4, 5]. Multi-criteria bilevel programs are an extension of bilevel programs with single objective and applied to model circumstances where players located at both upper and lower levels, take actions under multiple criteria consideration. Although it has many important applications in the real world, to efficiently solve the multi-criteria bilevel problem is difficult. This paper studies a special class of multi-criteria bilevel programs, i.e., multi-criteria bilevel optimization models with uncertain parameters in the objective functions. In reality, the player can not provide the weights to the objectives exactly. There may be ambiguity in the weights given by the player, as it is often not easy to decide relative weights for each objective. Therefore, in this paper, we suppose that the weights to the objectives are uncertain and are assumed to be attached to an convex and compact set. To deal with the weight uncertainty, a robust optimization approach is used.

Two classes of solution methods for multi-objective optimization problems are usually proposed. One is the iterative method by extending the iterative methods widely used in solving scalar optimization problems to the multi-objective setting [1, 3–5 , 1, 3–5]. At every iteration, this class of method has two features: (i) a descent direction is generated which guarantees a feasible solution that dominate the current point is computed; (ii) a line search is performed with the generated descent direction. The other one is the weighted approach, i.e., under consideration of the importance of objective a nonnegative weight is assigned. This method overcomes the shortcomings of multi-objective problems, i.e., it is difficult to make all objective to be optimal simultaneously. This method equivalently reduces the primitive multi-objective problem to a scalar-valued problem through optimizing a weighted sum objective [6]. So a weighted Pareto optimal point can be obtained. But there have some short comings of the current weight approach. First, the transformed scalar optimization problem may be difficult to solve [7, 8]. Second, in the real-world application the player has to choose the weight which canąŕt be known before. The existence of ambiguity in the choice of the weight makes it difficult to find relative weights for each objective. Besides as shown in the literature, the same decision-maker may rely on the elicitation methods to give the value of relative weights in the processing of solve multi-objective optimization [9]. In the bilevel setting with uncertainties considered in this paper, it is more difficult for the leader to exactly assume the weights of the follower’s objectives. Hence, some new method should be presented to copy with this setting.

This paper presents a new method, i.e., robust weighted method, to copy with the uncertainty weights. When each player uses this new approach, it can be shown that the computation for robust weighted Pareto optimum is cast as solving a mathematical programming with equilibrium constraints (MPEC). As we know that MPEC can be easily solved by some classic methods (for example SQP approaches (sequential quadratic programming)). When the weights are uncertain and correlated with the uncertain in the objectives, we also propose a corresponding computation method.

Though there are few studies on multi-objective bilevel programs, some interesting potential applications exist in the real-world. One example is Stackerberg game of a supply chain containing a manufacturer who supplies a whole set of products under supply uncertain to a risk-averse retailer satisfying consumer demand which is uncertain. At case, both the manufacturer and the retailer are all risk averse decision maker and have multi-criteria objectives. Then the manufacturer decides on the quantity for each product so as to maximize the profit and minimize the risk function simultaneously by forecasting the order quantity from the retailer and the corresponding wholesale prices stem form market clearing conditions. The retailer also decides her wholesale market order quantity for each product in order that he can simultaneously maximize the average profit and minimize the standard deviation of the profit.

Since the possible application, multi-objective bilevel programs have attracted some attention. For example, Yin [10] considers a multi-objective bilevel model for transportation scheme and management issues. Deb and Sinha [11] present evolutionary algorithms to solve multi-objective optimization problems. Pieume et al. [12] develop two methods for solving bilevel linear multi-objective bilevel optimization problems. Eichfelder [13] gives a solution method to solve nonlinear multi-objective bilevel problems based on a scaralization approach and the sensitivity analysis of adaptive parameters. Our approaches are not same as the above ways. In this paper, we study the stochastic multi-objective bilevel programs and consider that there are uncertainties in the weight. We note that our paper is closely related with the work of multi-objective game model provided by Qu and Ji [14], Qu, Ji and Goh [15]. However, the problem studied in this paper is different from the problems in these two papers. The problem in this paper is a Stackelberg game model, while it is Nash game in the above papers. Furthermore, we consider the uncertainties exist in both the parameters and weights. We note also that the model considered in this paper is also an extension the model in [16]. However, our method is different from that one in the following two aspects. First, this paper focus on the bilevel problems, while the single level problem is considered in that paper. Second, the method in [16] aims at present the equivalent reformulation with different choices of weight set. However, we present a MPEC reformulation for solving the bilevel problem.

The main contributions of this paper are as follows. A hybrid method is proposed to solve multi-objective bilevel programs with uncertain parameters. We show that an optimal solution can be obtained by means of solving a MPEC when the weight are deterministic and the weight sets chosen by the players are polytopes. We point out that the MPEC has been broadly researched and can be solved by the sequential quadratic programming (SQP) method [17]. We also show that when the weights are uncertain and correlated with the uncertain in the objectives, the corresponding computation method. The usefulness of the hybrid approach is shown in solving a bilevel multi-objective competition matters in a supply chain.

Section 2 reviews the basic concepts which are existing in multi-objective bilevel programs. In addition, we introduce a new concept about the robust weighted Pareto optimum. We point out that a robust weighted Pareto optimal solution is also a weighted Pareto optimum. Section 3 shows that when the weight are deterministic and the weighted index values are given as polytopes, the robust weight Pareto optimum can be equivalently reformulated as a MPEC that can be effectively settled by means of SQP methods. When the weights are uncertain and correlated with the uncertain in the objectives, we also show the corresponding computation method. In Section 4, we use an example which are analyzing a multi-objective bilevel competition problem in a supply chain to show the efficiency of our methods. Section 5 summarizes the full paper.

2 Preliminaries

Throughout this paper, the following notations will be presented. For any g, h ∈ R^m, denote $\begin{matrix} h \geq g (resp . h \leq g) \\ \Leftrightarrow h - g \in R_{+}^{m} (resp . h - g \in R_{+}^{m}) \\ \Leftrightarrow h_{j} - g_{j} \geq 0, j \in I (resp . h_{j} - h_{j} \leq 0, j \in I); \\ h ≻ g (resp . h ≺ g) \\ \Leftrightarrow g - h \in R_{+ +}^{m} (resp . g - h \in R_{+ +}^{m}) \\ \Leftrightarrow h_{j} - g_{j} > 0, j \in I (resp . h_{j} - g_{j} < 0, j \in I); \\ h ∊ g (resp . h ⪯ g) \\ \Leftrightarrow h - g \in R_{+}^{m} and h \neq g \\ (resp . h - g \in R_{+}^{m} and h \neq g) \\ \Leftrightarrow h_{j} - g_{j} \geq 0, j \in I and h \neq g \\ (resp . h_{j} - g_{j} \leq 0, j \in I and h \neq g); \end{matrix}$ where I : = {1, ⋯ , m} is the index set; Throughout this paper, the superscript U and subscript L signify leader’s and follower’s parameters, decision variables, cost functions and weights of payoff functions, respectively.

This paper studies the following stochastic multi-criteria bilevel optimization, $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} f^{U} (x^{U}, x^{L}, ξ^{U}) \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (2.1) $x^{L} \in S^{L} (x^{U}),$ where S^L (x^U) denotes the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} f^{L} (x^{L}, x^{U}, ξ^{L}) \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0, \end{matrix}$ (2.2) where fⁱ (x^U, x^L, ξⁱ) : R^{n
ⁱ} × R^{n
^j} × Ξ → R^{m
ⁱ} is a stochastic vector function, Gⁱ : R^{n
ⁱ} × R^{n
^j} → R^{p
ⁱ}, Hⁱ : R^{n
ⁱ} × R^{n
^j} → R^{q
ⁱ}, i, j ∈ {U, L}, i ≠ j. Here Ξ denotes as the support set of ξ. Usually, to deal with stochastic problem, we replace the stochastic objective with its expectation, i.e., the following multi-objective optimization model, $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} F^{U} (x^{U}, x^{L}) \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (2.3) $x^{L} \in S^{L} (x^{U}),$ where S^L (x^U) is the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} F^{L} (x^{L}, x^{U}) \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0, \end{matrix}$ (2.4) where $F^{i} (x^{U}, x^{L}) = 𝔼 [f^{i} (x^{U}, x^{L}, ξ^{i})], i = L, U$ . In what follows, we assume that all functions considered in the bilevel problem (2.3) are continuously differentiable and mⁱ ≥ 2, i = U, L. Because the lower level problem is multi-criteria problem (m^L ≥ 2), a common solution concept given is Pareto optimum or weak Pareto optimum, i.e., given x^U, the solution set S^L (x^U) is the Pareto optimal set or weak Pareto optimal set if for any given x^U and ${\bar{x}}^{L} \in S^{L} (x^{U})$ , no feasible point x^L in (2.4) such that $F^{L} (x^{L}, x^{U}) ⪯ F^{L} ({\bar{x}}^{L}, x^{U})$ or $F^{L} (x^{L}, x^{U}) ≺ F^{L} ({\bar{x}}^{L}, x^{U})$ .

Definition 2.1. (x^U, x^L) is said to be feasible for problem (2.3) if G^U (x^U, x^L) ≥0, H^U (x^U, x^L) =0, and x^L ∈ S^L (x^U). Locally Pareto optimal (resp. weak Pareto) of problem (2.3) refers to a point $({\bar{x}}^{U}, {\bar{x}}^{L})$ if it is feasible for (2.3) and there is no other feasible point (x^U, x^L) in the neighborhood of $({\bar{x}}^{U}, {\bar{x}}^{L})$ such that $F^{U} (x^{U}, x^{L}) ⪯ F^{U} ({\bar{x}}^{U}, {\bar{x}}^{L})$ (resp. $F^{U} (x^{U}, x^{L}) ≺ F^{U} ({\bar{x}}^{U}, {\bar{x}}^{L})$ ).

In the multi-criteria optimization literature, the weighted method has been extensively studied. However this method is also criticized for some defect. For instance,as indicated in the application, weights are not known shift to an earlier date and the modeler or decision -maker has to choose them while it is often difficult to to choose the appropriate weights to make reasonable decisions. In many cases, there may be ambiguity in the weights of chosen by decision makers. Therefore, it is necessary to provide a new way to deal with these problems. The worst case weighted approach is one possible choice as it provides an alternative to solve the weight uncertainty in the multi-objective bilevel model. Specifically, we assume that players in both level use the robust weighted approach to address the weight uncertainty, i.e., both the leader and the follower all use a robust weighted approach to minimize their weighted payoff functions.

3 MPEC reformulations for (2.3)

3.1 The reformulation with deterministic weights

We first consider a simple case that the weights are deterministic and are unrelated to the stochastic parameters in the objective functions.

Definition 3.1. Let $W^{i} \in W_{r}^{i} : = {w^{i} \in R_{+}^{m^{i}} | ∥ w^{i} ∥_{1} = 1}$ be a nonempty closed convex set of weights, i = U, L. (x^U, x^L) is called a robust weighted optimal solution of (2.3), if it is an optimum to the following problem $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} max_{w^{U} \in W^{U}} (w^{U})^{T} F^{U} (x^{U}, x^{L}) \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (3.5) $x^{L} \in S_{w}^{L} (x^{U}),$ where $S_{w}^{L} (x^{U})$ is the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} max_{w^{L} \in W^{L}} (w^{L})^{T} F^{L} (x^{L}, x^{U}) \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0 . \end{matrix}$ (3.6)

Different from weighted Pareto concepts, the new approach seeks an optimum that is robust and feasible for the worst case weights within the weight of the family. From Theorem 2.2 of Hu and Mehrotra [16] and Definitions 2.1 and 3.1, we have that the following theorem holds.

Theorem 3.1. Suppose $W^{i} \subset W_{r}^{i}$ is as the one in Definition 2, i = U, L. if $\bar{x} : = ({\bar{x}}^{U}, {\bar{x}}^{L})$ is a robust weighted optimum of (3.5) with the combination W : = (W^U, W^L) of weight sets, then the following conclusions are true,

$\bar{x}$ is also a weak Pareto optimal solution of (2.3);

when all of weights in W^U are all positive, $\bar{x}$ is also a Pareto optimal solution of (2.3);

when $\bar{x}$ is a unique optimum of (3.5), $\bar{x}$ is also a Pareto optimal solution of (2.3).

Now that the relationship between of (3.5) and (2.3) has been present. Our next step is to discuss how to implement such a solution. To do this, we assume that the weight sets Wⁱ, i = U, L, are given as polyhedral regions. Then a robust weighted optimal point can be converted into a MPEC problem. We note that this problem has been studied by many scholars, and can be solved by solver PATH [18].

With a fixed reference point and a perturbation region around the point, we assume that the uncertain weights W^U and W^L can be described, that is the weight sets can be given as follows: let ${\bar{w}}^{i} \in R^{m^{i}}$ be the reference point of wⁱ, Cⁱ ∈ R^bⁱ×mⁱ be a coefficient matrix used to denote a perturbation set around ${\bar{w}}^{i}$ , i = U, L, then let the disturbed area centre on ${\bar{w}}^{i}$ as follows, for i = U, L

$W^{i} = {w^{i} \in R^{m^{i}} | \begin{matrix} w^{i} = {\bar{w}}^{i} + (C^{i})^{T} v^{i}, \\ v^{i} \in V^{i} \subset R^{b^{i}} \end{matrix}}$ (3.7) where Vⁱ,i = U, L, are two uncertain sets which belongs to

${\tilde{V}}^{i} = {v^{i} \in R^{b^{i}} | \begin{matrix} {\bar{w}}^{i} + (C^{i})^{T} v^{i} \geq 0, \\ (e^{i})^{T} ({\bar{w}}^{i} + (C^{i})^{T} v^{i}) = 1, \end{matrix}}$ (3.8) here eⁱ ∈ R^{m
ⁱ}, i = U, L, are two unit vectors. Actually, this method has been extensively used in defining uncertain [14, 16].

Let

$V^{i} : = {v^{i} \in {\tilde{V}}^{i} | A^{i} v^{i} = γ^{i}, B^{i} v^{i} \geq c^{i}},$ (3.9) where Aⁱ ∈ R^lⁱ×bⁱ, γⁱ ∈ R^{l
ⁱ}, cⁱ ∈ R^{k
ⁱ}, and Bⁱ ∈ R^kⁱ×bⁱ, i = U, L. We now present a reformulation for problem (3.5) with Wⁱ given as (3.1)–(3.3). Next, we show that the computation method of MBG can be casted to solve a MPEC.

Lemma 3.3. Define Wⁱ, i = U, L, are given as (3.7)–(3.8), then the robust weighted bilevel optimization problem (3.5) can be reformulated as the following bilevel programming, $\begin{matrix} min_{x^{i}, z_{j}^{i}, i = U, L} ({\bar{w}}^{U})^{T} z_{3}^{U} + z_{4}^{U} - (γ^{U})^{T} z_{1}^{U} - (c^{U})^{T} z_{2}^{U} \\ s . t . C^{U} z_{3}^{U} + (A^{U})^{T} z_{1}^{U} + (B^{U})^{T} z_{2}^{U 2} = 0 \\ F^{U} (x^{U}, x^{L}) - z_{3}^{U} - z_{4}^{U} e \leq 0 \end{matrix}$ (3.10) $\begin{matrix} z_{1}^{U} \in R^{l^{U}}, z_{2}^{U} \in R_{+}^{k^{U}}, z_{3}^{U} \in R^{m^{U}}, z_{4}^{U} \in R \\ G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0 \\ (x^{L}, z_{1}^{L}, z_{2}^{L}, z_{3}^{L}, z_{4}^{L}) \in S_{w}^{L} (x^{U}), \end{matrix}$ where $S_{w}^{L} (x^{U})$ denotes the solution set of the problem at the lower level: $\begin{matrix} min_{x^{L}, z_{j}^{L}, j = 1, 2, 3, 4} ({\bar{w}}^{L})^{T} z_{3}^{L} + z_{4}^{L} - (γ^{L})^{T} z_{1}^{L} - (c^{L})^{T} z_{2}^{L} \\ s . t . C^{L} z_{3}^{L} + (A^{L})^{T} z_{1}^{L} + (B^{L})^{T} z_{2}^{L 2} = 0 \\ F^{L} (x^{L}, x^{U}) - z_{3}^{L} - z_{4}^{L} e \leq 0 \end{matrix}$ (3.11) $\begin{matrix} G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0 \\ z_{1}^{L} \in R^{l^{L}}, z_{2}^{L} \in R_{+}^{k^{L}}, z_{3}^{L} \in R^{m^{L}}, z_{4}^{L} \in R . \end{matrix}$

Proof. This Lemma can be proven as follows. Given the leader’s strategy x^U, it is easy to show that the follower’s optimization problem (3.6) is cast as $\begin{matrix} min_{x^{L}, t} t \\ s . t . max_{w^{L} \in W^{L}} (w^{L})^{T} F^{L} (x^{L}, x^{U}) \leq t, \end{matrix}$ (3.12) $G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0 .$

For any given (x^U, x^L), the maximization problem in the left hand-side of the first constraint of (3.12) can be equivalently cast to be $\begin{matrix} max_{v^{L}} (C^{L} F^{L} (x^{L}, x^{U}))^{T} v^{L} + ({\bar{w}}^{L})^{T} F^{L} (x^{L}, x^{U}), \\ s . t . {\bar{w}}^{L} + (C^{L})^{T} v^{L} \geq 0, e^{T} ({\bar{w}}^{L} + (C^{L})^{T} v^{L}) = 1, \\ A^{L} v^{L} = γ^{L}, B^{L} v^{L} \geq c^{L} . \end{matrix}$ (3.13)

The corresponding dual problem is $\begin{matrix} min_{z_{1}^{L}, z_{2}^{L}, z_{3}^{L}, z_{4}^{L}} ({\bar{w}}^{L})^{T} z_{3}^{L} + z_{4}^{L} - (γ^{L})^{T} z_{1}^{L} - (c^{L})^{T} z_{2}^{L}, \\ s . t . C^{L} z_{3}^{L} + (A^{L})^{T} z_{1}^{L} + (B^{L})^{T} z_{2}^{L} = 0 \end{matrix}$ (3.14) $\begin{matrix} F^{L} (x^{L}, x^{U}) - z_{3}^{L} - z_{4}^{L} e \leq 0 \\ z_{1}^{L} \in R^{l^{L}}, z_{2}^{L} \in R_{+}^{k^{L}}, z_{3}^{L} \in R^{m^{L}}, z_{4}^{L} \in R, \end{matrix}$ here “e” is the unit vector as well as “0” is the zero vector.

Hence, the proof of this theorem can be deduced from the strong duality theorem and (3.12)–(3.14). □

The above lemma shows the equivalence between the bilevel problems (3.5) and (3.10), i.e., if (x^U, x^L) is a robust weighted optimal solution to (3.5), then there is $(z_{j}^{i})_{i = U, L; j = 1, 2, 3, 4}$ such that $(x^{i}, z_{j}^{i})_{i = U, L; j = 1, 2, 3, 4}$ is an optimum to (3.10); otherwise if $(x^{i}, z_{j}^{i})_{i = U, L; j = 1, 2, 3, 4}$ is an optimal solution to (3.10), (x^U, x^L) is a robust weighted optimum to (3.5). So in what follows, we focus on the bilevel problem (3.10).

Given x^U, it is expected that a solution $(x^{L}, z_{j}^{L})_{j = 1, 2, 3, 4}$ of the lower level problem (3.11) is a stationary point of (3.11), i.e., it solves the following Karush-Kuhn-Tucker (KKT) system,

$\begin{matrix} \begin{matrix} \nabla_{x^{L}} Γ = \nabla_{x^{L}} F^{L} (x^{L}, x^{U}) λ_{2}^{L} - \nabla_{x^{L}} G^{L} (x^{L}, x^{U}) λ_{4}^{L} \\ + \nabla_{x^{L}} H^{L} (x^{L}, x^{U}) λ_{5}^{L} = 0; \\ \nabla_{z_{1}^{L}} Γ = - γ^{L} + A^{L} λ_{1}^{L} = 0; \\ \nabla_{z_{2}^{L}} Γ = - c^{L} + B^{L} λ_{1}^{L} - λ_{3}^{L} = 0; \\ \nabla_{z_{3}^{L}} Γ = {\bar{w}}^{L} + (C^{L})^{T} λ_{1}^{L} - λ_{2}^{L} = 0; \\ \nabla_{z_{4}^{L}} Γ = 1 - e^{T} λ_{2}^{L} = 0; \\ H^{L} (x^{L}, x^{U}) = 0; \end{matrix}} \\ \begin{matrix} F^{L} (x^{L}, x^{U}) - z_{3}^{L} - z_{4}^{L} e \leq 0, λ_{2}^{L} \geq 0; \\ (λ_{2}^{L})^{T} (F^{L} (x^{L}, x^{U}) - z_{3}^{L} - z_{4}^{L} e = 0; \\ z_{2}^{L} \geq 0, G^{L} (x^{L}, x^{U}) \geq 0, λ_{3}^{L} \geq 0, λ_{4}^{L} \geq 0; \\ (λ_{3}^{L})^{T} z_{2}^{L} = 0, (λ_{4}^{L})^{T} G^{L} (x^{L}, x^{U}) = 0, \end{matrix}} \end{matrix}$ (3.15) where Γ is the Lagrangian of (3.11) defined as

$\begin{matrix} Γ ((x^{L}, x^{U}), (z_{1}^{L}, z_{2}^{L}, z_{3}^{L}, z_{4}^{L}), (λ_{1}^{L}, λ_{2}^{L}, λ_{3}^{L}, λ_{4}^{L}, λ_{5}^{L})) \\ : = ({\bar{w}}^{L})^{T} z_{3}^{L} + z_{4}^{L} - (γ^{L})^{T} z_{1}^{L} - (c^{L})^{T} z_{2}^{L 2} \\ + (λ_{1}^{L})^{T} (C^{L} z_{3}^{L} + (A^{L})^{T} z_{1}^{L} + (B^{L})^{T} z_{2}^{L}) \\ + (λ_{2}^{L})^{T} (F^{L} (x^{L}, x^{U}) - z_{3}^{L} - z_{4}^{L} e) \\ - (λ_{3}^{L})^{T} z_{2}^{L} - (λ_{4}^{L})^{T} G^{L} (x^{L}, x^{U}) \\ + λ_{5}^{L} H^{L} (x^{L}, x^{U}), \end{matrix}$ (3.16)

Therefore replacing the lower level optimization problem (3.11) with (3.15) and (3.16) derives a MPEC,

$\begin{matrix} min_{x^{i}, z_{j}^{i} λ_{k}^{L}} ({\bar{w}}^{U})^{T} z_{3}^{U} + z_{4}^{U} - (γ^{U})^{T} z_{1}^{U} - (c^{U})^{T} z_{2}^{U} \\ s . t . C^{U} z_{3}^{U} + (A^{U})^{T} z_{1}^{U} + (B^{U})^{T} z_{2}^{U 2} = 0 \\ F^{U} (x^{U}, x^{L}) - z_{3}^{U} - z_{4}^{U} e \leq 0 \\ z_{1}^{U} \in R^{l^{U}}, z_{2}^{U} \in R_{+}^{k^{U}}, z_{3}^{U} \in R^{m^{U}}, z_{4}^{U} \in R \\ G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0 \\ (x^{L}, z_{1}^{L}, \dots, z_{4}^{L},, λ_{1}^{L}, \dots, λ_{5}^{L}) \\ solves {(3.15) and (3.16)} . \end{matrix}$ (3.17)

The solver PATH can solve the above problem [11]. If for any given x^U functions F^L (· , x^U) and H^L (· , x^U) are convex in x^L and G^L (· , x^U) is concave in x^L, then the bilevel optimization problem (3.10) is equivalent to the MPEC (3.18).

Theorem 3.2. Suppose the weight sets Wⁱ, i = U, L, are given as (3.7)–(3.9). If for any given x^U functions F^L (· , x^U) and H^L (· , x^U) are convex in x^L and G^L (· , x^U) is concave in x^L, then the bilevel optimization problem (3.5) is equivalent to the MPEC (3.18).

Proof. The assertion of this Theorem follows from Lemma 3.3 and the above discussions directly. □

3.2 The reformulation with uncertain weights

In this section, we need consider a version with uncertain weights. Let Ωⁱ, i = U, L be a state space which is a possible choice of weights for decision makers. Define $ϒ^{i} (Ω^{i}, 𝔽^{i}, W_{r}^{i}, μ^{i})$ as stochastic vector mapping from Ωⁱ to $W_{r}^{i}$ , i = U, L.

Definition 3.5. An optimum of the followingproblem $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} 𝔼 [(ϒ^{U})^{T} f^{U} (x^{U}, x^{L}, ξ^{U})] \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (3.18) $x^{L} \in S^{L} (x^{U}),$ where S^L (x^U) denotes the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} 𝔼 [(ϒ^{L})^{T} f^{L} (x^{L}, x^{U}, ξ^{L})] \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0, \end{matrix}$ (3.19) is named as a stochastic Pareto optimum.

As an extension of Pareto optimality, the stochastic Pareto optimality is used to copy with the case where the deterministic weights is replaced with the uncertain criteria weights. The above definition implies that the original problem reduces to a stochastic bilevel optimization problem (3.19). When we suppose ϒⁱ is independent of the random scenario ξⁱ, (3.19) reduces to $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} 𝔼 [(ϒ^{U})^{T}] F^{U} (x^{U}, x^{L}) \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (3.20) $x^{L} \in S^{L} (x^{U}),$ where S^L (x^U) denotes the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} 𝔼 [(ϒ^{L})^{T}] F^{L} (x^{L}, x^{U}) \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0, \end{matrix}$ (3.21)

We now study a robust version of (3.21), i.e., consider the following model, $\begin{matrix} min_{x^{i} \in R^{n^{i}}, i = U, L} max_{μ^{U} \in 𝔻^{U}} 𝔼_{μ} [(ϒ^{U})^{T}] F^{U} (x^{U}, x^{L}) \\ s . t . G^{U} (x^{U}, x^{L}) \geq 0, H^{U} (x^{U}, x^{L}) = 0, \end{matrix}$ (3.22) $x^{L} \in S^{L} (x^{U}),$ where S^L (x^U) denotes the solution set of the following problem:

$\begin{matrix} min_{x^{L} \in R^{n^{L}}} max_{μ^{U} \in 𝔻^{L}} 𝔼_{μ} [(ϒ^{L})^{T}] F^{L} (x^{U}, x^{L}) \\ s . t . G^{L} (x^{L}, x^{U}) \geq 0, H^{L} (x^{L}, x^{U}) = 0, \end{matrix}$ (3.23) where $𝔻^{i}$ denotes a set of combining possible probability distributions of ϒⁱ.

We now discuss the reformulation of the above worst-case weighted stochastic bilevel problem under first moment uncertainty. We suppose the weight set Wⁱ is perturbed by set Vⁱ defined as in (3.7). Define $Λ^{i} : Ω^{i} \to {\tilde{V}}^{i}$ as a random perturbation vector and thus $ϒ^{i} = {\bar{w}}^{i} + (C^{i})^{T} Λ^{i}$ . With these definitions, if the weight set is given as the one in [16] where the first moment uncertainty is present. Then from the discussion in [16] and the method in Section 3.1, we can show that (3.23) can be equivalently cast as a MPEC.

4 An application

4.1 Model description

To show the efficiency of the proposed approach, we discuss it’s possible application in last mile delivery optimization. We proposes a bi-level multi-criteria last mile delivery optimization model. We include the existence of uncertainty in both supply and demand sides. In this model, the upper level decision-maker sets the decision variables for travel time and cost. The 3PL makes multi-objective decisions by considering the constraints of travel time set by the center operator and their delivery capacity.

We use the following notations. m denotes the number of retailer stores. Usually, m can be as large as 250 in a mall. Each retailer store is denoted as (i : i = 1, ⋯ , m) who orders the products from a set of suppliers. n_i trucks are needed to send retailer store is order. z_ij is the quantity of indivisible cargo to be delivered to the mall by truck (j : j = 1, ⋯ , n_i) for retailer. Each truck j spends t_ij time to deliver products to retailer i. Therefore t_ij is relevant to the delivered amount z_ij and is defined as a function of z_ij. In general, if z_ij is so large that t_ij also can be assumed to be larger, though not in scale. x is the time window set by the leader. The per uncertain cost is supposed as c if which is under a given delivery time window, and is supposed as h if which is outside of the time window. Therefore the uncertain cost for delivery can be described as

$\begin{matrix} \tilde{R} (t, x) \\ : = \max {\begin{matrix} c \sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} + h {[\sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} - x]}^{+} \\ c \sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} \end{matrix}}, \end{matrix}$ where [a] ⁺ : = max {a, 0}. Besides this cost, we also assume there is other cost which can be expressed as a stochastic function $\tilde{f} (z)$ . We use λ and $\bar{λ}$ to denote the per uncertain management cost for the in-time window and out of the time window, respectively.

The leader aims at minimizing the transportation time window as well as CVaR_α which can be modeled as the following bilevel problem, $\begin{matrix} min_{(x, μ), (τ, t, z)} 𝔼 [\tilde{G} (x, μ) : = λ x + \bar{λ} μ] \\ min_{(x, μ), (τ, t, z)} {CVaR}_{α} (\tilde{G} (x, μ)) \\ s . t . μ \geq \sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} - x \end{matrix}$ (3.24) $μ \geq 0, \underline{x} \leq x \leq \bar{x},$ where (τ, t, z) ∈ S (x) and S (x) denotes the corresponding solution set of the following problem, $\begin{matrix} \min 𝔼 [\tilde{H} (τ, z) : = τ + f (z)] \\ \min {CVaR}_{α} (\tilde{H} (τ, z)) \\ s . t . \sum_{j = 1}^{n_{i}} z_{ij} = d_{i}, i = 1, \dots, m, \\ τ \geq c \sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij}, \end{matrix}$ (3.25) $\begin{matrix} τ \geq c \sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} + h (\sum_{i = 1}^{m} \sum_{j = 1}^{n_{i}} t_{ij} - x), \\ z_{ij} \geq 0, t_{ij} \geq 0, j = 1, \dots, n_{i}, i = 1, \dots, m . \end{matrix}$ CVaR_α is related with the random variable $\tilde{u}$ , which can be given as ${CVaR}_{α} (\tilde{u}) : = min_{v \in R} F_{α} (\tilde{u}, v)$ where $F_{α} (\tilde{u}, v) : = \frac{1}{α} 𝔼 {[- \tilde{u} + v]^{+}} - v$ with [γ] ⁺ = γ if γ ≥ 0, otherwise [γ] ⁺ = 0. This model is detailed in [19]. We note that there are many optimization models for designing urban transportation [20 –22] and many algorithms have also been proposed to solve the resulting models [23 –25].

4.2 Numerical tests

We now detail the numerical tests for finding a Pareto optimum. In this test, we solve the multi-objective bilevel models by using the proposed approach under the consideration that the weights sets are given as finite and general polyhedral weight sets respectively. Suppose m = 2, n_i = 2 for i = 1, ⋯ , m. The definition of other parameters can be found in [19].

Table 1
Numerical test results by weighted approach

$f_{1}^{U} / f_{2}^{U}$ $f_{1}^{L} / f_{2}^{L}$ (x, μ, τ) t

0.7 0.3 (2, 0, 1) (0.578, 1.021, 0.047, 0.356)

0.7 1.2 (2.2,0.498,0.248) (0.576, 1.311, 0.402, 0.411)

1 0.3 (2.054, 0.356, 1.383) (1.03, 1.024, 0.257, 0.099)

1 1.2 (2.954, 0, 1.377) (0, 0, 0, 2.954)

1.5 0.3 (2.474, 1.465, 2.702) (1.112, 1.36, 1, 0.467)

1.5 1.2 (2.5, 1, 2.25) (0, 3, 0.5, 0)

(RWPO) (2.2, 0, 1.1) (1.1, 0, 1.1, 0)

$f_{1}^{U} / f_{2}^{U}$	$f_{1}^{L} / f_{2}^{L}$	(x, μ, τ)	t
0.7	0.3	(2, 0, 1)	(0.578, 1.021, 0.047, 0.356)
0.7	1.2	(2.2,0.498,0.248)	(0.576, 1.311, 0.402, 0.411)
1	0.3	(2.054, 0.356, 1.383)	(1.03, 1.024, 0.257, 0.099)
1	1.2	(2.954, 0, 1.377)	(0, 0, 0, 2.954)
1.5	0.3	(2.474, 1.465, 2.702)	(1.112, 1.36, 1, 0.467)
1.5	1.2	(2.5, 1, 2.25)	(0, 3, 0.5, 0)
	(RWPO)	(2.2, 0, 1.1)	(1.1, 0, 1.1, 0)

We use Analytical Hierarchy Process (for brief AHP) [26] to generate weights of two objectives in models (4.25) and (4.26). The centre operator is assumed to have no certain idea with respect to the relative importance of $f_{2}^{U} (y) : = {CVaR}_{α} (\tilde{G} (x, μ))$ and $f_{1}^{U} (y) : = 𝔼$ $f_{2}^{L} (y) : = {CVaR}_{α} (\tilde{H} (τ, z))$ . In this case, the centre operator suppose that there are two possible scale indices for the two objective functions as $f_{1}^{L} / f_{2}^{L} = 0.3$ , 1.2.

Table 1 lists the numerical results, where y = (x, μ, τ, t, z) are the weighted Pareto optimum. The last row of Table 1 gives the robust weighted Pareto optimum (RWPO) with finite weights. With different choice of the weights, different weighted Pareto optimum can be obtained. We note that the robust weighted Pareto optimum is calculated by using the weight region generated as the convex hull of the weight vectors. From the results we can conclude that a unique Pareto optimum is often obtained by using the new approach. This feature implies that our method is more robust compared with the existed method in that there are different solution for choosing different weights by using weighted approach [6], but there is an unique solution by using our approach. Furthermore, The results of the analysis indicate that through addressing a bi-level multi-objective optimization model the risk-averse operator of the urban logistics consolidation centre can optimally set the time windows for delivery by taking into account the lower-level risk-averse decision makers response effectively. From the perspective of management, this efficaciously synchronizes the last mile retail delivery operations into the mall with the operations at the consolidation centre. It was a great help to maximize the worker productivity, space utilization and truckload optimization. Additionally, we showed that if the lower bound of the time window is large enough, then the 3PL can fix up the deliver by taking into account only the demand constraints. In general, the logistics delivery service provider merely needs to take into account the demands set by the retail stores without thinking the supply risk. Equally, when the upper bound of the time window is small enough, the cost and risk of the two lever decision makers will increase with the increase of punishment.

Next, we present the numerical tests with the general polytope weight region, where the reference point ${\bar{w}}^{j}$ and matrices $C_{i}^{U}$ and $C_{j}^{L}$ are defined as follows, ${\bar{w}}_{i}^{U} : = (1 / 2, 1 / 2)$ , i = 1, 2, ${\bar{w}}_{j}^{L} : = (1 / 3, 2 / 3)$ , j = 1, 2 and

$\begin{matrix} C_{i}^{U} : = [\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix}], i = 1, 2 \\ C_{j}^{L} : = [\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}], j = 1, 2 . \end{matrix}$

The perturbation subsets are defined as

$\begin{matrix} V_{i}^{U} : = {v_{i}^{U} \in R^{2} | e^{T} v_{i}^{U} \leq 1 - δ}, i = 1; \\ V_{j}^{L} : = {v_{j}^{L} \in R^{2} | e^{T} v_{j}^{L} \leq 1 - δ}, j = 1, 2, \end{matrix}$ where δ is a parameter defined in [0, 0.1). With the above data the solution with different δ is calculated by utilizing the approach developed in this paper. The stability results are shown in Table 2 which contains small data errors due to the small changes in δ.

Table 2

Numerical test results with general polytope weight regions

δ	(x, μ, τ)	t
0	(2.5, 0.5, 1.75)	(0.75,0.75, 0.75, 0.75)
0.007	(2.5, 0.5, 1.75)	(0.747, 0.742, 0.752, 0.759)
0.02	(2.5, 0.5, 1.75)	(0.75, 0.75, 0.751, 0.748)
0.05	(2.5, 0.5, 1.75)	(0.749, 0.761, 0.754, 0.698)
0.1	(2.5, 0.5, 1.75)	(0.8,0.691,0.747,0.762)

5 Conclusion

This paper introduces a hybrid approach to stochastic multi-objective bilevel problems. This approach can deal with the case when the player can not decide relative weights for each objective and therefore overcomes the shortcoming of the weighted approach which has been widely studied. We also discuss the corresponding computation method and show that the original problem is equivalently transformed into a MPEC which has been extensively studied and can be solved by the solver Path. The proposed method can put up with shortcomings of the existed methods to the multi-objective bilevel problems. There is no clear guidance to a decision-maker to pick up a solution among the obtained Pareto surface. However, a unique solution can be computed by our approach. Further, different decision-maker may have different opinions as to present relative weights for each objective is not easy. Therefore, the relative weights presented by different decision-maker can differ largely. However, our methods can overcome this shortcoming.

To show the efficiency of the proposed approach, an application o last mile delivery bilevel competition is presented. In this setting, no clear guidance can be found for the leader (central planner or 3PL) to choose a strategy among (possibly a vast number of) generated Pareto surface. However, there is an unique solution by using our approach. In the multi-objective competition in a last mile delivery bilevel competition, since different decision maker (central planner or 3PL) may have different opinions, different decision maker can give the different weights which maybe differ significantly. Furthermore, ambiguity is often existence when a decision maker (central planner or 3PL) choose the weight, because to give relative weights for each objective is often difficult. The approach proposed in this paper can overcome these shortcomings. The numerical tests show that our method is more “robust” than the existed weighted approach in that there are different solution for choosing different weights by using weighted approach, but there is a unique solution by using our approach. The limitations of our method are that it is difficult to correctly choose the weight set for the uncertain weights. Therefore, we can focus to propose some guidelines to choose it. Another extension of the proposed approach to more practical applications under multi-criteria considerations is also our further studies.

Footnotes

Acknowledgments

The work is supported by The Program for Professor of Special Appointment (Eastern Scholar) at Shanghai Institutions of Higher Learning (No. TP2014043). The work is also supported by Natural Scientific Foundation of China (No. 71571055).

References

and Goh

, Proximal point algorithms for multi-criteria DC programming with applications to portfolio optimization, Journal of Optimization Theory and Applications169(1) (2016), 280–289.

S.J.

, Goh

, Wu

S.Y.

and Souza

R.D.

, Multi-objective DC programs with infinite convex constraints, Journal of Global Optimization59(1) (2014), 41–58.

S.J.

, Goh

, Ji

and Souza

R.D.

, A new algorithm for linearly constrained c-convex vector optimization with a supply chain network risk application, European Journal of Operational Research247 (2015), 359–365.

S.J.

, Goh

, Souza

R.D.

and Wang

T.N.

, Proximal point algorithms for convex multi-criteria programs with applications to supply chain risk management, Journal of Optim Theory Applications163(3) (2014), 949–956.

S.J.

, Liu

, Goh

, Li

Y.J.

and Ji

, Nonsmooth multiobjective programming with quasi-Newton methods, European Journal Of Operational Research235(3) (2014), 503–510.

Wang

, Existence of a pareto equilibrium, Journal of Optimization Theory and Applications79(2) (1993), 373–384.

Yang

and Yang

, A newton-like trust region method for large-scale unconstrained nonconvex minimization, Abstract and Applied Analysis2013 (2013), Article ID 488407.

Yang

and Zhang

, On linear convergence of projected gradient method for a class of affine rank minimization problems, Journal of Industrial and Management Optimization12(4) (2016), 1507–1519.

Weber

and Borcherding

, Behavioral in uences on weight judgments in multiattribute decision making, European Journal of Operational Research67(2) (1993), 1–12.

10.

Yin

, Multiobjective bilevel optimization for transportation planning and management problems, Journal of Advanced Transportion36(1) (2001), 93–105.

11.

Deb

and Sinha

, Solving bilevel multi-objective optimization problems using evolutionary algorithms, Evolutionary Multi-Criterion Optimization8(3) (2009), 209–215.

12.

Pieume

, et al., Solving bilevel linear multiobjective programming problems, American Journal of Operational Research1(3) (2011), 214–219.

13.

Eichfelder

, Multiobjective bilevel optimization, Mathematical Programming Ser A123(2) (2010), 419–449.

14.

and Ji

, The worst-case weighted multi-objective game with an application to supply chain competitions, PLoS One11(1) (2016), e0147341.

15.

, Ji

and Goh

, The robust weighted multi-objective game, PLoS One10(9) (2015), e0138970.

16.

and Mehrotra

, Robust and stochastically weighted multi-objective optimization models and reformulations, Operational Research60(4) (2011), 936–953.

17.

Jian

, Li

and Mo

, A strongly and superlinearly convergent sqp algorithm for optimization problems with linear complementarity constraints, Applied Mathematics and Optimization54(1) (2006), 17–46.

18.

Ferris

and Munson

, Complementarity problems in gams and the path solver, Journal of Economic Dynamics and Control24(2) (2000), 165–186.

19.

, Qu

and Yu

, Bi-level multi-objective optimization model for last mile delivery using a discrete approach, Journal of Difference Equations and Applications25(1) (2016), 1–12.

20.

Feng

F.J.

and Shi

D.D.

, Complex network theory and its application research on P2P networks, Applied Mathematics and Nonlinear Sciences1(1) (2016), 45–52.

21.

Rao

, Goh

, Zhao

and Zheng

, Location selection of sustainability city logistics centers, Transportation Research Part D: Transport and Environment36(1) (2015), 29–44.

22.

Zhou

S.Z.

, Xu

and Xu

, A sufficient condition for the existence of a k-factor excluding a given r-factor, Applied Mathematics and Nonlinear Sciences2(1) (2017), 13–20.

23.

Dang

and Gao

, Non-monotonous accelerated parallel subgra-dient projection algorithm for convex feasibility problem, Optimization63(4) (2014), 1–4.

24.

Klymchuk

, Regularizing algorithm for mixed matrix pencils, Applied Mathematics and Nonlinear Sciences2(1) (2017), 123–130.

25.

Jiang

and Yuan

, A barzilai-borwein-based heuristic algorithm for locating multiple facilities with regional demand, Computational Optimization and Applications51(3) (2012), 1275–1295.

26.

Saaty

T.L.

, The modern science of multicriteria decision making and its practical applications: the AHP/ANP approach, Operations Research61(5) (2013), 1101–1118.