کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347548 699240 2013 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
ترجمه فارسی عنوان
پیاده سازی یک رویکرد سه مرحله ای برای زیر مشکل مشکلترین مسیریابی محدود منابع پویا در شاخه و قیمت
کلمات کلیدی
مشکل کمترین مسیر مساله محدودیت منابع، رویکرد سه مرحله ای، دوباره بهینه سازی قوس ثابت، نسل ستون، شعبه و قیمت،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
The resource-constrained shortest-path problem (RCSP) is often used as a sub-problem in branch-and-price because it can model the complex logic by which many actual systems operate. This paper addresses two special issues that arise in such an application. First, RCSP in this context is dynamic in the sense that arc costs are updated at each column-generation iteration, but constraints are not changed. Often, only a few arc costs are updated at an iteration. Second, RCSP must be solved subject to arcs that are forbidden or prescribed as corresponding binary variables are fixed to 0 or 1 by the branching rule. A reoptimizing algorithm for dealing with a few arc-cost changes and a method for dealing with fixed arcs are proposed and incorporated into a three-stage approach, specializing it for repeatedly solving the dynamic RCSP as a sub-problem in branch-and-price. Computational tests evaluate the effectiveness of the proposed algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 385-394
نویسندگان
, ,