نشریه تخصصی مهندسی صنایع، دوره 50، شماره 2، پاییز و زمستان 1395، از صفحه 177 تا 189
بهینه سازی توالی و تخصیص کامیون های ورودی و خروجی در باراندازهای متقاطع

جمال‌ارکات*1،‌پرک‌قدس2،‌فردین‌احمدی‌زر3
دانشیار گروه مهندسی صنایع، دانشگاه کردستان
کارشناس ارشد مهندسی صنایع، دانشگاه کردستان
دانشیار گروه مهندسی صنایع، دانشگاه کردستان

)تاریخ دریافت 05/02/95 ـ تاریخ دریافت روایت اصلاح شده 26/02/95 ـ تاریخ تصویب 11/03/95( چکیده
سیستم بارانداز متلاطع یک راهبرد لجستیکی است که براساس آن کااهای تخلیه شده از کـام یون هـای ورودی ،تلریبـاً بـدون ذخ یـره سـازی و به صورت مستلیم در کامیون های خروجی بارگیری می شوند؛ بنابراین، تلریباً هیچ موجودی در این مراکز توزیـع ، نگهـدار ی نمـ ی شـود . در ایـن تحلیق، مسئلة تخصیص کامیون ها به در های بارانداز و تعیین توالی هم زمان کامیون های ورودی و خروجی در یک بارانداز متلاطع دارندة چنـددر تخلیه و بارگیری بررسی می شود. بدین منظور، مسئلة مورد بررسی در قالب یک مدل ریاضی برنامه ریزی عدد صحیح مختل ارائه مـ ی شـود .
به دلیش ناچندجمله ای سخت بودن مسئله و همچنین به منظور حش مسئله در ملیاس بزرگ ،یک الگـور یتم شـب یه سـازی تبریـد ارائـه مـی شـود .
به منظور ارزیابی صحت مدل ریاضی و عملکرد الگوریتم پیشنهادی، تعدادی مثال عددی، حش و نتایج تحلیش می شوند.

واژه‌های‌کلیدی: الگوریتم شبیه سازی تبرید، بارانداز متلاطع، تخصیص در های بارانداز، زمان بندی کامیون ها.

مقدمه
بارانداز متلاطع1 یک راهبـرد لجسـتیکی اسـت کـه امـروزهشرکت های متعددی در حوزة صنایع مختلـف آن را بـه کـارمی برند. ایدة اصلی بارانداز متلاطع، انتلال مستلیم کااهای وارده به مرکـز توزیـع بـه وسـایش نللیـة خروجـی و بـدونذخیره سازی موقت است. ممکن است ایـن تکنیـک اهـداکمتفاوتی مانند ترکیب کااها2، کاهش زمان تحویش و کاهش هزینه ها را برآورده سازد. نبود ذخیرة موقت، حالـت ایـده آل به شمار می رود، اما معمواً در عمش، ذخیره سازی موقت ازم است، زیرا بسیاری از کااهای ورودی، پیش از بارگیری باید دسته بندی و ترکیـب شـوند. درنتیجـه، مـی تـوان سیسـتمبارانداز متلاطع را فرایند ترکیب کااهایی با ملصد یکسان- ک ه از من ابع مختل ف آم ده ان د- ب ا کمین ة جاب ه ج ایی و ذخیره سازی بین تخلیه و بارگیری کااها توصیف کرد. اگـرذخیره سازی کااها اجتناب ناپذیر باشد، ایـن ذخیـره سـازیباید برای بازة زمانی کوتاهی )حـداکثر 24 سـاعت( صـورتگی رد .در انباره ای متل اطع از می ان کارکرده ای اص لی

* نویسندة مسئول: تلفن: 08733660073

انبارداری یعنی دریافت، ذخیره سازی، برداشت سفارش هـا و ارســال، دو کــارکرد پرهزینــة ذخیــره ســازی و برداشــتس فارش ه ا ح ذک م ی ش وند. هرچن د ام روزه بس یاری از شرکت ها از بارانـدازهای متلـاطع اسـتفاده مـی کننـد، ایـنسیستم یک راه حش عمومی برای تمام کاربردها نیست. اپتـهو ویزوانـاتن 1[ ع واملی را برش مرده ان د ک ه ب ر ک اربرد و کارکرد بارانداز متلاطع در ملایسـه بـا توزیـع سـنتی تـأث یر می گذارند. در این زمینه، دو عامش نرخ تلاضـای محصـول وهزینة واحد اتمام موجودی، مهم ترین عوامش اند .
می توان سیستم های بارانداز متلاطع را براساس سه نوع ویژگی فیزیکی، عملیاتی و جریان کـاا دسـته بنـدی کـرد.ویژگی فیزیکی برای مدت طوانی ثابت مـی مانـد و شـامششکش و تعداد در های بارانـداز و شـیوة حمـش ونلـش داخلـیمی شود. شـیوة خـدمت دهـی و نحـوة اعمـال وقفـه3، جـزءویژگی های عملیـاتی هسـتند. ویژگـی جریـان کـاا شـامشالگوی ورود، زمان حرکت، قابلیت تعویض پذیری محصول4 و ذخیره سازی موقتی می شـود. در طـول فازهـای طراحـی و Email: [email protected]
اجرای بارانداز متلاطع باید در سه سطح راهبردی، تاکتیکیو عملیـاتی، تصـمیماتی اتخ اذ شـود. تصـمیمات راهب ردیشامش تصمیمات مکان یابی و جانمایی بارانداز متلاطع است .
تصمیمات تاکتیکی در زمینة شیوة جریـان کـاا در سـطحشبکه اتخاذ می شود. تصمیمات عملیـاتی آخـرین دسـته ازتصمیمات است که شامش مسیریابی وسایش نللیه، تخصیص در های بارانداز،5 زمان بندی کامیون6 و ذخیره سـازی موقـتمی شود. با توجه به اهمیت زمان پاسخ و اجرای عملیـات درصنعت بسیار رقـابتی توزیـع، مطالعـات بسـیاری در زمینـةتخصیص در های بارانداز و زمان بندی کامیون ها در سیسـتمبارانداز متلاطع صورت گرفته است.
مسئلة زمان بندی کامیون ها علاوه بر تخصیص کامیون ها به در های بارانـداز، درمـورد تـوالی ورود کـام یون هـای نیـز تصمیم می گیرد. پژوهش های محللان در این حوزه به سـهدسته تلسیم مـی شـود: دسـتة اول ماننـد یـو و اگبلـو 2[ زمان بندی بارانداز متلاطع را فل با یک در تخلیه و یک در بارگیری بررسی کرده اند. دستة دوم مانند کونور و گولیـاس 3[ فل زمان بنـدی کـامیون هـای ورودی یـا زمـان بنـدیکامیون های خروجی را در باراندازهایی با چنـد در تخلیـه وبارگیری بررسی کرده اند. دستة سوم زمـان بنـدی هـم زمـانک امیون ه ای ورودی و خروج ی را در باران دازهای دارن دة چندین در تخلیه و بارگیری بررسی کرده انـد. بـا توجـه بـهمسئله تحت بررسی، در ادامه صرفاً تحلیلات انجام شده در حوزه زمان بندی هم زمان کامیون های ورودی و خروجـی بـاوجود چندین درب باراندازی و بارگیری، مورد بررسـی قـرارمی گیرند.
لیم و همکاران 4[ در مسئلة زمان بندی کامیون فـرضکرده اند عملیات تخلیه و بارگیری کامیون ها در یک پنجـر ة زمانی ثابت انجام می گیرد. در مسئلة مـورد بررسـی، تعـدادکامیون ها از تعداد در های بارانداز بیشتر است؛ بنـابراین، بـادرنظرگرفتن محدودیت زمان عملیات ،مسئلة زمان بندی به مسئلة تخصیص کامیون ها به در های بارانـداز تبـدیش شـدهاست. هدک مسئله، کمینه کردن کش مسـافت پیمـوده شـده)طول سفر( اسـت. کـامیون هـا ممکـن اسـت بـه هـر دری تخصیص یابند )شیوة خدمت دهی مرکب( و هرفیت بارانداز نیز محـدود اسـت. همچنـین وقفـه ، مجـاز نیسـت و بـرای کامیون هایی که خدمت دهی نمی شـوند، عبـارتی بـه عنـوان جریمه به تابع هدک اضـافه شـده اسـت . ایـراد اصـل ی ایـن رویکرد، درنظرنگرفتن زمان ازم بـرا ی انتلـال کااهـا بـین در های بارانداز اسـت . محللـان از الگـور یتم هـای ژنتیـک و جست وجوی ممنوعه برای حش مسئله استفاده کرده اند. لیم و همکاران 5[ و میائو و همکاران 6[ مسئلة تحلیـق قبـشرا با درنظرگرفتن زمان سـفر بـین در هـا ی بارانـداز توسـعهداده انـد . ت ابع هـدک ای ن تحلیل ات، مجمـوع هزین ه ه ای عملی اتی )براس اس زم ان س فر( و هزین ة محمول ه ه ای تکمی ش نش ده را کمین ه م ی س ازد. ب ویزن 7[ در مس ئلة زمان بندی کامیون فرض کرده اسـت ذخیـره سـازی میـانی ب رای محص وات مج از نیس ت و درنتیج ه، محمول ه ه ای ورودی به کامیون خروجی مشخصی تخصـ یص مـ ی یابنـد و قابلیت تعویض پذیری ندارند. در این پژوهش، کـام یون هـا و حامش های استانداردی برای انتلال کااها درنظر گرفته شده است؛ بنابراین، فرض می شود زمـان توقـف ، بارانـداز ی و بـهحرکت در آمدن کامیون ها یکسان است. نویسنده یک مدل چندهدفه شامش کمینه سازی زمان جریـان ، زمـان فراینـد وتأخیر کـام یون هـای خروجـ ی را بـرا ی مسـئل ة زمـان بنـد ی کامیون ها ارائه داده است. برای حش مسئله ،از یـک رویکـرد برنامه ریزی پویا و یک الگوریتم شبیه سازی تبریـد اسـتفاده شده است.
لــی و همکــاران 8[ مســئلة زمــان بنــدی هــم زمــان کامیون های ورودی و خروجی را بررسی کرده اند و بـرای آنیک مدل ریاضی با هدک بیشـینه کـردن تعـداد محصـوات انتلالی ارائه داده اند. در این تحلیق، از الگوریتم های ژنتیـکبا عملگرهای هم گذری مختلـف بـه منظـور حـش مسـئله درملیاس بزرگ استفاده شده اسـت . جـو و کـیم 9[ مسـئل ة زمان بندی کامیون های ورودی، خروجی و ترکیبی را بررسی کرده اند. کامیون های ترکیبی نلش هر دو نوع کـام یون هـای ورودی و خروج ی را ایف ا م ی کنن د. در ای ن پ ژوهش ،دو الگوریتم ژنتیک و خود تکاملی7 بـرا ی کمینـه کـر دن دامنـ ة عملیات8 پیشنهاد شده اسـت . در سـه تحلیـق آخـر، زمـانانتلال محصوات بـ ین در هـا ی مختلـف ورود ی و خروجـ ی یکسان فرض شده است، درحالی که معمواً زمان مورد نیـاز به منظور انتلال کااها در بارانـداز متلـاطع بـه فاصـلة بـ ین در های ورودی و خروجی بستگی دارد.
شاکری و همکاران 10[ مسئلة زمان بندی کامیون ها را به صورت یک مسئلة زمان بنـد ی دومرحلـه ای ماشـ ین هـای موازی با تابع هدک کمینه سازی دامنة عملیات، مدل سـاز ی کرده اند. در این مسئله، شیوة خـدمت دهـی بارانـداز از نـوعمرکب و هرفیت انبار موقت، نامحدود درنظـر گرفتـه شـدهاس ت. کااه ای متف اوت ی ک ک امیون ب ه ص ورت م وازی باراندازی می شوند و انتلال کااها فل پ از تخلیة کامـش و حضور کامیون خروجی در محش بارگیری شروع می شـود . همچن ین ،ب ارگیری ی ک ک امیون خروج ی ،زم انی آغ از می شود که کااهای مربوط بـه آن در فضـا ی انبـار موجـودباشند. زمان سفر براساس مسافت بین در های بارانداز تعیین می شود و فرض شده است در ابتدای افق برنامه ریزی، تمـامکامیون ها دردسترس قرار دارنـد . وقفـه ، مجـاز نیسـت و درفاصلة بین تخلیه یا بارگیری دو کامیون متوالی، یـک زمـانآماده سازی نیز لحاظ شده است .لی و همکاران 11[ بـرا ی حش مسـئلة م طـرح شـده در تحلیـق قبـش، یـک الگـوریتم جست وجوی وابسته به رتبه بندی9 ارائه داده اند که شامش دو بخش است؛ در بخش اول ،یـک تـوالی شـدنی از کارهـا بـا توجه به تعداد در های بارانـداز ایجـاد مـی شـود و در بخـشدوم، کارها براساس مسافت بین در های تخلیـه و بـارگیری، به در های بارانداز تخصیص می یابند. لیائو و همکـاران 12[ دو نوع الگوریتم تکامش دیفرانسیلی ترکیبـی 10 را بـه منظـور تعی ین ت والی ک امیون ه ای ورودی و خروج ی ب ا ه دک کمینه کردن دامنـ ة عملیـات ارائـه داده انـد . الگـوریتم هـایارائه شده در این تحلیق عملکرد بهتری نسبت بـه الگـوریتم پیشــنهادی عربــانی و همکــاران 13[ دارنــد کــه بــرایزمان بندی کامیون ها در بارانداز متلاطع با یـک در تخلیـه ویک در بارگیری به کار گرفته شده است. همچنین، سیاسـتعملیاتی ارائه شده بـه منظـور کمینـه کـردن دامنـ ة عملیـات نسبت به سیاست ارائه شده از سوی یو و اگبلو 14[ کارایی بهت ری دارد. کئ و 15[ ب ه منظ ور بهب ود ک ارایی باران داز متلاطع، مسئلة زمان بندی کامیون های ورودی و خروجی را با هدک کمینه سازی دامنة عملیات بررسی کـرده اسـت. در این تحلیـق، از الگـوریتم جسـت وجـو ی همسـا یگی متغیـر)VNS( به منظور تعیین تـوال ی ورود کـام یون هـای ورودی و خروجــی اســتفاده شــده اســت. براســاس بهتــرین تــوالیبه دسـت آمـده از طریـقVNS و بـا درنظرگـرفتن سیاسـتنوبتی، کامیون ها به درهای بارانداز تخصیص داده می شـوند.وقفه مجاز نیست، زمان انتلال کااها درون بارانداز براسـاسفاص لة مس تلیم محاس به م ی ش ود و هرفی ت تجهی زات جابه جایی به منظور انتلال کااها بی نهایت فرض شده است.
محتشمی 16[ از بین 32 سناریوی پیشـنهادی یـو 17[، دو سناریو را برای توقف کامیون های خروجی بررسی کـردهاس ت. در س ناریوی نخس ت، وقف ه در عملی ات ب ارگیریکامیون های خروجی مجـاز نیسـت، امـا در سـناریوی دوم،ممکن است بارها وقفه صورت پذیرد .یو 18[ مسئلة تعیین توالی کامیون های ورودی و خروجی را با هدک کمینه کردن دامنة عملیات کش سیسـتم بررسـی کـرده اسـت. در مـدلارائه شده، علاوه بر تعیین توالی کامیون ها، مسـئلة تخصـیصمحصوات نیز به صورت هم زمان انجام می گیـرد. همچنـین،زمان سفر بین درهای مختلف تخلیه و بارگیری، ثابت فرض شــده اســت. اســدی و بــاقری 19[ مســئلة زمــان بنــدی کامیون ها را به همراه مسئلة تخصیص محصوات بـا هـدککمینه کردن تعداد کامیون های دارای تأخیر بررسی کرده اند .
در مسئلة مورد بررسی، کامیون هـای ورودی در زمـان هـایمتفاوتی دردسترس قرار می گیرند و فواصـش متفـاوتی بـیندره ای مختل ف تخلی ه و ب ارگیری منظ ور ش ده اس ت.همچنین، از الگوریتم های شبیه سازی تبرید و ژنتیک بـرایحش مسئله در ملیـاس بـزرگ اسـتفاده شـده اسـت. لـی وهمکاران 20[ مسئلة زمان بندی کامیون هـا را در شـرایطیکه امکان وقفه در عملیات تخلیـة کـامیون هـای ورودی بـهتعداد محـدود وجـود دارد، بـا هـدک کمینـه کـردن دامنـةعملیات بررسی کرده اند. از الگـوریتم بهینـه سـازی گروهـیذرات برای حش مسئله در اندازة بزرگ استفاده شـده اسـت.اسدی و باقری 21[ با بهره گیری از سیاست تولید بهنگـام،مجموع زودکردها و دیرکردهـای کـامیون هـای خروجـی راکمینه کـرده انـد. در مسـئلة مـورد بررسـی، کـامیون هـا درزمان های متفاوتی دردسترس قرار می گیرند و فواصـش بـیندرهای مختلف تخلیه و بارگیری متفاوت فرض شده اسـت.ارکات و همکاران 22[ مسئلة زمان بندی کـامیون هـا را دریک بارانداز متلاطع با هدک کمینـه کـردن دامنـة عملیـاتبررسی کرده انـد. در ایـن مسـئله، کـامیون هـای ورودی درزمان های متفاوتی دردسترس قرار می گیرنـد و حامـش یـکنوع کاا هستند.
در تحلیق حاضر، زمـان بنـد ی هـم زمـان کـامیون هـای
ورودی و خروجی در یک بارانداز متلاطع با چند در تخلیه وبارگیری، بررسی و مدل سـازی مـی شـود. در مـدل ریاضـیارائه شده، تخصیص کامیون های ورودی و خروجی به درهای تخلی ه و ب ارگیری و ت والی ورود ک امیون ه ا ب ه باران دازبه گونه ای تعیین می شود که دامنة عملیـات، کمینـه شـود.
ع لاوه ب ر زم ان بن دی ک امیون ه ا، ب ا توج ه ب ه ویژگ ی تعویض پذیری محصوات، مسئله تخصیص بهینة محصوات نیز در مدل ریاضی گنجانده مـی شـود . در تمـام تحلیلـات صورت گرفته در زمینة زمان بنـد ی هـم زمـان کـام یون هـای ورودی و خروجی، فرض می شود تا زمانی کـه تمـام بارهـای تخصیص یافته به یک کامیون خروجی روی سکوی بارگیری آماده نباشند، از ورود و استلرار کامیون مـذکور روی سـکو ، جلوگیری می شود؛ به عبارت دیگـر ، یـک کـامیون خروجـیزمانی می توانـد بـه در بـارگیری مراجعـه کنـد کـه امکـانبارگیری تمام کااهای تخصیص یافته فراهم باشـد . در مـدلارائه شده، این محدودیت حـذک مـی شـود و کـام یون هـا بـارعایت توالی بهینه برای هر در، به سـکو ی تخصـ یص یافتـه مراجعه می کنند. بـرای بـارگیری محصـوات کـامیون هـایورودی در هریک از کامیون های خروجی، یک توالی درنظـرگرفته می شود که براساس آن، کااهایی که زودتر به سکوی بـارگ یری متنـاهر رسـیده ان د، زودتـر بـارگیری مـی ش وند؛ بنابراین، بـرا ی بـارگ یری کااهـا ی رسـ یده از یـک کـام یون ورودی، نیــازی بــه منتظرمانــدن بــرای رســیدن بارهــای تخصیص یافته از سایر کامیون ها نیسـت . حـذک محـدودیتیادشده و استفاده از این راهبرد برای بارگیری کامیون هـایخروجی، موجب بهبود دامنة عملیات می شود. درنظرگرفتن زمان های جابه جایی بین درهای تخلیه و بارگیری متفـاوت،ویژگی دیگر مسئلة مورد بررسی است که بر نحوة تخصیص کامیون ها به درها تأثیر می گذارد.
درادامه، شکش کلی مسئله تشریح و بـر پا یـة مفروضـاتارائه شده، یک مدل ریاضی ارائه می شود. پ از طـرح یـک الگوریتم شبیه سازی تبرید برای حش مسئله در ابعاد بـزرگ ، صحت مدل ریاضی و کارایی الگوریتم حش از طریق تعدادی مثال عـدد ی ارزیـابی مـ ی شـود . درنهایـت، نتیجـه گیـری و پیشنهادها برای مطالعات آتی ارائه می شود.

بیان مسئله و ارائة مدل ریاضی
در یک سیستم بارانداز متلاطع، تعداد مشخصـ ی در ورودی و خروجی با موقعیت مکانی مشخص وجود دارد. در ابتـدا یهر دورة برنامه ریزی، تعدادی کامیون ورودی و خروجی کـههرک دام ب ه ترتی ب حام ش و نیازمن د ترکی ب مشخص ی از محصوات متنوع هسـتند در بارانـداز مسـتلرند. در اینجـا،هدک 1. به دست آوردن بهترین نحوة تخصیص کامیون هـای ورودی و خروجی به ترتیـب بـه درهـای تخلیـه و بـارگ یری بارانداز ،2. تعیین توالی بهینة مراجعه و استلرار کامیون های ورودی و خروج ی در دره ای باران داز و 3. تعی ین حج م محصول ارسـالی از کـام یون هـای ورودی بـه کـامیون هـای خروجی است. مسئله در قالب یک مدل برنامـه ریـزی عـددصحیح مختل با تابع هدک کمینه سازی دامنة عملیات ارائه می شود. در مدل سازی مسئلة مذکور، مفروضات زیر درنظـرگرفته می شود:
ک امیون ه ای ورودی و خروج ی در ابت دای دورة برنامه ریزی دردسترس اند.
هر در بارانداز فل به عملیات تخلیه یـا بـارگیریمحصوات تخصیص می یابد.
زمان ازم به منظور تخلیه یا بـارگیری هـر واحـدکاا فارغ از نوع آن، ثابت و مشخص است.
برای هر کامیون ورودی یا خروجی، امکان تخلیـهیا بارگیری چندین واحد کاا به صورت هـم زمـانوجود ندارد و در هر لحظـه فلـ مـی تـوان یـکواحد کاا را تخلیه یا بارگیری کرد.
هرفیت تجهیزات منتلش کننـد ة محصـوات درونبارانداز نامحدود است.
فاصلة هریک از درهای تخلیه از هریک از درهـایبارگیری مشخص است.
در عملیات تخلیه و بارگیری، وقفه مجاز نیست.
ذخیره سازی موقت، مجاز است و هرفیـت ناحیـة ذخیره سازی موقت، بی نهایت است.
زمان ازم به منظور هربار آماده سازی بارانداز ثابت است.
محصوات قابلیـت تعـویض پـذیری دارنـد؛ یعنـیمی توان کاای مورد نیاز هر کامیون خروجی را از هریک از کامیون های ورودی تأمین کرد.
در بارگیری کامیونهای خروجـی، کااهـایی کـهزودتر وارد شده اند، زودتر نیز بارگیری می شوند.
نمادگذاری به کاررفته در مدل ریاضی به شرح زیر است:
مجموعة اندیس ها
I: مجموعــة کــامیونهــای ورودی) i و i  انــدی کامیون های ورودی( J: مجموعة کـامیون هـای خروجـی) j و j  انـدی کامیون های خروجی( L: مجموعة درهای تخلیه) l اندی درهای تخلیه(
M: مجموع ة دره ای ب ارگیری) m ان دی دره ای بارگیری( K: مجموعــة انــواع محصــوات ) k انــدی انــواعمحصوات( پارامترها ‌Tlm: فاصلة زمانی بین در تخلیه l و در بارگیری m rik: تعداد واحد محصول نوع k در کامیون ورودی i s jk: تع داد واح د محص ول م ورد نی از ن وع k ب رای کامیون خروجی j
UD: زمان ازم به منظور تخلیه یا بارگیری یـک واحـدمحصول
Tc: زمان آماده سازی بارانداز
N: یک عدد مثبت بزرگ متغیرهای‌تصمیم IDil: اگر کامیون ورودی i به در تخلیـهl تخصـیصیابد برابر 1 و در غیر این صورت 0 است.
OD jm: اگر کـامیون خروجـیj بـه در بـارگیریm تخصیص یابد برابر 1 و در غیر اینصورت 0 است.
X ijk: تعداد محصول نوع k که از کامیون ورودی i به کامیون خروجی j انتلال مییابد.
EI i: زمان ورود کامیون ورودی i به در تخلیه
DI i: زمان خروا کامیون ورودی i از در تخلیه
EJ j: زمان ورود کامیون خروجی j به در بارگیری
DJ j: زمان خروا کامیون خروجی j از در بارگیری LTij: زمانی کـه کااهـای تخصـ یص یافتـه از کـامیونورودی i به کامیون خروجی j بارگیری می شوند.
DOJij: زمان اتمام بارگیری کااهای تخصیص یافتـه از
کامیون ورودی i روی کامیون خروجی j Cmax: دامنة عملیات v ij: اگر حداقش یک واحد محصول از کامیون ورودی iب ه کـامیون خروج ی j منتل ش ش ود براب ر 1 و در غی ر این صورت 0 است.
pii l: اگر در توالی مربوط بـه در تخلیـهl کـامیونi قبش از کامیون i  قرار گیرد )برای i  i ( یـا کـامیونi اولین کـامیون ورودی در تـوالی محـش در تخلیـهl باشـد)برای i  i ( برابر 1 و در غیر این صورت 0 است.
q jj m: اگر در توالی مربوط به در بـارگیریm کـامیونj قبش از کامیون j  قرار گیرد )برای j  j ( یا کامیون j اولین کـامیون خروجـی در تـوالی محـش در تخلیـهm باشد )برای j  j ( برابر 1 و در غیر این صورت 0 است.
Y ij: اگر کااهای تخصیص یافته از کامیون ورودی i به کامیون خروجی j قبش از ورود کامیون خروجی j بـه دربارگیری، آمادة بارگیری باشند، برابر 1 و در غیر این صـورت0 است.
Gii j: اگر در توالی مربوط بـه بـارگیری محصـوات درکامیون خروجی j، کااهای تخصیص یافتـه از کـامیونi قبش از کااهای تخصیص یافتـه از کـامیونi  قـرار گیرنـد)برای i  i ( یا کااهای تخصیص یافتـه از کـامیونi در ابتدای توالی بارگیری قرار داشته باشند )برای i  i ( برابر 1 و در غیر این صورت 0 است.
H ii j: اگر محصوات کامیون i قبش از اتمام بارگیری محصوات کامیون i  روی کامیون j، به سکوی بارگیری این کامیون وارد شده باشند برابر 1 و در غیر این صـورت 0 است.
مدل ریاضی مسئله به صورت زیر ارائه می شود:

Min C max )1( Subject to:
j Xijk  rik ; i k, )2(

i Xijk  S jk ; j k, )3(
k Xijk  Nvij ; i j, )4(
IDil 1 ; i l )5(
ODjm  1 ; j m )6(
Piil 1 ; l i )7(
Pi il  IDil ; l i,
i )8(
 Pii l  IDil ;l i,
i i, i )9(
qjjm  1 ; m j )10(
qj jm  ODjm ; m j,
j )11(
 qjj m  ODjm ; m j,
j, j j )12(
DIi  EIi UDrik ; i k )13(
DIi Tc  EIi  N 1Pii l  ; i i i, ,  i)14(
l
LTij  DI vi ij T ID OD vlmiljm ij  ; i j, )15(
 lm
DJ j Tc  EJ j  N 1qjj m  ; j j j, ,  j )16(
m

Giij 1 ; j )17( i
Gi ij  vij ; i j, )18(
i
 Gii j  vij ; i j, )19( i i , i
DOJij EJ j UDxijk 
k )20(
 N 2Yij Giij  ; i j,
DOJij DOJi j UDxijk 
k )21(
 N 2Yij Giij Gi ij  ; i i j, , 
DOJij LTij UDxijk 
k )22(
 N 2Yij Giij  ; i j,
DOJij DOJi j UDxijk 
k )23(
 N Y ij Giij  1 Hii j  ; i i j, ,  DOJij LTij UDxijk 
k )24(
 N Y ij Giij  Hii j  ; i j,
DJ j  DOJij ; i j, )25( Cmax  DJ j ; j )26(
xijk  0 & Integer ; , , i j k )27( EI DI EJ DJ DOJ LTi , i , j , j , ij , ij  0 ; , i j )28(

ID ODil , jm , , v Giji ij , , Y Hijii j , pii l , qjj m )29(
0,1 ; , , , , ,  i i j j l m رابطة 1 به عنوان تابع هـدک، دامنـة عملیـات را کمینـهمی سـازد. محـدود یت 2 تضـمین مـی کنـد بـرای هـر نـوعمحصول، حجـم کـاای انتلـالی از هـر کـامیون ورودی بـهکامیون های خروجی با حجم محصـول موجـود در آن برابـراست. محـدود یت 3 ملـزم مـ ی کنـد تلاضـا ی هـر کـامیون خروجی برای هر نوع کاا تأمین شود. محـدود یت 4 متغیـرتص میم v ij را تعری ف م ی کنـد. مح دودیت ه ای 5 و 6 به ترتیب تضمین می کنند هر کامیون ورودی و خروجی بـهیک ی از دره ای تخلی ه و ب ارگیری تخص یص داده ش وند .
محدودیت های 7 تا 9 و محدودیت های 10 تا 12 به ترتیـبتضمین می کنند توالی کامیون های ورودی و خروجی، یـکجایگشت کامـش باشـند. محـدود یت 13 زمـان خـروا هـرکامیون ورودی از بارانداز را تعیین می کنـد . محـدود یت 14 بیان می کند زمان ورود هـر کـام یون ورودی بـه در تخلیـه،بزرگ تر یا مساوی مجموع زمان خروا کامیون ورودی ملدم بر آن و زمان ازم به منظور آماده سازی است. محدودیت 15 کوچک ترین زمان ممکن برای بارگیری کااهـا ی انتلـال ی از ی ک ک امیون ورودی ب ه ی ک ک امیون خروج ی را تعی ین می کند. محدودیت 16 بیان می کند زمان ورود یک کامیون خروجی به در بارگیری، بزرگ تر یا مسـاو ی مجمـوع زمـانپایان بارگیری کامیون خروجی ملدم بـر آن و زمـان مـوردنیاز به منظور آماده سازی است. محـدودیت هـای 17 تـا 19 توالی بارگیری بارهای تخصیصی به هر کـامیون خروجـی را
بــه صــورت یــک جایگشــت کامــش تضــمین مــی کننــد .محدودیت های 20 تا 24 زمان اتمام بارگیری هر نوع کاای تخصیص یافته به هریک از کامیون های خروجی را با رعایـت وضعیت متغیرهای Gii j ،Y ij و H ii j محاسـبه مـی کننـد.محــدودیت 25 زمــان اتمــام بــارگیری کامــش هریــک ازکامیون های خروجی را محاسـبه مـی کنـد. محـدودیت 26 دامنة عملیات را محاسبه می کند. محدودیت های 27 تا 29 دامنة متغیرهای تصمیم مدل را مشخص میکنند.
در مدل ریاضی ارائه شده، محدودیت 15 بهدلیش وجـودحاصش ضرب چند متغیر، غیرخطی است. همچنین، تعـاریفارائ هشــده بــرای متغیره ای تصــمیمY ij و H ii j شــکش صریحی ندارد؛ یعنی متغیرهای یادشده به سایر متغیرهـایتصمیم مدل وابسته اند. به منظور خطی سازی محدودیت 15، از روش متعارک خطی سازی ضرب یـک متغیـر پیوسـته دریک متغیر دودویی استفاده می شـود. همچنـین، بـه منظـور ارائة شـکش ریاضـی تعـاریف مربـوط بـهY ij و H ii j از دو دسته متغیر دودویی کمکی جدید بـا انـدی هـایi و j استفاده می شود. پ از افزودن محدودیت های خطی سازی ،مدل به یک مدل خطی عدد صحیح مختل تبدیش می شود و می تـوان آن را بـا حـش کننـده هـای خطـی نـرم افزارهـایبهینه ساز حش کرد. تعداد محدودیت های خطی سـازی زیـاداست؛ بنابراین، در پژوهش حاضر ذکر نمی شود.
الگوریتم شبیه سازی تبرید
الگوریتم شبیه سازی تبریـد ) SA( روشـ ی فـرا ابتکـاری بـر مبنای جست وجوی محلی است که از فرایند تبریـد واقعـینشئت گرفتـه اسـت. ایـن الگـور یتم مـی توانـد بـا پـذیرش راه حش های بـدتر نسـبت بـه بهتـرین راه حلـ ی کـه تـاکنونب ه دسـت آمـده اسـت ، از گیرافتـادن در بهینگ ی محل ی جلوگیری کند. کیفیت راه حـش هـا ی حاصـش از SA موجـبش ده اس ت از آن در ح ش مس ائش بهین ه س ازی ترکیب اتی پیچیده در حوزه هـ ای مختلـف اسـتفاده شـود. متـروپل ی 23[ برای نخسـت ین بـا ر SA را در سـال 1943 ارائـه داد و کیر پاتریک و همکاران 24[ آن را گسترش دادند.
SA حرکت خود را از یک راه حش تصادفی به عنوان نلطة شروع آغاز می کند و دمای سیستم را برابر دمای اولیه قـرارمی دهد) 0T T(. در هر تکرار، یک راه حـش در همسـایگی راه حش فعلی تولید می شود. درصورتی کـه راه حـش همسـایه،راه حش بهتری باشد، جایگزین راه حـش فعلـی مـ ی شـود و در غیر این صورت، با احتمال بـه دسـت آمـده از تـابع بـولتزمن

)e 

KT (، این جایگزینی صورت می گیرد. در تابع بـولتزمن،Δ میزان اختلاک بـین ملـدار تـابع هـدک راه حـش فعلـی و همسایه، K ضریب ثابت بولتزمن و عددی در بازه) 1/0( و T دمای فعلی سیستم است. الگـوریتم دو حللـة داخلـی وخــارجی دارد. در حللــة داخلــی، فراینــد جســت وجــوی همسایگی تـا تولیـد تعـداد مشخصـی راه حـش همسـایه یـاراه حش های همسایة بهبوددهنده تکرار می شود. پ از اتمام حلل ة داخل ی، دم ای سیس تم در حلل ة خ ارجی ک اهش می یابد. فرایند کاهش دما تا زمانی ادامه می یابد کـه دمـا ی الگوریتم به دمای انجمـاد برسـد. بـا کـاهش دمـا ، احتمـالپ ذیرش راه ح ش ه ای غیربهبوددهن ده ک اهش م ی یاب د و همگرایی به سمت راه حش هایی با تـابع هـدک بهتـر صـورتمی گیرد. تعیین یا طراحی شیوة نمـایش راه حـش و طراحـیرویة تولید همسایه، دو عنصر کلیدی در طراحـی الگـوریتمشبیه سازی تبرید هستند. این دو عامش بر سرعت همگرایـیالگوریتم و کیفیت راه حش نهایی به دستآمده به شدت تـأثیرمی گذارند. ‌
در نمایش راه حش، با تصویرکردن خصوصیات راه حـش در رشته ای از نمادها ،یک ارتباط منطلی بین فضای مسـئله وفضای جست وجو ایجاد می شود. مسئلة مورد بررسی از سـهزیرمسئله تشکیش شده است؛ بنابراین، نحوة نمـایش شـامشسه نوع ماتری می شـود . بـرای مسـئلة تخصـیص و تـوالیک امیون ه ای ورودی ب ه دره ای تخلی ه از ی ک م اتری دوسطری استفاده می شود. در این مـاتری ، سـطر نخسـتنحوة تخصیص کامیون ها به درهای تخلیه را نشان می دهـدو یک بردار به طول تعداد کامیون ها و ملادیر بازه1,, L است. سطر دوم توالی کامیون هـا را نشـان مـی دهـد و یـکجایگشت کامش از اعداد 1 تا I است .شـکش 1 نمونـه ای از ماتری نخست را با شش کامیون ورودی و سـه در تخل یـه نشان می دهد. براساس شکش 1، کامیون های ورودی 1، 5 و 6 به در 1 تخصیص یافته اند و در توالی تخلیه برای این در ،کامیون های 6، 5 و 1 به ترتیب در موقعیت هـای اول، دوم و سوم از توالی قرار گرفته اند.
1 2 2 3 1 1
5 2 6 3 4 1
شکل 1. مثالی از بخش نخست نمایش راه حل

ماتری دوم، تخصیص و توالی کامیون های خروجی بـهدرهای بارگیری را نشان می دهد و مشابه ماتری تخصیص و توالی کامیون های ورودی است با ایـن تفـاوت کـه تعـدادستون های این ماتری به تعداد کامیون های خروجی است ،اعداد بردار تخصیص از بازه 1,, M  انتخاب می شـوند واعداد بردار توالی، یـک جایگشـت کامـش از اعـداد 1 تـاJ است. ماتری های نوع سوم که به تعـداد انـواع محصـواتهستند، نحوة تخصیص هریـک از محصـوات کـامیون هـایورودی به کامیون های خروجی را نشان می دهنـد و هریـکشامش دو سطر هستند .به منظور تشریح مناسب این بخـش،یک مثال ارائه می شود. فرض کنید تعداد کش محصول نـوع1 برابر با 11 واحد باشد. برای این محصول، ماتریسی بـا دوسطر و 11 ستون تشکیش مـی شـود. در سـطر اول، شـمارةهریک از کامیون های ورودی به صورت صعودی و بـه تعـدادواحـدهای محص ول ن وع 1 موجـود در ه ر ک امیون تک رار می شود. سطر دوم نیز بـه شـیوه ای مشـابه بـا شـماره هـایکامیون های خروجی، تکمیش می شود. تعـداد دفعـات تکـرارهر شمارة کامیون خروجی با تعداد واحـد محصـول نـوع 1 م ورد نی از آن براب ر اس ت. ب رخلاک س طر اول، چی دمانشماره های موجود در سـطر دوم، تصـادفی اسـت. شـکش 2، نمونه ای از نحوة نمایش راه حـش را بـرای محصـول 1 نشـانمی دهد.
1 1 2 2 2 3 4 4 5 6 6
2 3 2 2 1 2 3 2 1 1 1
شکل 2. مثالی از بخش سوم نمایش راه حل

تمام راه حش های تولیدشده بـه صـورت تصـادفی، شـدنیهس تند؛ بن ابراین، ب ه ح ذک، اص لاح ی ا جریم ه ک ردن راه حش های نشدنی نیازی نیست. راه حش اولیه الگـوریتمSA به صورت تصادفی تولید می شود.
برای به دست آوردن ملدار تابع هدک به ازای هـر راه حـشبه این ترتیب عمش مـی شـود: براسـاس مـاتری تخصـیص وتــوالی کــامیون هــای ورودی و مــاتری هــای تخصــیصمحصوات، زمـان هـای ورود و خـروا کـامیون هـای ورودیب ه دس ت م ی آین د. ب ا مش خص ش دن زم ان ه ای ورود کامیون های ورودی و حجم بـار ارسـالی و بـا درنظرگـرفتنزمان ازم برای تخلیـه و انتلـال محصـوات، زمـان شـروععملیات بارگیری برای هر کامیون خروجی محاسبه می شود .با توجه به ماتری تخصیص و توالی کامیون های خروجـی ، زمان های اتمام بارگیری هر کامیون خروجی قابـش محاسـبه است. بزرگ ترین زمـان خـروا، ملـدار تـابع هـدک )دامنـةعملیات( را نشان می دهد.
به منظور ایجاد بردار همسایه برای بردارهای تـوالی کـهمـ اهیتی جایگشـ تی دارنـ د از سـ ه اپراتـ ور معاوضـ ه،معکوس سازی و درا استفاده می شود. در هر راه حش، یکی از این اپراتورها با استفاده از چرخ رولت انتخاب می شود. برای بردارهای مربوط به تخصـیص کـامیون هـا بـه درهـا، تولیـدهمسایه به این شیوه اسـت کـه یکـی از درایـه هـای بـردارتخصیص به صورت تصادفی انتخاب می شود، سس بـا عـددتصادفی دیگری جایگزین می شود. برای تغییر ماتری هـایمربوط به تخصیص محصوات نیز از اپراتور معاوضه در سطر دوم ماتری استفاده می شود.
دمای اولیه، نرخ کاهش دما و معیار توقف، پارامترهـا ی کلیدی در الگوریتم SA به شمار می روند. ملدار دمای اولیـه باید به اندازه ای باشد که حداقش 90 درصـد از راه حـش هـا ی غیربهبوددهنــده در تکــرار اول پذیرفتــه شــوند. اگــر دمــا به آهستگی کاهش یابد، ممکـن اسـت راه حـش هـا ی بهتـر ی به دست آید، اما در ملابش زمان اجرای الگوریتم، طـوانی تـرمی شود. در این پژوهش ،به منظور بهنگام کردن دمـا از تـابعکاهش دمای هندسی به صورت T T استفاده می شـود که در آن  نرخ کاهش دماست. همچنین، از معیار دمـایانجماد به عنوان دستور توقف الگوریتم استفاده شده است.
نتایج محاسباتی
در این قسمت، با ارائة تعدادی مثال عـددی، صـحت مـدلریاضی ارائه شـده بررسـی و عملکـرد الگـوریتم پیشـنهادیارزیابی می شود .به دلیـش نبـود داده هـای واقعـی در ادبیـاتموضوع، چند مسئلة نمونه با ابعـاد کوچـک )مسـائش گـروهاول( و بزرگ )مسائش گروه دوم( بـه صـورت تصـادفی تولیـدمی شود .به منظور تشریح نحوة استفاده از مدل پیشـنهادی،در این بخش مثالی در اندازة کوچـک ارائـه مـی شـود. یـکبارانداز متلـاطع را بـا دو در تخلیـه و دو در بـارگیری، سـهکامیون ورودی و سه کامیون خروجی درنظر بگیرید. فاصلة در ورودی 1 از درهای خروجی 1 و 2 به ترتیب 5 و 9 واحد زمــانی و فاصــلة در ورودی 2 از درهــای خروجــی 1 و 2 به ترتیب 9 و 5 واحد زمانی است. تعداد محصـوات موجـوددر کامیون های ورودی و مورد نیاز کامیون های خروجـی درجدول 1 نشان داده می شود. همچنین، زمان ازم به منظـورتخلیه یا بارگیری هر واحد کاا ،5 واحد زمانی و زمان مورد نیاز به منظور آماده سازی بارانداز 20 واحد زمانی فرض شده است.

0-263790
کامیو
نوع
ن

شما
رة

کامیون

نوع

محصول

1

2

3

5

4

3

زمان

ورود

زمان

خروا

60
/
8

6
/
68

60
/
88

کامیو

نوع



قیمت: تومان


دیدگاهتان را بنویسید