بخشی از مقاله
چکیده
در این مقاله به ارائه مدل ریاضی برای این مساله با هدف کاهش بیشینه زمان تکمیل کارها برای جریان ورودی و خروجی کانتینرها پرداخته شده است. با توجه به ارتباط تنگاتنگ میان مساله زمانبندی جرثقیلهای اسکلهای و زمانبندی کامیونهای محوطه و لزوم هماهنگی موثر بین این تجهیزات جهت اجتناب از حالتی که جرثقیلهای اسکلهای و یا کامیونها منتظر یکدیگر باشند، در این مطالعه به بررسی مساله زمانبندی یکپارچه جرثقیلهای اسکلهای و کامیوهای محوطه پرداخته شده است.
فرضیات دنیای واقعی مانند عدم عبور جرثقیلهای اسکلهای از یکدیگر و وجود فاصله اطمینان بین جرثقیلها در مدل پیشنهادی گنجانده شده اند. به منظور بررسی و ارزیابی مدل پیشنهادی تعداد 45 مساله نمونه به صورت تصادفی تولید و حل شده است. نتایج نشان می دهد که مدل پیشنهادی برای مسائل در ابعاد کوچک قابلیت دستیابی به جواب بهینه را دارد. مدت زمان حل مساله برای ابعاد بزرگتر به ویژه با افزایش تعداد کانتینرها به صورت نمایی افزایش پیدا کرده و برای مسائل ابعاد بزرگ امکان حل مساله به صورت بهینه در مدت زمان معقول، امکانپذیر نمیباشد.
-1 مقدمه
ترمینال های کانتینری به ویژه در سالهای اخیر نقش مهمی در سیستم حمل و نقل بینالمللی ایفا میکنند. تجارت جهانی بنادر ترمینالی از 1280 میلیون کانتینر 20 فوتی - TEU - در سال 2010 به 1687 میلیون TEU در سال 2015 افزایش یافته است که بیانگر رشد میانگین سالانه 6/3 درصد می باشد .[1] با توجه به نرخ رشد سریع حجم کانتیرهای مبادله شده در دهه اخیر، لازم است کارایی عملیاتی در ترمینالهای کانتینری بهبود یابند.به صورت کلی، یک ترمینال کانتینری از دو بخش تشکیل یافته است. این بخش ها عبارتند از بخش سمت دریا با اسکلههایی که به منظور بارگیری یا تخلیه کشتیها مورد استفاده قرار می گیرند و بخش خشکی که کانتینرها توسط کامیونها حمل شده و ذخیره می شوند. سه نوع اصلی از تجهیزات در فرایند بارگیری و تخلیه در ترمینالهای کانتینری بکار گرفته میشوند؛
جرثقیلهای اسکلهای - QC - ، کامیونهای محوطهای - YT - و جرثقیلهای اسکلهای . - YC - برنامه ریزی عملیات در ترمینالهای کانتینری شامل مسائل اصلی تخصیص پهلوگاه - BAP - ، تخصیص جرثقیلهای اسکلهای - QCAP - ، زمان بندی جرثقیلهای اسکلهای - QCSP - ، زمانبندی تجهیزات حمل و نقل زمینی، زمانبندی جرثقیلهای محوطه و مکانیابی ذخیرهسازی کانتینرها در محوطه میباشد .[3] مساله زمانبندی جرثقیلهای اسکلهای و زمانبندی کامیونهای محوطه، ارتباط تنگاتنگی با هم دارند. از این رو لازم است هماهنگی موثری بین این تجهیزات شکل گیرد تا از حالتی که جرثقیلهای اسکلهای و یا کامیونها منتظر یکدیگر باشند، اجتناب شود. از این رو در این مطالعه به بررسی مساله زمانبندی یکپارچه جرثقیلهای اسکلهای و کامیوهای محوطه پرداخته شده است.
-2 مرور ادبیات
در این بخش مرور مختصری بر روی مطالعات صورت گرفته در حوزه مسائل زمانبندی جرثقیلهای اسکلهای و کامیونهای محوطه صورت گرفته است. تحقیقات بر روی این مساله سی سال قبل با مطالعه داگانزو - 1989 - آغاز شد. او یک مدل ریاضی با فرض حضور چندین کشتی در اسکله و چندین جرثقیل اسکلهای برای این مساله ارائه نموده است .[4] کیم و پارک - 2004 - مساله زمان بندی جرثقیل های اسکله ای را مورد بررسی قرار داده و یک الگوریتم شاخه و کران - B&B - و الگوریتم ابتکاری GRASP برای حل مساله توسعه دادهاند .[5]
مدل ارائه شده توسط کیم و پارک - 2004 - بعدا توسط موچیا و همکاران - 2006 - و بیرویرث و مایسل - 2009 - بهبود یافت. موچیا و همکاران - 2006 - یک الگوریتم مبتنی بر رویکرد شاخه و برش ارائه نمودند. الگوریتم پیشنهادی برای مسائل نمونه مورد استفاده توسط کیم و پارک - 2004 - ، پاسخهای با کیفیت بهتری ارائه مینماید .[6] بیرویرث و مایسل - 2009 - نیز الگوریتم شاخه و کران برای حل مساله توسعه دادهاند. نتایج حاصل از این الگوریتم نسبت به الگوریتمهای ارائه شده توسط کیم و پارک - 2004 - و موچیا و همکاران - 2006 - ، نتایج با کیفیت بهتری هستند .[7]
مطالعات اخیر بر مساله زمانبندی جرثقیلهای اسکلهای بر مدلسازی مسائل با در نظر گرفتن فرضیات اصلی در دنیای واقعی متمرکز شده اند. این ویژگیها عبارتند از فاصله ایمنی بین جرثقیلهای اسکلهای - مانند نوئن و همکاران [8] - 2013 - ؛ کاوشگر و همکاران - [9] - 2012 - ، عدم عبور جرثقیلهای اسکلهای از همدیگر - مانند لیو و همکاران [10] - 2006 - ؛ نو و مک - [2] - 2006 - و روابط پیشنیازی بین فعالیتها - مانند کیم و پارک [5] - 2004 - ؛ سامارا و همکاران . - [11] - 2007 - برای مرور مفصل مدلهای بهینهسازی و کاربردهای مدیریت عملیات در ترمینالهای کانتینری به منابع [12] و [13] مراجعه شود.
مساله زمان بندی کامیون های محوطه در بنادر کانتینری نیز در سالهای اخیر مورد بررسی محققین قرار گرفته است.
بیش - 2003 - مساله توزیع کامیونهای محوطه را با هدف کمینه کردن بیشینه زمان خدمتدهی به مجموعه مشخصی از کشتیها مورد بررسی قرار داد. همچنین یک الگوریتم ابتکاری بر مبنای مساله حمل و نقل ارائه شده است . [14] نو و همکاران - 2007 - مساله زمان بندی کامیون ها را با در نظر گرفتن زمانهای پردازش وابسته به توالی و زمانهای آماده به کار متفاوت برای کانتینرها، مورد بررسی قرار داده و یک مدل ریاضی عدد صحیح و الگوریتم فراابتکاری ژنتیک برای حل آن ارائه نمودهاند .[15]
در سال های اخیر، تعدادی مقاله به بررسی ارتباط بین عملیات جرثقیلهای اسکلهای و زمانبندی کامیونها پرداختهاند. چِن و همکاران - 2007 - مساله زمانبندی یکپارچه جرثقیلهای اسکلهای، کامیونهای محوطه و جرثقیلهای محوطهای را به صورت یک مساله جریان کارگاهی هیبرید با محدودیتهای پیشنیازی مدلسازی نمودهاند .[16] کائو و همکاران - 2010 - مساله زمانبندی جرثقیل های اسکله ای و کامیونهای محوطه را برای کانیتنرهای وارداتی مطالعه نموده و یک مدل برنامهریزی عدد صحیح و الگوریتم ژنتیک برای حل مساله ارائه نمودهاند [17]چِن. و همکاران - 2013 - مساله زمانبندی جرثقیلهای اسکلهای، کامیونهای محوطه و جرثقیل های محوطه را با رویکرد برنامهریزی محدودیتها مدلسازی کردهاند.
.[18] تانگ و همکاران - 2014 - مدل برنامه ریزی عدد صحیح برای مساله زمانبندی یکپارچه جرثقیلهای اسکلهای و کامیونهای محوطه برای کانتینرهای ورودی ارائه نموده است .[19] همچنین یک مدل برنامهریزی عدد صحیح توسط کاوشگر و هان - 2015 - برای زمان بندی همزمان جرثقیلهای اسکلهای و کامیونهای محوطه برای تخلیه کانتینرهای ورودی توسعه یافته است. .[20] هی و همکاران - 2015 - مساله زمانبندی یکپارچه عملیاتهای بنادر کانتینری را با هدف کمینه کردن انرژی حمل و نقل مصرفی را مورد بررسی قرار داده اند. .[21]
-3 تعریف مساله
در مساله زمان بندی یکپارچه جرثقیلهای اسکلهای و کامیونهای محوطه، علاوه بر تخصیص کانتینرها به جرثقیلهای اسکله ای و کامیونهای محوطه، توالی پردازش کانتینرها نیز تعیین خواهد شد. در این تحقیق به ارائه مدل ریاضی برای این مساله با هدف کاهش بیشینه زمان تکمیل کارها برای جریان ورودی و خروجی کانتینرها پرداخته شده است. فرضیات اصلی مساله مورد بررسی عبارتند از:
· هر جرثقیل یا کامیون در هر لحظه تنها به یک کانتینر میتواند خدمت دهد.
· جرثقیل ها در یک راستا حرکت می کنند و امکان اینکه از یکدیگر عبور کنند وجود ندارد. این فرض که یکی از محدودیتهای اصلی در دنیای واقعی به شمار میرود، فرض non-crossing نامیده میشود.
· با توجه به اینکه جابجایی جرثقیلهای اسکلهای زمانبر است، زمانی که جرثقیل به یک دسته کانتینر - bay - تخصیص یافت، تا زمان تکمیل آن کارها به bay دیگری تخصیص نخواهد یافت.
· روابط پیشنیازی بین کانتینرها وجود دارد. برای مثال کانتینرهایی که در ردیف های پایین تر هستند، پس از تخلیه کانتینرهای در ردیفهای بالایی باید تخلیه شوند.
· به منظور رعایت مسائل ایمنی، بین جرثقیلها فاصلهی اطمینانی - safety margin - وجود دارد.
· هیچگونه فضایی مابین جرثقیلهای اسکلهای و کامیونها به عنوان buffer برای ذخیره سازی کانتینرها در نظر گرفته نشده است.
-4 مدل برنامهریزی عدد صحیح
مساله زمان بندی یکپارچه جرثقیلهای اسکلهای و کامیونهای محوطه بر مبنای مساله زمانبندی کار کارگاهی منعطف - flexible jobshop - فرمولبندی شده است. در مساله کارِ کارگاهی منعطف تعداد n کار بر روی m ماشین بایستی پردازش شوند. هر کار - در اینجا کانتینر - دارای چند نوع عملیات است که با ترتیب و توالی خاصی بر روی ماشینها - در اینجا جرثقیلهای اسکله ای و کامیونهای محوطه - انجام میشوند. هر ماشین قادر است عملیاتهای مشخصی را پردازش کند. پردازش کانتینرها زمانی به اتمام خواهد رسید که تمام عملیاتهای آن اعم از تخلیه یا بارگیری و حمل و نقل توسط کانتینر به مقصد انجام شوند.
