WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION
Author(s):
Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:

In this paper, the problem of winner determination in a combinatorial reverse auction mechanism is considered for solving. Because of NP-completeness of finding a feasible solution for the formulated winner determination problem as well as its solving, the popular exact methods are failed in solving its large-scale instances. So, an exact problem-specific two-stage method is proposed to reduce the time required for its solving. The proposed method involves a well-known population-based metaheuristic called genetic algorithm and an advanced exact method called Dantzig-Wolfe decomposition in first and second stages, respectively. The genetic algorithm is used for finding a near-optimal feasible solution for the formulated winner determination problem as an initial solution for the second stage. The proposed genetic algorithm generates feasible solutions in initial population and repairs infeasible child solutions after reproduction using problem-specific operators. Also, Dantzig-Wolfe decomposition is used for decomposing the formulated winner determination problem with block-diagonal structure in its constraints matrix to a master problem and multiple sub-problems for finding its optimal solution within a reasonable time starting from the near-optimal feasible solution found by genetic algorithm in first stage. We conducted a computational experiment using randomly generated instances of winner determination problem with different sizes to evaluate the performance of our proposed two-stage method in solving the formulated winner determination problem. Computational results demonstrate that the genetic algorithm performs well in finding near-optimal solutions of the formulated problem. Also, the computational results show that the Dantzig-Wolfe decomposition based method in second stage can improve the near-optimal solution found by genetic algorithm in first stage and find the optimal solution of formulated winner determination problem as well as confirming the optimality or non-optimality of solution found by genetic algorithm. The other result is that the proposed two-stage method spends less time compared with LINGO software in finding optimal solution of formulated.

Language:
English
Published:
Industrial Engineering & Management Sharif, Volume:35 Issue: 1, 2019
Pages:
47 to 56
magiran.com/p2038690  
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یک‌ساله به مبلغ 990,000ريال می‌توانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
  • حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران می‌شود.
  • پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانه‌های چاپی و دیجیتال را به کاربر نمی‌دهد.
دسترسی سراسری کاربران دانشگاه پیام نور!
اعضای هیئت علمی و دانشجویان دانشگاه پیام نور در سراسر کشور، در صورت ثبت نام با ایمیل دانشگاهی، تا پایان فروردین ماه 1403 به مقالات سایت دسترسی خواهند داشت!
In order to view content subscription is required

Personal subscription
Subscribe magiran.com for 50 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!