1
مسائل مکانیابی هاب: مروری بر مدلها ، طبقه بندی، تکنیک های حل و کاربردها
استاد:
دانشجو:
درس:
طراحی سیستم های صنعتی
شماره دانشجویی:
2
3
هاب چیست؟
هاب ها تسهیلاتی هستند که به عنوان ادغام و یکپارچگی، اتصال، و نقاط تعویض برای جریان بین مبداها و مقاصد است.
4
هاب ها برای کاهش حمل و نقل بین گره های مبدا و مقصد به کار گرفته می شود.
5
یک شبکه کاملا متصل با k تا گره و بدون هیچ گره ی هاب، دارای
k(k-1) راه ارتباطی مبدا-مقصد است.
اگر یک گره هاب باشد، تنها 2(k-1)
راه ارتباطی مبدا-مقصد است.
Non-hub
یا
Spoke
multi-hub network : یک شبکه با بیش از یک هاب
با استفاده کمتر از منابع، جفت تقاضاها با یک شبکه هاب (network hub) نسبت به یک ساختار کاملا متصل به طور موثرتری خدمت داده می شوند.
6
هزینه ی یک شبکه هاب به ساختار آن بستگی دارد. فاصله کل کمان هایی که شبکه را متصل می کند ممکن است در شبکه هاب کمتر باشد، اما کل فاصله سفر ممکن است بیشتر باشد.
7
صنعت مخابرات در اصل یکی از قدیمی ترین کاربران مفهوم network hub باشد. با این وجود سیستم های لجستیکی، صنعت هواپیمایی و شرکت های پستی از کاربران اصلی این مفهوم باشند.
8
9
حکیمی (1964): اولین مقاله در زمینه بهینه سازی node ها منتشر کرد که انگیزه ای برای HLP بود.
Toh و Higgins (1985): درباره کاربرد مکانیابی شبکه هاب در صنعت هواپیمایی و خطوط هوایی به عنوان اولین تحقیق بحث کردند.
(1986a, 1986b) O’Kelly :اولین مقاله در زمینه HLP ، اولین فرمول های ریاضی و روش های حل را ارائه کرد.
Campbell ، Klincewiz ، Aykin ، Miller ، Kara ، Alumur ، Krishnamoorthy ، Ernst
10
بخش دوم : مدل های ریاضی
تعاریف اولیه و طبقه بندی
مدل ها
11
Solution domain (دامنه حل): شبکه (دامنه کاندید گره های هاب همه گره های شبکه است)، گسسته (دامنه کاندید گره های هاب یک سری از گرههای خاص است) و پیوسته (دامنه کاندید گره های هاب یک صفحه یا کُره است).
تعاریف اولیه
Criterion (معیار):Mini-Max(حداکثر هزینه حمل و نقل ازگره مبدا به گره مقصد حداقل شود) وMini-Sum (کل هزینه های متحمل شده توسط مکانیابی گره هاب و تخصیص گره هایnon-hub به گره های هاب حداقل شود).
تعیین تعداد هاب هایی که مستقر می شوند: (exogenous) برونی (تعداد هاب هایی که مکانیابی می شوند در درجه اول مشخص شده) و(endogenous) درونی (تعداد هاب هایی که مکانیابی می شوند از قبل مشخص نشده است.)
تعداد گره های هاب:single hub و multiple hubs
ظرفیت هاب: uncapacitated (نامحدود) و capacitated (محدود).
هزینه استقرار گره های هاب: بدون هزینه، هزینه های ثابت، و هزینه متغیر.
اختصاص یک گره non-hub به گره های هاب : به یک هاب (تک تخصیص) و به بیش از یک هاب (چند تخصیص).
هزینه اتصال گره های non-hub به گره های هاب: بدون هزینه، هزینه های ثابت، و هزینه متغیر.
12
مدل 1 : Single-HLP
معیار Mini-Sum
دامنه حل network
گره non-hub به گره هاب متصل است.
تعداد گره های هاب برای استقرار اگزوژن و برابر است با یک.
هیچ هزینه ای برای ایجاد هاب وجود ندارد.
هاب مستقر ظرفیت نامحدود دارد.
مسئله تک تخصیص است و تنها یک هاب مستقر می شود.
13
ورودی های مسئله
: hij مقدار جریان بین گره i و j
:Cij هزینه واحد انتقال از گره non-hub iبه گره هاب j است.
خروجی مدل binary (0 و 1) هست.
Yij برابر با 1 است اگر گره i به هاب مستقر در گرهj تخصیص داده شود.
14
15
معادله (1) : کل هزینه انتقال از طریق هاب را به حداقل می رساند.
معادله (2) : تنها یک هاب وجود دارد.
معادله (3) : گرهi تنها می تواند به یک گره هاب درJ مرتبط شود.
تابع هدف خطی
16
Oi : کل جریان خروجی از گره i است.
Di : کل جریان ورودی به گره i است.
مدل 2 : p-HLP
معیار Mini-Sum
دامنه حل network
هر گره non-hub فقط به یک گره هاب متصل می شود.
تعداد گره های هاب برای استقرار اگزوژن و برابر است با p.
هیچ هزینه ای برای ایجاد هاب وجود ندارد.
هاب ها ظرفیت نامحدود دارند.
مسئله تک تخصیص است و تنها به یک هاب تخصیص داده می شود.
حداقل یک یا حداکثر دو هاب برای سفر بین دو گرهnon-hub صرف شود
خروجی مدل binary (0 و 1) هست.
α یک عامل تخفیف دال بر اقتصاد مقیاس برای انتقال بین گره های هاب است (1≥ α ≥0) .
17
18
مدل 3 : Multi-objective p-HLP
هدف اول به حداقل رساندن هزینه کل حمل و نقل، و هدف دوم به حداقل رساندن بیشترین زمانی که گره هاب برای پردازش جریان صرف می کند .
هر گره non-hub فقط به یک گره هاب تخصیص می یابد.
معیار Mini-Sum و Mini-Max است.
دامنه حل شبکه است.
گره های هاب به طور کامل در ارتباط با یکدیگرند.
هر گره non-hub به یک single هاب متصل است.
تعداد هاب برای استقرار اگزوژن (برون زا) است.
حداقل یک یا حداکثر دو گره هاب باید برای سفر بین دو گره non-hub صرف شود.
هزینه های شروع خدمت در گره هاب در نظر گرفته نمی شود.
هاب ها نامحدود uncapacitated هستند.
متغیرهای تصمیم گیری باینری می باشند.
ورودی و خروجی های های مسئله مشابه p-HLP می باشد.
Tk زمانی است که گره هاب k طول می کشد تا یک واحد از جریان را پردازش کند.
19
معادله (27) شامل هزینه های کل حمل و نقل در شبکه هاب می باشد. معادله (28) حداکثر زمان سرویس که گره هاب k طول می کشد جریان های ورودی و خروجی را پردازش کند حداقل می کند.
مدل 4 : hub set covering location problem
مسائل مکانیابی hub set covering بسط خاصی از مسائل مکانیابی hub covering است که شبیه p-hub median با استثنائاتی فرموله می شود.
تعداد گره های هاب برای استقرار معلوم نیست، از این رو، هزینه های ثابت ایجاد هاب در نظر گرفته شده است.
ورودی مسئله: Fk، هزینه ثابت ایجاد هاب در گره k؛ Ckmij ،هزینه انتقال از گره مبدا i به گره مقصد j از طریق هاب واقع در گره k و m؛ Cij، حداکثر هزینه برای پوشش لینک اتصال گره های تقاضا i به j ، و Vkm ij برابر است با یک اگر هاب واقع در گره k و m بتواند جفت تقاضا (i, j) را پوشش دهد.
خروجی مدل شبیه p-hub median می باشد.
21
کل هزینه ایجاد هاب جدید توسط معادله (41) به حداقل می رسد. معادله (42) تصریح می کند که هر جفت تقاضا حداقل یک بار توسط یک جفت هاب پوشش داده شده است.
22
23
بخش سوم : روش های حل و الگوریتم های HLPs
Notations for different type of HLPs
الگوریتم های دقیق در HLPs
بسیاری از مقالات تا به امروز در حوزه HLPs به صورت نامحدود در نظر گرفته شده اند و تمام مقالات با ظرفیت محدود در سال های اخیر منتشر شده است. این نشان می دهد که حل HLPs محدود توسط الگوریتم های حل دقیق به تازگی توجه بیشتری در میان محققان به خود جلب کرده است.
24
25
Exact solution algorithms in HLPs
الگوریتم های ابتکاری و فرا ابتکاری در HLPs
حتی اگر روش بهینه سازی برنامه ریزی عدد صحیح برای حل مسائل کوچک HLP به کار رود، موارد بزرگتر HLPs نیاز به روش های ابتکاری و یا روش های فرا ابتکاری برای حل دارند.
واقعیت این است که، با کمک الگوریتم های فرا ابتکاری به حل بهینه یا نزدیک به بهینه در زمان محاسباتی کمتری می توان دست یافت.
26
Heuristic and meta-heuristic solution algorithms in HLP:
Nearest distance heuristic
branch and bound
Tabu search (with greedy algorithm)
Ant colony optimization (ACO)
Location–allocation (shortest route)
Heuristic algorithms
…..
27
بخش چهارم : کاربردها و مطالعات موردی در زندگی واقعی
بیشترین زمینه های کاربردHLP در خطوط هوایی و صنعت فرودگاه و سیستم های حمل و نقل می باشد. تفاوت بین این دو ناحیه این است که اولی در درجه اول در ادبیات استفاده می شود، اما دومی در 5 سال اخیر توجه بیشتری به خود جلب کرده است
28
29
Airlines and airport industries
Airport hubs – tourism/ Brazil
Emergency services
Post delivery services and rapid delivery packing systems
Postal services / Turkey
Supply chain management – logistics
Freight transport / Hong Kong
Telecommunication services and messag delivery networks
Transportation systems
Truck transportation / North America
Applications for HLP (real case)
بخش پنجم: نتیجه گیری و روند آینده
شکاف در HLP
در مکانیابی هاب، معیار مدل های ارائه شده معمولا با هزینه سروکار دارد. در واقع، هیچ تحقیقاتی بر عوامل موثر بر جریان بین گره های non-hub و گره های هاب وجود ندارد. این مهم است که هیچ تضمینی وجود ندارد که یک اتصال non-hub / hub ترافیک بیشتری نسبت به برخی از لینک های هاب ندارد.
در برخی از کاربردهای HLP مانند خطوط هوایی بین المللی، سیستم تحویل سریع و سایر توزیع های جهانی و سیستم های ارتباطی ،امکانات موجود فرض می شوند یک منطقه خدماتی نسبتا گسترده ای را پوشش می دهند. از این رو، با شبکه و مفروضات گسسته ی دامنه حل قابل اجرا نیستند. هیچ مطالعه ای در زمینه HLP پیوسته در سال های اخیر وجود ندارد.
30
شکاف در HLP
مکانیابی هاب با MCDM به طور گسترده در مطالعات قبلی در نظر گرفته نشده است. بسیاری از ادبیات فعلی بر به حداکثر رساندن سود و یا به حداقل رساندن هزینه معیاری به عنوان توابع هدف سنتی متمرکز شده اند. با این حال، در برخی از کاربردها مانند صنایع هواپیمایی، ما با دیگر توابع هدف مانند حداکثر کردن سهم بازار سروکار داریم. با در نظر گرفتن اهداف متضاد بیشتر، مشکلات بیشتر در دنیای واقعی می تواند موثر تر مورد تجزیه و تحلیل قرار گیرند.
31
روند آینده HLP
درنظر گرفتن مسائل مکانیابی تجهیزات با قابلیت اطمینان به منظور مقاومت در برابر بلایای پیش بینی نشده (بلایای ساخته دست انسان و یا طبیعی) یک روند جدید است. این موضوع می تواند با توجه به بلایای ممکن و اختلال در هاب و یا در spoke ها در HLP اعمال شود.
مدل سازی پایدار و توجه خاص به اثرات اجتماعی و زیست محیطی علاوه بر جنبه های اقتصادی کلاسیک از HLP می تواند یک منطقه تحقیقی قابل اجرا باشد. کاربرد این گونه مسائل در کار کردن با مواد خطرناک و آلودگی سیستم های لجستیکی (هوا، زمین، دریایی و لجستیک شهری) مشهود است. با این حال، یک چالش عمده در این زمینه، کمی کردن اثرات اجتماعی و زیست محیطی در مدل هاست.
32
روند آینده HLP
برخی از فرمول های جدید و تکنیک های حل آنها مربوط به مسائل دنیای واقعی نیست و فرمول ها قابل اجرا نیستند. به عنوان مثال، مکانیابی هاب پویا به دنیای واقعی نزدیک تر است و مطالعات مختلف پس از چند سال نشان می دهد که، هاب مستقر با توجه به تغییرات مختلف داده های اولیه در طول زمان در مکان بهینه نیست.
بسیاری از مدل های مورد استفاده در ادبیات HLPs پارامترهای قطعی در نظر گرفتند ، در حالی که پارامترهای احتمالی و نامشخص واقعی ترند. در واقع، بسیاری از ویژگی های HLPs مانند تقاضا و هزینه های راه اندازی هاب ها دارای عدم قطعیت ذاتی در کاربرد دنیای واقعی هستند.
33
با تشکر از توجه شما
خسته نباشید