华北电力大学数理学院，北京

收稿日期：2021年4月21日；录用日期：2021年5月7日；发布日期：2021年5月26日

摘要

本文利用机会理论这种新的数学工具，研究了不确定随机网络下的带资源约束的最短路径问题，即在具有双重不确定性的网络中，寻找一条始于源节点终于目的节点并满足资源约束的最短路径问题。根据机会理论的运筹法则，我们给出了不确定随机网络带资源约束的最短路径问题的机会分布函数，并应用不确定随机变量的新型互熵建立了一个模型——带资源约束的新型互熵最小最短路径优化模型，用于解决这个问题，与之相对应的一个算法也被提出，本文最后设计了一个数值实验用来验证模型的有效性。

关键词

不确定随机网络，机会理论，不确定随机变量，带资源约束的最短路径问题，新型互熵

The Shortest Path Problem with Resource Constraints in Uncertain Random Networks

Yujie Jiao, Xin Gao

School of Mathematical Sciences and Physics, North China Electric Power University, Beijing

Received: Apr. 21^st, 2021; accepted: May 7^th, 2021; published: May 26^th, 2021

ABSTRACT

In this paper, a new mathematical tool, chance theory, is used to discuss the shortest path problem (SPP) with resource constraints (RCSPP) in uncertain random networks, that is, in a network with double uncertainties, to find a shortest path (SP) that starts from the source node and ends at the destination node and satisfies the resource constraints. According to the theory of chance operational principles, we present the chance distribution function of the SPP with resource constraints in an uncertain random network and establish a model by applying a new type of cross entropy of uncertain random variables—a new type of cross entropy with resource constraints which is used to solve this problem, and at the same time an algorithm corresponding to it has also been proposed. At the end of this paper, a numerical experiment is designed to verify the validity of the model.

Keywords:Uncertain Random Network, Chance Theory, Uncertain Random Variable, Resource-Constrained Shortest Path Problem, Newly Definited Cross Entropy

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

最短路径问题(SPP)是网络优化中的经典问题之一，它被广泛应用于控制理论、交通工程、通信工程、系统工程等众多领域，是更复杂的网络流问题的基础子问题 [1]，许多基于此问题的优化问题 [2] [3] [4] [5] [6] 都被研究了。由于现实世界经常出现无法用大量数据模拟来生成概率分布函数的情景，这时为了处理这些问题，通常需要寻求该领域专家的帮助，根据其主观判断给出经验分布函数，用于解决现实问题。为了合理地处理专家经验数据 [7]，文献 [8] 于2007年提出了不确定理论，自此许多不确定优化问题都被解决了。但现实世界通常是存在多重不确定性的，为了处理具有双重不确定性——随机性与不确定性共存的网络，基于文献 [9]，文献 [10] 于2013年建模了不确定随机网络。基于上述原因，本文将在此网络的基础上讨论具有资源约束的最短路径问题这个具有实际应用价值的问题，并基于文献 [11] 提出的新型互熵定义，尝试设计一种优化模型用于此问题。

2. 预备知识

2.1. 机会理论

定义1 [9]：若 $\left(\text{Ω},\mathcal{A},\mathrm{Pr}\right)$ 为随机事件空间， $\left(\text{Γ},\mathcal{L},\mathcal{M}\right)$ 为一个不确定事件空间，则以 $\text{Γ}\times \text{Ω}$ 为全集，以 为乘积 $\sigma -$ 代数，以 $\mathcal{M}\times \mathrm{Pr}$ 为乘积测度函数的事件空间 $\left(\text{Γ},\mathcal{L},\mathcal{M}\right)\times \left(\text{Ω},\mathcal{A},\mathrm{Pr}\right)$ 为一个机会事件空间。若 $\text{Θ}\in \mathcal{L}\times \mathcal{A}$ 是此空间中的一个事件，则 $\text{Θ}$ 的机会测度定义如下：

$Ch\left\{\text{Θ}\right\}={\displaystyle {\int }_0^1\mathrm{Pr}\left\{\omega \in \text{Ω}|\mathcal{M}\left\{\gamma \in \text{Γ}|\left(\gamma ,\omega \right)\in \text{Θ}\right\}\ge x\right\}}\text{d}x$ (1)

定义2 [9]：不确定随机变量是一个从机会空间 $\left(\text{Γ},\mathcal{L},\mathcal{M}\right)\times \left(\text{Ω},\mathcal{A},\mathrm{Pr}\right)$ 到实数集 $\mathcal{R}$ 上的映射，即 $\xi \left(\gamma ,\omega \right)\in \mathcal{R}$，若B是 $\mathcal{R}$ 上的Borel集，则 $\left\{\xi \in B\right\}$ 是 $\mathcal{L}\times \mathcal{A}$ 上的一个事件。则其机会分布函数为

$\text{Φ}\left(x\right)=Ch\left\{\xi \le x\right\},\forall x\in \mathcal{R}$ (2)

注释1 $\forall x\in \mathcal{R},Ch\left\{\xi \le x\right\}=\text{Φ}\left(x\right),Ch\left\{\xi >x\right\}=1-\text{Φ}\left(x\right).$

定理1 [10] (运筹法则)：假设 ${\eta }_1,{\eta }_2,\cdots ,{\eta }_m$ 是一列相互独立的随机变量，其概率分布函数分别为 $Y_1,Y_2,\cdots ,Y_m$，假设 ${\tau }_1,{\tau }_2,\cdots ,{\tau }_n$ 是一列相互独立的不确定变量，对应的不确定分布函数分别为 ${\Upsilon }_1,{\Upsilon }_2,\cdots ,{\Upsilon }_n$。 $f:{\mathcal{R}}^{m+n}\to \mathcal{R}$ 为一个可测函数，则

$\xi =f\left({\eta }_1,{\eta }_2,\cdots ,{\eta }_m,{\tau }_1,{\tau }_2,\cdots ,{\tau }_n\right)$ (3)

的机会分布函数为：

$\text{Φ}\left(x\right)={\displaystyle {\int }_{{\mathcal{R}}^m}F\left(x;y_1,y_2,\cdots ,y_m\right)\text{d}{Y}_1\left(y_1\right)\text{d}{Y}_2\left(y_2\right)\cdots \text{d}{Y}_m\left(y_m\right)}$ (4)

其中对于 $\forall y_i\in \mathcal{R}\left(1\le i\le m\right)$，$F\left(x;y_1,y_2,\cdots ,y_m\right)$ 是不确定变量 $f\left({\eta }_1,{\eta }_2,\cdots ,{\eta }_m,{\tau }_1,{\tau }_2,\cdots ,{\tau }_n\right)$ 的不确定分布。

注释2 [10] 假设 $f\left({\eta }_1,{\eta }_2,\cdots ,{\eta }_m,{\tau }_1,{\tau }_2,\cdots ,{\tau }_n\right)$ 关于 ${\tau }_1,{\tau }_2,\cdots ,{\tau }_k$ 严格单调递增，关于 ${\tau }_{k+1},{\tau }_{k+2},\cdots ,{\tau }_n$ 严格单调递减，且 ${\Upsilon }_1,{\Upsilon }_2,\cdots ,{\Upsilon }_n$ 连续，则

$F\left(x;y_1,y_2,\cdots ,y_m\right)={\sup }_{f\left(y_1,\cdots ,y_m,z_1,\cdots ,z_n\right)=x}\left({\min }_{1\le i\le k}{\Upsilon }_i\left(z_i\right)\wedge {\min }_{k+1\le i\le n}\left(1-{\Upsilon }_i\left(z_i\right)\right)\right)$ (5)

定义3 [9]：若不确定随机变量 $\xi$ 的机会分布为 $\text{Φ}$，则其期望值为

$E\left[\xi \right]={\displaystyle {\int }_0^{+\infty }\left(1-\Phi \left(x\right)\right)\text{d}x}-{\displaystyle {\int }_{-\infty }^0\Phi \left(x\right)\text{d}x}$ (6)

其中对于 $\forall y_i\in \mathcal{R}\left(1\le i\le m\right)，E\left[F\left(x;y_1,y_2,\cdots ,y_m,{\tau }_1,{\tau }_2,\cdots ,{\tau }_n\right)\right]$ 是不确定随机变量 $f\left({\eta }_1,{\eta }_2,\cdots ,{\eta }_m,{\tau }_1,{\tau }_2,\cdots ,{\tau }_n\right)$ 期望值。

定义4 [11]：假设 ${\eta }_1$ 和 ${\eta }_2$ 为两个不确定随机变量，对应的机会分布函数分别为 ${\text{Φ}}_1$ 和 ${\text{Φ}}_2$，则 ${\eta }_1$ 和 ${\eta }_2$ 之间的互熵 $D\left[{\eta }_1;{\eta }_2\right]$ 定义为：

$D\left[{\eta }_1;{\eta }_2\right]={\displaystyle {\int }_{-\infty }^{+\infty }\left|{\Phi }_1\left(x\right)-{\Phi }_2\left(x\right)\right|\text{d}x}$ (7)

定理2 [11]：假设 ${\eta }_1$ 和 ${\eta }_2$ 为两个不确定随机变量，对应的正则机会分布函数分别为 ${\text{Φ}}_1$ 和 ${\text{Φ}}_2$，则 ${\eta }_1$ 和 ${\eta }_2$ 之间的互熵 $D\left[{\eta }_1;{\eta }_2\right]$ 可以根据两个变量的逆机会分布函数计算：

$D\left[{\eta }_1;{\eta }_2\right]={\displaystyle {\int }_0^1\left|{\Phi }_1^{-1}\left(\alpha \right)-{\Phi }_2^{-1}\left(\alpha \right)\right|\text{d}\alpha }$ (8)

例1 [10]：假设 ${\eta }_1,{\eta }_2,\cdots ,{\eta }_m$ 是一列相互独立的随机变量，其概率分布函数分别为 $Y_1,Y_2,\cdots ,Y_m$，假设 ${\tau }_1,{\tau }_2,\cdots ,{\tau }_n$ 是一列相互独立的不确定变量，对应的不确定分布函数分别为 ${\Upsilon }_1,{\Upsilon }_2,\cdots ,{\Upsilon }_n$。设 ${\xi }_1$ 为所有变量的和，则

${\xi }_1={\eta }_1+{\eta }_2+\cdots +{\eta }_m+{\tau }_1+{\tau }_2+\cdots +{\tau }_n$ (9)

的机会分布为

$\text{Φ}(x)={\displaystyle {\int }_{-\infty }^{+\infty }\Upsilon \left(x-y\right)\text{dY}\left(y\right)}$ (10)

其中

$\text{Y}\left(y\right)={\displaystyle {\int }_{y_1+y_2+\cdots +y_m\le y}\text{d}{Y}_1\left(y_1\right)\text{d}{Y}_2\left(y_2\right)\cdots \text{d}{Y}_m\left(y_m\right)}$ (11)

是随机变量的和： ${\eta }_1+{\eta }_2+\cdots +{\eta }_m$ 的概率分布，

${\rm Y}\left(z\right)={\sup }_{z_1+z_2+\cdots +z_n=z}{\Upsilon }_1\left(z_1\right)\wedge {\Upsilon }_2\left(z_2\right)\wedge \cdots \wedge {\Upsilon }_n\left(z_n\right)$ (12)

是不确定变量的和： ${\tau }_1+{\tau }_2+\cdots +{\tau }_n$ 的不确定分布。

2.2. 不确定随机网络

定义5 [12]：假设 $\mathcal{N}$ 是一个网络中点的集合， $\mathcal{U}$ 是网络中权重是不确定变量的边的集合，记 $\mathcal{U}=\left\{\left(i,j\right)|\left(i,j\right)是不确定边\right\}$，$\mathcal{R}$ 是网络中权重是随机变量的边的集合，记 $\mathcal{R}=\left\{\left(i,j\right)|\left(i,j\right)是随机边\right\}$，$\mathcal{W}$ 是网络中的边的权重的集合，包含所有的随机边和不确定边，记 $\mathcal{W}=\left\{w_{ij}|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right\}$，则满足上面条件的四元数组 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W}\right)$ 称为一个不确定随机网络。

例2：存在7个节点的一个不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W}\right)$ 如下图1所示，其中

$\begin{array}{l}\mathcal{N}=\left\{1,2,3,4,5,6,7\right\},\\ \mathcal{U}=\left\{\left(1,5\right),\left(2,3\right),\left(3,7\right),\left(4,5\right),\left(4,6\right),\left(5,6\right),(6,7)\right\},\\ \mathcal{R}=\left\{\left(1,2\right),\left(1,4\right),\left(2,4\right),\left(4,7\right)\right\}\\ \mathcal{W}=\left\{{\xi }_{12},{\xi }_{14},{\tau }_{15},{\tau }_{23},{\xi }_{24},{\tau }_{37},{\tau }_{45},{\tau }_{46},{\xi }_{47},{\tau }_{56},{\tau }_{67}\right\}\end{array}$

图1. 一个7节点不确定随机网络图

3. 不确定随机网络带资源约束的最短路问题新型互熵优化模型及实验

3.1. 问题描述

带资源约束的最短路径问题本质上是一个最短路问题，它的目标是寻找一条从源节点1到目的节点n的满足资源约束的路径中最短的路径。

为了方便研究，在介绍模型之前，我们首先做一些假设：

1) 在本文中我们研究单源节点带资源约束的路径问题，节点1被设置为唯一的源节点，节点n被设置为唯一的终点。

2) 假定不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 有向且无环，其中 $\mathcal{N}$ 为网络中节点的集合，一般设置为n个节点，即 $\mathcal{N}=\left\{1,2,\cdots ,n\right\}$，$\mathcal{U}$ 为网络中不确定边的集合，即 $\mathcal{U}=\left\{\left(i,j\right)|\left(i,j\right)是不确定边\right\}$，$\mathcal{R}$ 网络中随机边的集合，即 $\mathcal{R}=\left\{\left(i,j\right)|\left(i,j\right)是随机边\right\}$，$\mathcal{W}$ 为网络中所有的边的权重的集合，即 $\mathcal{W}=\left\{w_{ij}|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right\}$，$C$ 为资源成本矩阵(可设定为消耗时间，建设费用等，本文统一设置为成本)，并给定一个成本约束值d，被选择的路径还需要满足 ${\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{x}_{ij}}{c}_{ij}\le d$ 这一条件的约束，记约束条件为 $c\left(x\right)\le d$。

3) 假设研究的网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 中所有的边 $\left(i,j\right)$ 的权重为正则不确定随机变量，也就是说边的权重 $w_{ij}$，要么是正则不确定变量要么是正的随机变量，不存在其他情况。

4) 网络中存在的所有不确定随机变量相互独立，即所有的不确定变量相互独立，且所有的随机变量也相互独立。

5) 为了方便建模，在本文中使用

$L=\left\{x_{ij}|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right\}$ (13)

来代表不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W}\right)$ 中的一条从节点1到节点 $n$ 带资源约束的路径，其中 $x_{ij}\in \left\{0,1\right\}$，$x_{ij}=1$ 代表边 $\left(i,j\right)$ 出现在此条路径当中，反之，若 $x_{ij}=0$，则说明 $\left(i,j\right)$ 没有出现在此路径中。若 ${\xi }_{ij}$ 代表 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W}\right)$ 中边的权重(通常为距离、消费、时间等的一种表现形式)，则 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 中一条路径 $L$ 的权值为

${\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{x}_{ij}{\xi }_{ij}}$ (14)

另外可证明，若 $L$ 为网络中的一条带资源约束的路径，当且仅当：

$\{\begin{array}{l}\begin{array}{l}{\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{x}_{ij}{c}_{ij}}\le d\hfill \\ \begin{array}{cc}{\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{x}_{ij}}-{\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{x}_{ji}}& \{\begin{array}{ll}1,\hfill & i=1\hfill \\ 0,\hfill & 2\le i\le n-1\hfill \\ -1,\hfill & i=n\hfill \end{array}\end{array}\hfill \end{array}\hfill \\ x_{ij}\in \left\{0,1\right\},\forall \left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\hfill \end{array}$ (15)

3.2. 新型互熵优化模型

定理3：(不确定随机带资源约束的最短路径问题的理想路径机会分布函数)假定不确定随机网络为 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$，其中的不确定边 $\left(i,j\right)\in \mathcal{U}$ 的权重 $w_{ij}$ 对应的不确定分布为 ${\Upsilon }_{ij}$，其中的随机边 $\left(i,j\right)\in \mathcal{R}$ 的权重 $w_{ij}$ 对应的概率分布为 ${\text{Y}}_{ij}$，网络连接的成本矩阵 $C={\left(c_{ij}\right)}_{n\times n}$，限定的资源约束最大值为d，记路径 $\left(x|x_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right)$ 的连接成本 ${\displaystyle \underset{(i,j)\in L}{\overset{}{\sum }}{x}_{ij}{c}_{ij}}$ 为 $c\left(x\right)$，则从源节点到目的节点的资源约束最短路径 $L=\left(x|x_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right)$ 的机会分布函数为

$\text{Φ}\left(x\right)={\displaystyle {\int }_0^{+\infty }\cdots }{\displaystyle {\int }_0^{+\infty }G\left(x;y_{ij},\left(i,j\right)\in \mathcal{R},c\left(x\right)\le d\right)}{\displaystyle {\prod }_{\left(i,j\right)\in \mathcal{R}}\text{d}{Y}_{ij}\left(y_{ij}\right)}$ (16)

其中 $G\left(x;y_{ij},\left(i,j\right)\in \mathcal{R}，c\left(x\right)\le d\right)$ 由其逆不确定分布决定

$G^{-1}\left(\alpha ;y_{ij},\left(i,j\right)\in \mathcal{R}，c\left(x\right)\le d\right)=g\left(s_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}，c\left(x\right)\le d\right)$ (17)

$s_{ij}=\{\begin{array}{l}{\Upsilon }^{-1}\left(\alpha \right),\hfill \\ y_{ij},\hfill \end{array}\begin{array}{c}\left(i,j\right)\in \mathcal{U}\\ \left(i,j\right)\in \mathcal{R}\end{array}$ (18)

根据给定的不同的 $\alpha ,g$ 可以根据Flyod算法计算。

定理4：若 $L=\left\{x_{ij}|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right\}$ 为不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 中的一条约束路径，对应的机会分布函数为 ${\text{Φ}}_L\left(x\right)$，此网络的理想资源约束路径的机会分布函数为 $\text{Φ}\left(x\right)$，则对于网络中的任意路径 $L$，有 ${\text{Φ}}_L\left(x\right)\le \text{Φ}\left(x\right)$ 恒成立。

定义6：(带资源约束的新型互熵最小的最短路径)假设一个不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 的理想资源约束路径对应的函数为 机会分布函数为 $\text{Φ}\left(x\right)$，网络中存在的其他路径 $L$，对应的机会分布函数为 ${\text{Φ}}_L\left(x\right)$。若存在某条路径 $L^{*}$，对应的函数为 ${\xi }^{*}$，使得其与理想路径的新型互熵 最小，即对 $\forall x\in \mathcal{R}$，和所有的资源约束路径 $L$，有下式成立：

${\displaystyle {\int }_{-\infty }^{+\infty }\left|\Phi \left(x\right)-{\Phi }_{L^{*}}\left(x\right)\right|\text{d}x}\le {\displaystyle {\int }_{-\infty }^{+\infty }\left|\Phi \left(x\right)-{\Phi }_L\left(x\right)\right|\text{d}x}$ (19)

则称路径 $L^{*}$ 为此不确定随机网络的带资源约束的新型互熵最小的最短路径。

根据定义6，如果一条路径 $L^{*}=\left\{x_{ij}|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right\}$ 是一条新型互熵最小资源约束最短路径，则它应该是满足下述模型的最优解：

$\{\begin{array}{l}\underset{\left\{x_{ij,}\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right\}}{\min }{\displaystyle {\int }_{-\infty }^{+\infty }\left|\Phi \left(x\right)-{\Phi }_L\left(x|x_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right)\right|\text{d}x}\hfill \\ \begin{array}{c}\begin{array}{l}\text{subjectto:}\hfill \\ \hfill \end{array}\\ \underset{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{c}_{ij}\le d\end{array}\hfill \\ \underset{j:\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}-\underset{j:\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{{\displaystyle \sum }}{x}_{ji}=\{\begin{array}{l}1,i=1\hfill \\ 0,2\le i\le n-1\hfill \\ -1,i=n\hfill \end{array}\hfill \\ x_{ij}=\left\{0,1\right\},\forall \left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\hfill \end{array}$ (20)

其中 $\text{Φ}\left(x\right)$ 是理想资源约束路径的机会分布函数，

${\Phi }_L\left(x|\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right)=\mathcal{C}h\left\{\underset{\left(i,j\right)\in \mathcal{U}}{{\displaystyle \sum }}{x}_{ij}{\tau }_{ij}+\underset{\left(i,j\right)\in \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{\xi }_{ij}\le x\right\}$ (21)

为网络中其他资源约束路径的机会分布函数。

定理5：给定一个不确定随机网络 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\xi ,C\right)$，$\text{Φ}\left(x\right)$ 是此网络的理想资源约束路径的机会分布函数， $\left(x|x_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right)$ 为此网络中从源节点1到目的节点n的一条路径，网络中不确定边，即 $\left(i,j\right)\in \mathcal{U}$ 的权重为不确定变量 ${\tau }_{ij}$，其对应的不确定分布为 ${\gamma }_{ij}$，网络中随机边，即 $\left(i,j\right)\in \mathcal{R}$ 的权重为随机变量 ${\xi }_{ij}$，其对应的概率分布为 $Y_{ij}$。则模型(20)可以转化为下面的模型：

$\{\begin{array}{l}\underset{\left\{x_{ij,}\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\right\}}{\min }{\displaystyle {\int }_{-\infty }^{+\infty }\left|\Phi \left(x\right)-{\displaystyle {\int }_{-\infty }^{+\infty }\gamma \left(x-\underset{\left(i,j\right)\in \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{y}_{ij}\right)\text{d}Y\left(y\right)}\right|\text{d}x}\hfill \\ \begin{array}{c}\begin{array}{c}\text{subjectto:}\\ \end{array}\\ \underset{\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{c}_{ij}\le d\end{array}\hfill \\ \underset{j:\left(i,j\right)\in \mathcal{U}\cup \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}-\underset{j:\left(i,j\right)\in \mathcal{U}{{\displaystyle \cup }}^{\text{}}\mathcal{R}}{{\displaystyle \sum }}{x}_{ji}=\{\begin{array}{l}1,i=1\hfill \\ 0,2\le i\le n-1\hfill \\ -1,i=n\hfill \end{array}\hfill \\ x_{ij}=\left\{0,1\right\},\forall \left(i,j\right)\in \mathcal{U}\cup \mathcal{R}\hfill \end{array}$ (22)

其中

$\Phi \left(x\right)={\displaystyle {\int }_0^{+\infty }\cdots }{\displaystyle {\int }_0^{+\infty }G\left(x;y_{ij},\left(i,j\right)\in \mathcal{R},c\left(x\right)\le d\right){\displaystyle {\prod }_{\left(i,j\right)\in \mathcal{R}}\text{d}{Y}_{ij}\left(y_{ij}\right)}}$ (23)

$Y\left(y\right)={\displaystyle {\int }_{y_1+y_2+\cdots +y_m\le y}\text{d}{Y}_1\left(y_1\right)\text{d}{Y}_2\left(y_2\right)\cdots \text{d}{Y}_m\left(y_m\right)}$ (24)

$\Upsilon \left(r\right)={\sup }_{{\displaystyle {\sum }_{\left(i,j\right)\in \mathcal{U}}{x}_{ij}{r}_{ij}=r}}\left({\min }_{\left(i,j\right)\in \mathcal{U}}{\Upsilon }_{ij}\left(x_{ij}{r}_{ij}\right)\right)$ (25)

证明：根据定理3可得，网络的理想路径机会分布函数为

$\text{Φ}\left(x\right)={\displaystyle {\int }_0^{+\infty }\cdots }{\displaystyle {\int }_0^{+\infty }G\left(x;y_{ij},\left(i,j\right)\in \mathcal{R},c\left(x\right)\le d\right){\displaystyle {\prod }_{\left(i,j\right)\in \mathcal{R}}\text{d}{Y}_{ij}\left(y_{ij}\right)}}$ (26)

假设 $L_{}^{*}=\left(x|x_{ij},\left(i,j\right)\in \mathcal{U}\cup \mathcal{R},c\left(x\right)\le d\right)$ 为此网络中从源节点1到目的节点n的一条资源约束路径，则

$\begin{array}{c}{\Phi }_L\left(x\right)=\mathcal{C}h\left\{\underset{\left(i,j\right)\in \mathcal{U}}{{\displaystyle \sum }}{x}_{ij}{\tau }_{ij}+\underset{\left(i,j\right)\in \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{\xi }_{ij}\le x\right\}\\ ={\displaystyle {\int }_{\mathcal{R}}\mathcal{M}\left\{\underset{\left(i,j\right)\in \mathcal{U}}{{\displaystyle \sum }}{x}_{ij}{\tau }_{ij}+y\le x\right\}Y}\left(y\right)\end{array}$ (27)

其中 $Y\left(y\right)$ 是 ${\displaystyle \underset{(i,j)\in R}{\sum }{x}_{ij}}{\xi }_{ij}$ 的概率分布函数。

由于所有的不确定随机变量 ${\xi }_{ij}$ 彼此相互独立，故

$Y\left(y\right)={\displaystyle {\int }_{y_1+y_2+\cdots +y_m\le y}\text{d}{Y}_1\left(y_1\right)\text{d}{Y}_2\left(y_2\right)\cdots \text{d}{Y}_m\left(y_m\right)}$ (28)

又由于所有的不确定随机变量相互独立，故根据例1有

$\begin{array}{c}\mathcal{M}\left\{\underset{\left(i,j\right)\in \mathcal{U}}{{\displaystyle \sum }}{x}_{ij}{\tau }_{ij}\le x-y\right\}=\underset{{\displaystyle {\sum }_{(i,j)\in \mathcal{U}}{x}_{ij}{r}_{ij}=x-y}}{\sup }\left(\underset{(i,j)\in \mathcal{U}}{\min }{\Upsilon }_{ij}\left(x_{ij}{r}_{ij}\right)\right)\\ =\Upsilon \left(x-\underset{(i,j)\in \mathcal{R}}{{\displaystyle \sum }}{x}_{ij}{y}_{ij}\right).\end{array}$ (29)

结合式子(27) (28) (29)带入目标函数方程，得证。

3.3. 新型互熵优化模型算法及数值实验

由于在模型求解过程中都涉及到理想路径机会分布，但对于此类问题而言，直接给出机会分布函数的显式表达式是很困难的，于是在本文中我们设计了一个线性插值的办法用来拟合机会分布函数，步骤如下：

算法1：(用于求解理想带资源约束路径的机会分布)。

步骤1：对于不确定随机网络中的每个随机变量，我们根据随机变量的概率分布函数，使用蒙特卡洛模拟的方法生成1000个数，随机变量的取值便为蒙特卡洛模拟生成的依数值大小排序后的随机数值。

步骤2：设置矩阵 $T=\left[0,0.01,\cdots ,0.99,1\right]$，$\alpha$ 依次从T中取值，根据上述过程生成的数值计算 $G^{-1}\left(\alpha \right)$，得到不确定分布 $G\left(x\right)$ 的离散形式。

步骤3：对步骤2生成的离散形式的 $G\left(x\right)$，进行线性插值，并带入(4)式计算理想路径的机会分布 $\text{Φ}\left(x\right)$。

基于3.2节提出模型——不确定随机网络下的带资源约束的最短路径新型互熵优化模型(22)，我们设计了下面算法用来求解。

算法2：(适用于不确定随机网络的带资源约束的最短路径新型互熵优化模型(22)的求解)。

步骤1：结合定理1并利用上述提出的算法1计算理想路径的机会分布函数 $\text{Φ}\left(x\right)$。

步骤2：利用智能算法( $A^{*}$ 算法、广度优先算法、蚁群算法、遗传算法等均可)搜寻网络中的所有路径并储存。

步骤3：根据成本矩阵计算每条路径的成本，去掉不符合条件约束的路径。

步骤4：计算步骤3中储存所有路径与理想路径之间的新型互熵值。

步骤5：比较上一步得到的新型互熵值，选择新型互熵值最小的路径，即为所求。

下面给出一个数值实验，来验证我们提出的算法与模型的有效性。

例3给定一个具有8个节点12条边的不确定随机网络图 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 如图2所示，假设不确定权重为 ${\tau }_{23},{\tau }_{25},{\tau }_{38},{\tau }_{45},{\tau }_{46},{\tau }_{58},{\tau }_{67},{\tau }_{78}$ 它们为相互独立的正则不确定变量，且对应的正则不确定分布为 ${\Upsilon }_{23},{\Upsilon }_{25},{\Upsilon }_{38},{\Upsilon }_{45},{\Upsilon }_{46},{\Upsilon }_{58},{\Upsilon }_{67},{\Upsilon }_{78}$，随机边的权重为 ${\xi }_{12},{\xi }_{14},{\xi }_{16}$，它们为相互独立的不确定变量，对应的概率分布函数分别为 ${{\rm K}}_{12},{{\rm K}}_{14},{{\rm K}}_{16}$，假设此不确定随机网络图 $\left(\mathcal{N},\mathcal{U},\mathcal{R},\mathcal{W},C\right)$ 的权重与成本如表1所示，其中 $\mathcal{U}\left(a,b\right)$ 代表线形不确定分布， $\mathcal{Z}\left(a,b,c\right)$ 代表Z字形不确定分布。给定成本约束值d = 200。

图2. 8节点12条边不确定随机网络

表1. 图2的不确定随机网络的边权值与连接成本表

根据定理3可得

$\text{Φ}\left(x\right)={\displaystyle {\int }_0^{+\infty }{\displaystyle {\int }_0^{+\infty }{\displaystyle {\int }_0^{+\infty }G\left(x;y_{12},y_{14},y_{16},c\left(x\right)\le 200\right)\text{d}{Y}_{12}\left(y_{12}\right)\text{d}{Y}_{14}\left(y_{14}\right)\text{d}{Y}_{16}\left(y_{16}\right)}}}$ (30)

其中 $G\left(x;y_{12},y_{14},y_{16},c\left(x\right)\le 200\right)$ 可以根据其逆不确定分布计算。利用深度优先算法搜索网络发现一共有6条路径，但通过计算成本发现其中有一条路径 $L\left(1\to 4\to 6\to 7\to 8\right)$ 的成本值为238 > 200，故在第三步中完成后，提前删除此路径，将剩余的五条路径进行算法的第四步运算计算新型互熵值，计算结果列在表2中。

通过比较新型互熵的数值结果，我们发现路径3 $\left(1\to 4\to 5\to 8\right)$ 新型互熵值最小，而且通过图3的机会分布图也可以验证我们的计算结果的有效性——路径3是最接近理想约束路径的，即 $\left(1\to 4\to 5\to 8\right)$ 为此不确定随机网络下的带资源约束的新型互熵最小的最短路径。

表2. 新型互熵计算结果

图3. 理想资源约束路径与不确定随机网络中的其他约束路径的机会分布

4. 文章小结

本文研究了带资源约束的不确定随机最短路径问题，对此问题建立了新型互熵优化模型，并设计了相应的数值算法，用于求解，最后通过给出的数值算例验证了模型有效性。

基金项目

中央高校基本科研业务费专项资金资助(No. 2019MS048)。

文章引用

焦雨洁,高 欣. 不确定随机网络下的带资源约束的最短路径问题
The Shortest Path Problem with Resource Constraints in Uncertain Random Networks[J]. 应用数学进展, 2021, 10(05): 1622-1630. https://doi.org/10.12677/AAM.2021.105172

参考文献