بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوریتم ژنتیک ابتکاري براي حل مسئله "چیدن جعبه ها در کانتینر کشتی" با مدت زمان کمتر
چکیده
بیشتر کالاها در دنیا توسط کشتی ها در دریاها و اقیانوس ها حمل شده و به مقصد هدایت می شوند. این مقالـه بـه مسـئله "چیـدن جعبـه هـا در چندین کانتینر کشتی" 1(MCP) با تابع هدف کمینه سازي مقدار فضاي اتلاف شده در کانتینر ها (به متر مکعب) می پردازد. به دلیل اینکـه ایـن مسئله جزء مسائل NP-hard است، در این مقاله از الگوریتم ژنتیک2 ابتکاري براي حل آن استفاده شد. این الگوریتم ابتدا جعبه ها را گروه بنـدي می کند. سپس جمعیت ابتدایی را با استفاده از این گروه ها و با روش ابتکاري تولید کرده و عملگرهاي جابجایی و جهش را نیـز بـه کمـک همـین گروه بندي اجرا می کند. در این مقاله 9 مثال عددي با گستره 100 تا 2000 جعبه مطرح گردید و با الگوریتم ژنتیک پیشنهادي حل شد و با سـه روش بهینه سازي ازدحام ذرات 3(PSO)، سیستم ایمنی مصنوعی 4(AIS) و الگوریتم ژنتیک سـاده در تحقیقـات پیشـین مقایسـه گردیـد. نتـایج کارائی الگوریتم ژنتیک پیشنهادي را در رسیدن به جواب با مدت زمان کمتر نسبت به سه روش مذکور نشان دادند.
کلمات کلیدي: الگوریتم ژنتیک ابتکاري، گروه بندي جعبه ها، کانتینر کشتی، زمان کمتر در رسیدن به جواب.
-1 مقدمه و پیشینه تحقیق
با گسترش روز افزون تجارت جهانی، معاملات بین المللی و واردات و صادرات بین کشورهاي مختلف، به طبع تعداد و مقدار حمـل و نقـل کـالا هـر روز رو به افزایش است. با وجود راه هاي زمینی و هوایی، بیشتر محموله ها از طریق بندرگاه هاي اصلی در سـاحل دریاهـا و اقیـانوس هـا و توسـط کشتی هاي غول پیکر مخصوص بار جابجا می شوند .[1] محموله هامعمولاً در جعبه ها با اندازه هاي مختلف بسته بندي می شوند. جعبه ها نیز به طور منظم در کانتینر واقع در کشتی قرار می گیرند. درنتیجه نحوه چیدن جعبه ها در کانتینر ها و استفاده صحیح از فضـا بخصـوص هنگـامی کـه اندازه جعبه ها با هم متفاوت هستند (جعبه هاي نامتجانس)، براي سازمان هاي حمل و نقل و همچنین صاحبان کالاها بسیار مهم و حیاتی اسـت و اثر زیادي بر سود آنها دارد.
مسئله 5CP که چیدن B جعبه در یک کانتینر است، داراي معیارهاي مختلفی از قبیل اندازه جعبه (نامتجانس یا یکسان)، شکل جعبه (مکعبـی یـا غیر مکعبی) و تعداد کانتینر کشتی ها (یک یا بیشتر) می باشد. توابع هدف براي این مسئله می توانند (1 کمینه سازي تعداد مورد نیـاز از کـانتینر کشتی، (2 کمینه سازي طول مورد نیاز از کانتینر کشتی، (3 کمینه سازي مقدار فضاي اتلاف شده، (4 بیشینه سازي تعداد جعبـه چیـده شـده در کانتینر کشتی و یا (5 بیشینه سازي استفاده از فضا باشند.
فرضیات مهم و عمومی مسئله CP به منظور ساده سازي، مدل سازي و حل آن عبارتند از (1 :[1] جعبه ها بایسـتی در داخـل کـانتینر در تمـامی فضاها به صورت یکنواخت چیده شوند، به این معنا که تراکم جعبه ها در تمام گوشه کانتینرها یکسان باشد. (2 جعبه ها از نظر فیزیکی نمی توانند در فضاي اشغال شده جعبه هاي دیگر قرار بگیرند، به این معنا که جعبه ها نباید فضاي مشترك با یکـدیگر داشـته باشـند. (3 قابلیـت چـرخش در جعبه ها و قرار گیري آنها در 6 وضعیت بر طبق شکل 1 وجود دارد.
این مقاله یکی از حالات خاص مسئله CP یعنی مسئله پیچیده و مشکل MCP را در نظر می گیرد که در آن چندین کانتینر وجـود دارد. در ایـن مسئله B جعبه مکعبی نامتجانس با درنظر گرفتن فرضیات شماره 1، 2 و 3 در C کانتینر چیده می شوند تا مقدار فضاي اتلاف شده کمینـه گـردد
(تابع هدف شماره .(3
تعداد کل حالات براي چیدن B جعبه در کانتینرها برابر با B> است. در هر کدام از این حالات، قرار گرفتن B جعبه 6B وضعیت خواهد داشت (هر جعبه می تواند یکی از 6 وضعیت شکل 1 را بگیرد). به طور مثال تعداد 610 × 10! = 219 × 1012 امکان بـراي چیـدن 10 جعبـه در کانتینرهـاوجود دارد. در نتیجه مسئله MCP از نظر پیچیدگی محاسباتی جزء مسائل NP-hard است 1]و.[2 به این معنـا کـه اگـر انـدازه مسـئله (تعـداد
جعبهها) به صورت خطی افزایش یابد، زمان محاسبات براي یافتن بهترین جواب به صورت نمائی زیاد مـی شـود. در نتیجـه روش هـاي مبتنـی بـر جستجوي کامل مانند برنامه ریزي خطی([3] Beasley) 1 و شاخه و کران([4] Pisinger) 2 تنها درصـورتی کـه انـدازه مسـئله کوچـک باشـد،
مناسب هستند. بنابراین روش هاي فرا ابتکاري3 براي حل مسئله MCP ایجاد شدند که گستره وسـیعی از ایـن روش هـا ماننـد جسـتجوي تـابو4 Gendreau) و همکاران [5] و Bortfeldt و همکاران ([6]، الگوریتم ژنتیک Thapatsuwan) و همکـاران [1]، Thapatsuwan و همکـاران [7]، Bortfeldt و [8] Gehring و Thapatsuwan و همکاران ([9]، بهینه سازي کلونی مورچگـانLee) 5 و همکـاران ([10]، بهینـه سـازي ازدحـــام ذرات Thapatsuwan) (PSO) و همکـــاران [1] و Thapatsuwan و همکـــاران ([11] و سیســـتم ایمنـــی مصـــنوعی (AIS) Thapatsuwan) و همکاران ([1] در حل مسئله MCP به کار رفته انـد. اطلاعـات مفیـد در مـورد پیشـینه تحقیـق مسـئله MCP در مقـالات مختلفی از جمله [4] Pisinger، Ngoi و همکاران [12] و Egeblad و [13] Pisinger وجود دارند.
شکل :1 شش وضعیت قرار گیري جعبه ها درون کانتینرها
-2 مدل سازي مسئله چیدن جعبه ها در چندین کانتینر کشتی (MCP)
Christensen و [14] Rousoe و Chen و همکاران [15] یک مدل ریاضی براي مسئله MCP با تابع بیشـینه سـازي اسـتفاده از فضـا (تـابع هدف شماره (5 ارائه دادند. Thapatsuwan و همکاران [1] نیز در مقاله خود مسئله MCP را با تابع کمینه سازي مقدار فضاي اتلاف شده (تابع
هدف شماره (3 مدل سازي نمودند که این مدل با برنامه ریزي عدد صحیح ترکیبی خطی در زیر آمده است.
در این مدل پارامترهاي زیر وجود دارند. : B تعداد جعبه ها - : C تعداد کانتینر کشتی ها - li، wi و : hi طـول، عـرض و ارتفـاع جعبـه i ام - Lj، Wj و : Hj طول، عرض و ارتفاع کانتینر j ام.
متغیرهاي این مدل نیز در زیر آمده اند. xi، yi و : zi متغیرهایی که نشان دهنده محل جعبه i ام در کانتینر کشتی به صورت سـه بعـدي هسـتند
(نقطه مختصات در گوشه مربوط به چپ، عقب و پائین قرار دارد) - lix ، liy و : liz متغیرهاي صفر و یک، اگر طول جعبه i ام موازي محورهـاي
X، Y و Z باشد، مقدار این متغیر ها برابر با یک است، وگرنه این متغیرها مقدار صفر می گیرند - wix ، wiy و : wiz متغیرهاي صفر و یک، که
نشان دهنده موازي بودن عرض جعبه i ام با محورهاي X، Y و Z می باشند - hix ، hiy و : hiz متغیرهاي صفر و یک، که نشان دهنده مـوازي بودن ارتفاع جعبه i ام با محورهاي X، Y و Z می باشند - : leik متغیر صفر و یک، که نشان دهنده قرار گرفتن جعبه i ام در سمت چـپ جعبـه k ام است - : riik متغیر صفر و یک، که نشان دهنده قرار گرفتن جعبه i ام در سمت راست جعبه k ام اسـت - : beik متغیـر صـفر و یـک، کـه
نشاندهنده قرار گرفتن جعبه i ام در پشت سر جعبه k ام است - : fiik متغیر صفر و یک، که نشان دهنده قرار گرفتن جعبه i ام در جلوي جعبـه k ام است - : abik متغیر صفر و یک، که نشان دهنده قرار گرفتن جعبه i ام در بالاي جعبه k ام است - : unik متغیر صـفر و یـک، کـه نشـان-
دهنده قرار گرفتن جعبه i ام در زیر جعبه k ام است - : pij متغیر صفر و یک، که نشان دهنده قرار گرفتن جعبه i ام در کـانتینر j ام اسـت -
: cj متغیر صفر و یک، که نشان دهنده استفاده شدن کانتینر j ام است - : M عددي بسیار بزرگ که در محدودیت هاي M بزرگ بکار می رود. متغیرهاي leik، riik، beik، frik، abik و unik تنها هنگامی تعریف می شوند که i کوچکتر از k باشد. طول L کـانتینر کشـتی در محـور X،
عرض W آن در محور Y و ارتفاع H آن در محور Z قرار گرفته است. معادله 1 تابع هدف مسئله و یا کمینه سازي مقدار فضاي اتلاف شده را بیان
می کند. معادلات 2 تا 15 به عنوان محدودیت هاي مدل معرفی می شوند. محدودیت هاي 2 تا 7 نشان می دهند که جعبه هاي قرار گرفتـه نبایـد فضاي مشترك با همدیگر داشته باشند (فرض .(3 محدودیت 8 بر این نکته تمرکز دارد که تنها یکی از متغیر هاي leik، riik، beik، frik، abik و unik بایستی یک باشند. محدودیت 9 تضمین می کند که هر جعبه تنها در یک کانتینر قرار گیرد. محدودیت 10 مشخص می کند که به محض
تخصیص حداقل یک جعبه به کانتینر کشتی، آن کانتینر مورد استفاده قرار می گیرد. محدودیت هاي 11 تا 13 نشان می دهند که همه جعبه هاي چیده شده در یک کانتینر کشتی داخل فضاي فیزیکی آن کانتینر قرار می گیرند و امکان ندارد کـه بخشـی از جعبـه هـا از کـانتینر بیـرون بزننـد.
محدودیت هاي 14 و 15 محدوده قابل قبول براي متغیرها را بیان می کنند.
-3 مثال هاي عددي
در این مقاله 9 مثال عددي با تعداد 100، 250، 500، 750، 1000، 1250، 1500، 1750 و 2000 جعبه در نظر گرفته شده است. در تمامی ایـن مثال ها که در مقاله Thapatsuwan و همکاران [1] مطرح شدند، طول جعبه ها به صورت تصادفی در بازه 70 تا 100 سانتی متر، عرض جعبهها
به صورت تصادفی در بازه 50 تا 80 سانتی متر و ارتفاع جعبه ها نیز به صورت تصادفی در بازه 30 تا 60 سـانتی متـر انتخـاب مـی شـوند. در ایـن مثالها از کانتینر هاي استاندارد استفاده شد. هر کانتینر استاندارد در کشتی داراي 20 فوت 6) متر و 10 سانتی متر) طول، 8 فـوت 2) متـر و 44
سانتی متر) عرض و 8 فوت ارتفاع است. بعد از اینکه در هر مثال از 9 مثال مذکور با B جعبه، طول، عرض و ارتفاع جعبه ها مشخص گردیـد، ایـن
مثال ها با الگوریتم ژنتیک ابتکاري حل شد و نتایج آنها بـا روش هـاي بهینـه سـازي ازدحـام ذرات (PSO)، سیسـتم ایمنـی مصـنوعی (AIS) و الگوریتم ژنتیک ساده در مقاله Thapatsuwan و همکاران [1] مقایسه گردید. ذکر این نکته ضروري است که الگوریتم پیشنهادي بـه ایـن اعـداد
محدود نمی شود و این روش قادر است مسئله MCP را با هر اندازه اي از جعبه ها و هر اندازه اي از کانتینر ها حل نماید.
-4 الگوریتم ژنتیک ابتکاري براي حل مسئله MCP
شکل 2 فلوچارت الگوریتم پیشنهادي را نشان می دهد. مراحل این الگوریتم در زیر آمده است.
شکل :2 فلوچارت الگوریتم ژنتیک ابتکاري
-1 -4 کدگذاري کروموزوم ها
هر جواب مسئله MCP شامل C کانتینر است که در هر کدام از آنها تعدادي جعبه قرار گرفته اند. مجموع تمامی جعبه ها برابر با B می باشـد. در الگوریتم ژنتیک هر جواب با یک کروموزوم1 متناظر با خودش نشان داده می شود و هر کروموزوم نیز یک جواب را القا می کنـد. عـلاوه بـر آن هـر کروموزوم نیز مجموعه اي از تعدادي ژن2 است. در الگوریتم پیشنهادي تعداد ژن ها برابر با تعداد جعبه ها می باشد و هـر ژن نیـز شـامل دو عـدد است. عدد اول شماره جعبه و عدد دوم وضعیت چیدمان آن (بر طبق شکل (1 را نشان می دهد. یک مثال از این کرومـوزم در شـکل 3 نشـان داده شده است. اولین ژن در سمت چپ نشان دهنده این است که جعبه 5 در وضعیت 3 قرار دارد. شماره ژن ها از سمت چپ به راست ترتیـب چیـدن جعبه ها را نشان می دهند یعنی همان طور که در شکل 3 می بینید ابتدا جعبه شماره 5 (در وضعیت (3 و سپس جعبه شماره 3 (در وضعیت (1 و
... قرار می گیرند.
-2 -4 گروه بندي جعبه ها به نسبت تعداد جعبه ها می توان آنها را به تعدادي گروه تقسیم بندي نمود. این گروه بندي در تولید جمعیت ابتدایی و اعمال عملگرهاي ژنتیک به
کار می آید. گروه بندي در الگوریتم پیشنهادي به صورت زیر انجام می گیرد:
(1 اگر تعداد جعبه ها کمتر از 500 بود، آنها به 3 گروه "بزرگ" (گروه اول)، "متوسط" (گروه دوم) و "کوچک" (گروه سوم) تقسـیم بنـدي مـی-
شوند. (2 اگر تعداد جعبه ها مابین 500 و 999 بود، آنها به 4 گروه "بسیار بزرگ" (گروه اول)، "بـزرگ" (گـروه دوم)، "متوسـط" (گـروه سـوم) و
"کوچک" (گروه چهارم) تقسیم بندي می شوند. (3 اگر تعداد جعبه ها مابین 1000 و 1490 بـود، آنهـا بـه 5 گـروه "بسـیار بـزرگ" (گـروه اول)،
"بزرگ" (گروه دوم)، "متوسط" (گروه سوم) و "کوچک" (گروه چهارم) و "بسیار کوچک" (گروه پنجم) تقسـیم بنـدي مـی شـوند. (4 اگـر تعـداد جعبهها مابین 1500 و 2000 بود، آنها به 6 گروه "بسیار بسیار بزرگ" (گروه اول)، "بسیار بزرگ" (گروه دوم)، "بزرگ" (گـروه سـوم)، "متوسـط"
(گروه چهارم) و "کوچک" (گروه پنجم) و "بسیار کوچک" (گروه ششم) تقسیم بندي می شوند.
شکل :3 یک مثال از کروموزوم کدگذاري شده
-3 -4 تولید جمعیت ابتدایی1 با روش ابتکاري
به مجموعه اي از کروموزوم ها جمعیت2 و به تعداد کروموزم هاي هر جمعیت اندازه جمعیت3 گویند. جمعیت ابتدایی می توانـد بـه دو روش تولیـد شود. اولین روش، روش تصادفی است که Thapatsuwan و همکاران [1] در مقاله خود از این روش در الگوریتم ژنتیک ساده استفاده نمودند. در
روش تصادفی از بین B جعبه، اولین جعبه به تصادف انتخاب می شود و از بین 6 وضعیت مربوط به شکل 1، یک وضعیت نیز به تصـادف مشـخص می شود. سپس این جعبه طبق وضعیتش در کانتینر کشتی قرار می گیرد. بعد از آن نوبت به جعبه دوم و وضعیتش می رسد که در کـانتینر چیـده شود. این کار ادامه می یابد تا تمام جعبه ها در کانتینر کشتی چیده شوند.
دومین روش روش ابتکاري است که الگوریتم ژنتیک پیشنهادي در تولید جمعیت ابتدایی خود از این روش اسـتفاده نمـود. در ایـن روش جمعیـت ابتدایی نه براساس شانس و تصادف، بلکه بر اساس گروه بندي بدست آمده در بند قبلی تولید می شود. به این ترتیب که ابتدا جعبه هاي مربوط بـه گروه اول (جعبه هاي بزرگ تر) در کف کانتینر چیده می شوند. به صورتی که با احتمال بیشتر در وضعیت 1 و 2 (شکل (1 قرار گیرند چرا که ایـن دو وضعیت براي جعبه هاي بزرگتر مناسب تر است. سپس جعبه هاي گروه دوم بر روي جعبه هاي گـروه اول بـا 6 وضـعیت (شـکل (1 در کـانتینر کشتی قرار می گیرند. بعد از آن نوبت به گروه سوم می رسد. این کار تا زمانی ادامه می یابد تا همه جعبه ها در کانتینر ها چیده شوند. مزیت اولیـه و ظاهري روش ابتکاري نسبت به روش تصادفی این است که اگر از جواب هاينسبتاً خوب به جاي هر جواب تصادفی (خوب یا بد) اسـتفاده شـود، الگوریتم با احتمال بیشتري موفق می شود به جواب هاي بهتر دست یابد.
-4 -4 انتخاب در حرکت از هر جمعیت به جمعیت بعدي بایستی تعدادي کروموزوم انتخاب شوند که آنها را والد4 می نامند. در الگوریتم ژنتیـک ابتکـاري در ایـن
مقاله مجموع تابع برازندگی هر کروموزوم (یا تابع هدف هر جواب در معادله (1 با احتمال انتخاب شـدن آن کرومـوزوم برابـر مقـدار ثـابتی در نظـر گرفته می شود. به این معنا که هر کروموزوم با تابع برازندگی کمتر (هر جواب با تابع هدف کمتر)، شانس بیشتري براي انتخـاب شـدن در یـک یـا چند مرتبه دارد.
-5 -4 عملگر جابجایی5 به روش ابتکاري بعد انتخاب کروموزوم ها، دو عملگر بر آنها اعمال می شوند تا کروموزوم هاي جدید به نام فرزند6 در جمعیت بعدي بدست آیند. این حرکت از یـک
جمعیت به جمعیت بعدي تولید7 نامیده می شود. یکی از این عملگر ها جابجایی است که بر دو کروموزوم والد اعمال شـده و دو کرومـوزم فرزنـد را بدست می آورد. عملگر جابجایی با روش تصادفی و یا با روش ابتکاري بر کروموزوم هاي والد عمل می کنـد. Thapatsuwan و همکـاران [1] در
الگوریتم ژنتیک ساده خود، در اعمال عملگر جابجایی از روش تصادفی استفاده نمودند. در این روش ابتدا از بین B جعبه، تعدادي جعبه به تصـادف انتخاب می شوند. ژن هاي مربوط به این جعبه ها در دو کروموزوم والد با هم تعویض شده و دو کروموزوم فرزند بدست می آیند.
این مقاله از روش ابتکاري براي اعمال عملگر جابجایی استفاده می کند. در این روش در الگوریتم پیشنهادي، ابتدا از بین تمامی گروه هاي موجـود، یک گروه به تصادف انتخاب می شود. سپس تعدادي جعبه در گروه منتخب به تصادف برگزیده می شوند. ژن هاي مربوط بـه ایـن جعبـه هـا در دو کروموزوم والد با هم تعویض شده و دو کروموزوم فرزند بدست می آیند. در این روش جعبه ها با اندازه هايتقریباً یکسانی تعـویض مـی شـوند کـه احتمال رسیدن به جواب هاي بهتر را افزایش می دهد.
