Optimal decision of a disaster relief network equilibrium model

1.   Introduction

Disaster relief is a series of emergency response measures in emergency situations such as natural disasters. Usually, we need to deploy materials and personnel to the affected area under a limited cost budget to minimize the damage and casualties caused by disasters. Therefore, this paper studies an emergency and disaster relief network equilibrium problem with limited path capacity, and takes minimizing the disaster relief process cost as the optimization goal. Figuratively speaking, it means that the total traffic demand on a given network is allocated to the network according to certain rules. Many scholars have studied this problem ^[1,2]. Especially after the user equilibrium principle was proposed by Wardrop ^[3], people have obtained rich and perfect theoretical research results and many successful practical applications for the deterministic traffic allocation problem^[4]; but, the theoretical research on the equilibrium traffic allocation problem with randomness is not enough. In one such study^[5,6,7,8,9], Gwinner and Raciti presented a category of stochastic variational inequalities involving linear relationships within random sets ^[7], providing insights into testability, uniqueness, existence, and procedure under Banach space conditions. Additionally, they presented approximate solutions for these problems. Another research paper ^[8], employs the theory of stochastic variational inequalities to address a particular category of linear stochastic equilibrium problems within network environments, while ^[9] addresses nonlinear stochastic traffic equilibrium problems and proposes an approximation process based on averaging and truncation, ensuring norm convergence; Nagurney et al. ^[10] developed a disaster relief network model incorporating mean-square error, stochastic link costs, and a time target for delivering disaster relief materials to demand points in the presence of demand uncertainty. In the research conducted by Maugeri et al. ^[11], they investigated the general infinite-dimensional complementarity problem. They developed a novel model based on infinite-dimensional Lagrange theory, established optimality conditions, and simplified the problem by formulating it as a suitable system of equations and inequalities. It is noteworthy that stochastic methods have significantly enhanced important financial and economic models. For instance, weighted traffic equilibrium problems ^[12], oligopolistic market equilibrium problems ^[13], financial equilibrium problems ^[14], Walras equilibrium problems ^[15], Internet problems ^[16], and power supply chain problems ^[17] have all benefited from the application of stochastic methods.

So, in this paper, we study the randomness of natural disasters, and transform the stochastic equilibrium flow distribution model into a stochastic variational inequality model under certain constraints. However, the prediction error can vary between different models, so we need to find the optimal prediction model. Hence, this paper introduces the Expected Residual Minimization model (ERM). In terms of the existence and convergence of solutions, it is worth noting that Ceng et al. introduced the concepts of lower semi-continuity and pseudo-monotonicity in ^[18,19] and established the solvability of vector mixed variational inequalities and related vector-like variational inequalities by using Brouwer's fixed point theorem. In ^[20,21], the KKM-Fan lemma and Nadler's result are used to derive the solvability of pseudo-monotone generalized vector variational inequalities and generalized implicit vector equilibrium problems. Finally, the convergence of an algorithm for solving a class of mixed variational inequalities based on the auxiliary problem principle is given in ^[22]. The fundamental concept behind ERM is to discover the optimal prediction model by minimizing the disparity between the observed value and the predicted value. In this way, we can also quickly make the best decisions in uncertain situations, improve rescue efficiency, and reduce losses. Specifically, in the random rescue model, we need to predict the value of some variables (such as resource demand, personnel scheduling, task completion time, etc.) in order to optimize the rescue work plan. In order to achieve this goal, some predictive models (such as polynomial regression, neural networks, etc.) are often used to make predictions. However, different models may have different prediction errors, so we need to find the best model to make predictions.

In summary, this paper makes significant contributions in the following key areas: (1) Model Transformation: This paper innovatively transforms the stochastic network equilibrium model into a stochastic variational inequality problem. In contrast to existing approaches, the proposed method incorporates a novel algorithm specifically designed to address uncertain constraints; (2) Existence of Solutions: The paper enhances existing results by providing additional insights into the existence of solutions. Leveraging the KKM theorem and a variation of Brouwer's fixed point theorem, this study establishes the existence and convergence of solutions; (3) Computational Feasibility: To demonstrate the practical applicability of the proposed model, this paper employs the classical Sample Average Approximation (SAA) method for solving the problem. This not only showcases the feasibility of the model, but also highlights its potential for disaster relief implementation.

The organization of this paper is outlined as follows: In the second part, the stochastic disaster relief traffic flow equilibrium model is introduced in detail, the equilibrium conditions of stochastic generalization are proposed, and the variational characteristics of the equilibrium are given. In the third part, in a Hausdroff topological vector space, combing the conditions of lower semi-continuity and pseudo-monotonicity, the existence of the optimal solution to the random variational inequality has been proved through a variant of the KKM theorem and Brouwer's fixed point theorem; considering the existence of random variables in normed linear space, the deterministic expected residual minimization model (ERM) is established by introducing the Lagrange function and the NCP function, and the Quasi-Monte Carlo method is used to solve the stochastic variational inequality problem and analyze its convergence. In the fourth part, a numerical example is given to verify the feasibility and effectiveness of the model. Finally, in the fifth part, we summarize our research results and look forward to the future work.

2.   The model

For the convenience of the readers, we provide a detailed introduction to the disaster relief equilibrium model. The network comprises three key variables: O, A, and W. Under such a background, O is defined as the collection of disaster-affected nodes, denoted as $O = (O_{1}, O_{2}, \ldots, O_{p})$, A represents the set of directed routes connecting the affected pairs, expressed as $A = (A_{1}, A_{2}, \ldots, A_{n})$, and W is a collection of rescue center-disaster site pairs $(C/ D)$, represented as $W = {w_{1}, w_{2}, \ldots, w_{l}}\subset O\times O$. The flow on each route $A_{i}$ is denoted as $X_{i}$, and we establish the vector $X$ as $X = (X_{1}, \ldots, X_{n})$. A road is a sequence of consecutive routes, and we assume that each of the rescue center-disaster-affected area pairs is connected by at least $r_{j}\geq1$ paths, and the set of paths connecting them is denoted by $\mathbb{R}_{j}$, where $j = 1, \ldots, m$. All roads in the network can be organized into a vector denoted as $(R_1, \ldots, R_m)$. The structure of routes associated with these roads is represented using an route-road incidence matrix denoted as $\triangle = \{\delta_{ir}\}$, for $i = 1, \ldots, n$ and $r = 1, \ldots, l$, and, taking into account some road damage, the value is 1 when the disaster point can be reached through this section, and if this section cannot reach the disaster point, the value is 0. Each road $R_r$ corresponds to a flow $x_r$, and these flows are collectively grouped into a vector referred to as the road flow vector $(x_1, \ldots, x_m)$. The flow denoted as $f_{i}$ along route $A_{i}$ is equivalent to the cumulative flow across roads that incorporate the route $A_{i}$, and therefore $X_{i} = \Delta x_{i}$. Now we propose the cost of the rescue $s_{i}\geq0$ associated with $A_{i}$, considering that, in practical problems, this function is assumed to be continuous, bounded and convex in the domain. Therefore, the vector $s(X) = (s_{1}(X), \ldots, s_{n}(X))$ can be employed to denote the expenses associated with arcs within the network. Typically, $S_{r}(X) = \sum_{n}^{i = 1} \delta_{ir}s_{i}(X)$ or $S(x) = \Delta^{T}s(\Delta x)$. Rather than making assumptions about paths with infinite capacity, we assume that the existence of two road rescue capacity vectors $a, b$ where $a\leq b$, such that

Each pair denoted as $w_{j}$ is associated with a known random material demand $Q_{j}\geq 0$, which collectively forms the demand vector $(Q_{1}, \ldots, Q_{m})$. Specifically, this entails that the demand $Q_{j}$ satisfies the conservation law, and

Here we define the pair-incidence matrix $\Phi: = ({\varphi_{jr}}), j = 1, \ldots, m, r = 1, \ldots, l$. The elements $\varphi_{jr}$ assume a value of 1 when the road $R_{r}$ connects the pair $\omega_{j}$, and 0 otherwise.

So, based on the above, we can now provide the following equilibrium definition:

Definition 1. ^[23] A distribution $x\in K$ is considered an equilibrium distribution from the user's perspective if and only if it meets the following conditions:

where $K = \{x\in L^{2}(\Omega, P, R^{m}):a\leq x\leq b, \Phi x = Q\}$.

It is crucial to bear in mind that equilibrium distributions can be described through variational inequalities.

However, given the suddenness and uncertainty of disasters, and in order to better simulate the problem, this article considers the following problem of stochastic variational inequalities, denoted as SVIP $(S, K_{p})$: Determine a vector $x\in K_{p}$ such that, P-a.s.

Then, the random feasible set is defined by the following equation and P-a.s.

where $\Omega$ represents the fundamental sample space, which is a finite space. The mapping $S: R^n \times \Omega \rightarrow R^m$, and "P-a.s." stands for almost surely under the specified probability measure. Model (2.2) is evidently an expansion of the random complementarity problems previously investigated in references ^{[8,9,23,24,25,26]}. Without loss of generality, we limit the background of the problem to a Banach space, so we make the assumption that $x(\omega)\in L^{2}(\Omega, P, R^n)$, $Q(\omega)\in L^2(\Omega, P, R^m)$, and the stochastic expenditure function $S(x(\omega)):(\Omega, P, R^n)\rightarrow (\Omega, P, R^n)$. In this context, $(\Omega, P, R^n)$ denotes the set of functions that map from the probability space $\Omega$ to $R^m$, and these functions are required to be Lebesgue integrable under the probability measure. Moreover, the symbol $\langle \cdot, \cdot \rangle$ is employed to represent the standard inner product in $R^m$.

Definition 2. ^[24] The distribution $x\in K_P$ is regarded as an equilibrium distribution, if and only if it is for any $w_{j}\in W, \forall R_{q}, R_{S}\in \mathbb{R}_{j}$ and

Then we have for each $w_{j}\in W$, there exists a variable $S^{j}(\omega)$ such that for any $R_{r}\in\Re_{j}$ and P-a.s.

3.   Analysis of the existence and convergence

There are two standard ways to determine the existence of optimal disaster relief decisions, with and without the monotonic requirement. We will use the following definition.

Definition 3. ^[25] Assuming that E is a linear space, X is a nonempty subset of E, and $G:X\rightarrow 2^{E}$ is a set value mapping, then G is called a KKM mapping if for any finite set ${x_{1}, \ldots, x_{n}}$, there is

Here "con"stands for convex hull.

Definition 4. ^[27] Consider X and Y as Hausdorff spaces, and let T be a set-valued mapping from X to Y, $x_{0}\in X$, if for any $y_{0}\in T_{x_{0}}$ and any $y_{0}$ neighborhood $N_{y_{0}}$ there is a neighborhood $N_{x_{0}}$ of $x_{0}$ such that, for any $x_{0}\in N_{x_{0}}$, $T(x)\bigcap N(y_{0})\neq \emptyset$. Then, T is said to be lower semi-continuous at $x_{0}$. If for any $y\in X$, T is the lower semi-continuous function limited to line segment $[x_{0}, y]$, then T is said to be the lower semi-continuous function along the segment.

Theorem 1. ^[26] KKM Theorem: Let X be a Hausdorff space, and consider K as a nonempty subset of X, and T a set-valued mapping from X to Y such that for every $x\in K$ $T(x)$ is a closed subset in X, and there is

For every finite subset in K, if there is $x_{0}\in K$ such that $T(x_{0})$ is compact, then there is $\underset{y\in K_{P}}{\cap } T(x_{i}) \neq\emptyset$.

Theorem 2. If $S:L^{2}(\Omega, P, R^{n})\rightarrow L^{2}(\Omega, P, R^{n})$ is a set-valued mapping and pseudo-monotonic for all $x, y\in K_{P}$, and

If every pair of points $x, y\in K_P$ on the line segment $[x, y]$ exhibits lower semi-continuity, then a feasible solution exists for the variational inequality (2.2).

Proof of Theorem 2. $\forall y\in K_{P}, \omega \in \Omega$, define the mapping $F, G:L^{2}(\Omega, P, R^{n})\rightarrow L^{2}(\Omega, P, R^{n})$

Second, $\forall y\in K_{P}, \omega \in \Omega$, define a mapping,

Obviously, $x\in \underset{y\in K_{P}}{\cap }F(y(\omega))$ is true. In that case, x complies with the variational inequality, and $F(y(\omega))\subseteq H(y(\omega)).$

Step 1. Verifing that H is a KKM mapping.

Let $\bar{x} = \sum_{j = 1}^{m} \lambda_{j}y_{j}\geq0, \; \sum_{j = 1}^{m} \lambda_{j} = 1, \; 1\leq j\leq m$, if $\bar{x}\notin \cup _{j = 1}^{m} H(y_{j}(\omega))$, $\forall j = 1, \ldots, m$, and for $S(\bar{x}(\omega))$ we have $\langle S(\bar{x}(\omega)), y_{j}(\omega)-\bar{x}(\omega)\rangle < 0$. Furthermore, $\exists\lambda_{j} > 0$ such that

Then, summing the m equations and $\sum_{j = 1}^{m} \lambda_{j} = 1$, we obtain

Contradictorily, $\bar{x}\notin \cup _{j = 1}^{m} H(y_{j}(\omega))$. So, $\bar{x}\in \cup _{j = 1}^{m}H(y_{j}(\omega)), \forall j = 1, \ldots, m$, and therefore H is a KKM mapping. Similiary, G is a KKM mapping.

Step 2. Next we prove $\underset{y\in K_{P}}{\cap }G(y(\omega)) \subseteq \underset{y\in K_{P}}{\cap }F(y(\omega))$.

If $x_{0}\in \underset{y\in K_{P}}{\cap}G(y(\omega))$, then we have $\langle S(y(\omega)), y(\omega)-x_{0}(\omega)\rangle\geq0$. Assuming $x_{0}\notin \underset{y\in K_{P}}{\cap}F(y(\omega))$, then there exists $x_{0}\in K_{P}$ such that $\langle S(x_{0}(\omega)), y(\omega)-x_{0}(\omega)\rangle < 0$. Furthermore, due to C being pseudo-monotonic, there exists $y_{t_{0}}\in K_{P}$, and we have

So, we have $\langle S(y_{t_{0}}(\omega)), y_{t_{0}}(\omega)-x_{0}(\omega)\rangle < 0$, which contradicts with $x_{0}\in \underset{y\in K_{P}}{\cap } G(y(\omega))$, and then $\underset{y\in K_{P}}{\cap } G(y(\omega))\subseteq \underset{y\in K_{P}}{\cap } F(y(\omega))$ exist.

Otherwise, $F(y(\omega))\subseteq H(y(\omega)), H(y(\omega))\subseteq G(y(\omega))\Rightarrow F(y(\omega))\subseteq G(y(\omega))$, and we can obtain $\underset{y\in K_{P}}{\cap } G(y(\omega)) = \underset{y\in K_{P}}{\cap } F(y(\omega))$.

Step 3. Prove that $\forall y\in K_{P}, G(y(\omega))$ is a compact subset.

$\forall y\in K_{P}$, suppose $\{x_{k}\}\subseteq G(y(\omega))$ and $\{x_{k}\}$ converges to a point $\bar{x}$ in set $K_{P}$. For all k, and we have $\langle S(y(\omega)), y(\omega)-x_{k}(\omega)\rangle\geq0$. Furthermore, $\{x_{k}\}$ converges to $\bar{x}$, and we have

Therefore, we conclude that $\langle S(y(\omega)), y(\omega)-\bar{x}(\omega)\rangle\geq0$, therefore $\bar{x}\in G(y(\omega))$.

Step 4. From Step 3, it can be concluded that, $\forall y\in K_{P}, G(y(\omega)$ is a compact subset. According to Step 2 and Definition 3.1, it is known that

Furthermore, it is known that

Hence, there exists $\bar{x}\in K_{P}$ such that, for any $\bar{x^{*}}\in C\bar{x}$,

Absolutely, the conclusion is established, and the stochastic variational inequality has a solution. Now we show that the solution can converge to a saddle point. □

Definition 5. ^[24] Consider the set at $x^{*}\in K_{P}$

Call this set the tangent cone at $x^{*}$.

we can then deduce the following conclusions.

Theorem 3. If $x^{*}\in K_{P}$ is the optimal solution to problem (2.2), then

if and only if $D(x^{*}) = (-\infty, 0)$ is chosen as the descent direction.

Proof of Theorem 3. $\forall\alpha d\in T(x^{*})$, there is

By Definition 2.2 and Eq (2.3), we get

And,

□

Next, we review some concepts. We start by reviewing the Lagrange function, and consider the optimization problem

where $f(x(\omega)) = \langle S(x), y-x\rangle, f\in L^{2}(\Omega, P, R^{n}), x\in K_{P}$ satisfies the variational inequality (2.2), and we also introduce some of the following concepts, since the next goal is to give a reasonable restatement of $SVIP(S, K_{P})$. Then, by introducing the NCP function, combined with the Lagrange multiplier introduced in the previous section, we have

So, the conclusion is proven, and we have that $\lambda_{1}^{*}, \lambda_{2}^{*}\in L^{2}(\Omega, P, R_{+}^{n})$ and $\mu^{*}\in L^{2}(\Omega, P, R^{m})$, where $(x^{*}, \lambda_{1}^{*}, \lambda_{2}^{*}, \mu)$ is a optimal solution of the Lagrange function, i.e.,

And,

In order to solve the stochastic nonlinear complementarity problem (SLCP), we proposed an expected residual minimization (ERM) method based on the work of Chen and Fukushima ^[28]. Given our expected residual minimization model where our objective is to locate a vector $x^{*}\in K_{P}$ that minimizes the expected residuals for both (3.5) and (3.6), and in order to build the model smoothly, we give the following definition.

A function $\phi: R^{2} \rightarrow R$ is classified as an NCP function when it demonstrates the following characteristic:

Two commonly used NCP function are the "min" function

and the Fischer-Burmeister (FB) function from Fischer^[29]

Formulation (3.3) are a complementarity constraints, so with the NCP function, the Eq (3.3) can be converted to

where $\Psi:R^{l}\times R^{m}\rightarrow R^{m}$ is defined by

Here, we take $\phi(u, v) = u+v-\sqrt{u^{2}+v^{2}}$.

Based on these facts, we can build a desired residual minimization model

where $\rho:\Omega\rightarrow [0, +\infty)$ represents the satisfied probability density function and

Due to the existence of random variables, the expected value of E is not easy to calculate, so in order to overcome this problem, we can employ the SAA method to address the following approximation problem. Consider a collection of observations $\Omega_{k} = \{\omega^{q}|q = 1, \ldots, N_{k}\}$ generated via the Quasi-Monte Carlo method ^[28] such that $\Omega_{q}\subseteq\Omega$ and $k\rightarrow \infty$ have $N_{k}\rightarrow \infty$. For every $x\in K_{P}$, we call problem (3.8) an SAA problem, and we have

In addition, the observations produced by the quasi-Monte Carlo method have the following properties.

Lemma 1. ^[30] Suppose $\Gamma:\Omega\rightarrow R$ is integrable over $\Omega$. In that case, we obtain the following:

In the following we assume that both the $f(x(\omega))$ function and the function g are continuously differentiable, and we let $S^{*}$ and $S_{k}^{*}$ be the optimal solution sets for problems (3.7) and (3.8).

Theorem 4. For each k, assuming that $(x^{k}, \lambda^{k}, \mu^{k})\in S_{k}^{*}$ and $(x^{*}, \lambda^{*}, \mu^{*})$ is a convergence of the sequence $\{(x^{k}, \lambda^{k}, \mu^{k})\}$, then there is $(x^{*}, \lambda^{*}, \mu^{*})\in S^{*}$.

Proof of Theorem 4. For the convenience of proof, let $\lim_{k \to \infty}x^{k} = x^{*}, \lim_{k \to \infty}\lambda^{k} = \lambda^{*}, \lim_{k \to \infty}\mu^{k} = \mu^{*}$, then there exist compact sets U, V, W containing the sequences $\{x_{k}\}, \{\lambda_{k}\}, \{\mu_{k}\}$, and the functions $f(x(\omega^{q}))$, $g_{i}(x(\omega^{q})), i = 1, \ldots, n$ and functions $h_{j}(x(\omega^{q})), j = 1, \ldots, m, \omega^{q}\in\Omega_{k}$ are twice continuously differentiable on the closed interval, then there is the Lipschitz constant $M_{1}, M_{2}, M_{3}$ such that

Next, we have

where $M_{5} = max\{supV, \|\nabla g_{i}(x_{r}^{*}(\omega^{q}))|\}, i = 1, \ldots, n$. Then the same is true that

where $M_{6} = max\{supW, \|\nabla h_{j}(x^{*}(\omega^{q}))\|\}, j = 1, \ldots, m$.

Otherwise, due to

In addition, we also have

To sum up,

We know that

Then for $(x^{k}, \lambda^{k}, \mu^{k})\in S_{k}^{*}$, we have

when $k\to \infty$, and we obtain

The conclusion is proven. □

4.   Stochastic equilibrium numerical example

The problem of stochastic disaster relief equilibrium has important application value in studying its solution under uncertain conditions. Figure 1 shows a specific network ^[31], which contains four nodes, where node 2 is the rescue center and node 4 is the disaster site, containing 6 paths, 4 one-way paths and 1 bidirectional paths, and the incidence matrix between them can be expressed as

Let us assume that the cost function on each road is:

What governs variational inequality is the following problem: Find one $x\in K_p$ such that

and furthermore

where $\varepsilon$ is a non-negative random variable with uniform distribution over a specified interval [5,90], $\zeta_{1}$ is uniformly distributed in [0, 20], and $\zeta_{2}, \zeta_{3}$ is a random variable in normal numbers. Then, we establish an expected residual minimization model according to the previous part, using the sample approximation method, and we can obtain the solution of the model, $x = (101, 111, 204, 90, 168, 316)^{T}, S_{24} = 4675, S_ {42} = 4335$.

5.   Conclusions

The research focus of this paper is the problem of stochastic equilibrium, and a stochastic equilibrium model is established by introducing stochastic variational inequality. To solve this stochastic equilibrium model, we use the NCP function and the quasi-Monte Carlo method. By using the NCP function, combined with the Lagrange function, the complementary constraints in the original problem are combined with the original problem to transform into solving a model for minimizing the expected residuals. The quasi-Monte Carlo method provides an effective solution algorithm and performs convergence analysis, which makes the solution effectiveness of the model feasible.

Finally, a disaster relief example is given to verify the effectiveness of the model. This model helps decision-makers make decisions in disaster relief and optimize the allocation of disaster relief resources.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported in part by National Social Science Fund Project (No. 23BMZ062), the Major Projects of North Minzu University (No. ZDZX201805), governance and social management research center of Northwest Ethnic regions and First-Class Disciplines Foundation of Ningxia (No. NXYLXK2017B09), the youth talent support program of Ningxia (2021), and the leading talents support program of North Minzu University.

Conflict of interest

The authors declare that they have no conflicts of interest.