| 不可恢复道路堵塞路径选择问题及其算法 |
| |
| 引用本文： | 苏兵,徐渝. 不可恢复道路堵塞路径选择问题及其算法[J]. 运筹与管理, 2005, 14(3): 1-4 |
| |
| 作者姓名： | 苏兵 徐渝 |
| |
| 作者单位： | 西安交通大学,管理学院,陕西,西安,710049 |
| |
| 基金项目： | 国家自然科学基金资助项目(No.10371094，70471035) |
| |
| 摘 要： | 针对不可恢复道路堵塞的路径选择问题，分析了堵塞发生的不同起始时间对通过被堵塞边的费用(时间)产生的影响，这种影响引起的后效性使得这个问题不适合用动态规划中逆序推算方法求解。本设计了一种算法(MDA)，对经典的Dijkstra算法中的权值计算进行了修正，证明了算法的复杂性为O(n^2)，并用该算法对模型进行了求解。最后通过一个算例分析，对算法进行了验证。
|
| 关 键 词： | 路径选择问题 MD算法 Dikstra算法 堵塞不可恢复 |
| 文章编号： | 1007-3221(2005)03-0001-04 |
| 修稿时间： | 2004-10-29 |
Irrecoverable Blockage Routing Problem and Algorithms |
| |
| SU Bing,XU Yu. Irrecoverable Blockage Routing Problem and Algorithms[J]. Operations Research and Management Science, 2005, 14(3): 1-4 |
| |
| Authors: | SU Bing XU Yu |
| |
| Abstract: | For the irrecoverable routing problem, the blocked edge cost (time )is analyzed under the effect of the different starting time of blockages ,and the after-effect makes the problem unfit for a converse solution of dynamic programming. A new algorithm(MDA) for the irrecoverable blockage routing problem is proposed, that is a modification to the weight computation of Dijkstra algorithm. The complexity of the algorithm is O(n~2). A practical numeral analysis is given and the algorithm is validated. |
| |
| Keywords: | routing problem MD algorithm Dijkstra algorithm irrecoverable blockage |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
