کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10346583 | 698798 | 2011 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reduction approaches for robust shortest path problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Reduction approaches for robust shortest path problems Reduction approaches for robust shortest path problems](/preview/png/10346583.png)
چکیده انگلیسی
We investigate the uncertain versions of two classical combinatorial optimization problems, namely the Single-Pair Shortest Path Problem (SP-SPP) and the Single-Source Shortest Path Problem (SS-SPP). The former consists of finding a path of minimum length connecting two specific nodes in a finite directed graph G; the latter consists of finding the shortest paths from a fixed node to the remaining nodes of G. When considering the uncertain versions of both problems we assume that cycles may occur in G and that arc lengths are (possibly degenerating) nonnegative intervals. We provide sufficient conditions for a node and an arc to be always or never in an optimal solution of the Minimax regret Single-Pair Shortest Path Problem (MSP-SPP). Similarly, we provide sufficient conditions for an arc to be always or never in an optimal solution of the Minimax regret Single-Source Shortest Path Problem (MSS-SPP). We exploit such results to develop pegging tests useful to reduce the overall running time necessary to exactly solve both problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 38, Issue 11, November 2011, Pages 1610-1619
Journal: Computers & Operations Research - Volume 38, Issue 11, November 2011, Pages 1610-1619
نویسندگان
Daniele Catanzaro, Martine Labbé, Martha Salazar-Neumann,