استفاده ازکلنی مورچگان در مسیریابی وسایل نقلیه امدادی در شرایط – عمران

مشخصات فایل

مقطع:کارشناسی ارشد
رشته تحصیلی:مهندسی عمران
نوع ارائه:پایان نامه
تعداد صفحات:148
قالب بندی:word قابل ویرایش

نحوه خرید

استفاده ازکلنی مورچگان در مسیریابی وسایل نقلیه امدادی در شرایط – عمران

شما میتوانید تنها با یک کلید به راحتی فایل مورد نظر را دریافت کنید. 🙂

برای دسترسی به این فایل ابتدا باید اشتراک خریداری کنید. برای خرید اشتراک بر روی لینک زیر کلیک کنید.

ارتقاء عضویت

چکیده

فهرست مطالب

چكيده ………….. 1

مقدمه …………… 2

1- فصل اول: تعريف مسأله …….. 3
1- 1- مقدمه …………… 4
1- 2- تعريف مسأله مسيريابي براي وسايل نقليه امدادي ….. 5
1- 3- اهداف مطالعه …………. 7
1- 4- ضرورت انجام كار ………………. 8
1- 5- فرضيات ………………. 10
1- 6- روش انجام كار ………………. 11
1- 7- ساختار پاياننامه ……………. 13
2- فصل دوم: مروري بر مطالعات پيشين …….. 15
2- 1- مقدمه …………………. 16
2- 2- الگوريتم دايكسترا ………… 17
2- 3- دستور حل بلمن ……………. 19
2- 4- دستور حل فلويد …………….. 20
2- 5- الگوريتم *A ………… 22
2- 6- الگوريتم جستجوي سطحي (BFS) ….اا…. 23
2- 7- الگوريتم جستجوي عمقي (DFS) …..ا….. 25
2- 8- موقعيت الگوريتمهاي مسيريابي در مسايل چند هدفه ……… 27
2- 9- آشنايي با الگوريتمهاي فرا ابتكاري مورچگان …………. 29
2- 9- 1- اساس الگوريتمهاي فرا ابتكاري مورچگان ………….. 30
2- 9- 2- انواع مختلف الگوريتمهاي فرا ابتكاري مورچگان ………….. 33
2- 9- 3- الگوريتم فرا ابتكاري سيستم مورچگان AS)) …ا…. 35
2- 9- 4- الگوريتم فرا ابتكاري سيستم مورچگان نخبه EAS)) ….ا.. 37
2- 9- 5- الگوريتم فرا ابتكاري سيستم مورچگان مبتني بر رتبه (AS-Rank) ..ا. 38
2-9-6- الگــوريتم فــرا ابتكــاري سيســتم مورچگــان بــا تعيــين ســطح مقــادير بيشــينه و كمينــه فرمون(MMAS) ………ا…… 39

2- 9- 7- الگوريتم فرا ابتكاري سيستم اجتماع مورچگان (ACS) ……ا……. 41
2- 9- 8- الگوريتم جستجوي تقريبي و غير قطعي درخت جواب (ANTS) …ا….. 46
2- 10- استفاده از الگوريتم بهينهيابي مورچگان در مسايل تصميمگيري چند هدفه … 49
2- 11- مروري چند بر روشهاي بيمقياسسازي شاخصهاي تصميمگيري ….. 53
2- 11- 1- بيمقياسسازي با استفاده از نرم ………….. 54
2- 11- 2- بيمقياس كردن خطي ……… 54
2- 11- 3- بيمقياسي فازي ……………….. 55
3- فصل سوم: ارائه روش …………. 56
3-1- مقدمه ……………. 57
3-2- متدولژي روش حل مسأله مسيريابي چند هدفه با استفاده از الگوريتمهاي مورچگان ….. 60
3-2-1- پيادهسازي مسأله مسيريابي چند هدفه در قالب روش سيستم مورچه نخبه (EAS) ….ا…. 61
3-2-2- پيادهسازي مسأله مسيريابي چند هدفـه در قالـب روشهـاي سيسـتم چنـد دسـتهاي مورچـه
(MCAS) و سيستم چند دستهاي مورچه نخبه ((MCEAS …ا… 62
3-2-3- پيادهسازي مسأله مسيريابي چند هدفه در قالب روش رويكرد چند دسـته اي مورچـه (MCAA)ص 65
3-3- اصلاح و آمادهسازي شبكه پيش از آغاز فعاليت مورچههاي مسيرياب ….. 68
3-3-1- قطع برگها و حذف مسيرهاي بنبست در شبكه حمل و نقل …………. 69
3-3-2- تعريف و نقش مورچه ديدهبان در الگوريتم مسيريابي …………… 72
3-4- چگونگي توليد جواب در فرآيند مسيريابي توسط مورچههاي مسيرياب ………….. 73
3-4-1- نحوه تصميمگيري مورچهها در گزينش گرههاي شبكه …………. 74
3-5- به هنگامسازي فرمون كمانهاي شبكه ……….. 79
3-5-1- تبخير سراسري فرمون ……….. 81
3-5-2- تبخير موضعي فرمون …………. 81
3-5-3- فرمونگذاري توسط مورچههاي مسيرياب …………. 82
3-5-4- محدود كردن حد پايين سطح فرمون كمانهاي شبكه ………… 83
4- فصل چهارم: مطالعه موردي و نتايج عددي ……. 85
4-1- مقدمه …………………. 86
4-2- تعريف مسأله …………………. 86
4-3- تعيين كوتاهترين مسير چند هدفه بين يك مبدأ- مقصد با اسـتفاده از الگـوريتمهـاي مورچگـان 91
4-3-1- تحليل حساسيت پارامترهاي مدل در روش (MCAS) ……ا….. 94
4-3-2- تحليل حساسيت پارامترهاي مدل در روشهاي (EAS) ،(MCAA) ،(MCEAS) .ص 111
4-3-3- مقايسه نتايج به دست آمده از مدلهاي ارائه شده ……… 116
4-3-4- محدود كردن حد پايين ميزان فرمون كمانهاي شبكه در مدلهاي ارائه شده از طريق تعريـف كران پايين …………. 119
4-4- ارزيابي عملكرد مدلهاي ارائه شده در مقايسه باروش دايكسترا ………….. 121
4-4-1- مقايسه عملكرد مورچههاي مسيرياب تك هدفه با روش دايكسترا …… 122
4-4-2- مقايسه عملكرد مورچههاي مسيرياب چند هدفه با روش دايكسترا …. 123
4-5- به كارگيري روش حل مسيريابي چند هدفه با استفاده الگوريتم مورچگان در مسأله طراحي شبكه براي اعزام نيروهاي امدادي ……………….. 125

5- فصل پنجم: نتيجهگيري و پيشنهادات …………… 131
نتيجهگيري …………………. 132

پيشنهادات …………………. 136
منابع و ماخذ ………………… 137

فهرست منابع فارسي ………………. 137

فهرست منابع لاتين ………………… 137
چكيده انگليسي ……………. 142

چكيده
در اين پايان نامه براي حل مسأله مسيريابي چند هدفه وسايل نقليه امدادي در شبكه حمل و نقل رويكرد جديدي مبتني بر الگوريتم مورچگان ارائه گرديده اسـت . اهـداف مـورد بررسـي زمـان سـفر وقابليت اطمينان مي باشند. در ا يـن راسـتا ن يـز سـه الگـوريتم بـه نامهـاي (MCEAS) ,(MCAS) و(MCAA) بـر اسـاس الگـوريتم بهينـه يـابي مورچگـان (ACO) ارائـه گرد يـده و عملكـرد آنهـا بـا الگوريتم هاي مورچه نخبه(EAS) و دايكسـترا (DA)، مقايسـه شـده اسـت. نتـايج، نشـان از بهبـودجوابهاي بدست آمده از مدلهاي ارائه شده، نسبت به روشهاي متداول دارد.

مقدمه
در اين پاياننامه مسيريابي بر يك شبكه گراف متشكل از تعدادي گره و كمان بررسـي شـده اسـتكه ويژگي اصلي آن چند معيار بودن ميسريابي و تكيه بر دو معيار زمان سفر و قابليت اطمينـان سـفردر كمانهاي شبكه است. اين مسأله در واقع ميتواند در قالب ارائه نوعي نـرم افـزار جهـت مسـيريابي وسايل نقليه امدادي براي يافتن كوتاهترين مسير از مبدأ حركت يا پايانه (نقطه صـفر ) بـه هـر مقصـدمورد نظر در شبكه مطرح باشد. ماهيت اين مسيريابي بالطبع سرعت بـالاي پـردازش اطلاعـات جهـتارائه به كاربر و نيز ارائه يك الگوي مناسب يا بهينه جهـت حركـت در شـبكه را مـيطلبـد . در همـينراستا، اين پاياننامه از روش فراابتكاري مورچگان براي انجام مسيريابي چند هدفه خود بهره ميبرد.
ويژگي اصلي اين شيوه الگوريتميك دستيابي به جوابهايي بهينه با تكيـه بـر محـدوديتهـاي اعمـالشده بر معيارهاي مفروض و آن هم در كمترين زمان ممكن ميباشد. بنابراين تا حد زيادي پاسـخگوينيازهاي مطرح در مسأله مسيريابي براي وسايل نقليه امدادي خواهد بود.
به منظور پيادهسازي الگوريتم مورچگان از چند نسخه ارائه شده در اين خانواده يعني سيستم مورچـهنخبـه (EAS)، سيسـتم چنـد دسـتهاي مورچـه ((MCAS، سيسـتم چنـد دسـتهاي مورچـه نخبـه (MCEAS) و رويكرد چند دستهاي مورچه (MCAA) استفاده شد.
برخي از محدوديتهاي موجود در الگوريتم مورچگان (مثلاً جستجوي گره به گره و ناتواني مورچه-هاي مسيرياب در پيشبيني ادامه مسير در گراف شبكه) سبب شد كه بـا هـدف جلـوگيري از گرفتـارشدن مورچهها در يك مسير بنبست (مثلاً در ساختار يك شبكه درختي) پيش از آغاز فعاليت آنهـا،نوعي اصلاحات مقدماتي شامل قطع برگها و تصحيح مسيرهاي بـن بسـت در سـاختار شـبكه صـورتپذيرد، در ادامه مورچههاي مسيرياب در قالب دو دسته مجزا كه دسته اول مسيرهاي بـا معيـار زمـانبهينه و دسته دوم مسيرهاي با قابليت اطمينان بهينه را جستجو ميكنند، فعاليت خـود را آغـاز مـي-كنند. در پايان هر تكرار از الگوريتم تعدادي از مسيرهاي يافته شده پيشرو خواهد بود كه با توجه بـهدو نوع معيار متفاوت در مسيريابي به دست آمدهاند. لذا در اين مرحلـه بـا تعريـف نـوعي تـابع ارزش-گذاري، ارزش هر دو معيار در مسيرهاي به دست آمده، به صـورت فرمـونگـذاري (كـه ميـزان آن بـرمبناي هر دو معيار مطرح در مسأله ميباشد) بر كمانهاي مسير اعمال ميشود.
مدلهاي ارائه شده بر يك شبكه فرضي منطبق با شـبكه شـهر سـايوكس فـالز ايـالات متحـده مـوردآزمايش عددي قرار گرفتند. نتايج حكايت از توفيق بيشتر روشهـاي (MCEAS) و(MCAA) نسـبتبه دو روش ديگر داشت. در پايان با مقايسه مدلهاي برتر با روش قطعي دايكسترا به عنوان روش پايه، عملكرد اين مدلها مورد ارزيابي قرار گرفتند. سپس با استناد به نتـايج بـه دسـت آمـده از مـدلهـاي(MCEAS) و(MCAA) شبكهاي بر مبناي حداقل طول تحت پوشش جهت اعزام نيروهاي امدادي در شرايط بحران طراحي شد.

نتيجه گيري
مسأله مسيريابي (SP) يكي از مسائل مطرح و كاربردي در مهندسي حملونقل است كه رويكرد اصلي اين پژوهش را براي ارائه يك متدولژي كارآمد در حل نسخة چند هدفه آن (MSPP) به خود اختصاص داده است. تاكنون شمار زيادي از الگوريتمها جهت حل مسأله مسيريابي و يا به بيان ديگر مسأله كوتاه ترين مسير در شبكه ارائه گرديدهاند كه هر كدام داراي نقاط ضعف و قوت خود مي باشند. در اين رساله نيز با بهرهگيري از ايده يك الگوريتم فراابتكاري تحت عنوان الگوريتم مورچگان، چهار مدل مختلف به نام هاي (MCEAS) ،(MCAS) ،(EAS) و (MCAA) مطرح گرديدند كه از ميان آن ها دو مدل (MCEAS) و (MCAA) نتايج بهتري به بار آوردند.
با ملاحظه جدول (5-1) و مقايسه شماري از الگوريتم هاي مطرح در مسأله مسيريابي با مدل هاي ارائه شده در اين پژوهش مي توان ضمن تأييد ضرورت انجام اين تحقيق به عملكرد موفق مدلهاي مزبور نيز پي برد ضمن آن كه نتايج عددي ارائه شده در فصل پنجم نيز، تأييدي است بر صحت اين گفتار.
همان طور كه بارها و بارها پيش از اين اشاره شد، هدف از اين پژوهش حل مسأله كوتاهترين مسير با دو معيار غيرهمجنس زمان سفر و قابليت اطمينان به قابل عبور بودن مسير است كه در آن معيار قابليت اطمينان يك شاخص احتمالي و عددي بين صفر و يك براي هر كمان و نهايتاً براي هر مسير است. به فراخور عنوان اين رساله و كاربرد مورد انتظار آن در مورد مسيريابي وسايل نقليه امدادي، اعمال محدوديت هايي براي هر دو معيار مطرح شده در مسأله ضروري به نظر مي رسد. از اين ديدگاه مسيرهايي به عنوان مسيرهاي بهينه تلقي مي شوند كه در آن ها زمان سفر از حد مشخصي فراتر و قابليت اطمينان به مسير نيز از حد معيني كمتر نباشد.
در اين پژوهش نيم نگاهي نيز به مسأله طراحي شبكه مي شود. بدين منظور پس از شناسايي كوتاه ترين مسيرهاي بهينه بين مبادي و مقاصد مشخص، مبادي نمايانگر مراكز امداد رساني و مقاصد نمايانگر نقاط نيازمند به امداد در شبكه مي باشند، از بين اين مسيرها شبكه به نحوي طراحي ميشود كه با پوشش كمترين طول از شبكه تمامي نقاط حادثهديده توسط نيروهاي امدادي مورد رؤيت قرار گيرند.
در نهايت مي توان موارد زير را تحت عنوان نتايج كلي اين تحقيق بر شمرد:
1- هدف از اين پژوهش ارائه مدلي جهت يافتن كوتاه ترين مسير بين هر مبدأ و مقصد در شبكه با در نظر گرفتن معيارهاي تصميمگيري چندگانه و رعايت محدوديتهاي اعمال شده براي هر يك از معيارهاي مزبور مي باشد.
2- دو معيار زمان سفر و ميزان قابليت اطمينان به قابل عبور بودن مسير، معيارهاي مطرح در اين رساله مي باشند كه در واقع تا حد زيادي مي توانند بسياري از عوامل مؤثر ديگر در تصميم گيري براي گزينش ميسر، نظير طول، تراكم و عوارض مربوط به يك مسير را نيز در خود جاي دهند.
3- ايده اصلي اين پاياننامه جهت مواجهه با مسأله مسيريابي چند هدفه با قيد محدوديت براي معيارها، استفاده از الگوريتم مورچگان به صورت چند دسته اي ميباشد به نحوي كه هر دسته در صدد يافتن جوابهاي بهينه با در نظر گرفتن يك معيار مؤثر در تصميم گيري مي باشد وجه اشتراك دستههاي متفاوت جمعيت مورچگان، همان مفهوم آشناي فرمون است. اين مفهوم نيز در قالب يك تابع ارزش كه در برگيرندة تمامي معيارهاي مؤثر در تصميمگيري مي باشد، قابل تعريف است.
4- با توجه به دو معيار مطرح در اين رساله، مسأله تصميمگيري چند هدفه تبديل به يك مسأله تصميم گيري دو هدفه مي شود كه با چهار شكل مختلف از الگوريتم هاي مورچگان به نام هاي (MCEAS) ،(MCAS) ،(EAS) و (MCAA) پياده سازي مي شود. همچنين محدوديت هاي اعمال شده در معيارها نيز از طريق كنترل فرمون گذاري مورچه هاي مسيرياب قابل تحقق مي باشند.
5- پياده سازي مدلهاي ارائه شده بر روي يك شبكه فرضي حملونقل، نشان از نتايج ارشمندتر دو مدل (MCAA) و (MCEAS) نسبت به ساير مدلها دارد. همچنين مقايسة نتايج دو الگوريتم فوق و الگوريتم قطعي دايكسترا (DA) حاكي از صحت نتايج اين مدل ها و نيز توانمندي آن ها در اعمال محدوديت هاي مورد نظر بر معيارهاي مطرح شده ميباشد ، امري كه در مورد الگوريتم دايكسترا (DA) به اين صورت تحقق نمييابد.
6- از جمله نتايج كاربردي اين تحقيق، استفاده از كوتاهترين مسيرهاي به دست آمده بين مراكز امدادرساني و نقاط حادثهديده، براي طراحي يك شبكه حملونقل براساس معيار طول و در شرايط رخداد يك پيشامد فراگير همانند زلزله مي باشد. بر اين اساس كمترين طول ضروري براي پوشش تمامي نقاط حادثهديده در شبكه جهت اعزام نيروهاي امدادي مورد گشايش قرار مي گيرد و ساختار جديدي از شبكه ارائه مي گردد.

نحوه خرید

دانلود رایگان فایل
شما میتوانید تنها با یک کلید به راحتی فایل مورد نظر را دریافت کنید. 🙂

برای دسترسی به این فایل ابتدا باید اشتراک خریداری کنید. برای خرید اشتراک بر روی لینک زیر کلیک کنید.

ارتقاء عضویت

در صورت بروز هر گونه مشکل در روند خرید اینترنتی، بخش پشتیبانی کاربران آماده پاسخگویی به مشکلات و سوالات شما می باشد

راهنمای سایت

برخلاف سایت های دیگر که فایل ها را به صورت تکی می فروشند روال سایت ما این است که شما با عضویت در سایت ما میتوانید از تمام فایل های موجود استفاده کنید.

تمام مطالب سایت فقط برای اعضای سایت رایگان است.

نحوه عضویت در سایت