چکیده:در این پایاننامه موضوع مکانیابی آرکهاب با سطوح ظرفیت چندگانه و دو نوع تخصیص یگانه و چندگانه مورد بررسی قرار میگیرد. بررسی مکانیابی آرکهاب در ادبیات موضوع مکانیابی هاب نشان از نبود این سازوکار در ادبیات مکانیابی هاب دارد. در این تحقیق ابتدا به مسئله حمل و نقل و تاثیر آن بر اقتصاد کشور و نقش آن در تولید ناخالص ملی پرداخته شده و پس از آن مدل مکانیابی آرکهاب ارائه میشود. برای مدلسازی مسئله مکانیابی آرکهاب با تخصیص یگانه و چندگانه و سطوح ظرفیت چندگانه فرض دوم از مسئله مکانیابی هاب آزاد سازی میشود و مدل ریاضی بر مبنای فرض های جدید ساخته میشود. پس از آن مدل در نرم افزار گمس نوشته شده و با حل کننده cplex حل میشود. اطلاعات مورد استفاده در این تحقیق دادههای پست استرالیا میباشد. پس از حل این مسئله توسط گمس، الگوریتم ژنتیکی برای حل این مدل ارائه میشود که در آن از سه سطح تصمیم گیری استفاده شده است. در انتها نیز جوابها ارائه شده و مقایسه بین حل با نرم افزار و حل فرا ابتکاری صورت میگیرد. کلمات کلیدی: مکانیابی-مکانیابی هاب- مکانیابی آرکهاب- الگوریتم ژنتیک فهرستمطالبفصل اول – مقدمه و کلیات تحقیق1-1 مقدمه:21-2 مکانیابی هاب و آرکهاب21-2-1 مکانیابی آرکهاب51-3 الگوریتم ژنتیک61-3-3 ساختار الگوریتم ژنتیک131-4 مسئله تحقیق و ضرورت آن141-5 روش تحقیق151-6 ساختار گزارش پایاننامه151-7 نتیجهگیری16فصل دوم - ادبیات و پیشینه تحقیق2-1مقدمه182-2 اهمیت حمل و نقل182-3 جایگاه حمل و نقل و بررسی نقش آن در اقتصاد کشورها192-4 آثار عمده اقتصادی حمل و نقل202-4-1 ارزش افزوده بخش حمل و نقل212-4-2 سرمایه ثابت ناخالص در بخش حمل و نقل222-5 اشتغالزایی بخش حمل و نقل232-5-1 زیر بخش جادهای242-5-2 زیر بخش ریلی252-5-3 زیربخش هوایی252-5-4 زیربخشهای دریایی252-6 اهمیت حمل و نقل در جهت توسعه تجارت جهانی252-7 مدلسازی مسائل هاب272-8 مدلسازی مسائل آرکهاب282-9 نتیجهگیری28فصل سوم - روش تحقیق3-1 مقدمه303-2 مدلهای مکانیابی هاب303-3 مدلهای مکانیابی آرکهاب323-4 مدلسازی353-4-1 مدلهای هاب میانه353-4-2 مدلهای مکانیابی آرکهاب373-5 نتیجهگیری40فصل چهارم - مخاسبات و یافته های تحقیق4-1 مقدمه:424-2 مدل مکانیابی آرکهاب با تخصیص یگانه:42مفروضات:424-3 مدل مکانیابی آرکهاب با تخصیص چندگانه474-4 روش حل پیشنهادی مسئله مکانیابی آرکهاب با تخصیص یگانه524-4-1 نمایش جواب524-4-2 ایجاد جمعیت اولیه:534-4-3 استراتژی جریمه534-4-4 استراتژی انتخاب:544-4-5 استراتژی نخبه544-4-6 تابع برازش544-4-7 عملگر تقاطع544-4-8 عملگر جهش554-4-9 تنظیم پارامترها با روش تاگوچی554-5-7 عملگر تقاطع584-5-9 تنظیم پارامترها با روش تاگوچی594-6 نتایج بدست آمده برای مسئله مکانیابی آرکهابو مشخصات کامپیوتر مورد استفاده604-6 گزارش حل مسئله مکانیابی آرکهاب با تخصیص یگانه:634-7 نتیجه گیری68فصل پنجم - نتیجه گیری و پیشنهادات5-1 نتیجهگیری705-2 تحقیقات آتی و پیشنهادات71منابع و مأخذ72 فهرست جداول:جدول شماره 1 اثر تغییر خدمات حمل و نقل بر شاخص هزینه زندگی.................................................................... 21جدول شماره 2 ارزش افزودهبخشهای حمل و نقل و کل کشور.... 22جدول شماره 3 سهم اعتبارهای عمرانی بخش حمل و نقل از ک سرمایهگذاریهای عمرانی کشور (2)....................................... 23.جدول شماره 4 میزان اشتغال در بخش حمل و نقل، ارتباطات و انبارداری طی سالهای 75-1345......................................... 24جدول شماره 5 سطوح مورد استفاده در فرایند تاگوچی............................................................................................. 56جدول شماره 6 پارامترهای بهینه................................................................................................................................. 56جدول شماره 7 حل مسئله مکانیابی آرکهاب با تخصیص چندگانه..........................................................................59جدول شماره 8 حل مسئله مکانیابی آرکهاب با تخصیص یگانه با نرم افزار GAMS و مقایسه با حل با الگوریتم ژنتیک تنظیم شده........................................................................................................................................................ 60جدول شماره 9 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک.................... 61جدول شماره 10 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک................... 63جدول شماره 11 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک....................64جدول شماره 12 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک ...................65 (5آرکهاب)جدول شماره 13 حل مسئله مکانیابی آرکهاب با تخصیص چندگانه و مقایسه با الگوریتم ژنتیک.............................66فهرست تصاویر و نمودار:شکل شماره 1. شکل نمونه از توپولوژی هاب .............. ...4شکل شماره 2. حل مسئله مکانیابی10 هاب میانه که از دادههای CAB و ضریب 4/0 استفاده شده است ...............33شکل شماره 3. حل مسئله آرکهاب با 10 گره و ضریت تخفیف 4/0 و داده های CAB .......................................34 فصل اولمقدمه و کلیات مسئله 1-1 مقدمه:در این فصل به بررسی موضوع مورد تحقیق میپردازیم و به توضیح مدلی خاص از حمل و نقل در قالب مسئله مکانیابی هاب [1]میپردازیم، که اهمیتی بالقوه در ساختار شبکههای مخابراتی و حمل و نقلهای عظیم دارد. هابها نوعی خاص از تسهیلات هستند که به عنوان نقاط سوئیچ، مرتبسازی و انتقال در سیستمهای توزیع چند به چند فعالیت میکنند؛ پس از معرفی مسائل هاب و آرکهاب روش حل مورد نظر در این پایان نامه که در چارچوب الگوریتم ژنتیک است را بررسی کرده و در مورد آن توضیحاتی ارائه خواهد شد سپس به مسئله مورد تحقیق و ضرورت آن در ادبیات موضوع و روش تحقیق انجام گرفته، پرداخته میشود و در انتها نیز ساختار گزارش پایان نامه ارائه خواهد شد.هابها تسهیلات ویژهای هستندکه به عنوان نقاط تعویض،انتقال وطبقهبندی دربسیاری ازسیستمهای توزیع به کارگرفته میشوند. تسهیلات هاب به جای خدمترسانی هرجفت مبدأ-مقصد، جریانهارابه منظور استفاده ازصرفهجوییهای اقتصادی ناشی ازآن متمرکز مینمایند. جریانها ازمبدأ یکسان بامقصد های مختلف روی مسیرشان به یک هاب آرک شده و با جریانهایی که مبدأهای متفاوتی دارند امّا مقصدشان یکسان است ترکیب میشوند. یکیسازی برروی مسیر مبدأ تا هاب و از هاب تا مقصد و نیز بین هابها صورت میگیرد. تحقیقات راجع به مکانیابی هاب درطول دو دهه اخیر جایگاه مهمی در زمینه مکانیابی به خود اختصاص داده است، این امر در نتیجه استفاده فراوان از شبکههای هاب درحمل ونقل و ارتباطات مدرن بوده است.این سیستمها برای سفر یا ارتباطات بین خیلی از مبداها و مقاصد که در آنها هزینه این سفرها یا ارتباطات درمقیاس بزرگ مهم است، خدماتی ارائه میدهند. بجای ارتباط مستقیم بین هرمبدا-مقصد، شبکهی هاب با مجموعهی کوچکی از ارتباطها بین مبداها مقصدها و هاب و بین هرجفت ازهابها خدمت را ارائه میدهد. چنین شبکهای اجازه میدهد تا مجموعهی بزرگی ازمبادی و مقاصد با ارتباطات نسبتا کمتر، به یکدیگر مرتبط باشند. استفاده از ارتباطات کمتر اجازه میدهد تا جریان متمرکزتر شود و اجازه استفاده از مقیاس بزرگ به کار گرفته شود. مسئلهی مکانیابی هاب شامل مکانیابی تسهیلات هاب وطراحی شبکه هاب میباشد. مسئله مکانیابی هاب با مسائل مکانیابی کلاسیک در چند رویکرد اساسی فرق دارد. در مسئله مکانیابی تسهیلات گسسته کلاسیک، تقاضا برای خدمت درنقاط گسسته رخ میدهد، تسهیلات در نقاط گسسته استقرار داده شدهاند و تابع هدف عمدتا مربوط به فاصله یا هزینه بین تسهیلات و نقاط تقاضا میباشد. درمسائل مکانیابی هاب تقاضا با جریان بین چندین مبدا وچندین مقصد مشخص میشود، وتسهیلات هاب به عنوان نقاط ارتباط یا تمرکز، برای جریان بین مبدا ها و مقصدها هستند. یک هاب به عنوان نقطه ارتباط اجازه میدهد که جریان تغییر جهت دهد. بهعلاوه، یک هاب ممکن است کار تمرکز را برای ترکیب چندین جریان مجزای کوچک، برای مثال ازچندین مبدا، به جریان بزرگتر را فراهم کند، همچنین هاب ها ممکن است عملکرد تکه تکه کردن جریان بزرگتر به چندین جریان کوچکتر برای مقاصد مختلف را انجام دهند. بنابراین هابها نقاط میانی در امتداد جریان بین مبدا- مقصد هستند. (زمانیکه هاب متناظر با یک مبدا/مقصد برای جریانی خاص باشند، به عنوان نقطهی پایانی جریان میباشد). کاربردهای مدلهای مکانیابی هاب درحمل ونقل شامل حمل هوایی مسافران، حمل هوایی مواد یا بار، ارسال سریع (برای مثال سیستم تحویل یک شبه)، عملیات پستی وسیستم ترانزیت سریع میباشد، تقاضا معمولا با جریان مسافران یا کالاهای بین جفتی از شهرها مشخص میشود و این جریانها بوسیله وسایل نقلیهای ازقبیل هواپیما، وسایل نقلیهی موتوری، قطارها و غیره حمل میشود. تسهیلات هاب به عنوان ترمینالها یا مراکز سازمان دهنده حمل ونقل محسوب میشوند. محدودهی جغرافیایی مسئلهی مکانیابی تسهیلات هاب ممکن است محلی (به عنوان مثال برای یک شهر) یاجهانی باشد. مقیاس بزرگ حمل ونقل انجام شده ما را به متمرکزکردن جریان تشویق میکند.در مکانیابی تسهیلات به صورت مستقیم به نقاط مبدا و مقصد خدمت رسانی میکنند. تسهیلات هاب با متمرکز نمودن جریانهای بین مبادی و مقاصد شامل صرفههای اقتصادی حمل و نقل انبوه میگردد. این مسئله اولین بار در دهه 1980 ]11[ مطرح شده است. این مسئله به گونهایست که مکانیابی تسهیلات هاب تخصیص تقاط تقاضای شبکه به این تسهیلات هاب به نحوی است که ترافیک بین نقاط مبدا و مقصد با توجه به یک معیار عملکرد به صورت بهینه باشد ]8[. از جمله کاربردهای مسئله مکانیابی تسهیلات هاب میتوان به شبکههای پست و مخابرات و کامپیوتری اشاره کرد.مفروضات اصلی این مسئله که بر روی یک گراف تعریف میشود عبارتند از ]9[:1. کامل بودن گراف2. وجود صرفه اقتصادی یکپارچه سازی بین نقاط مبدا و مقصد3. عدم وجود خدمترسانی بین نقاط مبدا و مقصدتا کنون مدلهای ریاضی متنوعی برای مسائل هاب ارائه شده است که می توان به مکانیابی میانه P تسهیلاتی با تخصیص یگانه و چندگانه، مدل مکانیابی میانه تسهیل هاب با هزینه ثابت، مدل مکانیابی مرکز P تسهیل هاب با تخصیصهای یگانه و چندگانه و سر انجام مکانیابی پوشش تسهیلات هاب اشاره کرد. شکل شماره 1 شکل کلی مسئله مکانیابی هاب است که در آن نقاط خاکستری رنگ هاب بوده و نقاط سیاه رنگ نقاط مبدا و مقصد میباشند. شکل 1 شکل نمونه از توپولوژی هابفرض در مدل مکانیابی P تسهیل هاب با تخصیص یگانه این است که هر محموله قابل شکستن به محموله های کوچکتر نیست و باید توسط یک مسیر به مقصد برسد. در این مدل کمینه سازی هزینه (زمان یا هزینه) کل محموله ها است. در مدل مکانیابی P تسهیل هاب به صورت تخصیص چندگانه فرض بر این است که هر محموله قابل شکستن به محمولههای کوچکتر بوده و در نتیجه میتوان از چند مسیر برای رسیدن مقصد استفاده کرد.در حالت مکانیابی میانه تسهیلات با هزینه ثابت فرض میشود برای بازگشایی هر تسهیل هاب هزینه ثابتی به هزینه کل اضافه میشود؛ در این حالت تابع هدف برابر خواهد بود با کمینه سازی مجموع هزینه کل گشایش تسهیلات به اضافه هزینه حمل و نقل کالاها.برای مکانیابی مرکز P تسهیلاتی سه نوع تابع هدف می توان تعریف کرد1- کمینه سازی بیشترین هزینه برای هر جفت مسیر بین مبادی و مقاصد2- کمینه سازی بیشترین هزینه انتقال بر روی یک هاب، از مبدا به هاب، هاب به هاب و هاب به مقصد3- کمینه سازی بیشترین هزینه انتقال بر روی یک یال گذرنده از یک هاب به یک مبدا یا مقصد.توابع هدف مذکور به ترتیب در مسائل شبکههای حمل و نقل مواد زوال پذیر، شبکههای نیازمند تجهیزات خاص در تسهیلات هاب مانند تجهیزات سرمایشی، یا شبکههای با محدودیت زمان حمل و نقل و سرانجام شبکههای با خصوصیات ویژه برای یالهای انتقال هاب به هاب کاربرد دارند. مدل مکانیابی پوشش تسهیلات هاب به بررسی حالتی میپردازد که یک تقاضای انتقال محموله در صورت قرارگیری در شرایط مشخصی نسبت به یک تسهیل هاب، پوشش داده تلقی میشود. برای تحت پوشش قرار گرفتن یک نقطه تقاضا سه حالت میتوان متصور بود ]9[.1- هزینه انتقال هر یک از یالهای روی مسیر انتقال از مبدا به مقصد که حد اکثر از دو نسهیل هاب مشخص میگذرد از یک مقدار معین تجاوز ننماید.2- هزینه انتقال بر روی هر یک از یالهای مبدا-هاب و هاب مقصد از مقدار مشخصی تجاوز ننماید.همچنین میتوان برای مسئله مکانیابی تسهیلات هاب تابع هدف از نوع حداکثر پوشش نیز تعریف کرد.در مدل مکانیابی هاب یکی از اهداف حل مسئله این است که هابها کجا قرار دارند. در مسائل مکانیابی هاب یک ضریب تخفیف روی یالهایی که بین دو هاب هستند، تعریف میشود. این یال که همان آرکهاب است بین هر دو نقطه هاب در مدل P تسهیل هاب میانه وجود دارد. در مسئله P میانه فرض اصلی بر این است که شبکه گرههای هاب کامل است و تمام نقاط هاب دو به دو توسط آرکهابها بهم متصل هستند. لذا در این مدل مکان آرکهابها همزمان با مسئله انتخاب هابها حل میشود و مکان آرکهابها نیز مشخص میشود. مسئله انتخاب آرک کمبود قابل توجهی از مدل P هاب میانه را مورد بررسی قرار میدهد ]10[. مسائل هاب میانه عموما بعنوان یک مسئله مکانیابی شناخته میشوند. اما آنها را می توان بعنوان مسئله طراحی شبکه نیز به حساب آورد که شامل دو دسته مسائل طراحی شبکه هستند1.آرک هاب2. یال دسترسیمسئله آرکهابها در طراحی شبکه انتخاب آرکهابها است. با توجه به اینکه هابها کاملا با هم متصل هستند مکان آرک هابها را در مسئله مشخص میکنیم. طراحی یالهای دسترسی[2] انتخاب یالهای متصل کننده هابها به نقاط غیر هاب است.مسئله تخصیص یگانه مسئله بسیار مشکلی خواهد بود و جزو دسته مسائل Np-Hard میباشد ]10[. [1]Hub location[2]Access arc
مسئله انتخاب کمانهای هاب با تخصیص و سطوح ظرفیت چندگانهword
چکیده:در این پایاننامه موضوع مکانیابی آرکهاب با سطوح ظرفیت چندگانه و دو نوع تخصیص یگانه و چندگانه مورد بررسی قرار میگیرد. بررسی مکانیابی آرکهاب در ادبیات موضوع مکانیابی هاب نشان از نبود این سازوکار در ادبیات مکانیابی هاب دارد. در این تحقیق ابتدا به مسئله حمل و نقل و تاثیر آن بر اقتصاد کشور و نقش آن در تولید ناخالص ملی پرداخته شده و پس از آن مدل مکانیابی آرکهاب ارائه میشود. برای مدلسازی مسئله مکانیابی آرکهاب با تخصیص یگانه و چندگانه و سطوح ظرفیت چندگانه فرض دوم از مسئله مکانیابی هاب آزاد سازی میشود و مدل ریاضی بر مبنای فرض های جدید ساخته میشود. پس از آن مدل در نرم افزار گمس نوشته شده و با حل کننده cplex حل میشود. اطلاعات مورد استفاده در این تحقیق دادههای پست استرالیا میباشد. پس از حل این مسئله توسط گمس، الگوریتم ژنتیکی برای حل این مدل ارائه میشود که در آن از سه سطح تصمیم گیری استفاده شده است. در انتها نیز جوابها ارائه شده و مقایسه بین حل با نرم افزار و حل فرا ابتکاری صورت میگیرد. کلمات کلیدی: مکانیابی-مکانیابی هاب- مکانیابی آرکهاب- الگوریتم ژنتیک فهرستمطالبفصل اول – مقدمه و کلیات تحقیق1-1 مقدمه:21-2 مکانیابی هاب و آرکهاب21-2-1 مکانیابی آرکهاب51-3 الگوریتم ژنتیک61-3-3 ساختار الگوریتم ژنتیک131-4 مسئله تحقیق و ضرورت آن141-5 روش تحقیق151-6 ساختار گزارش پایاننامه151-7 نتیجهگیری16فصل دوم - ادبیات و پیشینه تحقیق2-1مقدمه182-2 اهمیت حمل و نقل182-3 جایگاه حمل و نقل و بررسی نقش آن در اقتصاد کشورها192-4 آثار عمده اقتصادی حمل و نقل202-4-1 ارزش افزوده بخش حمل و نقل212-4-2 سرمایه ثابت ناخالص در بخش حمل و نقل222-5 اشتغالزایی بخش حمل و نقل232-5-1 زیر بخش جادهای242-5-2 زیر بخش ریلی252-5-3 زیربخش هوایی252-5-4 زیربخشهای دریایی252-6 اهمیت حمل و نقل در جهت توسعه تجارت جهانی252-7 مدلسازی مسائل هاب272-8 مدلسازی مسائل آرکهاب282-9 نتیجهگیری28فصل سوم - روش تحقیق3-1 مقدمه303-2 مدلهای مکانیابی هاب303-3 مدلهای مکانیابی آرکهاب323-4 مدلسازی353-4-1 مدلهای هاب میانه353-4-2 مدلهای مکانیابی آرکهاب373-5 نتیجهگیری40فصل چهارم - مخاسبات و یافته های تحقیق4-1 مقدمه:424-2 مدل مکانیابی آرکهاب با تخصیص یگانه:42مفروضات:424-3 مدل مکانیابی آرکهاب با تخصیص چندگانه474-4 روش حل پیشنهادی مسئله مکانیابی آرکهاب با تخصیص یگانه524-4-1 نمایش جواب524-4-2 ایجاد جمعیت اولیه:534-4-3 استراتژی جریمه534-4-4 استراتژی انتخاب:544-4-5 استراتژی نخبه544-4-6 تابع برازش544-4-7 عملگر تقاطع544-4-8 عملگر جهش554-4-9 تنظیم پارامترها با روش تاگوچی554-5-7 عملگر تقاطع584-5-9 تنظیم پارامترها با روش تاگوچی594-6 نتایج بدست آمده برای مسئله مکانیابی آرکهابو مشخصات کامپیوتر مورد استفاده604-6 گزارش حل مسئله مکانیابی آرکهاب با تخصیص یگانه:634-7 نتیجه گیری68فصل پنجم - نتیجه گیری و پیشنهادات5-1 نتیجهگیری705-2 تحقیقات آتی و پیشنهادات71منابع و مأخذ72 فهرست جداول:جدول شماره 1 اثر تغییر خدمات حمل و نقل بر شاخص هزینه زندگی.................................................................... 21جدول شماره 2 ارزش افزودهبخشهای حمل و نقل و کل کشور.... 22جدول شماره 3 سهم اعتبارهای عمرانی بخش حمل و نقل از ک سرمایهگذاریهای عمرانی کشور (2)....................................... 23.جدول شماره 4 میزان اشتغال در بخش حمل و نقل، ارتباطات و انبارداری طی سالهای 75-1345......................................... 24جدول شماره 5 سطوح مورد استفاده در فرایند تاگوچی............................................................................................. 56جدول شماره 6 پارامترهای بهینه................................................................................................................................. 56جدول شماره 7 حل مسئله مکانیابی آرکهاب با تخصیص چندگانه..........................................................................59جدول شماره 8 حل مسئله مکانیابی آرکهاب با تخصیص یگانه با نرم افزار GAMS و مقایسه با حل با الگوریتم ژنتیک تنظیم شده........................................................................................................................................................ 60جدول شماره 9 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک.................... 61جدول شماره 10 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک................... 63جدول شماره 11 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک....................64جدول شماره 12 حل مسئله مکانیابی آرکهاب با نرم افزار GAMS و مقایسه با حل الگوریتم ژنتیک ...................65 (5آرکهاب)جدول شماره 13 حل مسئله مکانیابی آرکهاب با تخصیص چندگانه و مقایسه با الگوریتم ژنتیک.............................66فهرست تصاویر و نمودار:شکل شماره 1. شکل نمونه از توپولوژی هاب .............. ...4شکل شماره 2. حل مسئله مکانیابی10 هاب میانه که از دادههای CAB و ضریب 4/0 استفاده شده است ...............33شکل شماره 3. حل مسئله آرکهاب با 10 گره و ضریت تخفیف 4/0 و داده های CAB .......................................34 فصل اولمقدمه و کلیات مسئله 1-1 مقدمه:در این فصل به بررسی موضوع مورد تحقیق میپردازیم و به توضیح مدلی خاص از حمل و نقل در قالب مسئله مکانیابی هاب [1]میپردازیم، که اهمیتی بالقوه در ساختار شبکههای مخابراتی و حمل و نقلهای عظیم دارد. هابها نوعی خاص از تسهیلات هستند که به عنوان نقاط سوئیچ، مرتبسازی و انتقال در سیستمهای توزیع چند به چند فعالیت میکنند؛ پس از معرفی مسائل هاب و آرکهاب روش حل مورد نظر در این پایان نامه که در چارچوب الگوریتم ژنتیک است را بررسی کرده و در مورد آن توضیحاتی ارائه خواهد شد سپس به مسئله مورد تحقیق و ضرورت آن در ادبیات موضوع و روش تحقیق انجام گرفته، پرداخته میشود و در انتها نیز ساختار گزارش پایان نامه ارائه خواهد شد.هابها تسهیلات ویژهای هستندکه به عنوان نقاط تعویض،انتقال وطبقهبندی دربسیاری ازسیستمهای توزیع به کارگرفته میشوند. تسهیلات هاب به جای خدمترسانی هرجفت مبدأ-مقصد، جریانهارابه منظور استفاده ازصرفهجوییهای اقتصادی ناشی ازآن متمرکز مینمایند. جریانها ازمبدأ یکسان بامقصد های مختلف روی مسیرشان به یک هاب آرک شده و با جریانهایی که مبدأهای متفاوتی دارند امّا مقصدشان یکسان است ترکیب میشوند. یکیسازی برروی مسیر مبدأ تا هاب و از هاب تا مقصد و نیز بین هابها صورت میگیرد. تحقیقات راجع به مکانیابی هاب درطول دو دهه اخیر جایگاه مهمی در زمینه مکانیابی به خود اختصاص داده است، این امر در نتیجه استفاده فراوان از شبکههای هاب درحمل ونقل و ارتباطات مدرن بوده است.این سیستمها برای سفر یا ارتباطات بین خیلی از مبداها و مقاصد که در آنها هزینه این سفرها یا ارتباطات درمقیاس بزرگ مهم است، خدماتی ارائه میدهند. بجای ارتباط مستقیم بین هرمبدا-مقصد، شبکهی هاب با مجموعهی کوچکی از ارتباطها بین مبداها مقصدها و هاب و بین هرجفت ازهابها خدمت را ارائه میدهد. چنین شبکهای اجازه میدهد تا مجموعهی بزرگی ازمبادی و مقاصد با ارتباطات نسبتا کمتر، به یکدیگر مرتبط باشند. استفاده از ارتباطات کمتر اجازه میدهد تا جریان متمرکزتر شود و اجازه استفاده از مقیاس بزرگ به کار گرفته شود. مسئلهی مکانیابی هاب شامل مکانیابی تسهیلات هاب وطراحی شبکه هاب میباشد. مسئله مکانیابی هاب با مسائل مکانیابی کلاسیک در چند رویکرد اساسی فرق دارد. در مسئله مکانیابی تسهیلات گسسته کلاسیک، تقاضا برای خدمت درنقاط گسسته رخ میدهد، تسهیلات در نقاط گسسته استقرار داده شدهاند و تابع هدف عمدتا مربوط به فاصله یا هزینه بین تسهیلات و نقاط تقاضا میباشد. درمسائل مکانیابی هاب تقاضا با جریان بین چندین مبدا وچندین مقصد مشخص میشود، وتسهیلات هاب به عنوان نقاط ارتباط یا تمرکز، برای جریان بین مبدا ها و مقصدها هستند. یک هاب به عنوان نقطه ارتباط اجازه میدهد که جریان تغییر جهت دهد. بهعلاوه، یک هاب ممکن است کار تمرکز را برای ترکیب چندین جریان مجزای کوچک، برای مثال ازچندین مبدا، به جریان بزرگتر را فراهم کند، همچنین هاب ها ممکن است عملکرد تکه تکه کردن جریان بزرگتر به چندین جریان کوچکتر برای مقاصد مختلف را انجام دهند. بنابراین هابها نقاط میانی در امتداد جریان بین مبدا- مقصد هستند. (زمانیکه هاب متناظر با یک مبدا/مقصد برای جریانی خاص باشند، به عنوان نقطهی پایانی جریان میباشد). کاربردهای مدلهای مکانیابی هاب درحمل ونقل شامل حمل هوایی مسافران، حمل هوایی مواد یا بار، ارسال سریع (برای مثال سیستم تحویل یک شبه)، عملیات پستی وسیستم ترانزیت سریع میباشد، تقاضا معمولا با جریان مسافران یا کالاهای بین جفتی از شهرها مشخص میشود و این جریانها بوسیله وسایل نقلیهای ازقبیل هواپیما، وسایل نقلیهی موتوری، قطارها و غیره حمل میشود. تسهیلات هاب به عنوان ترمینالها یا مراکز سازمان دهنده حمل ونقل محسوب میشوند. محدودهی جغرافیایی مسئلهی مکانیابی تسهیلات هاب ممکن است محلی (به عنوان مثال برای یک شهر) یاجهانی باشد. مقیاس بزرگ حمل ونقل انجام شده ما را به متمرکزکردن جریان تشویق میکند.در مکانیابی تسهیلات به صورت مستقیم به نقاط مبدا و مقصد خدمت رسانی میکنند. تسهیلات هاب با متمرکز نمودن جریانهای بین مبادی و مقاصد شامل صرفههای اقتصادی حمل و نقل انبوه میگردد. این مسئله اولین بار در دهه 1980 ]11[ مطرح شده است. این مسئله به گونهایست که مکانیابی تسهیلات هاب تخصیص تقاط تقاضای شبکه به این تسهیلات هاب به نحوی است که ترافیک بین نقاط مبدا و مقصد با توجه به یک معیار عملکرد به صورت بهینه باشد ]8[. از جمله کاربردهای مسئله مکانیابی تسهیلات هاب میتوان به شبکههای پست و مخابرات و کامپیوتری اشاره کرد.مفروضات اصلی این مسئله که بر روی یک گراف تعریف میشود عبارتند از ]9[:1. کامل بودن گراف2. وجود صرفه اقتصادی یکپارچه سازی بین نقاط مبدا و مقصد3. عدم وجود خدمترسانی بین نقاط مبدا و مقصدتا کنون مدلهای ریاضی متنوعی برای مسائل هاب ارائه شده است که می توان به مکانیابی میانه P تسهیلاتی با تخصیص یگانه و چندگانه، مدل مکانیابی میانه تسهیل هاب با هزینه ثابت، مدل مکانیابی مرکز P تسهیل هاب با تخصیصهای یگانه و چندگانه و سر انجام مکانیابی پوشش تسهیلات هاب اشاره کرد. شکل شماره 1 شکل کلی مسئله مکانیابی هاب است که در آن نقاط خاکستری رنگ هاب بوده و نقاط سیاه رنگ نقاط مبدا و مقصد میباشند. شکل 1 شکل نمونه از توپولوژی هابفرض در مدل مکانیابی P تسهیل هاب با تخصیص یگانه این است که هر محموله قابل شکستن به محموله های کوچکتر نیست و باید توسط یک مسیر به مقصد برسد. در این مدل کمینه سازی هزینه (زمان یا هزینه) کل محموله ها است. در مدل مکانیابی P تسهیل هاب به صورت تخصیص چندگانه فرض بر این است که هر محموله قابل شکستن به محمولههای کوچکتر بوده و در نتیجه میتوان از چند مسیر برای رسیدن مقصد استفاده کرد.در حالت مکانیابی میانه تسهیلات با هزینه ثابت فرض میشود برای بازگشایی هر تسهیل هاب هزینه ثابتی به هزینه کل اضافه میشود؛ در این حالت تابع هدف برابر خواهد بود با کمینه سازی مجموع هزینه کل گشایش تسهیلات به اضافه هزینه حمل و نقل کالاها.برای مکانیابی مرکز P تسهیلاتی سه نوع تابع هدف می توان تعریف کرد1- کمینه سازی بیشترین هزینه برای هر جفت مسیر بین مبادی و مقاصد2- کمینه سازی بیشترین هزینه انتقال بر روی یک هاب، از مبدا به هاب، هاب به هاب و هاب به مقصد3- کمینه سازی بیشترین هزینه انتقال بر روی یک یال گذرنده از یک هاب به یک مبدا یا مقصد.توابع هدف مذکور به ترتیب در مسائل شبکههای حمل و نقل مواد زوال پذیر، شبکههای نیازمند تجهیزات خاص در تسهیلات هاب مانند تجهیزات سرمایشی، یا شبکههای با محدودیت زمان حمل و نقل و سرانجام شبکههای با خصوصیات ویژه برای یالهای انتقال هاب به هاب کاربرد دارند. مدل مکانیابی پوشش تسهیلات هاب به بررسی حالتی میپردازد که یک تقاضای انتقال محموله در صورت قرارگیری در شرایط مشخصی نسبت به یک تسهیل هاب، پوشش داده تلقی میشود. برای تحت پوشش قرار گرفتن یک نقطه تقاضا سه حالت میتوان متصور بود ]9[.1- هزینه انتقال هر یک از یالهای روی مسیر انتقال از مبدا به مقصد که حد اکثر از دو نسهیل هاب مشخص میگذرد از یک مقدار معین تجاوز ننماید.2- هزینه انتقال بر روی هر یک از یالهای مبدا-هاب و هاب مقصد از مقدار مشخصی تجاوز ننماید.همچنین میتوان برای مسئله مکانیابی تسهیلات هاب تابع هدف از نوع حداکثر پوشش نیز تعریف کرد.در مدل مکانیابی هاب یکی از اهداف حل مسئله این است که هابها کجا قرار دارند. در مسائل مکانیابی هاب یک ضریب تخفیف روی یالهایی که بین دو هاب هستند، تعریف میشود. این یال که همان آرکهاب است بین هر دو نقطه هاب در مدل P تسهیل هاب میانه وجود دارد. در مسئله P میانه فرض اصلی بر این است که شبکه گرههای هاب کامل است و تمام نقاط هاب دو به دو توسط آرکهابها بهم متصل هستند. لذا در این مدل مکان آرکهابها همزمان با مسئله انتخاب هابها حل میشود و مکان آرکهابها نیز مشخص میشود. مسئله انتخاب آرک کمبود قابل توجهی از مدل P هاب میانه را مورد بررسی قرار میدهد ]10[. مسائل هاب میانه عموما بعنوان یک مسئله مکانیابی شناخته میشوند. اما آنها را می توان بعنوان مسئله طراحی شبکه نیز به حساب آورد که شامل دو دسته مسائل طراحی شبکه هستند1.آرک هاب2. یال دسترسیمسئله آرکهابها در طراحی شبکه انتخاب آرکهابها است. با توجه به اینکه هابها کاملا با هم متصل هستند مکان آرک هابها را در مسئله مشخص میکنیم. طراحی یالهای دسترسی[2] انتخاب یالهای متصل کننده هابها به نقاط غیر هاب است.مسئله تخصیص یگانه مسئله بسیار مشکلی خواهد بود و جزو دسته مسائل Np-Hard میباشد ]10[. [1]Hub location[2]Access arc