不确定随机网络下的带资源约束的最短路径问题
The Shortest Path Problem with Resource Constraints in Uncertain Random Networks
摘要: 本文利用机会理论这种新的数学工具，研究了不确定随机网络下的带资源约束的最短路径问题，即在具有双重不确定性的网络中，寻找一条始于源节点终于目的节点并满足资源约束的最短路径问题。根据机会理论的运筹法则，我们给出了不确定随机网络带资源约束的最短路径问题的机会分布函数，并应用不确定随机变量的新型互熵建立了一个模型——带资源约束的新型互熵最小最短路径优化模型，用于解决这个问题，与之相对应的一个算法也被提出，本文最后设计了一个数值实验用来验证模型的有效性。
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.
文章引用：焦雨洁, 高欣. 不确定随机网络下的带资源约束的最短路径问题[J]. 应用数学进展, 2021, 10(5): 1622-1630. https://doi.org/10.12677/AAM.2021.105172

参考文献

[1] 徐庆征, 柯熙政. 必经点最短路径问题模型及相应遗传算法研究[J]. 系统工程与电子技术, 2009, 31(2): 459-462.
[2] Deng, Y., Chen, Y., Zhang, Y., et al. (2012) Fuzzy Dijkstra Algorithm for Shortest Path Problem under Uncertain Environment. Applied Soft Computing, 12, 1231-1237. [Google Scholar] [CrossRef] 
[3] Sheng, Y. and Gao Y. (2016) Shortest Path Problem of Uncertain Random Network. Computers & Industrial Engineering, 99, 97-105. [Google Scholar] [CrossRef] 
[4] Horváth, M. and Kis, T. (2016) Solving Resource Constrained Shortest Path Problems with LP-Based Methods. Computers & Operations Research, 73, 150-164. [Google Scholar] [CrossRef] 
[5] Thomas, B.W., Calogiuri, T. and Hewitt, M. (2019) An Exact Bidirectional A⋆ Approach for Solving Resource-Constrained Shortest Path Problems. Networks, 73, 187-205. [Google Scholar] [CrossRef] 
[6] Lin, L.H., Wu, C.Z. and Ma, L. (2020) A Genetic Algorithm for the Fuzzy Shortest Path Problem in a Fuzzy Network. Complex & Intelligent Systems, 7, 225-234. [Google Scholar] [CrossRef] 
[7] Liu, B. (2012) Why Is There a Need for Uncertainty Theory. Journal of Uncertain Systems, 6, 3-10.
[8] Liu, B. (2010) Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty. Springer-Verlag, Berlin.
[9] Liu, Y.H. (2013) Uncertain Random Variables: A Mixture of Uncertainty and Randomness. Soft Computing, 17, 625-634. [Google Scholar] [CrossRef] 
[10] Liu, Y.H. (2013) Uncertain Random Programming with Applications. Fuzzy Optimization and Decision Making, 12, 153-169.
[11] Jia, L., Yang, X. and Gao, X. (2018) A New Definition of Cross Entropy for Uncertain Random Variables and Its Application. Journal of Intelligent & Fuzzy Systems, 35, 1193-1204. [Google Scholar] [CrossRef] 
[12] Liu, B. (2014) Uncertain Random Graph and Uncertain Random Network. Journal of Uncertain Systems, 8, 2592-2599.

为你推荐