کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10347547 | 699240 | 2013 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On an exact method for the constrained shortest path problem
ترجمه فارسی عنوان
یک روش دقیق برای مشکل کمترین مسافت محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوتاه ترین مسیر مسدود، کوتاهترین مشکل مسیر نسل ستون،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 378-384
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 378-384
نویسندگان
Leonardo Lozano, Andrés L. Medaglia,