1- مقدمه

امروزه صنعت حمل‌ونقل از اهمیت بالایی برخوردار می‌باشد، چرا که رشد اقتصادی و ادامه حیات اقتصادی کشورها به صنعت حمل‌و‌نقل وابسته است. بر اساس آمار سازمان تجارت جهانی (2014)، در سال 2013 حجم تجارت جهانی به 12900 میلیارد دلار رسید. سهم حمل‌ونقل دریایی در جابه‌جایی کالاها در تجارت بین‌المللی حدودا 90% کل آن را تشکیل می‌داد. همچنین طبق همین آمار 3/13% از تناژ کشتی‌های موجود مربوط به کشتی‌های کانتینربر بود. میزان استفاده از کانتینر در حمل‌ونقل دریایی رو به افزایش است. به طوری که تعداد کانتینرهای حمل شده در جهان از 55 میلیون TEU در سال 2009 به 125 میلیون TEU در سال 2013 رسیده است (2014 UNCTAD,). همچنین طبق آمار سازمان بنادر و دریانوردی تعداد 2204183 TEU کانتینر در سال 1393 در بنادر جنوبی ایران تخلیه و بارگیری شده است. با توجه درصد بالای جابه‌جایی کانتینری کالا در تجارت جهانی و ایران، اهمیت حمل‌ونقل کانتینری دریایی در تجارت به‌عنوان دو عنصر جدانشدنی غیرقابل انکار است. بنابراین ارائه خدمات کارآمد در حمل‌ونقل دریایی از پارامتر های لازم و تاثیرگذار در تجارت بین المللی است.

 در دنیای امروز زمان و هزینه از عوامل مهم رقابت به‌حساب می‌آیند. به بیان دیگر، شرکت‌هایی موفق‌اند که بتوانند کالای خود را به موقع و با هزینه کمتر به دست مشتری برسانند (1980Pearson,). بهینه‌سازی و مدیریت صحیح کشتی‌های کانتینربر می‌تواند ضمن کاهش زمان و هزینه‌های حمل‌ونقل، ارائه خدمات سریع‌تری را فراهم آورد. در این پژوهش چند کشتی کانتینربر برای حمل کانتینر مدیریت می‌شوند. به‌طوری که با به‌کارگیری بهینه کشتی‌ها، هزینه و مدت زمان جابه‌جایی کانتینر کمینه می‌شود. کانتینرها از یک بندر هاب به چهار بندر واسطه‌ای با در نظر گرفتن محدودیت‌های زمانی جابه‌جا می‌شوند. هر بندر در موقعیت جغرافیایی مشخص و با فاصله کمتر از 600 مایل دریایی قرار دارد. برای هر بندر تعرفه‌های بندری و تعداد کانتینرهایی که باید جابه‌جا شود مشخص است. اطلاعات مربوط به کانتینرها شامل وزن، بندر مبداء ، بندر مقصد و مهلت تحویل آن در مقصد مشخص است.

1-1- پیشینة پژوهش

مسیریابی خطوط حمل‌ونقل کانتینری در سراسر جهان تبدیل به یک موضوع محبوب تحقیقات دانشگاهی شده است. از این رو مقالات زیادی با تمرکز بر جنبه‌های مختلف آن منتشر شده است. رونن (1993)، کریستیانسن و همکاران (2004 و 2013)، کجلدس[1] (2011)، در زمینه مسیریابی و برنامه‌ریزی کشتی،  هوف و همکاران (2010)، در موضوع  ترکیب ناوگان و مسیریابی، و  یانگ و همکاران (2012)، در زمینه طراحی شبکه خطوط حمل‌ونقل منظم تحقیقاتی را انجام داده‌اند. برانچ[2] و همکاران (2008)، روشی برای بهینه‌سازی تخلیه و بارگیری کانتینر در چند مرحله با استفاده از الگوریتم‌های ابتکاری ارائه دادند. در این تحقیق یک کشتی باید کانتینرهایی را از یک بندر هاب به چند بندر دیگر برساند و در باز گشت کانتینرها را از بنادرفرعی به هاب بازگرداند. نالوسامی[3] و همکاران (2009)، روشی برای مسیریابی بهینه برای مجموعه‌ای از چند کشتی ارائه دادند. در این پژوهش نیز از روش‌های فرا ابتکاری استفاده شده بود.

1-2- هدف تحقیق

هدف اصلی این تحقیق ارائه یک برنامه سفر برای ناوگانی از چند کشتی کانتینری واسطه‌ای برای حمل کانتینر از یک بندر هاب به بنادر واسطه‌ای و برعکس می‌باشد، به‌طوری که با در نظر گرفتن محدودیت‌های زمانی برای حمل و ظرفیت کشتی‌ها، هزینه‌های حمل‌ونقل کانتینرها کاهش یابد. برای این منظور باید به دو سوال پاسخ داده شود: (1) از چه تعداد کشتی و کدامیک استفاده کنیم؟ و (2) چه مسیری را برای کشتی‌ها انتخاب کنیم در واقع ترتیب ورود کشتی‌ها به هر بندر چگونه باشد؟

 2- روش انجام تحقیق

تحقیق حاضر از نظر هدف، از آن جهت که نتایج آن می‌تواند برای بهبود مدیریت سفرهای کشتی‌های کانتینربر مفید واقع شود تحقیقی کاربردی محسوب می‌شود.  روش گردآوری داده‌ها در این پژوهش، مطالعه کتابخانه‌ای و میدانی است. مراحل انجام این تحقیق به این ترتیب است که ابتدا یک مدل لجستیکی به صورت ریاضی، برای مدیریت کشتی‌ها تعریف می‌شود. این مدل ریاضی که یک مسئله بهینه‌سازی است شامل تابع هدف و قیود مسئله می‌باشد. در این مدل محدودیت‌های ظرفیت وسیله حمل و محدودیت زمانی در نظر گرفته شده است. سپس، مسئله بهینه‌سازی با در دست داشتن یک سناریو با اطلاعات واقع‌بینانه و استفاده از یک الگوریتم فرا ابتکاری حل می‌شود. در این تحقیق جهت پیاده‌سازی الگوریتم از نرم افزار متلب استفاده شده است.

3- تجزیه و تحلیل داده‌ها

3-1- رابطة ریاضی مسئله

رابطة ریاضی مسئله که برای بهینه‌سازی است، با توجه به هدف پژوهش که کمینه کردن مجموع هزینه‌های متغیر حمل، شامل هزینه سفر (سوخت + پرسنل) و هزینه عوارض و تعرفه‌های بندری، و نیز با عنایت به محدودیت‌های زمان حمل و ظرفیت کشتی، به این صورت می‌باشد:

متغیرهای ورودی

یک گراف جهت‌دار                                                                                                                                               G(P,A)

مجموعه گره‌های گراف G، گره 1 تا گره p نماینده بنادر می‌باشند                                                                          P={1,…,p}

مجموعه یال‌های گراف G  که گره  iرا به گره  j وصل می‌کند و نشان‌دهنده سفر انجام‌شده  کشتی از گره i به  j است.                                                                                                                                                                                   A={(i,j):i,j∈P,i≠j}

مجموعه کشتی‌ها (k) که ممکن است استفاده شود.                                                                    V={1,…k_max}                

مجموعه کانتینرهایی که باید حمل شود.                                                                                    C={1,…α_max}               

مجموعه سفرهای (ϕ) برای هر کشتی نشان‌دهنده تعداد کمان‌های (i, j) است که توسط کشتی در یک مسیر طی شده است.                                                                                                                                                                                                  

حال به ازای هر   داریم:

طول یال (i, j) متناظر با فاصله بندرi تا j به مایل دریایی                                                                                                     d_ij

سرعت کشتی به گره دریایی                                                                                                                                    vel_k

ظرفیت کشتی k                                                                                                                                                   Q_k

زمان تحویل کانتینر α                                                                                                                                             a_α

بنادر مبدا و مقصد کانتینر α                                                                                                                                     o_α;e_α

تعرفه‌های بندر i برای کشتی k                                                                                                                                 f_ik

مدت زمانتخلیه یا بارگیری هر کانتینر در بندر i                                                                                                           b_i

هزینه سفر برای کشتی k به ازای هر مایل دریایی                                                                                                        C_k

زمانی که کشتی k در سفرϕ به بندر i وارد می‌شود                                                                                      S_ikϕ

متغیرهای تصمیم گیری:

برابر با 1 است اگر کشتی k در سفر ϕام  از بندر i به بندر j سفر کند. و در غیر این صورت صفر است            

برابر با 1 است اگر کشتی k پس از ترک بندر i در سفر ϕام کانتینر α را بار گیری کرده باشد 

تابع هدف:

تابع هدف که مجموع هزینه سفر و تعرفه‌های بندری را کمینه می‌کند به این صورت بیان می‌شود:

محدودیت‌های مسئله:

محدودیت اول تضمین می‌کند کشتی به هر بندری وارد شود از آن خارج شود و به بندر دیگر رود . این محدودیت در مسایل VRP باز در نظر گرفته نمی‌شود و تنها زمانی استفاده می‌شود که بخواهیم کشتی به بندری که از آن سفر خود را آغاز کرده باز گردد. محدودیت دوم  باعث می‌شود عملیات بندری قبل از رسیدن کشتی به آن بندر آغاز نشود. نماد M₁، یک عدد ثابت بزرگ است. زمان سرویس‌دهی به زمان و فاصله طی‌شده توسط کشتی و مجموع زمان سرویس‌دهی به آن کشتی در بندر قبلی بستگی دارد. محدودیت سوم تضمین می‌کند ضرب‌العجل تحویل کانتینر از زمان تعیین‌شده تجاوز نکند. محدودیت چهارم تضمین می‌کند وزن مجموع کانتینرهای بارگیری‌شده در کشتی از ظرفیت آن تجاوز نکند. محدودیت پنجم تضمین می‌کند هر کانتینر با یک و تنها با یک کشتی بین بنادر حمل شود. محدودیت ششم مسئله مسیریابی برای کشتی و مسئله بارگیری کانتینرها را با یکدیگر تلفیق می‌کند. برای مثال اگر یک کانتینر در یک کشتی بارگیری شود آنگاه آن کشتی باید حتماً به بندری که مقصد کانتینر است سفر کند.

3-2- پیاده سازی و حل مسئله

با بررسی پیشینة تحقیق مشخص شد که با توجه به محدودیت‌های بسیار زیاد و فضای راه‌حل بزرگ در مسئله، استفاده از الگوریتم ژنتیک نتایج بهتری نسبت به دیگر روش‌ها دارد. بنابراین برای حل این مسئله از الگوریتم ژنتیک که یک الگوریتم فرا ابتکاری است استفاده شد. الگوریتم ژنتیک (GA) تکنیکی برای یافتن راه‌حل تقریبی برای مسائل بهینه‌سازی است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هلند در سال 1970 معرفی شد. روند استفاده از الگوریتمهای ژنتیک برای حل یک مسئله به صورت شکل (1) می باشد.

شکل(1): فلوچارت الگوریتم ژنتیک

مراحل مختلف الگوریتم و روش انجام آن برای حل مسئله به این صورت است: (1) معرفی جواب‌های مسئله به عنوان کروموزوم (کدگذاری)، (2) معرفی تابع تناسب و ارزیابی، (3) جمع‌آوری اولین جمعیت، (4) معرفی عملگرهای انتخاب، (5) معرفی عملگرهای تلفیق و جهش.

 کد گذاری[4]: برای کد کردن یک جواب بالقوه، مسیر طی‌شده به‌وسیله کشتی‌ها را که شامل ترتیب ورود هر کشتی به بنادر است در یک رشته از اعداد قرار می‌دهیم. برای مثال دو جواب زیر را در نظر بگیرید:

مسیر اول:                                            1 3 4 5 * 2 5 1 4

مسیر دوم:                                           1 3 4 5 * 3 2 5 4

این روش کدینگ، یک روش کدینگ تک قسمتی ناپیوسته است. و کروموزوم اول به معنی این است که کشتی اول مسیر خود را از بندر1 شروع و به ترتیب به بنادر 3، 4 و 5 سفر می‌کند و کشتی دوم از بندر2 سفر خود را آغاز و به ترتیب به بنادر 5، 1 و 4 سفر می‌کند.

علامت‌های * مسیرهای کشتی‌ها را از یکدیگر جدا می‌کند که به آنها حائل^[5] گفته می‌شود. تعداد حائل‌ها به تعداد کشتی‌ها منهای یک است. که می‌توانیم حائل‌ها را با اعداد دیگری جایگزین کنیم. در این رشته‌ها تعداد کشتی‌ها 2 فروند هستند و بنابراین تعداد حائل‌ها 1 است که با عدد 6 نشان می‌دهیم.

مسیر اول:                                            1 3 4 5 6 2 5 1 4

مسیر دوم:                                           1 3 4 5 6 3 2 5 4

بنابراین کد متناظر با یک مسیر، یک رشته از اعداد صحیح است که طول آن برابر با تعداد بنادر به اضافه تعداد کشتی‌ها منهای یک است.

ارزیابی[6]:

این مرحله نیز نقش بسیار مهمی در حل مساله به روش الگوریتم ژنتیک ایفا می‌کند. در این مرحله با معرفی یک معیار و اندازه، بهتر بودن یا نبودن هر جواب ممکن از جمعیت اولیه به دست می‌آید. یعنی اینکه این معیار به ما می‌گوید که مثلا جواب x واقع در جمعیت اولیه چقدر خوب است. مثلا اگر داشته باشیم f(a)=3 و f(b)=5، به این معنا است که عضو b در جمعیت اولیه بهتر از a است یا مقدار تناسب[7] بالاتری نسبت به a دارد. برای ساختن تابع تناسب می‌توانیم از رابطة ریاضی مسئله استفاده کنیم. همان‌طور که گفته شد در رابطة ریاضی مسئله یک تابع هدف و چند محدودیت وجود دارد، که شکل کلی آن با توجه به مسئله بهینه‌سازی مقید به این صورت است:

Time windows

Capacity

Tour lengh

.

برای اینکه تابع تناسب همه موارد موجود در مسئله را در برگیرد آن را به صورت تابع نامقید تغییر می‌دهیم. در این حالت قیود مسئله با دادن وزن به تابع اضافه می شود.

     تابع نامقید                        

در این رابطه قیود مسئله به عنوان تابع جریمه به تابع هزینه اضافه شده‌اند. و چنانچه در یک جواب از محدودیت‌های زمان و یا ظرفیت تخطی صورت گیرد، مقدار این توابع جریمه عددی مثبت می‌شود که مقدار آن نشان‌دهنده میزان تخطی است. ضرایب ثابت  و  میزان اهمیت هر قید را مشخص می‌کند و هر چقدر بزرگ‌تر فرض شوند محدودیت‌ها سخت‌تر می‌شوند.

انتخاب والدین:

پس از ارزیابی کروموزوم‌ها تعدادی از آنها برای تولید نسل جدید انتخاب می‌شوند. همان‌طور که اشاره شد عمل انتخاب به این صورت انجام می‌شود که همه جواب‌ها برای والدشدن هم‌شانس نیستند. به عبارت دیگر جواب‌هایی احتمال زیاد و بالاتری برای والدشدن دارند که مقدار تناسب آنها بالاتر باشد. ما می‌توانیم برای هر جواب یک عدد به عنوان تناسب، نظیر قرار دهیم، مثلا برای 2  x=عدد 4 و برای 0 =x عدد 2 را قرار دهیم. در این صورت مشخص است که 2 =x جواب بهتری نسبت به 0 =x است یعنی تناسب بالاتری دارد. حال می‌توانیم تابع احتمال انتخاب را به این صورت تعریف کنیم:

(p جمعیت و q اعداد نظیر شده است)

این نوع انتخاب که در نمودار (2) نشان داده شده است، با عنوان Roulette Wheel Selection بیان می‌شود.

نمودار (2): روش انتخاب Roulette Wheel

 تلفیق:

عملگر تلفیق روی جواب‌های انتخاب‌شده برای تغییر به این‌گونه عمل می‌کند که یک نقطه به صورت تصادفی روی رشته کروموزومی انتخاب می‌کند سپس ناحیه‌های چپ یا راست آن نقطه در رشته کروموزومی جابه‌جا می‌شود. همچنین برای تلفیق می‌توانیم دو نقطه انتخاب کنیم و ناحیه‌های بین دو نقطه را جابه‌جا کنیم. در شکل (2) تلفیق با یک، دو و چند نقطه انتخابی را مشاهده می‌کنید.[8]

شکل (2):عملگرهای تلفیق

جهش:

جهش نیز عملگری است که جواب‌های دیگری را به دست می‌دهد. نحوه عملکرد آن به این‌گونه است که به صورت تصادفی روی کروموزوم انتخابی، نقطه‌ای را انتخاب می‌کند و فرم آن را تغییر می‌دهد. عملگر جهش انواع مختلفی دارد:

عملگر دو گزینه‌ای (2-opt): دو یال (a , b) و (c , d) را از دورمان انتخاب می‌کنیم و بررسی می‌کنیم که آیا می‌توانیم این 4 رأس را با یک روش متفاوت به هم وصل کنیم تا کمترین وزن را به ما بدهد یا خیر. برای انجام این کار اگر Cab + Ccd > Cac + Cdb باشد لازم است یال‌های (a , b) و (c , d) را بایال‌های (a , c) و (d , b) عوض کنیم.

عملگر سه گزینه‌ای (3-opt): سه یال تصادفی را برای یال‌های (a , b) و (c , d) و (e , f) بررسی می‌کنیم اگر Cab + Ccd + Cef > Cac + Cbe + Cdf باشد، یال‌های (a , b) ، (c , d) و (e , f)را با یال‌های (a , c) و (b , e) و (d , f) عوض کنیم.

رمز گشایی[9]:

رمز‌گشایی در مقابل کدگذاری است. در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مساله به دست داد، باید بر عکس کدگذاری،  جواب‌ها رمزگشایی شود تا بتوانیم نسخه واقعی جواب را به وضوح به دست آوریم.

3-3- پیاده‌سازی مدل

در این پژوهش، مدل برای یک سناریوی با اطلاعات واقعی شامل پنج بندر (امام خمینی، بوشهر، عباس، عسلویه و جبل‌علی) و 3 کشتی کانتینربر (کشتیرانی والفجر) و تعداد 5000 کانتینر پیاده‌سازی و نتایج بررسی شد.

جدول (1): داده‌های مربوط کشتی‌های مختلف

جدول (2): فواصل بنادر

تعرفه‌های بندری در همه بنادر ثابت و براساس تناژ کشتی‌ها است. جدول (3) اطلاعات کانتینرها را به لحاظ مبدأ، مقصد، مهلت تحویل و وزن نشان می‌دهد.

جدول (3): اطلاعات کانتنرها

جدول(4) نتایج پیاده‌سازی و ترتیب تردد هر کشتی به بنادر را نشان می دهد.

جدول (4): نتایج پیاده‌سازی، مسیرهای بهینه‌شده

در نمودار (1) با مقایسه جواب‌های ارایه شده در بارست‌های مختلف الگوریتم می‌توان مشاهده نمود که با تغییر تعداد و نوع کشتی‌هایی که جهت حمل کانتینرهای موجود استفاده می‌شود و ترتیب تردد کشتی‌ها به بنادر و همچنین کانتینرهایی که به هر کشتی برای حمل تخصیص می‌یابد، هزینه کل تغییر می‌کند. هر چقدر تعداد بارست‌های الگوریتم افزایش می‌یابد تعداد، نوع کشتی و مسیر اختصاص‌یافته به آن بهینه می‌شود و نتیجتاً هزینه نهایی کاهش می‌یابد.

نمودار (1): ارتباط هزینه کل با ترتیب تردد و نوع کشتی‌ها

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

4- نتیجه‌گیری

روش ارائه‌شده در این پژوهش برای حل یک مسئله با سناریوی مربوط به اطلاعات یک شرکت کشتیرانی واسطه‌ای می‌باشد. نتایج نشان داد که در صورت استفاده از این روش، هزینه‌ها می‌تواند تا 17% کاهش یابد. هرچند نتایج نشان می‌دهد که برخی از محدودیت‌ها برآورده نشده‌اند، اما این امر به دلیل در نظر گرفتن محدودیت‌ها به‌صورت محدودیت نرم بوده است، که با افزایش میزان جریمه از تخطی به یک مقدار بزرگ، تعداد تخطی به صفر کاهش یافت و میزان کاهش هزینه 5% شد