بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
طراحی مدل مکان یابی هاب با تخصیص چند گانه قابل اطمینان
چکیده
حوزه ی مکان یابی از جمله مواردی است که می تواند باعث افزایش کارآیی و صرفه جویی در منابع و نیروی انسانی گردد. یکی از مباحث جدیدی که در حوزه مکان یابی در سالهای اخیر مطرح شده ، مسأله مکان یابی هاب است . این مبحث به جهت کاربرد های وسیع از جمله مسافرت های هوایی ، خدمات پستی ، سیستم توزیع ، صنعت حمل و نقل و شبکه های کامپیوتری از اهمیت زیادی برخوردار شده است و این به دلیل بروز اتفاقات و عوامل غیر منتظره ای بوده که منجر به هزینههای عملیاتی سنگینی برای سیستم طراحی شده میگردد.
بنابراین یکی از عوامل کلیدی که میتواند تأثیر قابل توجهی بر افزایش هزینههای عملیاتی پس از طراحی و استقرار یک سیستم بگذارد مبحث قابلیت اطمینان می باشد، که تعریف آن عبارت است از احتمال اینکه سیستم مأموریت خود را بصورت رضایت بخشی برای یک دوره زمانی مشخص ودر شرایط کاری معین انجام دهد.
هدف از این مفاله ، بهینه سازی قابلیت اطمینان سیستم بر مبنای مکان یابی هاب و کاهش توقف سیستم با استفاده از هاب پشتیبان می باشد . ازاینرو مدلی به منظور مکان یابی هاب ها و تخصیص گره ها به هاب ها در جهت افزایش قابلیت اطمینان ارائه شده است ، بدین صورت که مسیرهای قابل اطمینان شناسایی می شوند و در صورتی که مسیرهایی قابل استفاده نباشند از هاب پشتیبان استفاده می شود. این مدل پیشنهادی تحت قالب یک مسئله با داده های فرضی و با استفاده از نرم افراز lingo حل میگردد.
واژگان کلیدی
مکانیابی، مکان یابی هاب، هاب پشتیبان، قابلیت اطمینان، مدل بهینه سازی
-1 مقدمه
یکی از مباحث جدیدی که در حوزه مسائل مکان یابی مطرح شده ، مسأله مکان یابی هاب1 است . این مبحث به جهت کاربرد های وسیع از جمله مسافرت های هوایی ، خدمات پستی ،توزیع و ارسال سفارشی ، صنعت حمل و نقل باربری ، شبکه های فیبر نوری و شبکه های کامپیوتری از اهمیت زیادی برخوردار است . (Alumur, Kara, 2008)
در این سیستم ها محصولات ( اعم از مخابره اطلاعات ، جابه جایی مسافر ،مرسولات پستی و ... ) از چندین مبدا به مقاصد متعددی ارسال می گردند. عملکرد این سیستم ها می تواند با استفاده از نقاط هاب بهبود یابد. بدین صورت که با تمرکز جریان ها در هاب هزینه توزیع کاهش می یابد. محصولات در هاب ها جمع آوری، طبقه بندی و توزیع می شوند. به جای ارتباط مستقیم بین هر مبدا و مقصد، جریان ها از یک مبدا با مقاصد متفاوت در یک هاب جمع می شوند و با جریان هایی که دارای مقصد یکسان هستند و از مبدا های دیگری رسیده اند، ترکیب شده و ارسال می گردند.( (Tan, Kara, 2007
تخصیص گره ها دارای دو حالت تکی2 و چندگانه3 است . در تخصیص یگانه، هر گره دقیقا به یک هاب تخصیص می یابد . در چندگانه جریان های خروجی و ورودی به گره مورد نظر می تواند از چند هاب مختلف تامین گردد (Campbell, 1994). طراحی شبکه های دارای قابلیت اطمینان 4 بیشتر، در سیستمهای هاب موضوعی حیاتی است،زیرا شبکههایی که این موضوع را در نظر نمیگیرند، کاملا آسیب پذیر هستند. در بررسی امکانات و قابلیت های یک سیستم، باید "احتمال" کارکرد موفقیت آمیز و بدون اشکال آن را ارزیابی نمود.((Kim, O'Kelly, 2009 مکان یابی هاب دارای قدمت کوتاهی است و جزء علوم نوین مکان یابی شمار می آید، پاره ای از مطالعات صورت گرفته در این زمینه به شرح زیر می باشد:
مسائل هاب در ابتدا توسط اوکلی(1986) 5 مطرح شد . و ی مدلی بر روی مجموعه ای از داده های گرفته شده در مرود پرواز های هوایی صورت گرفته بین هر جفت از 25 شهر اصلی ایالات متحده را پیاده سازی کرد اوکلی در سال 1987 مسئله مکان یابی Pهاب با تخصیص یگانه را بیان کرد که در آن P عدد هاب وجود داشت و هر گره غیر هاب فقط به یک گره هاب تخصیص داده می شد. تابع هدف حداقل کردن مجموع هزینه ها بود. هیچ گره غیر هابی به گره غیر هاب دیگر متصل نمی شد و ظرفیت نامحدود و هزینه تاسیس هاب نیز در نظر گرفته نشده بود.
کمبل6 در سال 1991 مساله مکان یابی هاب با تخصیص چندگانه را بیان کرد. وی مدلش را مانند مساله P میانه فرموله کرد و آن را مدل مکان یابی میانه P هاب نامید. در این مساله هر گروه غیره هاب می تواند به بیش از یک گره هاب تخصیص داده شود . تابع هدف آن مینیمم کردن هزینه سفر بین نقاط بود.
ماریانو و سرا7 در سال 2003 الگوریتم جستجو ممنوع را در مکان یابی خطوط هوایی با این فرض به کار بردند که هر گره گره هاب یک صف M/D/C می باشد. در این روش تنها یک بخش از حل موجه بررسی شد. این روش برای شیکه هایی با بیش از 50 گره و 4 الی 5 هاب بسیار مناسب می باشد.
کیم1 و اوکلی (2009) مسئله مکانیابی هاب دارای حداکثر قابلیت اطمینان را ارائه دادند که برای اولین بار مفهوم قابلیت اطمینان را در مکانیابی هاب بیان کردند. مدل مطرح شده دارای هدف ماکزیمم کردن قابلیت اطمینان بود.
داوری و همکاران (2010) با در نظر گرفتن مفهوم فازی برای قابلیت اطمینان، مدلی را با توجه به هدف ماکزیمم کردن قابلیت اطمینان پیشنهاد دادند. کریمی و بشیری در سال 2011 مسئله مکان یابی هاب با در نظر گرفتن پوشش قابلیت اطمینان را ارائه دادند که در این مدل کارایی شبکه از نظر قابلیت اطمینان در کل جریانهای مبدا-مقصد از یک مقداری کمتر نمی شد.
در مطالعه حاضر، مدل کیم و اوکلی ( (2009 توسعه داده شده و برای جلوگیری از توقف جریان در شبکه هاب از هاب پشتیبان استفاده می شود و هر کدام از گره ها به هاب ها به گونه ای تخصیص می یابند که قابلیت اطمینان بیشینه شود.
در ادامه روش شناسی تحقیق و داده ها ارائه می شوند، سپس بحث و یافته های تحقیق آورده می شوند ودر انتها نتیجه گیری می شود.
-2 داده ها و روش شناسی
این مقاله از نظر هدف از نوع توسعه ای کاربردی میباشد و از لحاظ گردآوری از نوع پیمایشی میباشد.باتوجه به موضوع و روش حل،ماهیت داده ها کمی میباشدو از نظر خصوصیات موضوع و مساله از نوع مقایسه ای میباشد.
-1-2مدل پایه ی مکان یابی هاب بر مبنای قابلیت اطمینان مسیرها
کیم و اوکلی (2009) این مدل را برای بیشینه کردن قابلیت اطمینان ارائه کردند. آنها در این مدل به قابلیت اطمینان مسیرها توجه نمودند. تابع هدف و محدودیت های این مدل به صورت زیر می باشند:
در این مدل میزان جریان موجود بین گره های i , j می باشد و کسری از جریان بین i و j است که از طریق هاب های k و m می گذرد . میزان قابلیت اطمینان در مسیر های می باشد . که از رابطه زیر به دست می آید :
ضریب یا فاکتور تخفیف می باشد و باعث می شود قابلیت اطمینان مسیر بین دو هاب بیشتر از قابلیت اطمینان مسیر بین یک هاب و غیر هاب گردد .
محدودیت اول نشان دهنده این است که تعداد هاب ها p عدد باشد . محدودیت دوم نشان دهنده این است که همه جریان بین i , j باید از طریق هاب های k, m بگذرد که k می تواند برابر m باشد . محدودیت سوم و چهارم بیان می کنند که قبل از این جریان از i به j برود باید در مکان های k و m هاب داشته باشیم . محدودیت پنجم نشان دهنده برنامه ریزی صفر و یک مسئله است و محدودیت آخر کسری از جریان بین i و j از طریق هاب هایm و k را نشان می دهد .
-2-2 مدل پیشنهادی
در این مدل علاوه بر بیشینه کردن قابلیت اطمینان، جلوگیری از توقف سیستم هم در نظر گرفته شده و با در نظر گرفتن هاب های پشتیبان میتوان مانع از توقف سیستم شد که این مسئله باعث افزایش قابلیت اطمینان سیستم می شود.
مشخصههای ساختاری این مدل ریاضی برابر است با:
-1-2-2 پارامتر ها
-2-2-2 فرضیات
· خرابی مسیرها مستقل از یکدیگر می باشد.
· میزان جریان بین هر دو گره یکسان می باشد
· خرابیهای به وجود آمده در سیستم قابل بررسی و رفع میباشند.
· در حالتی که سیستم سالم است جریان بینj, i از طریق هاب های m, k صورت می گیرد( m, k می توانند برابر باشند یعنی در یک مسیر، به جای یک هاب دو هاب وجود داشته باشد) و در هنگام خرابی از هاب پشتیبانs استفاده می شود .
-3-2-2 متغیرهای تصمیم
-4-2-2 تابع هدف و محدویت های آن
این تابع هدف بیان می کند که هاب ها باید به صورتی در نقاط کاندیدا مکان یابی شوند که قابلیت اطمینان سیستم بیشینه گردد. هدف از بهینه یابی قابلیت اطمینان، افزایش احتمال کارکرد سیستم و کاهش خرابی ها می باشد.
