بخشی از مقاله
خلاصه
مزایده ترکیبی مکانیزمی برای تخصیص کالاها به صورت ترکیبی در یک مزایده است و زمانی که مجموعه ای از کالاها با هم برای خریداران دارای ارزش می باشد و در اختیار داشتن کالاها به صورت جداگانه مورد نظر نمی باشد ، بسیار کارا می باشد . در این مطالعه الگوریتم فرا ابتکاری شبیه سازی تبرید برای شناسایی برنده در مزایده ترکیبی ارائه می شود که نخست با استفاده از روشی ابتکاری مبتنی بر ساختار توپولژیک مساله ، مبادرت به کاهش فضای حل مساله می کند و سپس با استفاده از الگوریتم شبیه سازی تبرید جواب نهایی مساله را استخراج می کند .
نتایج این مطالعه نشان می دهد که الگوریتم پیشنهادی نسبت به روش های دقیق توسعه داده شده در مساله پیش رو، در زمان کمتری به استخراج جواب نهایی مساله می پردازد و کیفیت راه حل بدست آمده در مقایسه با الگوریتم های دقیق ، از دقت مناسبی برخوردار است..
.1 مقدمه
در این مطالعه به بررسی مساله شناسایی برنده در مزایده ترکیبی خواهیم پرداخت. مزایده ترکیبی به عنوان یکی از کارآترین مکانیزم های مزایده برای تخصیص کالاها زمانی که دسته ای از کالاها برای خریداران دارای ارزش می باشد استفاده می شود. به عبارتی دیگر ارزش مجموعه ای از کالاها را نمی توانیم با جمع ارزش کالاها به صورت منحصر به فرد بدست آوریم. علی رغم اینکه مسائل مزایده دنیای واقعی، مسائل با اندازه کوچک می باشند و الگوریتم های دقیق توسعه داده شده به این منظور در زمان قابل قبول، قابلیت حل مساله را دارند ، مسائل مزایده در بسیاری از کاربردها به عنوان مساله پایه در نظر گرفته می شود که می توان مسائل زمانبندی، تخصیص منابع در پروژه و مدیریت ریسک را در قالب مزایده مدل سازی کرد و اینگونهمسائل ذاتاً اندازه بزرگی دارند و بنابراین با توجه به اینکه شناسایی برنده در مزایده ها یک مساله NP-hard است، به الگوریتم های نیاز داریم که جوابیقابل قبول و نه لزوماً بهینه را در زمان معقول ارائه دهند.
بنابراین در این مطالعه یک الگوریتم فرا ابتکاری هیبرید ارائه می دهیم که در زمان معقول و با کیفیت قابل قبول ، برنده مزایده ترکیبی را شناسایی می کند.
مزایده به عنوان یکی از روش های تخصیص منابع در دنیای واقعی ، در طول زمان مطرح بوده است. بنابراین برای اینکه این تخصیص منابع کارا و تا حدودی عادلانه باشد ، مکانیزم های مختلفی برای انجام فرایند مزایده پیشنهاد شده است. بسیاری از مسائل مزایده شامل فروش مجموعه ای از آیتم ها می باشد که در این قبیل مزایده ها ، طراحی مزایده باید به گونه ای باشد که حداکثر سود برای فروشندگان را در بر داشته باشد. بعضی از دیگر مزایده ها ، شامل تخصیص وظایف به اعضای یک سازمان می باشد که در این قبیل مزایده ها ، تخصیص وظایف باید بر مبنای کارایی و عملکرد افراد باشد که در این صورت حداکثر عملکرد را برای یک سازمان تضمین می کند .
در مزایده ترکیبی مجموعه ای از آیتم ها توسط فروشندگان ارائه می شود ، سپس خریداران مجموعه آیتم های مورد نظر خود به همراه قیمتی که برای آن آیتم ها در نظر دارند را به مزایده گر1 ارائه می دهند. البته خریداران می توانند پیشنهادهای مختلفی برای آیتم ها ارائه دهند . برای مثال یک پیشنهاد خریدار می تواند شامل سه آیتم باشد و پیشنهاد دیگرش یک آیتم و نیازی نیست پیشنهادهای مختلف یک خریدار مکمل یکدیگر باشند. در مساله مزایده ترکیبی ساده از هر آیتم یک واحد وجود دارد . بعد از اعلان پیشنهادها وظیفه مزایده گر ، مشخص کردن برنده های مزایده می باشد. یعنی مشخص می کند که آیتم ها به کدام خریداران تخصیص داده شود .
در این مطالعه با استفاده از روش های ابتکاری مبادرت به کاهش فضای جستجو می کنیم . استفاده از روش های ابتکاری باعث همگرایی سریعتر می شود و فرایند جستجو را در نواحی که تضمین می کند جواب بهینه در آن نواحی نمی باشد ، انجام نمی دهد. سپس از الگوریتم شبیه سازی تبرید ، جستجو را تا رسیدن به جواب نهایی ادامه می دهیم . استفاده از روش ابتکاری برای کاهش فضای جستجو در کنار الگوریتم شبیه سازی تبرید باعث می شود که کیفیت جواب های بدست آمده در مقایسه با استفاده از هر کدام از روش ها به صورت جداگانه دقیق تر باشد.
در الگوریتم پیشنهادی نخست داده های مورد نیاز مساله را در قالب سناریوهای مختلف شبیه سازی می کنیم . سپس با استفاده از روش ابتکاری فضای حل مساله را کاهش می دهیم که در این روش آیتم ها و پیشنهادهای مغلوب را از فضای حل حذف می کنیم و سپس الگوریتم شبیه سازی تبرید را بر روی فضای کاهش داده بکار می بریم و جواب نهایی را بدست می آوریم.
در این مطالعه در بخش مرور ادبیات به مرور کتاب ها و مقالات مورد استفاده و مکانیزم های مختلف مزایده می پردازیم. سپس در قسمت مدل سازی ، مدل ریاضی مساله پیش رو و الگوریتم ابتکاری و شبیه سازی تبرید مورد استفاده شرح داده می شود. سپس در بخش تفسیر نتایج ، نتایج اجرای الگوریتم پیشنهادی با الگوریتم دقیق شاخه روی آیتم مقایسه می شود. بخش نهایی ، نتایج تحقیق و پیشنهادات برای مطالعات آتی شرح داده می شود.
.2 مرور ادبیات
مزایده یکی از روش های معمول در تخصیص منابع و وظایف شناخته می شود. مزایده ها را می توان در حالت کلی به صورت زیر تقسیم بندی کرد.
.1 مزایده می تواند یک بعدی یا چند بعدی باشد.
.2مزایده می تواند یک طرفه و یا دو طرفه باشد.
.3مزایده می تواند سر به مهر یا به صورت علنی باشد.
.4می تواند اولین - قیمت یا K امین قیمت باشد.
.5می تواند یک واحدی یا چند واحدی باشد.
.6می تواند یک آیتمی یا چند آیتمی باشد - مزایده ترکیبی - در مزایده یک بعدی تنها جنبه ای از یک پیشنهاد که مهم است، قیمت است.
در مزایده چند بعدی ابعاد دیگری مانند کیفیت، تاریخ تحویل و... نیز در نظر گرفته می شوند .
در مزایده یک طرفه، یکی از طرفین مزایده یعنی خریدار یا فروشنده می توانند پیشنهاد دهند. در مزایده دو طرفه هر دوی فروشنده و خریدار پیشنهاد می دهند و وظیفه مزایده گر تطابق بین خریدار و فروشنده است.در یک مزایده باز همه پیشنهاد دهنده ها می توانند پیشنهادهای یکدیگر را ملاحظه کنند. در یک مزایده مهر و موم تنها مزایده گر به پیشنهادها دسترسی دارد.
در مزایده اولین قیمت، برنده مزایده، قیمتی که پیشنهاد داده یعنی بالاترین قیمت را می پردازد اما در یک مزایده K امین قیمت، برنده قیمت پیشنهادی که در رتبه K قرار دارد را می پردازد. در مزایده یک واحدی، برای هر آیتم، تنها پیشنهاد یک واحد از آن آیتم را می توان داد در حالی که در مزایده چند واحدی، چندین واحد از یک آیتم را در هر پیشنهاد می توان تقاضا کرد. در مزایده ترکیبی در هر پیشنهاد چندین آیتم را می توان بر شمرد که لزوماً ارزش گذاری آن پیشنهاد برابر مجموع ارزش آیتم ها به صورت منحصر به فرد نمی باشد. هر ترکیبی از حالات فوق برای یک مزایده امکان پذیر است برای مثال یک مزایده می تواند یک بعدی، دو طرفه، علنی، سومین قیمت، چند واحدی و چند آیتمی باشد.
برخی از انواع مزایده های رایج عبارتند از :[2] مزایده انگلیسی2، بیشترین قیمت از پیشنهادهای مهر و موم شده3، مزایده داتچ4، مزایده ویکری .5 مزایده های نامبرده به عنوان مزایده های ساده شناخته می شوند. در این مزایده ها آیتم ها به صورت جداگانه پیشنهاد می شوند. گونه ای دیگر از مزایده ها مزایده های ترکیبی می باشد در مزایده های ترکیبی به جای استفاده از یک پیشنهاد برای یک آیتم از یک مجموعه از پیشنهادات برای آیتم ها استفاده می شود.
مثالی از مزایده ترکیبی فروش حق توزیع توسط دولت محلی است که شرکت های تلفن همراه ترجیح می دهند که مکان هایی به آنها تخصیص داده شود که در نزدیکی آنها فرکانس هایی داشته باشند یا تخصیص به گونه ای باشد که توسعه پهنای باند آنها باعث شود نقاط بیشتری را پوشش دهند. مزایده های ترکیبی در حالت کلی شامل موارد زیر است:
مزایده ترکیبی ساده [1]، معاوضه های ترکیبی [3]، مزایده های ترکیبی چند آیتمی مخلوط[4]و مزایده های چند صفتی .[5] در این مطالعه شناسایی برنده در مزایده های ترکیبی ساده را بررسی خواهیم کرد. شناسایی برنده در یک مزایده ترکیبی یک مساله NP-hard است.[6] می توانیم مساله مزایده ترکیبی را به یک مساله برنامه ریزی ریاضی تبدیل کرد که با استفاده از الگوریتم های شناخته شده می توان آن را در زمان چند جمله ای حل کرد. این مورد تنها در صورتی اتفاق می افتد که قیمت ها به آیتم های جداگانه ضمیمه شود
یکی از الگوریتم های دقیق برای حل مساله شناسایی برنده در مزایده ترکیبی الگوریتم شاخه روی آیتم می باشد .[8] این الگوریتم پیشنهادها را در یک ساختار درختی مناسب قرار می دهد و با استفاده از روش شاخه و حد پیشنهادهای برنده را شناسایی می کند.
در بعضی از روش های ابتکاری که برای حل مزایده های ترکیبی استفاده می شود ، از ساختار توپولژیک مساله با کاهش فضای حل و بکار گیری روش های دیگر از جمله روش شاخه روی آیتم برنده مزایده را شناسایی می کند . در این الگوریتم ها پیشنهادها و آیتم های مغلوب شناسایی و حذف می شوند
