不确定随机网络下的带资源约束的最短路径问题

The Shortest Path Problem with Resource Constraints in Uncertain Random Networks

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

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.