1-  مقدمه

سیستم سفارش‌های مستمر یکی از سیاست‍های متداول و پرکاربرد در مباحث کنترل موجودی است در این روش برای هر کالا عددی به عنوان نقطه سفارش[1] (R) در نظر گرفته و موجودی کالا به صورت مستمر بررسی می‍شود. هنگامی که مقدار موجودی کالا به نقطه سفارش رسید، برای آن کالا به مقدار معینی سفارش برابر با حجم سفارش[2] (Q) صادر می‍شود. در این سیستم، هدف حداقل کردن هزینه‍های موجودی با تعیین مقادیر بهینه نقطه سفارش و حجم سفارش تحت شرایط مساله است. از شرایط مساله می‌توان به هزینه‌های نگهداری، سفارش‌دهی، مواجه با کمبود، فروش از دست رفته و یا محدودیت انبار، تقاضای احتمالی، فاصله زمانی تحویل احتمالی، کالاهای فاسد شدنی و... اشاره کرد.

در این تحقیق، سیستم متداول سفارش‌هایی مستمر با تقاضای احتمالی و تابع توزیع نرمال تحت شرایط متاثر بودن تقاضا از متوسط درصد کمبود کالا بررسی می‌شود. هدف از این شرایط، مدل کردن هزینه‌های مرتبط با کسر اعتبار سازمان در زمان مواجه با کمبود می‌باشد. در سیستم‍های معمول کنترل موجودی برای تقاضاهایی که با کمبود مواجه می‍شوند، یکی از حالات زیر در نظر گرفته می‍شود:

کل تقاضاها در مدت زمان فقدان موجودی، منتظر می‍مانند و به محض دریافت موجودی به آنها پاسخ داده می‍شود (پس افت).

حالت دوم تقاضاها در مدت زمان فقدان موجودی، منتظر نمی‍مانند (فروش از دست رفته)

حالت سوم، حالتی ترکیبی از هر دو حالت بالاست، بدین ترتیب که درصدی از تقاضا به صورت تقاضای پس‍افت در سیستم منتظر می‍ماند. برای مثال، مونتگومری و همکاران[3] (1973)، رزنبرگ[4] (1979) و پارک[5] (1982) به بررسی مدل‌هایی پرداختند که کسر ثابتی از تقاضاها در زمان کمبود به صورت سفارش‌هایی عقب افتاده در سیستم باقی می‍ماند.

برخی از محققان نیز مساله کنترل موجودی با سفارش‌هایی عقب‌افتاده جزئی را با رویکرد اصطلاحاً مشتری ناشکیبا[6] مدل نموده‍اند. در این رویکرد زمانی که تقاضایی با کمبود مواجه می‍شود، کسری از تقاضا، که وابسته به شرایط مساله در زمان رخ دادن کمبود است، به صورت سفارش‌هایی عقب افتاده در سیستم باقی می‍ماند. برای مثال، لی و ناهمیاس[7] (1993) به برسی مدل کنترل موجودی‍ای پرداختند که در آن حداکثر زمان قابل انتظار از دید مشتریان مشخص و ثابت بوده است. پاپاکریستوز و اسکوری[8] (2000) به بررسی سیستم سفارش‌هایی مستمری با تقاضای مشخص و وابسته به زمان، نرخ ثابت فساد با افق برنامه‍ریزی محدود برای کالاهای فسادپذیر پرداختند. آنها مدل خود را برای شرایطی که کسری از سفارش‌هایی عقب افتاده در سیستم باقی بماند، توسعه دادند. در مطالعه آنها، این کسر برابر با تابع نمایی منفی‍ای از مدت زمان انتظار استد. سپس آنها مدل خود را برای شرایط تخفیف کلی نیز توسعه دادند. از دیگر مقالاتی که به بررسی سفارش‌هایی عقب افتاده جزیی با رویکرد مشتری ناشکیبا پرداخته‍اند، می‍توان به مقالات چو و چن[9] (2002)، ونگ[10] (2002) و سن‌جوزه و همکاران[11] (2005) اشاره کرد.

در همه مقالات فوق نرخ سفارش‌هایی عقب افتاده جزئی، ثابت یا تنها وابسته به مدت زمان انتظار است، در حالی که این نرخ می‍تواند وابسته به طول دوره کمبود نیز باشد. برای مثال، شرایطی را در نظر بگیرید که مدت زمان انتظار طولانی، اما نسبت به طول دوره کمبود حائز اهمیت نباشد. در چنین شرایطی، مشتریان همچنان در سیستم باقی خواهند ماند. محققین زیر مساله سفارش‌های عقب افتاده جزئی را با توجه به عامل فوق بررسی کرده‍اند.

یو[12] (2005) به بررسی سیستم بهینه سفارش‍دهی‍ با تقاضای فصلی پرداخته است. در مطالعه او احتمال این که مشتری‍ای کالایی را به صورت سفارش‌های عقب‍افتاده خریداری کند وابسته به فاصله زمانی بین دو فصل و مدت زمان انتظار مشتری است. سان جوزه و همکاران[13] (2007) سیستم کنترل موجودی با تقاضای ثابت در طول افق نامحدود و تقاضای پس‍افت جزئی را بررسی نمودند، آنها فرض نمودند درصدی از مشتریان که مایل به انتظار نیستند متناسب با طول دوره کمبود و مدت زمان انتظار است و براساس فرضیات فوق سیاست بهینه سفارش را تعیین کردند.

کریشنامورتی و آرتلیژو[14] (2006) سیستم سفارش‌های مستمری ارائه کردند که در آن تقاضاهای مواجه با کمبود از سیستم خارج شده و پس از مدتی تصادفی دوباره به سیستم باز می‍گردد و در صورت عدم برآورده شدن تقاضا مجدداً فرآیند فوق تکرار می‍شود.

در این تحقیق، تاثیر میزان کمبود بر تقاضا به‌طور مستقیم مورد بررسی قرار می‌گیرد که در تحقیقات پیشین این اثر مستقیم و مدل یکپارچه بررسی نشده است. هدف از این تاثیر مستقیم، مدل‍سازی هزینه‌های مرتبط با کسر اعتبار سازمان در فضای رقابتی می‍باشد. سازمان‌دهی سایر بخش‌های این مقاله به صورت ذیل می‌باشد. مساله مورد بررسی در بخش دوم ارایه و مدل‌سازی شده است. بخش سوم به ارایه الگوریتم پیشنهادی می‌پردازد. بخش چهارم به معرفی آزمایش‌های انجام شده و تحلیل آنها می‌پردازد و نتایج تحقیق در بخش پنجم آورده شده است.

 

2-  تعریف مساله و مدل‍سازی

مدل موجودی سفارش‌های مستمر در این تحقیق بر پایه مدل عمومی سفارش‌های مستمر ارایه شده در کتب موجودی سیلور و همکاران[15] (1998) بوده و تنها تغیر موجود، متاثر بودن تابع تقاضا از متوسط درصد کمبود کالاست. متوسط درصد کمبود به‌صورت متوسط نسبت تقاضاهایی که با کمبود مواجه شده‌اند، تعریف می‌گردد. برای این منظور کافی است میزان متوسط کمبود را در هر دوره سفارش‌گذاری تعیین و بر میزان سفارش مربوطه تقسیم کرد. عدد به دست آمده نشان‌دهنده متوسط درصد کمبود خواهد بود.

در این تحقیق، مسأله تعیین مقادیر نقطه سفارش دهی و میزان سفارش در سیستم سفارش‌های مستمر با هدف حداکثر نمودن سود بررسی می شود که در آن فاصله زمانی تحویل ثابت و مشخص بوده و تابع تقاضا احتمالی و متأثر از درصد کمبود کالاست. کمبود کالا موجب می‌گردد که تعدادی از مشتریان با کمبود مواجه شده و تاثیر منفی آن موجب کاهش تقاضای مشتریان می‌گردد. به عبارتی، در صورتی که مشتری بداند در صورت سفارش به یک فروشنده، با احتمال زیادی سفارش او به موقع تحویل داده نخواهد شد، سعی می‌نماید که فروشندگان دیگری را انتخاب و به آنها سفارش دهد. احتمال کمبود برای یک فروشنده به کاهش سفارش به او و سفارش به سایرین منجر خواهد شد و به علت احتمال کمبود، تقاضای برای کالای او کاهش می‌یابد. ‌فرضیات ذیل در این تحقیق در نظر گرفته شده است:

تغییر تقاضا به کندی رخ میدهد. به همین برای، مقدار تقاضای بهدست آمده براساس مقادیرR و Q تقریبا ثابت فرض میشود.

افق برنامه‍ریزی نامحدود فرض شده است.

فاصله زمانی تحویل ثابت است و برابر با یک واحد زمان فرض شده است. به عبارتی، همه‍متغیرها بر حسب فاصله زمانی تحویل ارائه شده‍اند (مانند هزینه‍ نگهداری، مقدار تقاضا...).

کلیه تقاضاهای مواجه شده با کمبود به صورت تقاضای پسافت در سیستم باقی می‍مانند و در نخستین فرصت ممکن برآورده میشوند.

هزینه مواجه با کمبود خطی و براساس متوسط مقدار کمبود در هر دوره محاسبه می‍گردد.

هزینه سفارش‍دهی ثابت بوده، حجم سفارش در آن تاثیری ندارد.

تابع تقاضا احتمالی بوده، از توزیع نرمال با میانگین µ و انحراف معیار  پیروی می‍کند.

 با توجه به متاثر بودن تقاضا از متوسط درصد کمبود کالا، حداکثر مقدار تقاضا در شرایطی رخ می‍دهد که درصد کمبود کالا کمتر از مقدار از پیش مشخص شده‍ پارامتر j باشد، این مقدار تقاضا با _MAXµ نشان داده می‍شود و در صورتی که متوسط درصد کمبود کالا بیشتر از پارامتر مشخص j باشد تقاضا تا اندازهای کاهش پیدا میکند که متوسط درصد کمبود کالا کمتر یا مساوی مقدار مشخص j شود. معادله (1) نشان‌دهنده این محدودیت و نحوه تاثیر‌گذاری آن بر تقاضاست. همان‌طور که در قسمت‌های قبلی در تعریف متوسط درصد کمبود شرح داده شد، متوسط درصد کمبود به صورت متوسط نسبت تعداد تقاضاهایی که با کمبود مواجه می‌شوند، محاسبه می‌گردد. یک دوره زمانی از چند دوره سفارش‌گذاری تشکیل شده است و با توجه به اینکه در یک دوره سفارش‌گذاری تنها در انتهای دوره احتمال کمبود وجود دارد، این نسبت از طریق رابطه زیر قابل محاسبه است.

 

                                                  (1)

 

که در آن  بیانگر مقدار مورد انتظار کمبود در یک دوره است و از طریق معادله (2) محاسبه می‌شود:.

 

 

 

در معادله بالا  نشان‌دهنده نقطه سفارش و  نشان‍دهنده تابع تقاضا در واحد زمان ست در این تحقیق، واحد زمان برابر با فاصله زمانی تحویل فرض شده است. لذا در صورتی که تابع توزیع نرمال را به صورت معادله (3) در نظر بگیریم، مقدار  مطابق با معادله (4) محاسبه خواهد شد. بر این اساس، رابطه (1) به رابطه (5) تبدیل خواهد شد.

 

(3)                        

(4)     (5)                       

در رابطه بالا µ نشان‌دهنده متوسط مقدار تقاضا و  نشان‌دهنده انحراف معیار تقاضاست. بیشترین مقدار µ ممکنی که رابطه بالا را ارضاع نماید نشان‍دهنده متوسط تقاضا به ازای مقادیر R و Q مشخص است. مقدار _MAXµ نشان‌دهنده حداکثر میزان تقاضا در صورت عدم وجود کمبود است و یا به عبارتی، حداکثر سهم شرکت از بازار محصولات را نشان می‍دهد. مقدار µ می‍تواند بین مقادیر _MAXµ و 0 باشد که این معادله در رابطه (6) نمایش داده شده است:

 

 (6)                                   

 

هرچه مقدار "حجم سفارش" یا Q بیشتر باشد تعداد دفعاتی که سیستم با کمبود مواجه می‍شود کمتر شده، فاصله زمانی بین دو سیکل افزایش می یابد و کمبودها با فاصله زمانی بیشتری رخ می‍دهند. این موضوع، باعث جلب اعتماد مشتریان و افزایش تقاضا می‍گردد. برای مثال، در نقطه مشخصی که مقادیر در معادله (5) صدق می‍کنند، با افزایش مقدار Q، مقدار  می‍تواند افزایش یابد که در صورت ثابت فرض کردن R، این تغییر با افزایش µ و  (افزایش تقاضا) همراه است.

با افزایش نقطه "سفارش دهی" یا R، احتمال مواجه شدن با کمبود و تعداد مورد انتظار کالاهای مواجه با کمبود به ازای تقاضای فعلی(µ) کاهش یافته، این امر باعث افزایش رضایت مشتریان و تقاضا می‍گردد. سپس با افزایش تقاضا یا µ مقدار   مجددا افزایش می‍یابد. طبق رابطه فوق افزایش تقاضا تا حدی رخ می‍دهد که مقادیر جدید R , Q , µ در رابطه فوق صدق کنند.

پارامتر j را می‍توان حداکثر درصد کمبود قابل قبول از نظر مشتریان دانست. به عبارتی دیگر، هرچه مقدار این پارامتر کمتر باشد، بازار رقابتی‍تر و هزینه‍های مواجه با کمبود بیشتر است. مقدار این پارامتر را می‍توان از داده‍های موجود و اطلاعات گذشته شرکت مشخص نمود.

با کاهش تقاضا، یا ریزش مشتریان، طبیعتاً مقدار انحراف معیار تقاضا نیز کاهش پیدا میکند.در صورتی که _MAXµ را مجموع میانگین تقاضای n مشتری در نظر بگیریم با کاهش این مشتریان،انحراف معیار توزیع مجموع تقاضاهای این مشتریان نیز به صورت معادله (7) تغییر میکند.

 

(7)                                  

در رابطه بالا، فرض بر آن است که تقاضای کل عبارت است از مجموع n متغیر مستقل (با فرض هم توزیع بودن) که در صورت کاهش این متغیرها، واریانس مجموع آنها نیز به همان نسبت کاهش پیدا می‍کند.

هدف اصلی این مساله، انتخاب مقادیرR  ، Q به گونه ای است که تابع سود یا بیشینه گردد.. این تابع در معادله (8) نشان داده شده است:

 

(8)        

 

که در آن TIC_r,qمجموع هزینههای موجودی است و از جمع مقادیر هزینه​های سفارش​دهی، هزینه​های نگهداری و هزینه​های کمبود به دست می آید و در معادله (9) نشان داده شده است.

 

(9)       

TOC_r,q،THC_r,qو TSC_r,q

 

به‌ترتیب نشان‌دهنده مجموع هزینههای سفارشدهی، مجموع هزینههای نگهداری و مجموع هزینههای کمبود بوده و در معادلات (10) تا (12) نشان داده شده​اند.

 

(10)                               

(11)                                

(12)                           

 

در معادلات فوق S، h، C، ،  به‌ترتیب نشان‍دهنده هزینه مواجه با کمبود به ازای هر واحد در زمان، هزینه نگهداری به ازای هر واحد در زمان، هزینه ثابت سفارش‍دهی، قیمت فروش کالا و قیمت تمام‍شده کالا هستند.

همچنین، نشان‍دهنده سطح موجودی بوده و با تقریب ارائه شده توسط لائوا و لائو[16] (2002) بر اساس معادلات (13) تا (15) محاسبه خواهد شد.

 

(13)                               

(14)                        

         (15)

 

همان‌طور که در معادله (5) نشان داده  شده است محدوده متغیر  به دو متغیر ،  وابسته بوده و  باید بیشترین مقدار ممکن را اختیار کند، از آنجا که امکان ساده‍سازی معادله (5) به نحوی که  را بر اساس دو متغیر دیگر بیان شود، وجود ندارد، به‌عبارتی، امکان محاسبه تغیرات متغیر  نسبت به دو متغیر ،  به صورت کلی (نه به صورت نقطه‌ای) و نمایش آن به صورت معادله وجود نداشته و نقاط بهینه محلی تابع سود لزوماً محدود نبوده، که بتوان بعد از محاسبه، آنها را مقایسه نمود و بهترین نقطه را به عنوان جواب بهینه انتخاب کرد، برای محاسبه نقطه بهینه تابع  از الگوریتم‌های ابتکاری استفاده شده و فضای جستجو نیز به اعداد صحیح محدود شده است. همچنین، در واقعیت نیز مقادیر ،  بیانگر تعداد یا حجمی از کالا بوده و معمولا دارای مقادیر صحیح هستند و در صورت اعشاری بودن این مقادیر می‌توان با تغییر واحد، این مقادیر را به عدد صحیح تبدیل کرد.

در ذیل برای تشریح مساله مورد نظر یک مثال ارائه می‌گردد. فرض کنید در این مثال، هزینه ثابت سفارش‍دهی برابر با 1000، حداکثر تقاضا 100، حداکثر انحراف معیار 25، هزینه نگهداری به ازای هر کالا در واحد زمان 300، هزینه مواجه با کمبود به ازای هر کالا در واحد زمان 400، حداکثر درصد کمبود مجاز برای مشتریان 0.00001 و تفاوت قیمت فروش با قیمت تمام شده 500 واحد پولی باشد. این مساله دارای چندین نقطه بهینه محلی است که در زیر 2 نقطه​ آن نشان داده شده​ است.

 

 

 

 

شکل تابع سود مثال فوق به ازای مقادیر سود بیشتر از صفر از دو زاویه مختلف در شکل 1 نشان داده شده است. همان‌طور که در این شکل مشاهده می‌شود، یال موجود به صورت دندانه‍دار بوده، نشان‍دهنده نقاط بهینه محلی در مثال فوق است. همچنین، تغییرات تقاضا به ازای تغییرات R و Q در شکل 2 نمایش داده شده است.

 

 

 

شکل1- تابع سود مثال فوق به ازای مقادیر سود بیشتر از صفر.

 

 

 

شکل2- تغییرات تقاضا به ازای تغییرات نقطه سفارش و حجم سفارش

همان‌طور که در شکل2 مشاهده می‌گردد، میانگین تقاضا نسبت به تغییرات "نقطه‍ سفارش" حساس بوده، با افزایش مقدار "نقطه‍ سفارش"میانگین تقاضا تا رسیدن به حداکثر مقدار خود افزایش می‍یابد، اما میانگین تقاضا نسبت به "حجم سفارش" چندان حساس نبوده، با افزایش "حجم سفارش" مقدار کمی افزایش پیدا می‍کند.

 

3- ارائه الگوریتم پیشنهادی

3-1 الگوریتم ژنتیک

الگوریتم ژنتیک یک متدولوژی عمومی برای جستجو در فضاهای جواب گسسته، مطابق با روش به‌کار گرفته شده در فرآیندهای طبیعی انتخاب در سیستمهای بیولوژیکی است. الگوریتم ژنتیک جزئی از محاسبات تکاملی است که خود جزئی از هوش مصنوعی است. ویژگیهای خاص این الگوریتم باعث میشود که نتوانیم آن را یک جستجوگر تصادفی ساده قلمداد کنیم. در واقع، ایده اولیه این روش از نظریه تکاملی داروین الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار است. الگوریتم ژنتیک در حل بسیاری از مسایل بهینه‌سازی عملکرد خوبی از خود نشان داده و در این تحقیق نیز به‌عنوان یکی از الگوریتم‌های ابتکاری، به‌کار گرفته شده است(فتاحی، 1388).

در هر الگوریتم، پارامترها و اجزایی وجود دارند که بر کیفیت الگوریتم تاثیر بسزایی دارند، لذا در ذیل پارامترهای موثر بر الگوریتم ژنتیک پیشنهادی برای مساله مورد نظر بررسی می‌گردند.

 

3-1-1 جمعیت اولیه

در این تحقیق چندین نقطه بهینه محلی جزو جمعیت اولیه خواهند بود. در این مرحله چندین بار نقاط تصادفی (R و Q های تصادفی) انتخاب می‍گردد و سپس هر بار یکی از پارامتر‍‍های R یا Q انتخاب شده (مثلا Q) و با افزایش (یا کاهش) یکنواخت آن در راستای حداکثر کردن تابع هدف به مقدار جدیدی برای این پارامتر رسیده می‌شود. سپس همین کار را با پارامتر دیگر (مثلا R و با مقدار جدید به دست  آمده Q) انجام داده، چرخه بالا را تا جایی که تغییر در یک پارامتر باعث بهبود تابع هدف نشود، تکرار می‍کنیم. نقطه R و Q به دست آمده یکی از نقاط مورد نظر ما برای جمعیت اولیه است. به صورت خلاصه این الگوریتم در شکل 3 نمایش داده شده است.

 

3-1-2 ساختار نمایش

برای معرفی ساختار نمایش کروموزوم از کدگذاری باینری استفاده می‍گردد. در این روش، نیمی از ژن‍های کروموزوم، نشان‌دهنده مقدار متغیر R و نیمه دیگر نشان‌دهنده متغیر Q هستند. طول هر کروموزوم یا تعداد ژن‍های آن با توجه به مساله متفاوت استد و در هر مساله حداکثر مقدار هر یک از متغیر‍ها تا A برابر حداکثر مقدار متوسط تقاضا در نظر گرفته شده است. بنابراین، طول هر کروموزوم برابر با دو برابر تعداد ژن‍های لازم برای نمایش A برابر تقاضاست.

 

شکل3- الگوریتم ابداعی برای ایجاد جمعیت اولیه

برای مثال، اگر در یک مساله A برابر با 3 و حداکثر تقاضا 100 فرض شود، تعداد ژن های لازم برای نشان دادن هر یک از متغیرهای ،  برابر با 9 عدد است و لذا طول کروموزوم برابر با 18 خواهد بود.

èتعداد ژن های لازم=9

 

مقدار پارامتر A بیان‍کننده حداکثر مقدار متغیرهای R , Q است. با افزایش مقدار A فضای جستجو برای متغیرهای فوق و زمان لازم برای حل مساله افزایش می‍یابد. در صورتی که مقادیر،  به ترتیب 25 و 127 باشد، کروموزوم مثال فوق مطابق شکل (4) خواهد بود.

 

شکل4- ساختار کروموزوم برای الگوریتم پیشنهادی

 

3-1-3 عملگر تقاطع

عملگرهای تقاطع متعددی برای جمعیت فوق می‍توان تعریف کرد. در زیر چهار عملگر متفاوت ارائه و مورد مقایسه شده‌اند. این عملگرها در زیر شرح داده شده‍اند.

عملگر تقاطع تک نقطه‍ای: در این‍جا عملگر تقاطع از نقطه اتصال دو متغیر برای تقاطع عمل می‍کند و یا به عبارتی، مقادیر R و Q در تولید فرزندان بین دو والد تعویض می‍شوند.

عملگر تقاطع دو نقطه‍ای: در این عملگر یکی از نقاط در محدوده‍ میانی ژن‍های R و دیگری در محدوده‍ی میانی ژن‍های Q به صورت تصادفی انتخاب می‍گردد و عمل تقاطع انجام می‍شود. نقطه اول به صورت تصادفی در نیمه‍ اول کرموزوم و نقطه‍ دوم نیز به صورت تصادفی در نیمه دوم کروموزوم انتخاب می‍گردد .

عملگر تقاطع چهار نقطه‍ای: این عملگر از هر قسمت کروموزوم (کروموزوم‍ها دارای دو بخش به طول مساوی و به‍ترتیب بیان‍کننده نقطه سفارش‍دهی و حجم سفارش هستند) دو نقطه تصادفی انتخاب کرده، عمل تقاطع بین نقاط انجام می‍گیرد. نقطه‍های اول و دوم به صورت تصادفی در نیمه اول، و نقطه‍های سوم و چهارم در نیمه دوم انتخاب می‍گردد.

در عملگر تقاطعی یکنواخت، ژنها به صورت تصادفی از والد1 یا والد2 انتخاب میشوند.

 

3-1-4 عملگر جهش

در این مقاله، احتمال جهش بیان‍کننده احتمال رخ دادن جهش در هر کروموزوم است. بدین ترتیب، با داشتن طول هر کروموزوم احتمال جهش برای ژن‌های آن محاسبه شده، ژن‍های کروموزوم با احتمال به دست آمده متمم می‍شوند. برای مثال، در صورتی که احتمال جهش یک کروموزوم به طول 20 را 20% در نظر بگیریم، احتمال جهش هر ژن آن به صورت زیر محاسبه می‍شود:

 

احتمال رخ ندادن جهش در کروموزوم 

 

احتمال رخ دادن جهش در هر ژن کروموزوم به طول:

20:

 

علت استفاده از روش فوق، متغیر بودن طول کروموزوم‍هاست، در صورتی که احتمال جهش برای هر ژن از پیش تعیین شده و طول کروموزوم کوتاه باشد، ممکن است الگوریتم در بهینه محلی گرفتار شود و در مواقعی که طول کروموزوم بلند باشد، الگوریتم را تبدیل به جستجو'گر تصادفی می‍کند. برای مثال، در صورتی که طول کروموزوم 50 و احتمال جهش هر ژن 0.03 در نظر گرفته شود احتمال جهش نکردن کروموزوم برابر با 0.21 و در صورتی که طول کروموزوم 10 باشد، این احتمال برابر با 0.73 درصد است.

 

3-1-5 عملگر انتخاب

در این تحقیق، به علت اختلاف زیاد بین مقادیر برازندگی برای انتخاب کروموزومها از روش رتبهبندی خطی استفاده شده است. در حالتی که اختلاف بین مقادیر برازندگی یک جمعیت زیاد باشد، معمولاً از روش رتبه‌بندی برای انتخاب استفاده می‌شود. در این حالات، روش رتبه‌بندی موجب می‌گردد که از همگرایی بیش از حد سریع الگوریتم جلوگیری کند. در روش رتبه‌بندی خطی، افراد جمعیت برحسب برازندگی‏شان به ترتیب از 1 تا N (تعداد جمعیت) رتبه‏بندی می‏شوند. نرخ انتظار هر فرد هم به جای بستگی به برازندگی مطلق، به رتبه‏ آن فرد بستگی دارد. پس از رتبه‌بندی افراد جمعیت، هر عضو با احتمالی برابر با نسبت رتبه آن عضو به مجموعه رتبه‌های کل جمعیت انتخاب می‌گردد.

 

3-1-6 تنظیم پارامتر‍های الگوریتم ژنتیک

به منظور بهینه‍سازی پارامترهای الگوریتم ژنتیک، مقدار پارامترهای این الگوریتم را ‍متغیر فرض کرده و توسط رویه تکرای مقادیر آنها مورد ارزیابی قرار گرفته است (فتاحی، 1388). در محاسبات فوق، معیار ارزیابی پارامترها، تعداد نقاط جستجو شده در الگوریتم ژنتیک تا رسیدن به نقطه بهینه فرض شده است. برای این منظور، الگوریتم زنتیک برای هر حالت پارامترها، 20 بار اجرا و متوسط نقاط جستجو شده به عنوان معیار ارزیابی پارامترها محاسبه شده‌است. نقطه بهینه مطلق نیز برای مسایل مورد استفاده (جدول شماره1) در الگوریتم فوق به روش جستجوی نقطه به نقطه محاسبه گردیده است.

 

جدول 1 - خصوصیات مساله‌ها برای تنظیم پارامتر الگوریتم ژنتیک

 

نتایج بهترین پارامترها برای مساله ژنتیک با عملگرهای متفاوت در جدول 2 نمایش داده شده است. در ابتدا به تحلیل کارایی عملگرهای انتخابی می‌پردازیم. براساس جدول شماره 2 مشخص شد که عملگر شماره 4 که همان عملگر یکنواخت برای ادغام است، نتایج بهتری را نسبت به بقیه به دست  آورده است. همچنین،  براساس نتایج به دست آمده، عملگرها به ترتیب ذیل دارای کارایی بهتر هستند. ابتدا عملگر یکنواخت (شماره 4) بهترین نتیجه و سپس عملگر چهار نقطه‍ای (شماره 3)، عملگر دو نقطه‍ای (شماره 2)، و عملگر تک نقطه‍ای (شماره 1) دارای کارایی بوده‌اند. به‌ همین علت در ارزیابی‌ها عملگر یکنواخت به عنوان عملگر مناسب برای ادغام انتخاب گردید.

 

جدول 2 - نتایج بهترین پارامترها برای مساله ژنتیک با عملگرهای متفاوت

 

سپس برای تنظیم سایر پارامترها، شش مساله مورد بررسی با هر شش حالت این پارامترها حل گردیده و کمترین مجموع تعداد نقاط جستجو شده برای شش مساله، معیار ارزیابی این پارامترها قرار گرفته است. نتایج در جدول 3 نمایش داده شده​اند. پارامترهای بهینه الگوریتم علاوه بر عملگر یکنواخت که برای ادغام استفاده شده بود عبارتند از: اندازه جمعیت 12، تعداد فرزندان 8، احتمال جهش 0.36

 

جدول 3 - حل 6 مساله مورد بررسی با ترکیب پارامترهای مورد مطالعه

 

همچنین در الگوریتم ژنتیک استفاده شده در این مساله به ازای هر چند نسل (در اینجا 50 نسل)، شعاع کوچکی از بهترین نقطه موجود فعلی به صورت نقطه به نقطه بررسی می‍شود و بهترین نقطه‍ موجود در این شعاع به جمعیت الگوریتم ژنتیک افزوده می‍شود. این امر باعث افزایش چشمگیر سرعت حل مساله می‍گردد. برای نشان دادن این موضوع، تعدادی مساله تصادفی طرح شده و میانگین زمان حل و نقاط جستجو شده برای 10 بار اجرا معیار مقایسه قرار گرفته است. زمان حل برنامه و انحراف معیار نمونه‍ها در الگوریتم جدید کوچکتر از روش قبلی است که برتری این روش را نسبت به الگوریتم عادی ژنتیک نشان می‍دهد. به منظور اثبات کوچکتر بودن مقادیر نقاط جستجو شده در الگوریتم جدید از آزمون فرض برابری میانگین‌های دو جامعه نرمال با واریانس‌های نامعلوم و نه لزوماً مساوی استفاده شده است.

 

 

 

 

 نشان​دهنده متوسط نقاط جستجو شده در عملگر تقاطعی یکنواخت است و نشان​دهنده متوسط نقاط جستجو شده در عملگر تقاطعی یکنواختی است که به ازای هر 50 نسل شعاع کوچکی اطراف بهترین نقطه جمعیت را به صورت نقطه به نقطه جستجو می​کند پس از انجام آزمون‍ها، فرض صفر در همه نمونه‍ها در سطح معنادار 0.95 رد می‍شود. شکل‌ 5 نشان‍دهنده‍ روند همگرایی پنج عملگر فوق در دو مساله تصادفی است. همچنین، تعداد نسل​ها را برابر با میانگین نسل​ها تا رسیدن به جواب بهینه یعنی 611 قرار می‌دهیم.

 

 

 

شکل 5 - مقایسه روند همگرایی 5 عملگر در دو مساله تصادفی

3-2  الگوریتم انجماد تدریجی

الگوریتم انجماد تدریجی ([17]SA) یا انجماد تدریجی یک روش تصادفی بوده که از مکانیزم آماری برای یافتن جواب‍های مسایل بهینه‍سازی استفاده می‍کند. SA بر مبنای فرایند آنیلینگ شکل گرفته است. جستجوی جواب با استفاده از SA با تولید یک نقطه اولیه آغاز می‍شود و هر جواب به عنوان یک آرایش مولکولی با سطح انرژی برابر با مقدار تابع هدف برای رشته جواب متناظر در نظر گرفته می‍شود، سپس دمای اولیه الگوریتم با تابع از پیش تعریف شده‍ای کاهش داده شده و در هر دما چندین نقطه تولید و سپس ارزیابی می‍شود (فتاحی، 1388).

 

جدول4 - نتایج بهترین پارامترها برای الگوریتم انجماد تدریجی

 

جواب‍های بهتر جایگزین جواب‍های قبلی شده و جواب‍های بدتر در هر مرحله با احتمال P_n جایگزین رشته جواب قبلی می‍شوند. شانس جا به جایی یک جواب خوب با یک جواب بدتر، خروج الگوریتم از بهینه محلی را تضمین می‍کند و از طرف دیگر، کاهش احتمال پذیرش جواب بدتر با کاهش دما، موجب تضمین همگرایی SA است. به همین ترتیب، الگوریتم ادامه می‍یابد تا شرایط مورد نظر برای خاتمه الگوریتم حاصل گردد(مثلا دمای الگوریتم به زیر دمای حداقل تعریف شده برسد) (فتاحی، 1388).

برای تعیین مقادیر بهینه پارامترهای الگوریتم انجماد تدریجی نیز از روش استفاده شده در تعیین مقادیر بهینه پارامترهای الگوریتم ژنتیک، استفاده شده است. نتایج به شرح جدول 4 است.

به منظور تعیین بهترین حالت، هر شش مساله با شش حالت پارامترهای فوق حل گردیده و مجموع نقاط جستجو شده برای هر پارامتر معیار ارزیابی بهترین پارامتر قرار گرفته است و نتیجتاً دمای اولیه 2099، نرخ کاهش دما 0.17، و تعداد نقاط پذیرش شده لازم در هر حلقه 9 عدد است. همچنین، در الگوریتم فوق در صورتی که بیش از 400 نقطه جستجو شود، دما کاهش می‍یابد.

برای تعیین دمای پایانی الگوریتم، مسایل را با پارامترهای فوق دمای اولیه 2099، نرخ کاهش دما 0.17، و تعداد نقاط پذیرش شده لازم در هر حلقه 9 عدد حل کرده و حداقل دمایی که الگوریتم به جواب بهینه رسیده، برابر با 1.2 به عنوان دمای پایانی الگوریتم فرض می‍شود. روند همگرایی نقاط پذیرش‍شده در الگوریتم انجماد تدریجی در شکل 6 نمایش داده شده است.

 

 

شکل 6 - نمایش روند همگرایی نقاط پذیرش‍شده در الگوریتم انجماد تدریجی

4- تجزیه و تحلیل

4-1 مقایسه دو الگوریتم ژنتیک و انجماد تدریجی

پس از تعیین پارامترهای هر یک از الگوریتم‍ها به منظور مقایسه دو الگوریتم ژنتیک و انجماد تدریجی تعدادی مساله تصادفی طرح شده و نتایج آزمایش‍ها در زیر مقایسه شده‍اند. مسایل را در سه دسته کوچک (جدول 5)، متوسط (جدول 7)، بزرگ (جدول 9) بر اساس مقدار حداکثر تقاضا تقسیم می‍کنیم:

تقاضاهای کمتر از 3000 مسایل کوچک، بین 3000 تا 20000 مسایل متوسط و از 20000 به بالا مسایل بزرگ. در هر دسته 10 مساله تصادفی طرح گردیده و پس از 10 بار حل هر مساله توسط هر دو الگوریتم، این الگوریتم‍ها براساس بهترین پاسخ، کمترین انحراف معیار و متوسط مقدار پاسخ مقایسه گردیده‍اند.

 

4-1-1 دسته اول مسایل کوچک

از نظر بهترین نقطه 90% نتایج یکسان، و 10% مواقع الگوریتم انجماد تدریجی، از نظر میانگین 40% مواقع نتایج یکسان و در 60% مواقع الگوریتم انجماد تدریجی نتایج بهتری حاصل نموده است. همچنین، از نظر تعداد نقاط جستجو شده به طور کلی الگوریتم انجماد تدریجی نقاط کمتری را مورد جستجو قرار داده و زمان حل الگوریتم بسیار کمتر از الگوریتم ژنتیک است(جدول 6). شایان ذکر است که مجموع نقاط جستجو شده در الگوریتم ژنتیک ثابت و برابر 6888 نقطه است.

جدول 5 - خصوصیات مسایل دسته اول

 

شکل‌های 7 تا 9 نشان‍دهنده روند همگرایی در الگوریتم ژنتیک و انجماد تدریجی در دو مساله تصادفی در هر دسته از مسایل است، خطوط آبی نشان‍دهنده بهترین نقطه جمعیت در هر مرحله از الگوریتم ژنتیک و خطوط قرمز نشان‍دهنده بهترین نقطه در هر 8 بار جستجو در الگوریتم انجماد تدریجی است. دلیل انتخاب هر 8 بار هم مقیاس کردن دو الگوریتم انجماد تدریجی و ژنتیک است، زیرا در هر مرحله از الگوریتم ژنتیک حداقل 8 نقطه جدید به دست می‍آید (تعداد فرزندان برابر با 8 است).

 

4-1-2 دسته دوم مسایل متوسط

در ارتباط با این دسته از مسائل، از نظر بهترین نقطه 40% نتایج یکسان، و 60% مواقع الگوریتم انجماد تدریجی نتایج بهتری حاصل نموده است. همچنین، از نظر میانگین نتایج و انحراف معیار در همه‍ موارد الگوریتم انجماد تدریجی نتایج بهتری نسبت به الگوریتم ژنتیک به دست آورده است (جدول 8).

 

 

 

شکل 7 - مقایسه همگرایی الگوریتم SA و GA برای دسته اول مسایل

 

 

جدول 7 - خصوصیات مسایل دسته دوم

 

از نظر تعداد نقاط جستجو شده، به طور کلی الگوریتم انجماد تدریجی نقاط کمتری را مورد جستجو قرار داده است و زمان حل الگوریتم بسیار کمتر از الگوریتم ژنتیک است.

 

 

شکل 8.- مقایسه همگرایی الگوریتم SA و GA برای دسته دوم مسایل

4-1-3 دسته سوم مسایل بزرگ

در این مسایل، الگوریتم انجماد تدریجی در همه موارد نتایج بهتری نسبت به الگوریتم ژنتیک ارائه کرده، اما متوسط نقاط جستجو شده به شدت افزایش یافته و به طور متوسط 55 برابر نقاط جستجو شده در الگوریتم ژنتیک است. نتایج در جدول 10 و شکل شماره 9 نمایش داده شده است. همان طور که در این شکل مشاهده می‍شود، الگوریتم انجماد تدریجی سریعتر و یکنواخت‍تر به سمت نقطه بهینه نزدیک می‌شود.

 

جدول 9. خصوصیات مسایل دسته سوم

 

 

شکل 9-مقایسه همگرایی الگوریتم SA و GA برای دسته سوم مسایل

 

شایان ذکر است که سرعت حل برنامه‍ها به شدت تحت تاثیر دقت مورد محاسبه و پارامترهای ورودی مساله است. در نهایت، برای نشان دادن تفاوت بین افزایش هزینه‍های کمبود و مدل فوق که در چکیده بیان شد، فرض کنید با قرار دادن هزینه‍های کمبود برابر با 200000 در مثال 1 علی‍رغم نزدیک شدن نقاط R و Q به نقاط بهینه، سود حاصله به طور کلی متفاوت بوده یا برای مثال درهمه نقاطی که با کمبود‍های بیش از 0.01% رو به رو شوند، نقاط غیرقابل قبول و مقدار سود آنها منفی است، در حالی که در مدل فوق آن نقاط نیز سودآور اما بهینه نیستند. در ضمن، از دید مدیریت پرداخت چنین هزینه‍ای برای کمبود کاملا غیرعقلانی است. در دو مدل برای نقطه‍ (R , Q) = (50،150): مدل فوق جواب   و در حالتی که هزینه کمبود مطابق فوق باشد، داریم:

 

5- نتیجه گیری

آنچه در این تحقیق بررسی شده، شرایطی است که در آن مقدار تقاضا متاثر از درصد کمبود کالاست. تحت شرایط فوق در صورت افزایش موجودی و به تبع آن افزایش هزینه‍های نگهداری و کاهش درصد کمبود کالا، انتظار می‍رود مقدار تقاضا و درآمد شرکت افزایش یابد. مساله تعیین سیاست بهینه سفارش‍دهی در راستای حداکثر نمودن سود شرکت است.

همان ‌طور که در مقدمه بیان شد، برای اعمال تاثیر هزینه‍های کمبود تاکنون مدل‍های متنوعی به وجود آمده و توسعه داده شده‍اند. در این پروژه این تاثیرپذیری به شکل دیگری مدل و بررسی شده است. هدف از این نوع مدل کردن، اعمال تاثیر هزینه‍های کمبود مرتبط با اعتبار سازمان در فضای رقابتی بر تقاضای سازمان است.

در الگوریتم ژنتیک مورد استفاده در این مقاله، به ازای هر چند نسل (در اینجا 50 نسل)، شعاع کوچکی از بهترین نقطه موجود فعلی به صورت نقطه به نقطه بررسی می‍شود و بهترین نقطه‍ موجود در این شعاع به جمعیت الگوریتم ژنتیک افزوده می‍شود. این امر باعث افزایش چشمگیر سرعت حل مساله می‍گردد. نتایج محاسباتی کارایی الگوریتم ژنتیک توسعه یافته را نشان می‌دهد.

نتایج محاسباتی کارایی دو الگوریتم در یافتن نقاط نقطه سفارش و میزان سفارش در شرایطی که تقاضا متاثر از میزان کمبود است را نشان می‌دهد. همچنین،  نتایج اهمیت توجه به موضوع، تاثیر کمبود روی تقاضا را نشان می‌دهد. در این حالت، هزینه کمبود به صورت واقعی‌تری مدنظر قرار گرفته است و نتایج در شرایط واقعی‌تری از مساله به دست  می‌آید. در این میان نتایج مقایسه دو الگوریتم توسعه یافته نشان می‌دهد که در مجموع الگوریتم انجماد تدریجی ارایه شده نسبت به الگوریتم ژنتیک ارایه شده برای مساله مورد بررسی در این تحقیق نتایج بهتری را به دست  می‌آورد. از نظر تعداد نقاط جستجو شده نیز به طور کلی الگوریتم انجماد تدریجی نقاط کمتری را مورد جستجو قرار داده است و زمان حل الگوریتم بسیار کمتر از الگوریتم ژنتیک است.

توسعه مدل فوق برای سفارش‌های چند کالایی با توجه به محدودیت‍های حداکثر فضای کل انبار و وجود نرخ‍های متفاوت J_i که نشان‍دهنده حداکثر کمبود قابل قبول برای هر کالاست، می‍تواند زمینه‍ای برای تحقیقات آینده باشد.