مسیریابی وسایل نقلیه در زنجیره تأمین چند‌محصولی با استفاده از الگوریتم شبیه‌سازی تبرید جمعیتی

مقدمه

مسأله مسیریابی وسایل نقلیه (VRP^[i]) یکی از مهم‌ترین مسائل موجود در صنایع جهان است و امروزه به‌علت کاربردهای واقعی در مسائل صنعتی توجه زیادی به آن شده است. اولین بار این مسأله را دانتزیک و رامسر مطرح کردند. این مسأله، در زمینه‌های حمل­ونقل، توزیع و لجستیک مهم است (دانتزیگ و رامسر^[ii]، 1959). در سال‌های اخیر، برای کاهش قیمت­ها و افزایش رقابت‌پذیری، فشار زیادی بر صنایع وارد شده است. دراین‌راستا، مدیران از روش­های مختلفی چون برنامه­ریزی و زمان‌بندی تولید استفاده کرده­اند و تمرکز آنها به درون بنگاه برای کاهش هزینه­ها بوده است؛ ولی سازمان­ها برای ادامۀ حیات و بقا، ناچار به تعامل با سایر سازمان­ها هستند؛ از‌این‌رو برای کاهش هزینه­ها باید دیدی فر‌ا‌سازمانی داشت. بنابراین بررسی هم‌زمان نحوۀ مسیریابی و زمان‌بندی حمل­ونقل با زمان‌بندی تولید، توجه بسیاری از مدیران را به خود جلب کرده است؛ زیرا این دو نوع زمان‌بندی بر یکدیگر تأثیر متقابل دارند و تصمیماتی که در یکی از این دو مسأله گرفته می­شود، روی تصمیمات مسائل دیگر اثرگذار است. ازاین‌رو این مقاله، زمان‌بندی تولید و حمل­ونقل در یک زنجیره تأمین را با در نظر گرفتن تأثیر متقابل این دو برهم بررسی می‌کند. زنجیره تأمین شامل مجموعه­ای از تأمین­کنندگان، تولیدکنندگان و توزیع‌کنندگان است که هدف واحد آنها، برطرف‌کردن نیاز مشتری است. یک زنجیره تأمین، تعیین‌کنندۀ تمام سطوحی است که در یک کالای تولیدی، ارزش افزوده ایجاد می‌کند ( چانگ و لی^[iii]، 2004). از سوی دیگر حالت چند‌محصولی نیز در این زنجیره تأمین در نظر گرفته شده است. حالت چندمحصولی یعنی یک تأمین­کننده قادر به پردازش تمام سفارش‌ها نیست و با‌توجه‌به ماهیت سفارش‌ها، تنها بخشی از آنها را پردازش می‌کند. مسأله VRP دارای نسخه‌های متعددی است. در این پژوهش حالتی از آن در نظر گرفته می­شود که تعدادی وسایل نقلیه ناهمگن وظیفۀ جمع آوری سفارش‌ها را از تأمین‌کنندگان در نقاط جغرافیایی متفاوت بر عهده دارند. تفاوت مسأله بررسی‌شده در این پژوهش با مسأله VRP این است که در مسأله VRP فرض می‌شود مقدار کالایی که باید از هر تأمین­کننده حمل شود، مشخص است؛ اما در مسأله بررسی‌شده در این پژوهش، فرض می‌شود تخصیص سفارش‌ها به تأمین­کنندگان و تعیین توالی تولید آنها، جزءِ متغیرهای تصمیم مسأله است.

زنجیره تأمین بررسی‌شده در این مقاله مربوط به یک زنجیره تأمین دو‌بخشی است. بخش نخست شامل تأمین‌کنندگان است. این تأمین­کنندگان در نقاط مختلف جغرافیایی مستقر هستند و هریک توانایی تولید برخی از سفارش‌ها را دارند. بخش دوم متشکل از چند وسیلۀ نقلیه است که باید سفارش‌های پردازش‌شده نزد تأمین­کنندگان را جمع­آوری کنند و به شرکت سازنده تحویل دهند. شکل 1 نشان‌دهندۀ شمای کلی زنجیره تأمین بررسی‌شده، است. در این زنجیره، 5 سفارش، 4 تأمین­کننده و 2 وسیله نقلیه در نظر گرفته شده است. در این شکل، تخصیص سفارش‌ها به تأمین‌کنندگان، وسایل نقلیه و مسیر حرکت وسایل نقلیه مشخص شده است. این ساختار در صنایعی نظیر خودروسازی، محصولات الکترونیکی و صنایع شیمیایی وجود دارد.

هدف مسأله، تعیین چگونگی تخصیص سفارش‌ها به تأمین­کنندگان، تعیین ترتیب پردازش سفارش‌ها تخصیص‌یافته به یک تأمین­کننده، تخصیص سفارش‌ها به وسایل نقلیه و تعیین ترتیب حمل به هر وسیلۀ نقلیه است؛ به قسمی که مجموع زمان تحویل سفارش‌ها حداقل شود.

1

2

3

4

1

2

5

1

4

2

3

تأمین­کننده :

وسیله نقلیه :

سفارش :

راهنما

تولیدکننده :

شکل 1- حالت کلی زنجیرۀ تأمین

 

در ادامه در بخش 2، ادبیات در حوزۀ زنجیره تأمین مرور می­شود. در بخش 3 دربارۀ مسأله بررسی‌شده به‌تفصیل توضیح داده می‌شود و مسأله با یک مدل برنامه­ریزی عدد صحیح مختلط فرموله می­شود. در بخش 4 روش­های حل پیشنهادی ارائه‌می‌شوند. در بخش 5 الگوریتم شبیه­سازی تبرید جمعیتی با الگوریتم ژنتیک و شبیه­سازی تبرید کلاسیک مقایسه می‌شود و درنهایت در بخش 6 جمع­بندی و زمینه­هایی برای پژوهش‌های آتی فراهم می‌شود.

 

مرور ادبیات

تاکنون پژوهش‌های متعددی در زمینۀ ترکیب زمان‌بندی تولید و حمل­ونقل در زنجیره تأمین انجام شده است. وانگ و چنگ^[iv] (2009) مسأله زمان‌بندی تأمین و تحویل سفارش‌ها را با هدف حداقل‌کردن بازۀ ساخت بررسی کرده‌اند. در مسأله آنها وسیلۀ نقلیه با ظرفیت محدود و زمان حملِ ثابت، سفارش‌ها را از انبار تأمین­کنندگان به کارخانه و وسیله‌ای دیگر از کارخانه به مشتریان انتقال می‌دهد. آنها نشان دادند مسأله از نوع NP-hard است و یک الگوریتم ابتکاری برای حل آن ارائه کرده‌اند. یمیر و دمیرلی^[v] (2010) یک الگوریتم ژنتیک برای زمان‌بندی در یک زنجیره تأمین دو مرحله­ای ارائه کرده­اند. آنها یک مدل برنامه­ریزی خطی عدد صحیح مختلط^[vi] نیز برای بهینه­سازی تأمین و مونتاژ قطعات و زمان‌بندی توزیع، ارائه کرده‌اند. اسکولز ریتر و همکاران^[vii] (2010) یکپارچگی تولید و حمل­ونقل در یک زنجیره تأمین عمومی را بررسی و یک مدل ریاضی برای حل مسأله ارائه کرده‌اند. تابع هدف مسأله آنها حداقل‌کردن مجموع هزینه­های دیرکرد سفارش‌ها، هزینه­های پردازش، هزینه‌های نگهداری سفارش‌ها و هزینه­های ثابت و متغیر حمل‌ونقل هستند. لئو و چن^[viii] (2012) یکپارچگی مسیریابی، کنترل موجودی و زمان‌بندی را در یک زنجیره تأمین بررسی کرده‌اند و پس از مدل‌سازی ریاضی مسأله، الگوریتم جستجوی همسایگی برای حل آن ارائه کرده‌اند. تابع هدف مسأله، حداقل‌کردن مجموع هزینه­های موجودی، مسیریابی و استفاده از وسایل نقلیه است. مهرآوران و لجندران^[ix] (2012) زمان‌بندی در محیط جریان‌کاری با زمان­های آماده­سازی وابسته به توالی را با دو تابع هدف حداقل‌کردن سفارش‌های نیمه‌ساخته و حداکثرکردن سطح سرویس بررسی کرده‌اند. آنها یک الگوریتم جستجوی ممنوع^[x] برای حل مسأله، ارائه کرده‌اند. کو و وانگ^[xi] (2012) مسأله مسیریابی چندنقطه­ای وسیلۀ نقلیه را با هزینۀ بارگیری بررسی کرده‌اند و روش جستجوی همسایگی متغیر را برای حل آن ارائه کرده­اند. روش آنها شامل سه مرحله است: مرحلۀ اول ایجاد یک روش تصادفی برای تولید جواب اولیه؛ مرحلۀ دوم، انتخاب تصادفی چهار اپراتور برای جستجو در جواب­های همسایگی و مرحلۀ سوم، ارائه معیارهای مشابه شبیه­سازی تبرید برای پذیرش پاسخ­های همسایگی است. عثمان و دمیرلی^[xii] (2012) زمان‌بندی تحویل و اندازۀ انباشتۀ اقتصادی را در یک زنجیره تأمین سه‌مرحله­ای و چند‌محصولی بررسی کرده‌اند. این مراحل شامل تأمین­کنندگان ردۀ دوم، تأمین­کنندگان ردۀ اول و مونتاژکنندۀ قطعات هستند. آنها یک مدل جدید بر پایه مسأله تخصیص مضاعف برای مسأله ارائه کرده‌اند. مدل آنها، سیکل مشترکی را برای هماهنگی در پر ‌و‌ تخلیه‌شدن انبارها، تعیین می­کند. الریچ^[xiii] (2013) یکپارچگی زمان‌بندی ماشین­آلات و مسیریابی وسایل نقلیه را با در نظر گرفتن پنجره­های زمانی مطالعه کرده است. در این پژوهش یک زنجیره تأمین دو‌مرحله­ای بررسی شده است. مرحلۀ نخست شامل یک محیط ماشین­های موازی^[xiv] با زمان­های آمادگی وابسته به ماشین است. مرحلۀ دوم نیز شامل یک ناوگان وسایل نقلیه با ظرفیت­های حمل متفاوت است. کابرا و همکاران^[xv] (2013) زمان‌بندی در زنجیره تأمین داروسازی را برای یک محیط چند‌مرحله­ای، چند‌محصولی و چند‌دوره­ای بررسی کرده‌اند. آنها زمان‌بندی را به‌صورت پیوسته در نظر گرفته و یک مدل برنامه­ریزی عدد صحیح مختلط برای آن ارائه کرده‌اند. آورباخ و بیسان^[xvi] (2013) مسأله زمان‌بندی در یک زنجیره تأمین دوسطحی را بررسی و یک الگوریتم تخمینی برای آن ارائه کرده‌اند. در مسأله آنها قطع عملیات مجاز و تحویل سفارش‌ها به‌صورت دسته­ای در نظر گرفته شده است. تابع هدف، حداقل‌کردن مجموع جریان سفارش‌ها و هزینه­های تحویل کالاها در نظر گرفته شده است. رن و همکاران^[xvii] (2013) یک زنجیره تأمین دو‌مرحله­ای را در نظر گرفتند. در این زنجیره، تعدادی تأمین­کننده، قطعات لازم برای یک مونتاژکننده را فراهم می­آورند. زمان تحویل هر محصول برابر حداکثر زمان تحویل قطعاتی است که تأمین­کنندگان برای مونتاژکننده فراهم می­آورند. توماس و همکاران^[xviii] (2014) زمان‌بندی در زنجیره تأمین زغال سنگ را با چند فعالیت مستقل، بررسی کرده‌اند. در این مسأله، محدودیت­های منابع با هم در ارتباط هستند. مسأله آنها از دو زیرمسأله برنامه­ریزی و زمان‌بندی تشکیل شده است. آنها یک مدل ریاضی عدد صحیح مختلط برای مسأله، ارائه و از تکنیک تولید ستون^[xix] برای حل آن استفاده کرده‌اند. ساویک^[xx] (2014) ارتباط زمان‌بندی با انتخاب تأمین‌کنندگان را در حالت وجود ریسک­های قطع، بررسی و یک مدل برنامه­ریزی عدد صحیح مختلط و احتمالی برای مسأله ارائه کرده‌اند. در این پژوهش، فرض شده است تأمین­کنندگان در دو دستۀ­ داخل ناحیه تولید و خارج آن تقسیم­بندی شده­اند. تابع هدف، حداقل‌کردن هزینه­ها و افزایش سطح سرویس هستند. سالوارجاه و ژانگ^[xxi] (2014) زمان‌بندی زنجیره ­تأمینی را بررسی کرده‌اند که در آن یک تولیدکننده، مواد نیمه‌ساخته را از تأمین­کنندگان در زمان­های متفاوت دریافت می‌کند و کالاهای تکمیل‌شده را به‌صورت دسته­ای به مشتریان تحویل می­دهد. تابع هدف مسأله آنها حداقل‌کردن مجموع وزنی جریان سفارش‌ها و هزینه­های تحویل دسته­ها هستند و برای حل آن یک الگوریتم ابتکاری پیشنهاد کرده‌اند. ری و همکاران^[xxii] (2014) یک مسأله حمل‌ونقل چندانباری را با در نظر گرفتن چندین وسیلۀ حمل بررسی کرده­اند که امکان تحویل چند‌نوبتۀ کالا در آن وجود دارد. آنها یک مدل برنامه‌ریزی خطی جدید ارائه داده­اند. همچنین با ارائۀ یک الگوریتم ابتکاری، جوابی نزدیک به جواب بهینه به‌دست آورده‌اند. آرچتی و همکاران^[xxiii] (2015) یک مسأله حمل­ونقلِ چند‌دوره­ای را با در نظر گرفتن تاریخ تحویل بررسی کرده­اند. هدف، یافتن مسیر بهینه برای وسایل نقلیه است؛ به‌گونه­ای که تمام هزینه­های حمل­ونقل، انبارداری، جریمه­ها، هزینه­های سرویس­دهی و ... حداقل شوند. آنها یک الگوریتم شاخه­وکران و یک تحلیل محاسباتی برای حل این مسأله ارائه دادند.

با در نظر گرفتن میزان یکپارچگی شرکت­ها در زنجیره تأمین، پژوهش‌های انجام‌شده به چهار دسته تقسیم می‌شوند. 1)‌ پژوهش‌هایی که رابطۀ شرکت‌های سازنده با تأمین­کنندگانشان را بررسی کرده‌اند؛ 2) پژوهش‌هایی که رابطۀ شرکت سازنده با توزیع­کنندگان یا مشتریانشان را بررسی کرده‌اند؛ 3) پژوهش‌هایی که رابطۀ چند شرکت سازنده را با یکدیگر بررسی کرده‌اند (برو‌ن‌سپاری^[xxiv])؛ 4) پژوهش‌هایی که ترکیبی از حالت‌های بالا را در نظر گرفته‌اند.

از نظر سطح بررسی زنجیره تأمین، پژوهش‌های انجام‌شده به دو دسته تقیسم می‌شوند: 1) پژوهش‌هایی که به‌صورت کلان در زنجیره تأمین، برنامه­ریزی تولید^[xxv] و هماهنگی را انجام داده‌اند. 2) پژوهش‌هایی که به‌صورت عملیاتی زمان‌بندی و هماهنگی را در زنجیره تأمین انجام داده‌اند. بررسی ادبیات موضوع نشان می­دهد، ترکیب مسأله VRPبا مسأله زمان‌بندی تولید در زنجیره تأمین در حالت وجود محدودیت در تخصیص سفارش‌ها به تأمین­کنندگان تاکنون بررسی نشده است.

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

مسأله ذگردی و بهشتی­نیا^[xxvi] (2009) نزدیک‌ترین پژوهش به این پژوهش است. آنها در مسأله خود فرض کرده­اند، تأمین­کنندگان در نواحی مختلف جغرافیایی پراکنده شده­اند و زمان حمل­ونقل بین تأمین­کنندگان در یک ناحیه جغرافیایی، برابر صفر در نظر گرفته می­شود. همچنین فرض شده است حمل‌ونقل بین تأمین­کنندگانی که در نواحی مختلف جغرافیایی پراکنده­اند مجاز نیست. به‌عبارتِ‌دیگر، در مسأله آنها محاسبات حمل‌و‌نقل بین تأمین‌کنندگان انجام نمی­شود؛ یعنی مسأله مسیریابی وسایل نقلیه مطرح نیست. در این مقاله، مسأله آنها برای توسعه حالتی است که حمل­ونقل بین تمام تأمین‌کنندگان مجاز است و زمان­های حمل‌ونقل در نظر گرفته می‌شود‌؛ به‌عبارتی مسأله مسیریابی نیز در نظر گرفته می­شود. بررسی مقالات موجود در ادبیات موضوع نشان می­دهد، ترکیب مسأله VRPبا مسأله زمان‌بندی تولید در زنجیره تأمین در حالت وجود محدودیت در تخصیص سفارش‌ها به تأمین­کنندگان تاکنون بررسی نشده است. همچنین برای حل آن از یک الگوریتم ترکیبی با نام شبیه­سازی تبرید جمعیتی (PSA) استفاده می­شود. این الگوریتم، تلفیق جدیدی از دو الگوریتمِ ژنتیک (GA) و شبیه­سازی تبرید (SA) است.

جدول 1- دسته‌بندی مسائل در ادبیات موضوع زمان‌بندی در زنجیره تأمین

 

بنابراین نوآوری‌های این مقاله به‌شرح زیر هستند:

• تعمیم مسأله ذگردی (2009) در حالتی که حمل‌و‌نقل بین همه تأمین­کنندگان مجاز است و نباید زمان حمل بین تأمین­کنندگان را نادیده گرفت.
• ارائه ترکیبی از مسأله VRP و زمان‌بندی تولید در تأمین­کنندگان یک زنجیره تأمین در حالتی که هر تأمین­کننده قادر به پردازش تمام سفارش‌ها نباشد.
• توسعۀ یک مدل ریاضی جدید برای حل مسأله.
• ارائه یک الگوریتم ترکیبی به‌نام الگوریتم شبیه­سازی تبرید جمعیتی (PSA^[xxvii]) برای حل مسأله که تلفیق جدیدی از دو الگوریتم GA^[xxviii] و SA^[xxix] است و همگام­سازی دو الگوریتم مذکور با فرضیات این مسأله.

 

 

تعریف مسأله

در این بخش، ابتدا فرضیات مسأله تبیین و سپس مدل ریاضی مربوط به مسأله ارائه می­شود.

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

تعاریف و مفروضات مسأله بررسی‌شده به‌شرح ذیل هستند:

• تعداد n سفارش وجود دارد. m تأمین­کننده بدون محدودیت ظرفیت، این سفارش‌ها را پردازش می‌کنند. همچنین این n سفارش با l وسیلۀ نقلیه، جمع­آوری و به شرکت اصلی انتقال داده می‌شوند. هریک از این n سفارش دارای حجم یا وزن مشخصی هستند؛ اما ممکن است این حجم یا وزن با هم برابر نباشند.
• تأمین­کنندگان در نقاط مختلف جغرافیایی قرار دارند و و فاصلۀ آنها نسبت به هم و نسبت به شرکت اصلی مشخص است. برای کاهش هزینه­های حمل­ونقل، وسایل نقلیه مجاز هستند سفارش‌ها را از تأمین­کنندگان در نواحی جغرافیایی مختلف بارگیری کنند. تأمین­کنندگان به‌علت داشتن تجهیزات تخصصی، توانایی پردازش تمامی سفارش‌ها را ندارند و فقط سفارش‌های خاصی را پردازش می‌کنند.
• هر وسیلۀ نقلیه، پس از تحویل محموله به شرکت اصلی، از مسأله حذف نمی­شود و باید دوباره استفاده شود. سفارش‌هایی را که هربار با یک وسیلۀ نقلیه به شرکت اصلی تحویل داده می­شوند، یک محموله می‌گویند. هر محموله شامل کالاهای پردازش‌شدۀ چند تأمین­کنندۀ مختلف است. زمان تحویل به شرکت، برای سفارش‌های موجود در یک محموله، یکسان است. حداکثر محمولۀ هر وسیله در بیشترین حالت ممکن برابر با تعداد سفارش‌ها است؛ آن‌هم وقتی همۀ سفارش‌ها به یک وسیله نقلیه تخصیص یابد و این وسیله در هر محمولۀ خود یک سفارش را حمل کند.

سوال اصلی پژوهش به‌صورت زیر است:

نحوۀ زمان‌بندی تولید و حمل‌و‌نقل در زنجیره تأمینی شامل یک شرکت سازنده با تأمین‌کنندگانش با هدف حداقل‌کردن مجموع زمان تحویل سفارش‌ها چگونه باشد؟

سوالات فرعی پژوهش نیز به صورت زیر است:

• اختصاص سفارش‌ها به تأمین­کنندگان چگونه باشد؟
• توالی انجام سفارش‌های تخصیص‌یافته به هر تأمین­کننده چگونه باشد؟
• نحوۀ تخصیص محموله­ها به وسائل چگونه باشد؟
• نحوۀ تقسیم‌بندی سفارش‌های تخصیص‌یافته به هر وسیلۀ نقلیه به محموله‌های مختلف و مسیریابی حرکت آن چگونه باشد؟

شکل 2، یک جوابِ شدنی مسأله بررسی‌شده را نشان می­دهد؛ به‌طوری که دو وسیلۀ نقلیه مسئولِ جمع‌آوری سفارش‌های پردازش‌شده هستند. وسیلۀ نقلیه اول، ابتدا باید سفارش شماره 4 را نزد تأمین‌کننده چهارم بارگیری کند، سپس با‌توجه‌به ظرفیت باقی‌مانده، سفارش دوم نزد تأمین­کنندۀ اول را بارگیری کرده و به کارخانه سازندۀ محصولات نهایی تحویل دهد. همچنین وسیله نقلیۀ دوم باید سفارش‌های 1 و 5 نزد تأمین­کنندۀ سوم و سپس سفارش 3 نزد تأمین­کنندۀ دوم را بارگیری و به کارخانه تحویل دهد.

 

 

شکل 2- یک جواب شدنی از مسأله

 

مدل ریاضی مسأله: در این بخش مدل ریاضی عدد صحیح مختلط مسأله بیان می­شود. قبل از ارائه مدل ریاضی مسأله، ابتدا نمادهای استفاده‌شده معرفی می­شوند. مجموعۀ استفاده‌شده در مدل عبارت‌اند از:

- مجموعه‌ای شامل N سفارش، هر سفارش با اندیسi یا q نشان داده می­شود:

- مجموعه‌ای شامل Sتأمین­کننده، هر تأمین­کننده با اندیس s یا s' نشان داده می­شود:

- مجموعه‌ای شامل V وسیلۀ نقلیه، هر وسیلۀ نقلیه با اندیس m نشان داده می­شود:

- ممکن است هر وسیلۀ نقلیه نیز چندین محموله داشته باشد که اندیس آن با b نمایش داده می­شود:

- در هر محموله، اولویت بارگذاری سفارش‌ها با اندیس p نشان داده می­شود. بیشترین مقدار برای p برابر N است (وقتی همه سفارش‌ها به یک محموله از یک وسیلۀ نقلیه اختصاص یابد):

پارامترهای مسأله نیز عبارتند از:

- ظرفیت اشغالی توسط سفارش i ام: Vol_i

- ظرفیت حمل وسیلۀ نقلیه mام برحسب تعداد سفارش‌ها: Cap_m

- زمان پردازش سفارش i ام: pt_i

- مدت زمان تردد بین تأمین­کنندۀ s و کارخانه با وسیلۀ نقلیه m: ttT_ms

- مدت زمان تردد بین تأمین­کنندۀ s و s' با وسیلۀ نقلیه m:

- یک ماتریس با ابعاد N*S، اگر a(i,s) برابر 1 باشد به‌معنای مجاز‌بودن تخصیص سفارش i به تأمین­کنندۀ s است و بالعکس: A

- یک عدد بزرگ مثبت: M

متغیرهای تصمیم مدل نیز به‌صورت زیر هستند:

- زمان تکمیل سفارش i در مرحلۀتأمین­کنندگان: c_i

- زمان تحویل سفارش iبه کارخانه: D_i

- زمان بارگذاری سفارش i ام روی یکی از وسایل نقلیه به‌منظور حمل: L_i

- وقتی وسیلۀ نقلیه m ام، آماده حمل سفارش i در bامین مأموریت خود است: av_mbi

- اگر سفارش i ام به تأمین­کنندۀ s ام داده شود، برابر یک و در غیر این‌صورت برابر صفر است: x_si

- اگر در مرحلۀ تأمین­کنندگان سفارش i قبل از سفارش q قرار گیرد، برابر یک و در غیر این‌صورت برابر صفر است: y_iq

- اگر اولویت حمل pاام در bامین حمل به وسیلۀ نقلیه m مربوط به سفارش iاام باشد برابر یک و در غیر ‌این‌صورت برابر صفر است: U_mbip

مدل ریاضی مسأله به‌صورت زیر است:

 

مجموعه محدودیت 2 نشان می‌دهد، هر سفارش تنها باید به یک تأمین­کننده تخصیص داده شود. مجموعه محدودیت 3 نشان می‌دهد، هر سفارش باید تنها به یک وسیلۀ نقلیه و به یک محموله از آن تخصیص یابد. مجموعه محدودیت 4 نشان می‌دهد، یک سفارش نمی­تواند به بیش از یک موقعیت در محموله­ها و وسایل نقلیه تخصیص یابد. مجموعه محدودیت 5 تضمین می­کند، در هر محموله مجموع فضای اشغالیِ سفارش‌های تخصیص‌یافته به یک وسیلۀ نقلیه نباید از ظرفیت آن وسیلۀ نقلیه بیشتر شود. مجموعه محدودیت 6 زمان تکمیل هر سفارش در مرحلۀ تأمین­کنندگان را در نظر می­گیرد. مجموعه محدودیت 7 بیان می­کند، هر تأمین­کننده نمی­تواند در هر لحظه بیش از یک سفارش را پردازش کند. مجموعه محدودیت 8 مقداری از متغیرهای زاید را حذف می‌کند. مجموعه محدودیت 9 تضمین می­کند، اگر به اولویت p ام محمولۀ b ام از وسیلۀ نقلیه mاام سفارشی تخصیص نیابد، به اولویت p+1 ام آن محموله، سفارشی تخصیص داده نمی‌شود. مجموعه محدودیت 10 تضمین می­کند، اگر به محمولۀ b ام از وسیلۀ نقلیه m ام سفارشی تخصیص نیابد، به محمولۀ b+1 ام آن سفارشی تخصیص داده نمی‌شود. مجموعه محدودیت 11 و 12 نشان می‌دهند، زمان بارگذاری هر سفارش برابر بیشینۀ زمان تکمیل پردازشِ سفارش و زمان آماده‌بودن وسیلۀ نقلیه مرتبط برای حمل آن است.

مجموعه محدودیت 13 تعیین‌کنندۀ زمانِ آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به اولویت اولِ اولین محموله آن اختصاص یافته است. مجموعه محدودیت 14 تعیین‌ کنندۀ زمان آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به اولویت اولِ یک محموله اختصاص یافته است؛ زمان آماده‌بودن با‌توجه‌به زمان تحویل سفارش‌های محمولۀ قبلی، مقصد محمولۀ قبلی و زمان حمل تا تأمین­کنندۀ مرتبط، تعیین می‌کنند. مجموعه محدودیت 15تعیین کنندۀ زمان آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به یک محموله اختصاص یافته است؛ زمان ‌آماده‌بودن با‌توجه‌به زمان بارگذاری سفارش اولویتِ حمل قبلی و زمان حمل بین تأمین‌کنندگان مرتبط تعیین می­شود. مجموعه محدودیت 16 زمان تحویل یک سفارش را با‌توجه‌به زمان بارگذاری کلیۀ سفارش‌های متعلق به محموله خود و مقصد آن تعیین می­کنند. مجموعه محدودیت 17 از اختصاص سفارش‌ها به تأمین­کنندگان غیرمجاز جلوگیری می­کند.

در‌واقع زمان بارگذاری یک قطعه هنگامی اتفاق می‌افتد که سفارش نزد تأمین کننده آماده و وسیلۀ نقلیه به محل تأمین کننده رسیده است.

همان‌گونه که اشاره شد، C_i بیانگر زمان تکمیل سفارش i ام و Av_mbiبیانگر زمان آماده‌بودن وسیلۀ نقلیه برای حمل سفارش مربوطه است. زمان بارگذاری واقعی سفارش i ام که با L_i نشان داده می­شود، بزرگتر یا مساوی هر دو این متغیرها است. محدودیت‌های 11 و 12 بیانگر این نکته هستند.

چانگ و لی (2004) نشان می‌دهند، مسأله بررسی‌شده در حالتِ وجود یک وسیلۀ نقلیه، دو تأمین­کننده و بدون در نظر گرفتن فاصلۀ بین تأمین‌کنندگان، از نوع NP-hard است؛ بنابراین حالت تعمیم­یافتۀ مسأله شامل S تأمین­کننده و V وسیلۀ نقلیه از نوع NP-hard خواهد بود.

 

ارائه روش­های حل

برای حل مسأله مذکور، سه الگوریتم شامل الگوریتم ژنتیک، الگوریتم شبیه­سازی تبرید و الگوریتم ترکیبی به‌نام الگوریتم شبیه­سازی تبرید چند­جمعیتی (PSA) (تلفیقی جدید از الگوریتم­های ژنتیک و شبیه­سازی تبرید)، ارائه می­شوند.

الگوریتم GA: الگوریتم GA یک الگوریتم فرا ابتکاری است و در حل مسائل NP-hard استفاده می­شود. این الگوریتم جواب­‌های خوبی در زمان معقول ارائه می­دهد. ایدۀ اصلی الگوریتم ژنتیک از اصل تنازع بقاء موجودات گرفته شده است. این الگوریتم را جان هالند^[xxx] در سال 1970 ارائه داده است.

گام­های الگوریتم فراابتکاری GA برای این مسأله به‌شرح ذیل است:

گام 1) ایجاد تعدادی جواب تصادفی( نسل اولیه^[xxxi]).

گام 2) انجام عملگر­های تلفیق^[xxxii] و جهش^[xxxiii] برای تعدادی از جواب­های این نسل.

گام 3) انتخاب نسل بعدی با استفاده از عملگر انتخاب^[xxxiv].

گام 4) اگر معیار خاتمه محقق شد، الگوریتم پایان می­یابد، در ‌غیر‌ این‌صورت به گام 2 بازگشته و این روند تکرار می­شود.

تعریف ساختاری مناسب برای رمزنگاری^[xxxv] هر جواب به‌صورت یک کرومزوم، کلیدی­ترین عنصر در الگوریتم ژنتیک به‌منظور حل مسائل جدید است. به‌عبارت‌دیگر، اگرساختار کرومزومی در فضای ژنوتایپ^[xxxvi] تعریف شود که معادل هر جواب در فضای فنوتایپ^[xxxvii] باشد، حل مسأله با الگوریتم ژنتیک میسر است و بالعکس.

ساختار کرومزوم در الگوریتم ژنتیک ارائه‌شده، دو‌بُعدی است. بُعد عمودی، نشان­دهندۀ تأمین­کنندگان و وسایل نقلیه و بُعد افقی نشان­دهندۀ سفارش‌های تخصیص‌یافته و ترتیب آنها به هر‌یک از تأمین‌کنندگان و وسایل نقلیه است.

شکل 3- سفارش­های تخصیص‌یافته و ترتیب آنها

 

به‌منظور توضیح بیشتر، فرض کنید 5 سفارش، 3 تأمین­کننده و2 وسیلۀ نقلیه وجود دارد و تخصیص سفارش­ها به تأمین­کنندگان و وسایل نقلیه، همچنین اولویت پردازش و حمل آنها به‌صورت شکل 1 است. آنگاه ساختار کرومزومی بیان‌کنندۀ تخصیصِ شکل 3، شکل 4 خواهد بود.

 

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

 

درصورت تخصیص سفارش‌ها بیش از ظرفیت وسیلۀ نقلیه به آن، برای وسیلۀ نقلیه مذکور تور (محموله) جدیدی ایجاد می­شود. نحوۀ تشکیل این تورهای جدید برای هر وسیلۀ نقلیه با الگوریتم زیر است:

گام 1- اولویت سفارش‌های اختصاص داده‌‌شده به وسیلۀ نقلیه مورد نظر را براساس ساختار کرومزوم در نظر بگیرید.

گام 2- سفارش با اولویت اول را به اولین تور اختصاص دهید.

گام 3- سفارشی که اولویت حمل اول را داشته و هنوز به محموله‌ها تخصیص نیافته است، در نظر بگیرید. اگر ظرفیت وسیلۀ نقلیه اجازه تخصیص سفارش مذکور را به تور فعلی می­دهد، این تخصیص را انجام دهید؛ در ‌غیر ‌این‌صورت، تور فعلی را بسته و تور جدیدی ایجاد کنید. این سفارش را به تور جدید تخصیص دهید و تور جدید را به‌جای تور فعلی در نظر بگیرید.

گام 4- اگر تمامی سفارش‌ها تخصیص داده‌شده به وسیلۀ نقلیه به تورها تخصیص یافته‌اند، الگوریتم را خاتمه دهید؛ در‌ غیر ‌این‌صورت به گام 2 بازگردید. هر وسیلۀ نقلیه پس از جمع‌آوری سفارش‌های یک تور، به کارخانه بازگشته و آنها را تحویل می‌دهد و دوباره برای جمع­آوری سفارش‌های تور بعدی عازم می­شود.

مانند سایر مسائل زمان‌بندی، درصورت تغییر در ورودی‌های مسأله، نظیر تعداد وسایل نقلیه، تعداد سفارش‌ها و .. مسأله جدید باید دوباره حل شود.

عملگر تلفیق: عمل تلفیق به‌صورت شکل 5 انجام می­شود. برای این کار ابتدا دو کرومزوم از چرخ رولت انتخاب می­شوند. سپس یک آرایه تصادفی صفر و یک تولید می­شود. تعداد سلول­های آن به‌اندازه تعداد سفارش‌ها هستند. سفارشی که در آرایۀ تولید‌شده، عدد صفر به آن تعلق گرفته، جایگاه خود را در کرومزوم فرزند از والد اول و سفارش با عدد یک جایگاهش را از والد دوم به ارث می­برد. اگر این جایگاه قبلا پر شده، سفارش به اولین سلول خالی سمت راست تخصیص می­یابد.

عملگر جهش: شکل 6 چگونگی عملگر جهش را نشان می­دهد. در این حالت با احتمال 0.5، بخش تأمین­کننده و یا وسیلۀ نقلیه انتخاب شده و دو سفارش به‌صورت تصادفی با هم تعویض می­شوند.

در عملگر تعویضِ استفاده‌شده، ابتدا یک عدد تصادفی بین 0 و 1 تولید می­شود. اگر عدد تصادفی تولید‌شده بین 0 و 5/0 باشد، 2 ژن را از تکۀ مربوط به تأمین­کنندگان انتخاب کرده و مکان این 2 ژن تعویض می­شود. در تخصیص جدید باید دقت داشت که تأمین­کننده می‌تواند سفارش تعویض‌شده را پردازش کند یا خیر. درصورت مثبت‌بودن جواب، روند کار ادامه پیدا می­کند؛ در ‌غیر ‌این‌صورت جریمۀ زیادی به تابع هدفِ این کرومزوم اختصاص داده می­شود. حال اگر عدد تصادفی تولید‌شده بین 5/0 و 1 باشد، 2 ژن را از تکۀ مربوط به وسایل نقلیه انتخاب کرده و مکان این 2 ژن تعویض می­شود.

 

 

شکل 5- عملگر تلفیق

 

 

شکل 6- عملگر جهش

 

با استفاده از روش تاگوچی پارامترهای الگوریتم GA به‌صورت جدول 2 تعیین شدند.

 

جدول 2- پارامترهای الگوریتم GA

 

الگوریتمSA: کریک پاتریک و وکی^[xxxviii] (1983) الگوریتم شبیه­سازی تبرید را برای حل مسائل بهینه­سازی ترکیبی پیشنهاد کردند. این الگوریتم با الهام‌گرفتن از نحوۀ سرد‌‌شدن فلزات، مسائل مختلف را بهینه‌سازی می­‌کند. گام­های الگوریتم فرا ابتکاری SA برای این مسأله به شرح ذیل هستند:

گام 1- دمای اولیه، تابع سرمایش، شرط خاتمه و تابع احتمال پذیرش جواب­های بد (تابع بولتزمان) را تعیین کنید.

گام 2- یک جواب اولیه برای ورودی الگوریتم در نظر بگیرید.

گام 3- با استفاده از عملگر­ تعویض، تعداد K همسایگی­ برای جواب فعلی ایجاد کنید.

گام 4- اگر مقدار بهترین همسایگی به‌دست آمده از جواب فعلی بهتر باشد، آن را جایگزین جواب فعلی کنید؛ در‌ غیر ‌این‌صورت یک عدد تصادفی بین صفر و یک ایجاد کنید. اگر این عدد از مقدار تابع بولتزمان کمتر باشد، بهترین همسایگی را جایگزین جواب فعلی کنید؛ در غیر ‌این‌صورت آن را رد کنید. تابع بولتزمان به‌صورت  است، در آن ∆f میزان تفاوت تابع هدفِ بهترین همسایگی ایجاد‌شده و جواب فعلی وT میزان دما در هر مرحله است.

گام 5- با تابع سرمایش دما را کاهش دهید. دمای جدید به‌صورت T_new=(𝛼)T_old محاسبه می­شود.

گام 6- اگر معیار خاتمه محقق شد، الگوریتم پایان می­یابد، در ‌غیر ‌این‌صورت به گام 3 بازگردید.

با استفاده از روش تاگوچی پارامترهای الگوریتم SA به‌صورت جدول 3 تعیین شدند.

 

جدول 3- پارامترهای الگوریتم SA

 

الگوریتمPSA: برای حل مسأله مذکور، از ترکیب دو الگوریتم قبلی، روشی جدید با نام PSA ارائه می­شود. گام­های الگوریتم PSA برای این مسأله به‌شرح ذیل هستند:

گام 1- پارامترهای الگوریتم نظیر اندازۀ جمعیت اولیه (PopSize)، تعداد همسایگی (K)، دمای اولیه، تابع سرمایش، شرط خاتمه و تابع احتمال پذیرش، جواب‌های بد (تابع بولتزمان) را تعیین کنید.

گام2- به‌اندازۀ جمعیت اولیه، تعدادی کرومزو­م­ تصادفی ایجاد کنید.

گام3- برای هر کرومزوم، K همسایگی­ با استفاده از عملگر­ تعویض، ایجاد کنید.

گام4- بهترین و بدترین جواب هر جمعیت همسایگی را پیدا کنید.

گام5- برای هر کرومزوم با استفاده از عملگر تلفیق بر روی بهترین همسایگی آن کرومزوم و بهترین همسایگی (PopSize-1) کرومزوم دیگر اجرا کنید. همین عمل را یک‌بارِ دیگر برای بدترین همسایگی­ها نیز انجام داده و جواب­های تولید‌شده را به جمعیت همسایگی همان جامعه اضافه کنید.

گام6- از بین کل همسایگی‌های ایجاد‌شده برای هر کرومزوم، اگر مقدار تابع هدف بهترین همسایگی از مقدار تابع هدف خود کرومزوم بهتر است، آن را جایگزین کرومزوم فعلی کنید؛ در ‌غیر ‌این‌صورت با ‌استفاده از تابع بولتزمان دربارۀ جایگزینی یا رد آن تصمیم­گیری کنید.

گام 7- با تابع سرمایش، دما را کاهش دهید.

گام 8- اگر معیار خاتمه محقق شد، الگوریتم را پایان دهید، در‌ غیر ‌این‌صورت به گام 3 بازگردید.

 

شبه کد الگوریتم PSA

1: Procedure populated simulated Annealing

2: for i=1:population size do

3:          pop(i)←produce feasible solution;

4:         fit(i)←pop(i) fitness;

5:          Globalbestfit=Inf;

6: end for

7: while T>=T_F do

8:           for i=1:population size do

                        %% neighborhood population(i)

9:                     for j=1:neighborhood size do

10:                               g=1;

11:                               check=0;

12:                               while check==0 && g<=G do

13:                                           newpop(j,i)←pop(i) neighborhood;

14:                                           if newpop(j,i) is feasible do

15:                                                       check=1;

16:                                           end if

17:                                           g=g+1;

18:                               end while

19:                               if check==0 do

20:                               newpop(j,i)←produce feasible solution;

21:                               end if

22:                               newfit(j,i)←newpop(j,i) fitness;

23:                   end for

24:                   best(i)←best of neighborhood population(i);

25:                   bestfit(i)←best(i) fitness;

26:          worst(i)←worst of neighborhood pop(i);

27:       end for

28:       for i=1:population size do

29:                   kk=1;

30:                   for k =1: population size , k≠i do

31:                    crossover [best(i) & best (k)]

                          newpop(j+kk,i) , newpop(j+kk+1,i) ↵ ;

32:                    crossover [worst (i) & worst (k)]

                          newpop(j+kk+2,i) , newpop(j+kk+3,i) ↵ ;

33:                    kk=kk+4;

34:                   end for

35:       end for

36:       for i=1:population size do

37:                   newbest(i)←best of new neighbor pop(i);

38:                   newbestfit(i)←fitness of newbest(i);

39:                   if newbestfit(i)<fit(i) do

40:                               fit(i)←newbestfit(i);

41:                               pop(i)←newbest(i);

42:                               if fit(i)do

43:                                           Globalbestfit←fit(i);

44:                                           Globalbestpop←pop(i);

45:                               end if

46:                   else do

47:                               pr=exp(-(k*(newbestfit(i)-fit(i)))/T);

48:                               if random number ∈(0,1)do

49:                                           fit(i)←newbestfit(i);

50:                                           pop(i)←newbest(i);

51:                               end if

52:                   end if

53:       end for

54:       T=∝ ∈(0,1) × T;

55: end while

56: [Finalfit , index]=min(Globalbestfit);

57: Finalpop= Globalbestpop(index);

58: end procedure

 

با استفاده از روش تاگوچی پارامترهای الگوریتم PSA به‌صورت جدول 4تعیین شدند.

 

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

 نتایج محاسباتی

در این بخش، اعتبار الگوریتم PSA سنجیده می‌شود. به‌این‌منظور، ابتدا نتایج حاصل از الگوریتم با الگوریتم SA و توسعۀ الگوریتم DGA ارائه‌شده در پژوهش ذگردی و بهشتی نیا (2009) برای مسأله بررسی‌شده در این پژوهش، مقایسه می­شود. این مقایسه به‌ازای مسائل تصادفی با ابعاد مختلف انجام می‌شود. الگوریتم SA ساختاری مشابه ساختار الگوریتم استفاده‌شده در PSA دارد؛ با این تفاوت که از یک جواب اولیه برای جستجوی فضای جواب استفاده می­کند.

در ادامه با ریلکس‌کردن فرضِ وجود زمان حمل‌های متفاوت بین تأمین‌کنندگانِ مختلف، مسأله را تبدیل به مسأله بررسی‌شده در پژوهش ذگردی و بهشتی نیا می‌کند و عملکرد PSA و DGA را با هم مقایسه می‌کند.

سپس نتایج به دست آمده از الگوریتم PSA برای مسائل با ابعاد کوچک با حل دقیق مقایسه می­شود. در انتها نیز حساسیت روی برخی پارامترهای اصلی مسأله، تحلیل می‌شود.

تولید مسائل تصادفی: برای مقایسۀ الگوریتم PSA با الگوریتم های GA و SA، ابتدا تعدادی مسائل تصادفی با ابعاد مختلف ایجاد و با هریک از این الگوریتم ها حل می­شوند. سپس با استفاده از آزمون فرض، عملکرد الگوریتم PSA با دو الگوریتم دیگر مقایسه می­شود. برای تولید مسائل تصادفی سه پارامتر اصلی مسأله شامل تعداد سفارش، تعداد وسیله نقلیه و تعداد تأمین­کننده انتخاب و برای هریک از آنها 3 حالت در نظر گرفته شد. برای سایر پارامترها نیز توزیع یکنواختی در نظر گرفته شد و مقادیر آنها از توزیع‌های مربوطه تعیین شد. جدول 5 پارامترهای مسأله و مقادیر در نظر گرفته شده برای هریک از آنها را نشان می­دهد.

 

جدول 5- مقادیر مختلف پارامترها

 

مقایسه با سایر الگوریتم­ها: از ترکیب حالات مختلف برای پارامترهای مسأله، 27 مسأله تصادفی ایجاد می‌شود. این 27 حالت در جدول 6 نشان داده شده‌اند. باتوجه‌به تصادفی‌بودن ماهیت الگوریتم­های فرا ابتکاری، ممکن است در هر‌بار اجرا، نتایج متفاوتی به ‌‌دست آید.

بنابراین برای انجام آزمون فرض، همۀ 27 مسأله شکل‌گرفته به تعداد 20 مرتبه با هر سه الگوریتم حل شده­اند. بهرای آزمون فرضِ تست برابری­ میانگین نتایجِ به ‌دست آمده از الگوریتم PSA با الگوریتم­های دیگر، از آزمون T استفاده شده است. به‌ازای هریک از 27 مسأله، دو آزمون فرض تشکیل می‌شود (در مجموع 54 آزمون). فرض‌های آزمون‌ها به‌صورت زیر هستند:

فرض H₀: میانگین نتایج به ‌دست‌ آمده از PSA برابر با میانگین نتایج به ‌دست ‌آمده از SA (توسعه DGA) یکسان است.

فرض H₁: میانگین نتایج به ‌دست ‌آمده از PSA کوچکتر از میانگین نتایج به ‌دست ‌آمده از SA (توسعه DGA) است.

سطح اطمینان همۀ آزمون­ها برابر با 95 درصد در نظر گرفته می­شود. در حالت‌هایی که فرض H₀ رد شود؛ یعنی در آن حالت‌ها، عملکرد الگوریتم PSA بهتر از الگوریتمِ مقایسه‌شده است.

جدول 6 برای هریک از الگوریتم‌ها و به‌ازای هر‌حالت، مقادیر میانگین جواب‌ها، بهترین جواب و میانگین زمان‌های حل (بر حسب ثانیه) را نمایش می­دهد. همچنین در این جدول مقدار p-value حاصل از انجام آزمون‌های فرض نشان داده شده است. نتایج نشان می­دهد، در 73 آزمون از 74 آزمون انجام‌شده، مقدار p-value کمتر از 05/0 است. این نتیجه، برتری PSA را نسبت به دو الگوریتم دیگر، نشان می‌دهد.

 

جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

ادامه جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

ادامه جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

اگر تأمین­کنندگان به چند ناحیۀ جغرافیایی تقسیم شوند، به‌نحوی که زمان­های حمل بین تأمین­کنندگان داخل یک ناحیه برابر صفر و زمان­های حمل بین تأمین­کنندگان نواحی مختلف برابر با عددی بسیار بزرگ باشد، مسأله تبدیل به مسأله در نظر گرفته شده شده در پژوهش ذگردی و بهشتی نیا (2009) می‌شود. همان‌گونه که اشاره شد، آنها برای حل مسأله از یک الگوریتم ژنتیک به نام DGA استفاده کرده‌اند. برای مقایسات بیشتر، با قرار‌دادن زمان‌های حمل بین تأمین­کنندگان، نتایج الگوریتم PSA با الگوریتم DGA مقایسه و نتایج در جدول 7 نشان داده شده است. این جدول نشان می­دهد، در سطح اطمینان 95 درصد در 23 مورد فرض H₀ رد شده است؛ بنابراین نتیجه می‌شود، الگوریتم PSA نسبت به الگوریتم DGA برتر است.

 

جدول 7- نتایج آزمون فرض مقایسه PSA و DGA

مقایسه با حل دقیق: به‌علت NP-Hard بودن مسأله، به دست آوردن جواب بهینه برای مسائل با ابعاد متوسط و بزرگ در زمان معقول امکان پذیر نیست؛ بنابراین برای مقایسه با حل دقیق، تعدادی مسأله با ابعاد کوچک ایجاد و با الگوریتم PSA حل شده­اند. نتایج به‌دست آمده با الگوریتم PSA با جواب بهینۀ محاسبه‌شده با نرم­افزار GAMS مقایسه و در جدول 8 نشان داده شده است. همان‌طور که در این جدول نشان داده شده است، PSA در برخی مسائل جواب دقیق را ارائه داده است و در برخی مسائل جواب به ‌دست‌ آمده با جواب بهینه فاصله دارد؛ اما این اختلاف ناچیز است. همچنین زمان حل الگوریتم PSA از نرم­افزار GAMS بسیار کمتر است.

 

جدول 8- مقایسه با حل دقیق

 

تحلیل حساسیت: در ادامه برای تحلیل بیشتر، حساسیت روی سه پارامتر اصلی تحلیل می‌‌شود؛ به‌همین دلیل سه پارامتر اصلی شامل، تعداد سفارش‌ها، تعداد تأمین‌کنندگان و تعداد وسایل نقلیه، انتخاب و با تغییر مقادیر آنها به‌صورت صعودی (ضمن ثابت نگه داشتن مقدار سایر پارامترها) تغییرات مقدار تابع هدف، بررسی می‌شود. جدول 9 مقادیر در‌ نظر گرفته‌ شده برای هر پارامتر و نتایج به ‌دست آمده در هر حالت را نشان می­دهد.

شکل­های 7، 8، 9 و نمودارهای تغییر تابع هدف و زمان حل برای تغییرات تعداد سفارش، تعداد وسیلۀ نقلیه و تعداد تأمین­کننده را نشان می­دهند.

شکل 7 نشان می­دهد، با افزایش تعداد سفارش‌ها میزان تابع هدف و زمان حل نیز افزایش می­یابد؛ زیرا سفارش‌های بیشتری باید به تعداد ثابتی از تأمین‌کنندگان و وسایل نقلیه تخصیص یابد و در‌نتیجه به‌طور متوسط بارِ کاری تأمین­کنندگان و وسایل نقلیه افزایش و زمان تحویل سفارش‌ها طولانی‌تر خواهد شد. در‌صورتی ‌که افزایش زمان­های تحویل در این حالت برای مدیریت خوشایند نباشد، پیشنهاد می­شود با استفاده از سیاست خرید قطعاتِ آماده از بازار، تعداد سفارش‌ها را برای برنامه­ریزی کاهش داده و میانگین زمان‌های تحویل را به مقدار هدف رساند. شکل 8 وشکل 9 نشان می­دهند با افزایش تأمین­کنندگان و وسایل نقلیه روند نمودار نزولی می‌شود و تابع هدف کاهش می­یابد؛ زیرا سفارش‌های مشخصی به تأمین­کنندگان و وسایل نقلیۀ مختلفی تخصیص داده‌شده و به‌طور متوسط بارِ کاری هریک از آنها کمتر و زمان­های تحویل کوتاه‌تر می‌شود؛ اما زمان حل، همچنان به‌دلیل افزایش فضای جواب، افزایش می­یابد. اگر میانگین زمان­های تحویل برای مدیریت، خوشایند نباشد، پیشنهاد می‌شود، تعداد تأمین‌کنندگان طرف قرارداد یا تعداد وسایل نقلیۀ استفاده‌شده افزایش و متوسط بارکاری روی هریک از تأمین‌کنندگان و وسایل نقلیه کاهش یابد؛ درنتیجه میانگینِ زمان­های تحویل به مقدار هدف برسد.

جدول 9- تحلیل حساسیت برای سه پارامتر اصلی

 

 

 

 

شکل 7- تغییرات تعداد سفارش

 

شکل 8- تغییرات تعداد وسیله نقلیه

 

 

شکل 9- تغییرات تعداد تأمین­کننده

 

خلاصه، نتیجه­گیری و زمینۀ پژوهش‌های آتی

در این مقاله زمان‌بندی وسایل نقلیه در زنجیره تأمین با در نظر ‌گرفتن اثرات متقابل بین بخش حمل‌و‌نقل و بخش تولید، بررسی شده است. زنجیره تأمین بررسی‌شده، شامل مجموعه­ای از تأمین­کنندگان است. در این زنجیره، یک ناوگان حمل­ونقل مشترک، سفارش‌های تخصیص داده شده به خود را به یک شرکت سازندۀ محصولات نهایی منتقل می­کند. این مجموعه از تأمین­کنندگانِ مستقر در نقاط جغرافیایی مختلف، قابلیت پردازش تمامی سفارش‌ها را ندارند و با‌توجه‌به توانایی­های خود، بخشی از آنها را پردازش می‌کنند. همچنین ناوگان حمل‌و‌نقل، متشکل از چندین وسیلۀ نقلیه با ظرفیت بارگیری محدود و میانگین سرعت متفاوت است، این میانگینِ سرعت، در کل دورۀ برنامه‌ریزی ثابت است. هدف، نحوۀ تخصیص سفارش‌ها به تأمین­کنندگان و تعیین توالی ساخت آنها در هر تأمین­کننده به‌همراه تخصیص سفارش‌ها به وسایل نقلیه و تعیین توالی حمل آنها است؛ به قسمی که مجموع زمان تحویل سفارش‌ها حداقل شود. این مسأله تاکنون در ادبیات موضوع بررسی نشده‌ است. ابتدا برای این مسأله یک مدل ریاضی عدد صحیح مختلط ارائه شد و برای حل آن سه الگوریتم ژنتیک، شبیه سازی تبرید و شبیه سازی تبرید جمعیتی (ترکیبی از دو الگوریتم GA و SA)، ارائه شد. برای بررسی کیفیت جواب­های PSA، ابتدا تعدادی مسأله تصادفی با ابعاد مختلف ایجاد شد و نتایج آن با الگوریتم SA و توسعۀ الگوریتم DGA ارائه‌شده مقایسه شد. سپس با ریلکس‌کردن فرضِ وجود مسافت بین تأمین­کنندگان موجود در یک ناحیۀ جفرافیایی، مسأله تبدیل به مسأله‌ای شد که ذگردی و بهشتی­نیا (2009) آن را مطرح کرده‌اند و نتایج PSA در این حالت با نتایج DGA ارائه‌شدۀ آنها، مقایسه شد. نتایج نشان می‌دهد در همۀ مقایسه‌ها الگوریتم PSA برتر است. برای اثبات برتری الگوریتم­ PSA، از آزمون فرض استفاده شده است. به‌علاوه به ازای مسائل با ابعاد کوچک، نتایج الگوریتم PSA با جواب بهینه مقایسه شد. نتایج مقایسه‌شده نشان از کارایی بالای الگوریتم PSA دارد. درنهایت با انجام تحلیل حساسیت روی پارامترهای اصلی (تعداد سفارش‌ها، تعداد تأمین‌کنندگان و تعداد وسایل نقلیه) تأثیر تغییرات آنها بر تغییرات تابع هدف و زمان حل نشان داده شد.

در انتها نیز چند زمینه برای پژوهش‌های آتی به‌شرح زیر پیشنهاد می­شود:

• بسط مسأله بررسی‌شده در این پژوهش در حالتی که چند شرکت سازندۀ محصول نهایی و چند پایانۀ حمل­ونقل در نقاط مختلف جغرافیایی قرار داشته باشند.
• اضافه کردن محدودیت ظرفیت تولید در تأمین­کنندگان.
• اضافه کردن فرضیاتی مانند وجود حالت ساخت و مونتاژ در شرکت سازنده مرکزی.
• ارایه روش‌های حل دیگر، مانند الگوریتم زنبور عسل^[xxxix] و جستجوی ممنوعه برای این مسأله.

تعداد مشاهده مقاله: 2,272

تعداد دریافت فایل اصل مقاله: 1,277