|
|||||
|
|
The robust shortest path problem in series-parallel multidigraphs with interval data |
|
| Authors: | Adam Kasperski Pawe? Zieliński |
| Affiliation: | a Institute of Industrial Engineering and Management, Wroc?aw University of Technology, Wybrze?e Wyspiańskiego 27, 50-370 Wroc?aw, Poland b Institute of Mathematics, Wroc?aw University of Technology, Wybrze?e Wyspiańskiego 27, 50-370 Wroc?aw, Poland |
| Abstract: | In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed. |
| Keywords: | Robust optimization NP-hardness Pseudopolynomial algorithm Shortest path problem Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ | |