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

بخشی از مقاله

چكيده

اين مقاله به يكپارچگي مسائل حملونقل و زمانبندي توليد در يك زنجيره تأمين چندمحصولي با زمان پردازش فازي ميپردازد . اين زنجيره تأمين شامل دو سطح ميباشد. سطح اول آن، كارخانه سازنده محصولات نهايي و سطح دوم آن، تأمين كنندگان تخصصي رده اول ميباشد كه توسط يك ناوگان حملونقل با يكديگر در ارتباط هستند. هدف از بررسي اين مسئله، تخصيص سفارشات به تأمين كنندگان و وسايل نقليه، تعيين توالي پردازش سفارشات تخصيص داده شده به تأمين كنندگان و تعيين توالي حمل سفارشات تخصيص داده شده به وسايل نقليه ميباشد به طوري كه مجموع زمان تحويل سفارشات به كارخانه سازنده محصولات نهايي كمينه گردد. براي حل مساله از الگوريتم ابتكاري جديدي با الهام از الگوريتم شاخه و كران استفاده ميشود. براي اعتبار سنجي جوابهاي بدست آمده توسط اين الگوريتم، مسئله توسط دو الگوريتم فراابتكاري ديگر حل شده و نتايج باهم مقايسه مي شوند. نتايج بدست آمده نشان دهنده برتري الگوريتم پيشنهادي ميباشد.

١- مقدمه

زنجيره تامين١ شامل چند شركت مي باشد كه كه داراي ماهيت حقوقي مستقل هستند و توسط جريانهاي مالي، مواد و انرژي با يكديگر در ارتباط هستند. بررسي يكپارچه و تركيبي مسائل زمانبندي توليد و مسيريابي وسايل نقليه - ٢ - VRP داراي پتانسيل قابل توجهي براي بهبود عملكرد ميباشد. اين بررسي همزمان، باعث كاهش هزينههاي خريد و توليد، كاهش اتلافات و بهبود مستمر و درنهايت افزايش رضايتمندي مشتري نهايي ميشود.

از اين رو، اين مقاله به بررسي همزمان مسائل زمانبندي حملونقل و توليد در يك زنجيره تأمين چندمحصولي با زمان پردازش غير قطعي از نوع عدد فازي مثلثي٣ ميپردازد. بدان صورت كه تعدادي سفارش به تأمين كنندگان تخصصي كه در نقاط جغرافيايي مختلفي پراكنده هستند، تخصيص داده ميشود و اين سفارشات پردازش شده بايد توسط يك ناوگان حملونقل اشتراكي به شركت سازنده محصولات نهايي انتقال داده شوند. هدف از بررسي اين مسئله، تعيين نحوه تخصيص سفارشات به تأمين كنندگان و وسايل نقليه، تعيين توالي پردازش سفارشات تخصيص داده شده به تأمين كنندگان و تعيين توالي حمل سفارشات تخصيص داده شده به وسايل نقليه ميباشد به نحوي كه مجموع زمان تحويل سفارشات به كارخانه كمينه گردد.

نوآوريهاي اين مقاله به شرح ذيل ميباشد:

تركيب مسائل VRP و زمانبندي توليد در زنجيره تأمين در حالتي كه زمان پردازش سفارشات فازي ميباشد. ارائه الگوريتم ابتكاري٤ جديد با الهام از الگوريتم شاخهوكران٥ در ادامه در بخش ٢ به مرور ادبيات پرداخته ميشود. در بخش ٣ مفروضات مسئله توضيح داده مي شوند. در بخش ٤ روشهاي حل اين مسئله بيان شده و در بخش ٥ اين روشهاي حل با يكديگر مقايسه ميشوند. و درنهايت در بخش ٦ نتيجه گيري و زمينههايي براي تحقيقات آتي بيان ميگردد.

٢- مرور ادبيات

تاكنون تحقيقات متعددي در زمينه تركيب مسائل حملونقل و زمانبندي توليد در يك زنجيره تأمين ارائه شده كه در اين بخش به آن پرداخته مي شود. اسكولز ريتر و همكاران ]١[ كپارچگي توليد و حمل-ونقل در يك زنجيره تأمين عمومي را بررسي و يك مدل رياضي بمنظور حل مسئله ارائه نمودهاند. تابع هدف مسئله آنها كمينه نمودن مجموع هزينههاي ديركرد سفارشات، هزينههاي پردازش، هزينههاي نگهداري سفارشات و هزينههاي ثابت و متغير حملونقل است. باتنگر و همكاران ]٢[ به بررسي برنامهريزي حملونقل و زمانبندي در حالت وجود دو نوع حملونقل هوايي و دريايي پرداختهاند. هزينه حملونقل دريايي كم و براساس پيش بيني تقاضا و هزينه حملونقل هوايي بالا و بر اساس پيشبينيهاي نزديك به موعد تحويل در نظر گرفته شده است.

تابع هدف مسئله آنها كمينه نمودن هزينههاي نگهداري موجودي، تعداد كانتينرهاي مورد استفاده و هزينههاي حملونقل است. لئو و چن]٣[ به بررسي يكپارچگي مسيريابي، كنترل موجودي و زمانبندي در يك زنجيره تأمين پرداخته و پس از مدلسازي رياضي مسئله، يك الگوريتم جستجوي همسايگي به منظور حل مسئله ارائه نمودهاند. تابع هدف مسئله كمينهسازي مجموع هزينههاي موجودي، مسيريابي و استفاده از وسايل نقليه است. الريچ]٤[ به يكپارچگي زمانبندي ماشين-آلات و مسيريابي وسايل نقليه با در نظر گرفتن پنجرههاي زماني٦ پرداخته است. كلوديا و همكاران ]٥[ يك مسئله حملونقل چند دوره-اي را بررسي كردهاند كه در آن تاريخ تحويل كالا در نظر گرفته شده است.

هدف، يافتن مسير بهينه براي وسايل نقليه است به گونهاي كه تمامي هزينههاي حملونقل، انبارداري، جريمهها، هزينههاي سرويس-دهي و ... كمينه شود. آنها يك الگوريتم شاخهوكران و يك تحليل محاسباتي براي حل اين مسئله ارائه دادند. مادان كومار و راجندران ]٦[ براي مسئله مسيريابي وسايل نقليه سبز در يك زنجيره تأمين نيمه هادي، يك مدل برنامه ريزي خطي عدد صحيح مختلط دو بخشي ارائه دادند. بخش اول براي پيدا كردن مسيرهايي با هزينه سوخت كمتر با توجه به ظرفيت خودرو و انواع درخواستها براي برآوردن تقاضاهاي مشتريان ميباشد.

بخش دوم به منظور رسيدگي به سناريوي قيمت سوختهاي مختلف و ايستگاههاي سوختگيري مختلف ميباشد. بهشتي نيا و قاسمي ]٧[ يك الگوريتم فراابتكاري٧ جديد به نام الگوريتم مسابقات قهرماني چند ليگي٨ به منظور حل مساله زمانبندي يكپارچه توليد و حمل و نقل در زنجيره تامين ارائه نمودند. برومند و بهشتي نيا ]٨[ به بررسي مساله زمانبندي يكپارچه توليد و حمل و نقل در زنجيره تامين در حالت چندهدفه پرداخته و يك الگوريتم ژنتيك٩ تركيبي جديد به GA-VIKOR به منظور حل مساله ارائه نمودند. بهشتي نيا و    همكاران ]٩[، به بررسي مساله زمانبندي يكپارچه توليد و حمل و نقل در زنجيره تامين در حالت توليد چند مكاني پرداخته اند و از يك الگوزيتم ژنتيك توسعه يافته جهت حل مساله استفاده نمودند.

طاهري و    بهشتي نيا ]١٠[ يك الگوريتم ژنتيك توسعه يافته به نام الگوريتم ژنتيك سفر زماني جهت حل مساله زمانبندي يكپارچه توليد و حمل و    نقل در زنجيره تامين ارائه نمودند. ناجيان و بهشتي نيا ]١١[ تركيب دو حالت مسيريابي وسايل نقليه و بارگيري متقاطع را در مساله زمانبندي يكپارچه توليد و حمل و نقل در زنجيره تامين در نظر گرفته و    يك الگوريتم ژنتيك جديد به منظور حل مساله توسعه داده اند. بررسي ادبيات موضوع نشان ميدهد كه تركيب مسائل زمانبندي توليد در زنجيره تأمين با VRP در حالتي كه زمان پردازش سفارشات فازي باشد، تاكنون مورد بررسي قرار نگرفته است. از اين رو اين مقاله به   رابطه بين تأمين كنندگان و سازنده پرداخته و سيستم حملونقل با ظرفيت محدود را درنظر گرفته است.

٣- تعريف مسئله

اين مقاله به بررسي همزمان زمانبندي توليد و حملونقل در يك زنجيره تأمين تخصصي با زمان پردازش فازي ميپردازد كه هدف آن كمينه نمودن مجموع زمان تحويل سفارشات به كاخانه سازنده محصولات نهايي ميباشد. فرضيات اين مسئله به شرح ذيل ميباشد: زنجيره تأمين مورد بررسي شامل ٢ سطح ميباشد، سطح اول آن كارخانه سازنده محصولات نهايي و سطح دوم آن تأمين كنندگان تخصصي رده اول ميباشد كه توسط يك ناوگان حملونقل با يكديگر در ارتباط هستند.

تعداد n سفارش موجود، بايد توسط m تأمين كننده مورد پردازش قرار گيرند و همچنين بايد توسط l وسيله نقليه به شركت سازنده محصولات نهايي انتقال داده شوند. هر يك از اين n سفارش داراي زمان پردازش فازي بوده، كه به صورت اعداد فازي مثلثي درنظر گرفته ميشود. بدين صورت كه به هر سفارش سه عدد به صورت - a,b,c - تخصيص داده ميشود. كران بالا كه با c نشان داده ميشود بيانگر بيشينه زمان مورد نياز براي پردازش سفارش مورد نظر ميباشد. b بيانگر محتملترين زمان مورد نياز براي پردازش سفارش مورد نظر و a كه كران پايين ميباشد بيانگر كمترين زمان مورد نياز براي پردازش سفارش مورد نظر مي-باشد.

براي بدست آوردن زمان تكميل تقريبي هر سفارش از فرمول ٦b+c - /٤ - a+ استفاده ميشود. هر يك از اين n سفارش، داراي حجم مشخصي ميباشد كه ممكن است با ساير سفارشات برابر نباشد. تأمين كنندگان به علت داشتن تجهيزات تخصصي، توانايي پردازش تمامي سفارشات را ندارند، بلكه با توجه به ماهيت سفارشات مي-توانند بخشي از آنها را مورد پردازش قرار دهند. همچنين اين تأمين كنندگان در نقاط جغرافيايي مختلفي مستقر هستند، كه فاصله آنها نسبت به هم و نسبت به كارخانه سازنده محصولات نهايي مشخص و معلوم ميباشد.

ناوگان حملونقل از l وسيله نقليه ناهمگن تشكيل شده است. بدان معنا كه هر يك از اين وسايل نقليه داراي ظرفيت محدود و متفاوت بوده و ميانگين سرعت آنها در كل دوره برنامه ريزي ثابت ميباشد. اين ميانگين سرعت وسايل نقليهها ممكن است با يكديگر متفاوت باشند. براي كاهش هزينههاي حملونقل، وسايل نقليه مجاز ميباشند سفارشاتي را كه نزد تأمين كنندگان مختلفي پردازش شدهاند بارگيري نمايند. همچنين اين وسايل نقليه بعد از تحويل سفارشات به كارخانه، از مسئله حذف نشده بلكه بايد دوباره مورد استفاده قرار گيرند.

به سفارشاتي كه هر بار توسط وسايل نقليه به كارخانه تحويل داده ميشود، محموله گويند. هر محموله ميتواند حاوي سفارشات پردازش شده نزد تأمين كنندگان مختلف باشد. همچنين تمام سفارشات موجود در يك محموله داراي زمان تحويل به كارخانه يكساني ميباشند. در ابتداي برنامه ريزي، تمام وسايل نقليه در كارخانه سازنده محصولات نهايي مستقر ميباشند. هدف از بررسي اين مسئله، تخصيص سفارشات به تأمين كنندگان و وسايل نقليه، تعيين توالي پردازش سفارشات تخصيص داده شده به تأمين كنندگان و همچنين تعيين توالي حمل سفارشات تخصيص داده شده به وسايل نقليه ميباشد به طوري كه مجموع زمان تحويل سفارشات به كارخانه سازنده محصولات نهايي كمينه گردد.

٤- روشهاي حل ٤.-١- الگوريتم ابتكاري مبتني بر رويكرد شاخه و كران

الگوريتم پيشنهادي از الگوريتم شاخه و كران به منظور جستجوي جواب بهينه استفاده مي كند. الگوريتم شاخه و كران يك روش حل دقيق به منظور حل مسايل بهينه سازي است كه در آن تمام حالتهاي ممكنه با زدن شاخه ها جستجو مي شوند. مزيت روش شاخه و كران به روش شمارش كامل، اين است كه با استفاده از كرانهاي بالا و پايين برخي شاخه ها از جستجوي بيشتر حذف مي شوند و از اين رو سريعتر مي توان به جواب بهينه رسيد. با توجه به NP-hard بودن مساله استفاده از روشهاي بهينه براي حل مساله در زمان معقول امكان پذير نمي باشد و بايد از روشهاي ابتكاري با فراابتكاري به منظور حل مساله استفاده نمود. در الگوريتم ابتكاري پيشنهادي از نحوه شاخه زدن شاخه ها در الگوريتم شاخه و كران الهام گرفته شده است و به جستجوي فضاي جواب مساله پرداخته مي شود.

گامهاي الگوريتم پيشنهادي به صورت زير است:

١- يك جواب تصادفي را به عنوان ورودي الگوريتم درنظر بگيريد.

٢- با استفاده از عملگر تعويض تعداد K همسايگي براي جواب اوليه ايجاد كنيد. هر يك از اين K همسايگي را يك شاخه بناميد.

٣- براي هر شاخه K همسايگي و L جواب تصادفي جديد ايجاد كنيد.

٤- از بين جوابهاي توليد شده با تابع هدف بهتر از جواب فعلي، يكي را براساس معيار چرخ گردان انتخاب كرده و جايگزين جواب فعلي در آن شاخه كنيد. در غير اين صورت همسايگيهاي توليد شده را رها كنيد و به گام ٥ برويد.

٥- اگر معيار خاتمه الگوريتم تحقق يافته است، الگوريتم خاتمه مي-يابد. در غير اين صورت به گام ٣ برگشته و اين روند تكرار ميگردد.