A Branch-and-Price Algorithm for Solving the Railroad Blocking Problem
Author(s):
Abstract:
The railroad blocking problem is one of the most important planning problem in freight railways. By solving this problem, once can minimize volume of switching process and total cost of delivering the commodities. This paper presents a method based on branch and price algorithm for solving the railroad blocking problem. This algorithm is a combination form of branch-and-bound and column generation algorithms. Branch and price is a variant of branch and bound, with bounds provided by solving linear programs using column generation at nodes of the branch and bound tree. In branch and price algorithm, re-optimize column generation algorithm in each of branches. Because the bound provided by the LP relaxation is weak, we suggest cuts to strengthen it and show the effect of adding them on the column generation procedure. Implementation of this algorithm has been done by Java programming language. To analyze the quality of the algorithm, some simulated problems with different size generated and are solved by CPLEX software. The results of our algorithm compared with CPLEX’s results. The comparison shows the efficiency and accuracy the purpose algorithm.
Keywords:
Language:
Persian
Published:
International Journal of Industrial Engineering & Production Management, Volume:25 Issue: 1, 2014
Pages:
99 to 108
magiran.com/p1270067
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!