|
|
|
|
تعیین برندگان در مناقصه‌ی ترکیبی با الگوریتم ژنتیک و روش تجزیه‌ی دنتزیگ ولف
|
|
|
|
|
|
|
|
نویسنده
|
علائی رضا ,ستاک مصطفی
|
|
منبع
|
مهندسي صنايع و مديريت شريف - 1398 - دوره : 35-1 - شماره : 1/1 - صفحه:47 -56
|
|
|
|
|
چکیده
|
در این مقاله به ارائه‌ی یک روش دومرحله‌یی برای حل دقیق حالت خاصی از مسئله‌ی تعیین برندگان در مناقصه‌ی ترکیبی پرداخته می‌شود که ترکیبی از الگوریتم ژنتیک و روش تجزیه‌ی دنتزیگ ولف است. الگوریتم فراابتکاری ژنتیک برای یافتن جواب موجه و نزدیک بهینه‌ی مسئله ارائه شده است که خروجی آن نقطه‌ی شروع روش دقیق تجزیه‌ی دنتزیگ ولف است که با توجه به ساختار بلوکی قطری مسئله برای تجزیه‌ی مسئله و یافتن جواب بهینه‌ی آن در زمان کمتر ارائه شده است. نتایج محاسباتی حاصل از به کارگیری روش ارائه شده برای حل نمونه‌های تصادفی مسئله نشان می‌دهد که روش مبتنی بر تجزیه‌ی دنتزیگ ولف علاوه‌بر تعیین نوع (بهینه یا غیربهینه) جواب‌های حاصل از الگوریتم ژنتیک، قادر به بهبود جواب‌های غیربهینه تا رسیدن به جواب بهینه است. همچنین نتایج حاصل نشان می‌دهد که روش دومرحله‌یی ارائه شده در مقایسه با نرم‌افزار لینگو زمان کمتری را صرف یافتن جواب بهینه‌ی نمونه‌های مختلف مسئله می‌کند.
|
|
کلیدواژه
|
انتخاب تامین‌کنندگان، مناقصه‌ی ترکیبی، مسئله‌ی تعیین برندگان، الگوریتم ژنتیک، روش تجزیه‌ی دنتزیگ ولف
|
|
آدرس
|
دانشگاه صنعتی خواجه نصیرالدین طوسی, دانشکده‌ی مهندسی صنایع, ایران, دانشگاه صنعتی خواجه نصیرالدین طوسی, دانشکده‌ی مهندسی صنایع, ایران
|
|
پست الکترونیکی
|
setak@kntu.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIGWOLFE DECOMPOSITION
|
|
|
|
|
Authors
|
|
|
Abstract
|
In this paper, the problem of winner determination in a combinatorial reverse auction mechanism is considered for solving. Because of NPcompleteness 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 largescale instances. So, an exact problemspecific twostage method is proposed to reduce the time required for its solving. The proposed method involves a wellknown populationbased metaheuristic called genetic algorithm and an advanced exact method called DantzigWolfe decomposition in first and second stages, respectively. The genetic algorithm is used for finding a nearoptimal 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 problemspecific operators. Also, DantzigWolfe decomposition is used for decomposing the formulated winner determination problem with blockdiagonal structure in its constraints matrix to a master problem and multiple subproblems for finding its optimal solution within a reasonable time starting from the nearoptimal 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 twostage method in solving the formulated winner determination problem. Computational results demonstrate that the genetic algorithm performs well in finding nearoptimal solutions of the formulated problem. Also, the computational results show that the DantzigWolfe decomposition based method in second stage can improve the nearoptimal 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 nonoptimality of solution found by genetic algorithm. The other result is that the proposed twostage method spends less time compared with LINGO software in finding optimal solution of formulated winner determination problem.
|
|
Keywords
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|