بخشی از مقاله
چکیده
یکی از مباحثی که در دهه اخیر مورد توجه بسیاری از مدیران و کارشناسان صنایع قرار گرفته افزایش کارآیی و بهرهوری سیستمهای حملونقل است بگونهای که محصول پس از تولید در زمان مناسب و با حداقل هزینه، به دست مشتری برسد. از این رو اهمیت به دو مسأله منطقی به نظر میرسد، یک ایجاد محورهایی بهعنوان واسطههای انتقال جریان از چندین مبدا به چندین مقصد و نیز پاسخگویی در زمان مجاز به تورهای هر محور است، دیگری مسیری است که وسایلنقلیه در بازه پنجره زمانی مربوط به هر گره مقصد میبایست طی کنند.
از سوی دیگر این مسائل ممکن است باعث بوجود آمدن اختلاف هزینهی زیاد بین محورها و برهم زدن اعتدال بین آنها گردند. بنابراین در این مقاله مدلی ارائه شده است که ضمن کاهش هزینههای کل سیستم، به برقراری توازن هزینه میان وسایل نقلیه میپردازد. با توجه به چند هدفه و NP-Hard بودن مسأله، روش الگوریتم فراابتکاری رقابت استعماری چند هدفه - - MOICA جهت ارائه جوابهای پارتو پیشنهاد و برای نشان دادن کارایی الگوریتم پیشنهادی، جوابهای بدست آمده در ابعاد کوچک و متوسط و بزرگ با جوابهای بدست آمده از الگوریتم NSGA-II مقایسه میشود. سپس عملکرد آن با استفاده از شاخصهای ارزیابی حفظ کارایی الگوریتم جهت حل مسئله در ابعاد بزرگ، مشخص میگردد .
-1 مقدمه
مسأله مکانیابی محور - Hub Location - بهدلیل کاربرد بسیاری که در حملونقل مدرن و سیستمهای ارتباطی دارد، در چند دهه اخیر از اهمیت بهسزایی برخوردار است. هدف آن تامین تقاضا با جابهجایی افراد، کالا و اطلاعات از طریق تسهیلات خاصی بهنام محور که واسطههای توزیع بین جفت گرههای مبدا و مقصد هستند، میباشد.[1] در این شبکهها جمعآوری و توزیع تقاضا در محور میتواند به صورت رفتوبرگشتی و یا یکطرفه باشد که آن به مقدار تقاضا بستگی دارد.
برخی از کاربردهای مسائل محور عبارتند از: صنایع ارتباطات و مخابرات[2]، حملونقل هوایی[3]، زمینی[4]، خدمات پستی [5] و حملونقل عمومی، شهری و سیستمهای ارتباطات از راه دور و خدمات اضطراری. بهطور معمول اینگونه مسائل ، شامل مکانیابی محورها و غیر محورها در یک شبکه توزیع و تخصیص تمامی نقاط مبدا و مقصد - غیر محورها - به محورها به-صورت مستقیم و یا مسیریابی آنها در یک تور میباشد، به گونهای که هزینههای شبکه اعم از جمعآوری و توزیع و سایر هزینههای مرتبط به آن حداقل شود.
در برخی مقالات با مشخصکردن مکان محورها تنها به مسأله تخصیص پرداخته اند[6]، اما در برخی دیگر هر دو مکانیابی و تخصیص را با هم در نظر گرفته اند[7] و از آنجایی که این دو مقوله روی یکدیگر اثر دارند باید توامان با هم در نظر گرفت که در این مقاله نیز بدینصورت لحاظ شده است. محورها با کاهش تعداد لینکهای ارتباطی میان گرههای مبدا و مقصد از اتصال مستقیم تمامی گرهها به یکدیگر جلوگیری کرده که این کار سبب کاهش هزینهها نسبت به یک شبکه با اتصالات کامل - گراف کامل - شدهاست.
[8] بهطور کلی در مسائل کلاسیک مکانیابی محور سه فرض اصلی در نظر گرفته میشود که اجمالا عبارتند از: - 1شبکه محور بهصورت گراف کامل - 2 ارتباط بین محورها که شامل ضریب آلفا بین 1]، - 3 [0ارتباط مستقیم بین گرههای غیرمحور ممنوع[9] که حالتهای پایه مسائل مکانیابی محور توسط Nickel و Hamacher در سال 1998 طبقهبندی شدهاند که در این طبقهبندی این مسائل از 7 جنبه مورد بررسی قرار میگیرند.
مسأله دیگری که میتوان با مسأله مکانیابی محور مدلسازی کرد، مسأله مسیریابی حملونقل مسافر بهخصوص حملونقل شهری و عمومی میباشد که بسیار کم مدنظر قرار گرفته است. مسأله مسیریابی 5 دسته مختلف دارد که با توجه به ادبیات موضوع مقاله مورد نظر، ترکیبی از انواع مسایل مسیریابی است. مسأله مسیریابی وسیلهنقلیه - VRP - به مجموعهای از مسایل اطلاق میشود که در آن ناوگانی متشکل از چندین وسیلهنقلیه از یک یا چند قرارگاه به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی میپردازند و به آنها باز میگردند، این امر را به نحوی انجام میدهند که هزینههای انجام این کار به حداقل برسد.
در سال 2013 بانوس و همکاران[10] مقاله ای منتشر کردند که در آن یک مسأله مسیریابی وسایلنقلیه با در نظرگرفتن پنجره زمانی بهدنبال کمینهسازی هزینه کل سیستم حملونقل و همچنین کاهش اختلاف مسافتهای پیموده شده توسط وسایل حمل بوده است که در اصطلاح به آن بالانس مسافت میگویند. آنها این مدل دوهدفه را با استفاده از چندین روش فراابتکاری حل و جوابهای پارتو تشکیل شده را مورد مقایسه و ارزیابی قرار دادند. Cetiner و همکاران در سال[11]2010 یک راه حل دو مرحلهای برای این مسأله تدوین کردهاند که در این مسأله تخصیص چندگانه مجاز بوده و سوار و پیادهکردن همزمان و محدودیت برای بیشینه مسیر تور در نظر گرفته شده است.
در مرحله اول حل، محل محورها و تخصیص گرههای غیر محور به محور اتفاق میافتد و در مرحله بعد مسأله فروشنده دورهگرد برای هر محور حل میشود. مسألهمجدداً با بهروزکردن میزان مسافت میان گرهها در مرحله اول حل می-شود. از آنجاییکه مسأله مجزا برای هر محور حل میشود امکان دارد یک گره غیرمحور بدون هیچ ضرورتی در دو مسیر واقع شود. این روش برای 7 مثال حل شده است. همچنین در این مسأله هیچ محدودیتی برای ظرفیت محور و وسیلهی حمل در نظر گرفته نشده است و فقط طول مسیر تور محدودیت دارد. همچنین مسیر هر وسیلهی نقلیه از یک محور آغاز و تمامی گرههای غیرمحور را که به آن تخصیص داده شده است را بازدید میکند و به محور مربوطه باز میگردد.
برای این مسأله یک نوع فرمولیزاسیون جدید در سال 2013 توسط de camargo صورت گرفتهاست.[12] در این مقاله ناوگان حمل یکسان و ضریب تخفیف در نظر گرفته شده است و سوار و پیادهکردن همزمان اتفاق میافتد، ولیکن محدودیتی برای ظرفیت محور وجود ندارد و هر گره غیرمحور فقط یک دفعه ملاقات می شود. مدلسازی ارائه شده به گونهای است که از الگوریتم تجزیه بندرز برای حل آن استفاده نمود. هدف در این مسأله نیز کمینهکردن هزینه است.
این مسأله به روش دقیق و برای ابعاد کوچک حل شد. Julia در سال 2014 مدلی متفاوت از مکانیابی - مسیریابی چند به چند ارائه نمود که در آن دو فرض چندمحصولی و حمل-ونقل بین محورها در نظر گرفته شده است که این مدل ترکیبی را برای ابعاد کوچک با نرمافزار Cplex کد کرده و بهعلاوه فرض نقطه شروع چندگانه را اضافه و با روش ابتکاری Fix-and-Optimize و الگوریتم ژنتیک برای ابعاد بزرگ حل نموده که با نتایج بهدست آمده، کارایی مدل مفروض نشان داده شده است.
مختاری و عباسی[13] در سال 2014 این مسأله را با روشهای VNS, PSO برای ابعاد بزرگ حل کردهاند و این مدل را با در نظر گرفتن نمونههای کوچک 300 گرهای در مقایسه با نتایج الگوریتم بندرز مقایسه نموده و با نزدیک بودن جوابها صحت آن را تأیید کرده است. زرندی، همتی و داوری[14] در سال - 2013 - مدل مکانیابی- مسیریابی با محدودیتهای ظرفیت وسیلهی نقلیه، محور و پنجره زمانی ارائه کرد. در این مدل زمان سفر به صورت غیرقطعی فازی در نظر گرفته شده است. این مدل یک مدل چندسطحی، چنددپویی با محدودیت ظرفیت برای انبارها و محورها همراه با محدودیت زمانی است که با الگوریتم شبیهسازی تبرید مدل شده است.
.1,2 ارایه مدل پیشنهادی
این مسأله بهدنبال آن است که هر وسیله نقلیه با ظرفیت مشخص بتواند محموله مورد نظر را از چندین مبدا به چندین مقصد با عبور از حداقل یک محور در بازه پنجره زمانی سخت مربوط به هر گره و حداکثر زمان مجاز سفر و نیز محدودیت طول سفر دریافت و تحویل دهد و همزمان کل هزینه حملونقل و اختلاف بیشترین و کمترین مسافت و زمان سفر برای هر وسیلهنقلیه، بهعنوان نوآوری مقاله، حداقل شود تا از این طریق سطح سرویس در زمان مطلوب هر گره چنان افزایش یابد که منجر به افزایش بهرهوری نیروی انسانی، ماشینآلات، انرژی و کاهش اثرات زیستمحیطی و خستگی رانندگان در شبکه گردد.
در بخش دوم مدل برنامهریزی ریاضی مسأله با بیان تمامی فرضیات و محدودیتهای آن توصیف و یک مدل ریاضی دوهدفه ارائه میگردد. در بخش سوم اعتبارسنجی مدل تکهدفه ، رویکردهای حل دوهدفه، محدودیت اپسیلون - - -constraint و الگوریتم پیشنهادی رقابت استعماری چندهدفه - MOICA= A multi-Objective Imperialist Competitive Algorithm - توضیح داده میشود و در بخش چهارم کارآیی الگوریتم پیشنهادی نسبت به ژنتیک چند هدفه NSGA-II با دو شاخص بررسی می-شود. در نهایت در بخش پنجم جمعبندی و نتیجهگیری مشخص میگردد.
.2 مدلسازی ریاضی
.2,2 فرضهای مسأله :
➢ در میان هر دو گره تقاضایی قطعی وجود دارد و پارامترهای مسأله همگی قطعی میباشند.
➢ تمامی گرهها امکان تبدیل شدن به محور را دارند و فاکتور تخفیف برای اتصال بین محورها نیز در این مسأله وجود دارد.
➢ در هر بار دیدن هر گره هدف دریافت و تحویل بهطور همزمان میباشد مبدا وسایلنقلیه، محورها در نظرگرفته شده است.
➢ یک وسیلهی نقلیه از هر محور خارج شود باید به همان بازگردد و حرکتش در هر تور دارای محدودیت حداکثر زمان و طول سفر است.
➢ هر گره میتواند با بیش از یک محور سرویس داده شود - تخصیص چندگانه - و دارای پنجره زمانی سخت برای خدمترسانی است.
➢ ناوگان حملونقل همگن و با ظرفیت محدود است. مدل تک محصولی و تک دورهای، با تابع دوهدفه میباشد.
➢ محورها با ظرفیت محدود و اتصالات بین آنها به صورت گراف کامل و تعدادشان متغیر تصمیم است.
