بخشی از مقاله
چکیده
در مسئله مکان یابی هاب مقداري محموله از یک سري مبدا به یک سري مقصد انتقال می یابند، اما از آن جایی که ارتباط مستقیم هر کدام به دیگري هزینه بسیار زیادي دارد، تعدادي از مراکز به عنوان نقاط هاب در نظر گرفته می شوند. سرعت افزایشی تغییرات در ساختار هزینه و تقاضا، خیلی اوقات سازمان ها را براي ایجاد مجدد شبکه مجبور می کند. در این مقاله یک رویکرد چند دوره اي که این تغییرات را لحاظ می کند و پیکربندي بهینه شبکه مکان یابی هاب را امکان پذیر می کند، توسعه داده شده است. در مسئله مورد پژوهش هاب ها داراي طول عمر مشخص هستند. نتایج نشان می دهد؛ تشکیل شبکه پویا در مقایسه با حالت ایستا، هزینه کمتري در پی خواهد داشت و همچنین هزینه ها در زمانی که هاب ها امکان بازسازي داشته باشند، کمتر خواهد بود.
.1مقدمه
مسائل مکان یابی هاب، به دلیل کاربرد بسیاري که در حمل و نقل مدرن و سیستم هاي ارتباطی دارند، در سه دهه اخیر از اهمیت به سزایی برخوردار شده اند. هاب عبارت است از مراکز جمع آوري و توزیع که به جاي ارتباط مستقیم میان دو نقطه، با هدف اتصالات کمتر و غیر مستقیم بین گره ها، مورد استفاده قرار می گیرد. بدین ترتیب طراحی شبکه مبتنی بر هاب سبب کاهش بسیار زیادي در هزینه هاي جابه جایی خواهد شد.
در یک مسئله مکان یابی هاب، هدف یافتن هاب ها و مسیرها براي فرستادن کالا از یک سري مبدا به یک سري مقصد است به گونه اي که فرایند جمع آوري و توزیع بهینه شود. هدف این روش کاهش هزینه ها - هزینه تاسیس هر هاب و هزینه انتقال در هر مسیر - و در زمان مناسب می باشد. کالا از مبدا به هاب ها فرستاده می شود و در آنجا دوباره سازماندهی شده و از آنجا به مقصد نهایی فرستاده می شود. . هاب ها سه وظیفه اصلی دارند:
- 1 فاز جمع آوري: که در آن تقاضا از نقاط غیر هاب به نقاط هاب، جمع آوري می شود.
- 2 فاز انتقال: تقاضا را به دیگر هاب ها - در صورت وجود - انتقال می دهند.
- 3 فاز توزیع: تقاضاهاي دریافت شده از دیگر هاب ها در شبکه را به نقاط غیرهاب مقصد ارسال می نمایند. مسائل مکان یابی هاب از لحاظ انواع تخصیص نقاط به هاب قابل تقسیم بندي هستند که عبارتند از:
تخصیص تکی :که کل جریان هر مبدا و یا مقصد دقیقا به یک نقطه ي هاب تخصیص پیدا می کند.
تخصیص چندگانه : که جریان هر مبدا و یا مقصد به بیش از یک نقطه ي هاب تخصیص پیدا می کند .[1]
اگر شبکه اي با N نقطه داشته باشیم که هر کدام بتوانند هم مبدا باشند و هم مقصد، N* - N-1 - کمان وجود خواهد داشت. شکل 1 یک گراف کامل از اتصالات در شبکه اي با 6 نقطه را نشان می دهد اما در شکل 2 یکی از نقاط به عنوان هاب در نظر گرفته شده است و تعداد کمان ها به 5 مسیر کاهش یافته است. بدین ترتیب طراحی شبکه مبتنی بر هاب سبب کاهش بسیار زیادي در هزینه هاي جابه جایی خواهد شد.
شکل -1 شبکه بدون هاب
شکل -2 شبکه هاب
در واقعیت، فقط براي یک دوره واحد تصمیم گیري نمی شود و برنامه ریزي براي یک افق زمانی با چندین دوره انجام می شود. بنابراین ممکن است با توجه به عوامل مختلف، پیکربندي اولیه شبکه تغییر یابد. در هر دوره از افق برنامه ریزي، پیکربندي دوره قبلی به روزرسانی می گردد و این روند تا پایان افق زمانی ادامه پیدا خواهد کرد .[2] در این مقاله، مسئله مکان یابی هاب پویا با تخصیص تکی در حالتی که هر هاب طول عمر مشخص دارد، بررسی شده است.
یک افق برنامه ریزي با تغییرات جریان میان گره هاي مبدا و مقصد و تغییرات هزینه هاي ثابت تسهیلات در نظر گرفته شده است. هدف، کمینه کردن هزینه کل در افق برنامه ریزي می باشد. تابع هزینه کل شامل هزینه هاي حمل و نقل براي جمع آوري و توزیع کالاها و هزینه هاي تسهیلات براي راه اندازي، بستن و بازسازي هاب در مدت افق برنامه ریزي می باشد. هاب ها می توانند باز شوند - یک غیر هاب، هاب می شود - ، بسته شود - یک هاب، غیر هاب می شود - و یا اینکه بازسازي شوند. در این مقاله سطوح ظرفیت و بازسازي چندگانه در نظر گرفته شده است.
.2 پیشینه موضوع تحقیق
در زیر مروري بر مقالات ارائه شده در زمینه مکان یابی هاب انجام شده است. اوکلی در سال 1987 مسئله ي مکان یابی هاب با تخصیص تکی با ظرفیت نامحدود که در آن تعداد گره هاي هاب به صورت برون زا تعیین می شدند، را ارائه داد. در این مسئله هزینه اي براي تاسیس تسهیل هاب در نظر گرفته نشد. .[3] کمپبل - 1991 - براي نخستین بار، یک مدل ریاضی خطی براي مسئله p-hub میانه با تخصیص چندگانه بدون محدودیت ظرفیت ارائه داد. لازم به ذکر است که در مسائل p-hub میانه ، هزینه ثابت ایجاد هاب نادیده گرفته می شود.
.[4] اوکلی - 1991 - نخستین مسئله مکان یابی هاب با تخصیص تکی و هزینه ثابت ایجاد هاب را به صورت یک مدل ریاضی درجه دو معرفی نمود. در مسائل با هزینه ثابت هاب بر خلاف مسائل p-hub میانه ، هزینه ثابت ایجاد هاب در نظر گرفته شده و تعداد هاب ها به عنوان متغیر در مدل مطرح می شود. .[5] کمپبل - 1994 - پیشنهاد داد که مدل هاي پایه را می توان با در نظر گرفتن هزینه ثابت ایجاد ارتباط بین گره هاي غیرهاب و هاب، به صورت مسائل مکان یابی p-hub میانه با هزینه ثابت اتصال، توسعه داد.
در این پژوهش همچنین، براي نخستین بار، یک مدل عدد صحیح خطی براي مسئله p-hub میانه با تخصیص چندگانه بدون محدودیت ارائه شد. .[6] ارنست و کریشنامورتی - 1996 - یک مدل عدد صحیح خطی متفاوت براي مسئله p-hub میانه با تخصیص تکی پیشنهاد و براي حل مدل ارائه شده، یک الگوریتم فراابتکاري مبتنی بر شبیه سازي تبرید ارائه دادند. آنها تلاش نمودند با در نظر گرفتن جریان بین هاب ها به عنوان یک جریان چند کالایی، مدلی با متغیرها و محدودیت هاي کم تر ولی با کارایی بیش تر براي حل مسائل اندازه بزرگ معرفی نمایند. .[7] ارنست و کریشنامورتی - 1999 - ، یک مدل ریاضی عدد صحیح مختلط جدید براي مسئله مکان یابی هاب تخصیص تکی با محدودیت ظرفیت بر مبناي ایده مطرح شده در ارنست و کریشنامورتی - 1996 - ارائه دادند. .[8] کارا و تنسل - - 2003 مدل هاي خطی گوناگونی براي مسئله پوشش جزیی تخصیص تکی ارائه دادند. .[9]
دي کامارگو و همکاران - - 2008 از روش تجزیه بندرز براي حل دقیق مسئله مکان یابی هاب تخصیص چندگانه بدون محدودیت ظرفیت استفاده نمودند. .[10] کونتراس و همکاران - 2009 - از آزادسازي لاگرانژ براي حل مسئله مکان یابی هاب تخصیص تکی با محدودیت ظرفیت استفاده نمودند. .[11] کرریا و همکاران - - 2010 به توسعه مدل مکان یابی هاب تخصیص تکی با محدودیت ظرفیت پرداختند که در آن، علاوه بر تعداد و مکان هاب، ظرفیت هاب هم خود بخشی از فرآیند تصمیم گیري بود.
به این ترتیب تصمیماتی که با حل مدل باید گرفته می شد عبارت بود از: - 1 انتخاب مدل و تعداد هاب ها - 2 تخصیص گره هاي غیرهاب به هاب ها - 3 توزیع جریان در زیر شبکه هاي تعریف شده توسط هاب ها - 4 سطوح ظرفیت هاب ها - انتخاب هر سطح هزینه متفاوتی را به مسئله تحمیل می کرد - به صورت بهینه. .[12] آلومور و کارا - 2008 - و زنجیرانی و همکاران - 2013 - هر دو معروف ترین و جدید ترین مرور ادبیات هاي موجود در زمینه مکان یابی هاب هستند. 13] و .[1 لی و همکاران - 2013 - مسئله مکان یابی هاب را همانند شبکه صف GI/G/1 مدل سازي کردند، مدل صف و مدل مکان یابی و تخصیص با یکدیگر ترکیب شده و سپس مسئله مکان یابی هاب چند نوعی - Multimodal - با درنظر گرفتن محدودیت ظرفیت پیشنهاد و ارزیابی شد.
در یک شبکه هاب چند نوعی، منابع محدود در هاب ممکن است سبب تاخیردر حمل و نقل شود که روي خدمت دهی تاثیر خواهد گذاشت. .[14] توکلی مقدم و همکاران - 2014 - مسئله مکان یابی هاب چند نوعی در حالتی که چند سطح ظرفیت وجود دارد و شبکه هاب ناکامل است، را مورد بررسی قرار داد. علاوه بر مکان یابی و تخصیص، در مورد وضعیت حمل و نقل و سطوح ظرفیت نیز براي کمینه کردن هزینه و زمان حمل و نقل تصمیم گیري شد. .[15] برنامه ریزي چند دوره اي در مکان یابی هاب بر خلاف مکانیابی تسهیلات و زنجیره تامین، مورد توجه زیادي قرار نگرفته است.
براي اولین کار در زمینه مکان یابی هاب چند دوره اي می توان به مقاله کمبپل - 1990 - که مدل تقریب پیوسته یک کشتی که یک منطقه ثابت با تراکم افزایشی تقاضا را تحت پوشش قرار می داد، اشاره کرد. بعدها، گلاره - 2008 - مسئله مکان یابی هاب چند دوره اي براي حمل و نقل عمومی در نظر گرفت که در آن وضعیت هاي مکان هاي هاب می تواند در مدت افق برنامه ریزي تغییر کند. .[16] پیکربندي مجدد بر پایه مجموعه هاب و کمان هاي اولیه می باشد. در این مقاله شبکه هاب، یک گراف کامل در نظر گرفته شده است.
مدل عدد صحیح مختلط پیشنهادي حتی براي مسائل سایز کوچک، به صورت بهینه قابل حل نبود و آنها روي پیشنهاد براي یک الگوریتم ابتکاري متمرکز شدند. تیموریان و همکاران [17] و تقی پوریان و همکاران [18]، مسائل مکان یابی هاب در زمینه برنامه ریزي اورژانسی براي صنعت هوایی را بررسی کردند. برخی یا همه ي ظرفیت یک فرودگاه می تواند به دلیل شرایط هوایی غیر قابل دسترس شود. پروازها ممکن است به هاب هاي مجازي که در مواقع اضطراري فعال می شوند، مسیردهی شوند. مدل هاي برنامه ریزي عدد صحیح مختلط و برنامه ریزي عدد صحیح فازي براي تعیین مکان هاب هاي مجازي و مسیر بین مبدا-مقصد در مدت افق برنامه ریزي توسعه داده شده است. کنترراس و همکاران [11]، یک مسئله مکان یابی هاب پویا بدون محدودیت ظرفیت را در نظر گرفتند.
آنها مورد تخصیص چندگانه را با استفاده از رویکرد شاخه و کران که از آزادسازي لاگرانژ براي حل مسائل بالاي 100 گره استفاده می کند را بررسی کردند. در هورهامر - 2014 - ، مسئله مکان یابی هاب چند دوره اي با تخصیص تکی و ظرفیت چندگانه مورد بررسی قرار گرفت. در این مقاله چندین مدل برنامه ریزي عدد صحیح مختلط پیشنهاد شد و در نهایت این مدل ها با هم مقایسه شدند. .[19] گلاره و همکاران - 2015 - ، مدل ریاضی مسئله مکان یابی هاب چند دوره اي با تخصیص چندگانه و ظرفیت بودجه را ارائه دادند. مدل پیشنهادي ویژگی هاي زیادي از آنچه در عمل در حمل و نقل دریایی و زمینی وجود دارد را شامل می شد. در این مقاله همچنین الگوریتم فراابتکاري که جواب هاي با کیفیت بالا در مدت زمان منطقی و معمول ارائه می داد، پیشنهاد شد. .[5]
