کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1133726 1489084 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new hybrid algorithm for the balanced transportation problem
ترجمه فارسی عنوان
یک الگوریتم ترکیبی جدید برای مشکل حمل و نقل متعادل
کلمات کلیدی
برنامه ریزی خطی، مشکل حمل و نقل الگوریتم هیبرید دقیق هورستیک، مستطیل دوگانه منفی، مجموعه های منفی، حمل و نقل هولناک حریصانه
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
چکیده انگلیسی


• We propose a hybrid algorithm completely free of degeneracy and cycling.
• The hybrid algorithm is more efficient than the transportation simplex method.
• The algorithm’s run-time grows, nearly, as a linear function of problem size.
• We propose two very efficient heuristics for the BTP.
• We present an improved Ford–Fulkerson algorithm for the BTP.

We propose a heuristic-exact hybrid algorithm that consists of a heuristic phase, based on two novel heuristics, followed by an exact phase, based on an adapted Ford–Fulkerson algorithm, to solve the Balanced Transportation Problem (BTP). First, we propose three alternative primal models for the BTP. We also define the concepts of negative sets, negative dual rectangles, and the optimal tableau for the BTP. Next, we explore the relationships between these concepts. We also propose two greedy heuristics, based on a linear programming relaxation of the BTP model, to find some negative sets and negative dual rectangles. These two heuristics turn out to be very efficient and obtain optimal or near-optimal BTP tableaus rapidly, as confirmed by the computational experiments. Then, an adapted Ford–Fulkerson algorithm is presented and used to find an optimal solution. The two important advantages of our adapted Ford–Fulkerson algorithm over the standard Ford–Fulkerson algorithm are more flexibility and efficiency. Extensive computational results show that the growth in run-time of our hybrid algorithm, on average, is approximately a linear function of the BTP size. It has significant advantage over the transportation simplex method and on the largest problem instances it is almost five times faster. A key feature of the proposed algorithm is that it is free of degeneracy and cycling altogether.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 82, April 2015, Pages 115–126
نویسندگان
, , ,