突发灾害下可靠路径搜索模型与算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (28): 1-3.

突发灾害下可靠路径搜索模型与算法

缪成¹,吴启迪¹,许维胜²

1.同济大学经济与管理学院,上海 200092
2.同济大学电子与信息工程学院,上海 200092

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-01 发布日期:2007-10-01
通讯作者: 缪成

Model and algorithm of reliable path finding under sudden-onset disaster

MIAO Cheng¹,WU Qi-di¹,XU Wei-sheng²

1.School of Economics and Management,Tongji University,Shanghai 200092,China
2.School of Electronics and Information Engineering,Tongji University,Shanghai 200092,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-10-01 Published:2007-10-01
Contact: MIAO Cheng

摘要/Abstract

摘要： 在分析突发灾害爆发时可靠路径搜索问题特点的基础上,提出了一种在不确定网络中不依赖于弧的旅行时间概率分布的可靠路径搜索方法。该方法通过场景集描述网络旅行时间的不确定性,应用Minimax理论构建求解所有场景下可靠路径的数学模型,并设计了问题求解算法,分析了算法的时间复杂性,最后通过典型算例对算法进行了验证。

关键词: 可靠路径搜索, 不确定性网络, 最小最大

Abstract: Characteristics of reliable path finding under sudden-onset disaster are analyzed.A method of reliable path finding under uncertain network,which is independent of probability distribution of arcs’ travel time,is brought forward on the basis of those characteristics.The uncertainty of travel time of road network is depicted by means of scenario union firstly,then a path finding modal applied minimax theorem is constructed for obtaining most reliable path of all scenarios.To solve this modal,a algorithm is devised and its complexity is analyzed.The algorithm is validated by one typical calculation example at last.

Key words: reliable path finding, network under uncertainty, minimax

缪成¹,吴启迪¹,许维胜². 突发灾害下可靠路径搜索模型与算法[J]. 计算机工程与应用, 2007, 43(28): 1-3.

MIAO Cheng¹,WU Qi-di¹,XU Wei-sheng². Model and algorithm of reliable path finding under sudden-onset disaster[J]. Computer Engineering and Applications, 2007, 43(28): 1-3.

[1]	王晓初1，王士同1，包芳2. 基于数据分布一致性最小最大概率机[J]. 计算机工程与应用, 2016, 52(16): 79-84.
[2]	葛宇1，梁静2，许波3，余建平4. 基于蛙跳算法的无线传感器网络节点定位[J]. 计算机工程与应用, 2012, 48(20): 126-130.
[3]	李剑，尚赵伟，张凌峰. 特征加权最小最大概率机[J]. 计算机工程与应用, 2012, 48(11): 102-106.
[4]	万树平. 对方案有偏好的最小最大偏差多属性决策方法[J]. 计算机工程与应用, 2009, 45(19): 195-197.
[5]	张奋潘梅生邹北骥. 基于SR-树的空间对象最近邻查询[J]. 计算机工程与应用, 2007, 43(4期): 173-175.