کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10348216 | 699390 | 2012 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper focuses on the common scenario in which the resource-constrained shortest path problem (RCSP) on an acyclic graph is a sub-problem in the context of column generation. It proposes a pseudo-polynomial time, three-stage solution approach. Stages 1 (preprocessing) and 2 (setup) are implemented one time to transform RCSP into a shortest path problem, which is solved by stage 3 (iterative solution) at each column generation iteration, each time with different arc costs. This paper analyzes certain properties related to each stage as well as algorithm complexity. Computational tests compare the performances of this method, a state-of-the-art label-setting algorithm, and CPLEX optimization software on four classes of instances, each of which involves either one or multiple resources, and show that the new method is effective. The new method outperforms the label-setting algorithm when resource limitations are tight-as can be expected in practice, and outperforms CPLEX for all tested instances. The label-setting algorithm outperforms CPLEX for all single-resource RCSP instances and almost all multiple-resource RCSP instances.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 2, February 2012, Pages 164-178
Journal: Computers & Operations Research - Volume 39, Issue 2, February 2012, Pages 164-178
نویسندگان
Xiaoyan Zhu, Wilbert E. Wilhelm,