دانلود پایان نامه با موضوع مکانیابی

دانلود پایان نامه ارشد

-ساعت كار مورد نياز، نحوه بهبود سيستم نجات و همچنین پارامترهاي مورد نياز براي تعريف مدل يادآوري مي گردد. سپس الگوريتمي براي شناسايي شهرهاي امدادرسان به شهر آسيب ديده ارائه مي گردد. در نهايت مدل اصلي كه مدل تخصيص نيروهاي امدادرسان به شهرهاي مختلف است ارائه خواهد شد .

4- 2 الگوریتم مورد استفاده در مکانیابی ایستگاه های امداد رسان
مدل مسئله ي مکانیابی ایستگاهای امداد و نجات مورد نظر با بزرگ شدن مسئله، بسيار پيچيده و بزرگ ميشود، به دليل محدوديت هاي حافظه و بالارفتن زمان حل، نمي توان با استفاده از روش حل دقيق، جواب مسئله را به دست آورد. به همين منظور الگوريتم حل ابتكاري براي مسئله ي تحت بررسي ارائه شده است. اين الگوريتم از دومرحله تشكيل شده است؛ در مرحله ي اول بهترين نحوه توزيع آمبولان سها و تخصيص تقاضاهاي موجود به بيمارستان ها و مراكز خدمات فوري تهاي پزشكي در هريك از دور ههاي زماني تعيين شده است كه در اين مرحله از تعريف دو الگوريتم شبيه سازي تبريد به نام هاي SA1 وSA2 استفاده شد. در مرحله ي دوم براي تعيين بازآرايي مناسب آمبولانس ها بين دوره هاي متوالي و اينكه آمبولانس ها در صورت نياز به جابجايي ازكدام مركزEMS به كدام مركزEMS منتقل شوند، از يك الگوريتم حريصانه69استفاده شده است.

4-2-1 الگوریتم تبرید
شبيه سازي تبريد يك تكنيك محاسباتي تصادفي براي به دست آوردن جواب هاي نزديك به بهينه در مسائل بهينه سازي تركيبي مي باشد. اين روش از فرايند ترموديناميكي سرد كردن فلزات مذاب براي به دست آوردن كمترين حالت انرژي حاصل مي شود.
مزيت اصلي شبيه سازي تبريد، نسبت به روش هاي جستجوي تصادفي، توانايي آن براي جلوگيري از افتادن در بهينه هاي محلي هنگام جستجو براي مينيمم محلي است.
در استراتژي جستجوي شبيه سازي تبريد، الگوريتم از يك جواب اوليه آغاز می شود . در هر مرحله جواب هاي جديد توسط حركات تصادفي در همسايگي جواب فعلي توليد مي شوند. اگر جواب جديد مقدار تابع هدف را بهبود دهد، جايگزين جواب فعلي مي گردد در غير اين صورت جواب جديد با احتمال مشخصي شانس پذيرش دارد. اين احتمال به صورت زير تعريف مي شود:

به طوريكه است، است ، که x جواب فعلي است، y جواب جديد توليد شده ، C تابع هدف كه در اينجا بيشينه سازي درنظر گرفته شده است و Ti دماي تبريد در مرحله i ام و p احتمال پذيرش مي باشد. استفاده از احتمال فوق در الگوريتم بدين صورت است كه در هر مرحله اگر شد، يك عدد تصادفي بين صفر و يك توليد مي شود و با احتمال مذكور مقايسه مي گردد. چنانچه اين عدد تصادفي از احتمال كوچكتر بود، جواب جديد پذيرفته مي شود.
همان طور كه ديده مي شود، احتمال پذيرش حركت اشتباه تابعي از دما مي باشد. در ابتداي الگوريتم كه دما بالاتر است، بيشتر حركت ها پذيرفته مي شود. اين امر اجازه حركت در فضاي جواب را مي دهد. دما در هر مرحله تا زماني كه تعداد ثابتي تكرار (L) انجام شود، ثابت باقي مي ماند. سپس به تدريج كاهش مي يابد. با كاهش دما، احتمال پذيرش حركت اشتباه نيز كاهش مي يابد تا در انتها فقط حركت هاي موثر مورد پذيرش واقع مي شوند. الگوريتم تا زمان رسيدن به دماي پاياني ادامه مي يابد.

4-2-2 برنامه سرد سازي
برنامه سرد سازي شامل پارامترهايي است كه نحوه سرد كردن الگوريتم را مشخص مي كنند. مهمترين پارامترهاي برنامه سرد سازي درجه حرارت آغازين70 و نرخ كاهش درجه حرارت در هر مرحله 71مي باشند. اين پارامترها نقش مؤثري در همگرايي الگوريتم به جواب بهينه، ايفا مي كنند. بدين منظور نحوه تعيين پارامترهاي فوق به طور مختصر توضيح داده مي شوند.

4-2-3 درجه حرارت آغازين (T_0)
درجه حرارت آغازين بايد به اندازه كافي گرم باشد تا حركت به همه ي حالت هاي مجاور را اجازه دهد. اگر درجه حرارت آغازين خيلي زياد باشد، جستجو مي تواند به هر همسايگي حركت كند و جستجو به جستجوي تصادفي تبديل مي شود. اين جستجوي تصادفي ادامه مي يابد تا زماني كه دما به اندازه ي كافي كاهش يابد. مقادير بسيار بزرگT_0 موجب طولاني شدن مدت زمان اجراي الگوريتم و گسترش نقاط جستجو مي باشد و مقادير بسيار كوچك آن ممكن است موجب همگرايي زود هنگام شده و الگوريتم در بهينه ي محلي متوقف شود.

4-2-4 دماي پاياني
به طور معمول اجازه داده مي شود تا دما كاهش يابد و به صفر برسد. با ابن حال، اين موضوع مي تواند اجراي الگوريتم را خيلي طولاني كند. در عمل خيلي مهم نيست كه اجازه داده شود تا دما به صفر برسد، زيرا با نزديك شدن به صفر، احتمال پذيرش حركت اشتباه، غالبا با زماني كه دما مساوي صفر شود، يكي خواهد بود. بنابراين شرط توقف مي تواند يك دماي پايين مناسب باشد.

4-2-5 كاهش دما
نرخ كاهش پارامتر دما براي موفقيت هر فرايند SA ، حياتي است. از نظر تئوري پيشنهاد مي شود كه بايد اجازه دهيم تا سيستم در دماي فعلي خود و قبل از كاهش دما، به توزيع ايستاي خود خيلي نزديك گردد و بايد دما كم كم به صفر نزديك شود. براي رسيدن به اين منظور تعداد تكرار در هر دما نسبت به اندازه ي مسئله، نمايي خواهد بود كه به معني زمان محاسباتي غيرقابل قبول است. لذا كاهش تعداد تكرارها اجتناب ناپذير است. بنابراين مي توان از تعداد تكرارهاي زياد در تعداد كمي دما، يا تعداد كمي تكرار در تعداد زيادي دما استفاده كرد و يا يك توازن بين هر دوي آنها ايجاد كرد. به طور كلي شش روش عمده براي زمان بندي سرد شدن مورد استفاده قرار میگیرد كه پر کاربردترین آن ها شامل يك تابع كاهش هندسي به صورت است .
تجربه نشان داده است كه مقادير نسبتا بزرگ αبهترين نتيجه را دارد و اكثر موفقيت هاي گزارش شده از مقادير بين %8و %99 استفاده کرده اند .

4-2-6 تعداد تكرار در هر دما
تعداد تكرار در هر دما معمولا مرتبط با اندازه همسايگي يا گاهي فضاي جواب است و ممكن است براي دماهاي مختلف متفاوت باشد. يك روش اين است كه تعداد تكرار ثابتي در هر دما داشته باشيم.
روش ديگر اين است كه به صورت پويا تعداد تكرارها، با پيشروي الگوريتم تغيير يابد. به عنوان مثال مهم است كه در دماهاي پايين تر، زمان بيشتري صرف كنيم .[56]

4-3 شرح كلي رو ش حل ابتكاري
همان طور كه گفته شد، الگوريتم حل ابتكاري از دو مرحله تشكيل شده است. در مرحله ي اول كه در بخش 4-4 به تشريح آن خواهيم پرداخت، هدف يافتن بهترين نحوه توزيع آمبولانس ها در مراكز و تخصيص بيماران به بيمارستان ها و مراكز در هريك از دوره هاي زماني است.
پس از پايان مرحله ي اول و يافتن بهترين نحوه توزيع آمبولانس ها در هريك از دور ههاي زماني، در ادامه و در مرحله ي دوم با استفاده از الگوريتمي كه در بخش 4-5 معرفي خواهد شد سعي در يافتن نحوه بازآرايي مناسب براي آمبولان سها در دوره هاي زماني متوالي خواهيم داشت. در شكل 4-1 مراحل كلي الگوريتم ارائه شده مشاهده مي شود.

شکل 4-1 فلوچارت الگوریتم ابتکاری ارائه شده
4-4 مرحله ي اول: توزيع آمبولانس ها و تخصيص بيماران در هر دوره
به اين منظور اقدام به تعريف دو الگوريتم شبیه سازي تبريد ( SA2و 1 SA) نموديم كه الگوريتم SA2 به عنوان يك زيرالگوريتم در SA1 اجرا میشود. پارامترهاي الگوريتم اول را با α1 و L1 ،T1 و پارامترهاي الگوريتم دوم را با α2 و L2 ،T2 نشان مي دهيم.
در ادامه ابتدا به شرح الگوريتم SA1 و پس از آن الگوريتم SA2 را توضيح مي دهيم.

1-4-4 الگوريتم SA1
هدف از اجراي الگوريتم SA1 يافتن بهترين نحوه توزيع آمبولانس در بين مراكز EMS در دوره زماني فعلي است. مراحل اجراي اين الگوريتم در شكل 4-2 آمده است.
جواب اوليه
در ابتدا مي بايست يك جواب اوليه براي اين الگوريتم ارائه دهيم. به اين منظور گام هاي زير را انجام مي دهيم. گام اول: براي هر مركز خدمات فوريت هاي پزشكي، شاخص ، DH1(j) كه اين شاخص بيان گر اولويت مراكز EMS براي دريافت آمبولانس مي باشد، تعريف مي شود. اين شاخص حداقل مقدار ميان دو مقدار زير است:
*مجموع تقاضاهاي موجود در دوره كه در فاصله ي زماني r_2 از اين EMS قرار دارند و مي بايست به بيمارستان منتقل شوند.
* مجموع ظرفيت بيمارستان هايي كه با اين مركز در ارتباط هستند.

بله
شکل 4-2 فلوچارت الگاریتم SA1
پس از تعيين اين شاخص، گام هاي دوم و سوم را تا زمانيكه تمامي آمبولانس ها به مراكز EMS تخصيص يابند، ادامه مي دهيم.
گام دوم: با استفاده از تكنيك چرخ رولت72 كه مقادير آن بر اساس شاخص DH1(j) محاسبه شده اند، يكي از مراكز EMS را انتخاب مي كنيم.
گام سوم: در صورتيكه ظرفيت مركز EMS انتخاب شده در گام دوم از نظر تعداد آمبولانس ممكن براي تخصيص به آن، تكميل نشده باشد يك آمبولانس به آن تخصيص داده مي شود و از تعداد آمبولانس هاي موجود يكي كم مي شود.
به عنوان مثال فرض كنيد 20 آمبولانس و 5 مركز خدمات فوريت هاي پزشكي داشته باشیم، يك جواب ابتدايي براي اين مثال كه به صورت تصادفي ايجاد شده است، مي تواند به صورت جدول زير باشد.

5
4
3
2
1
شماره مراكز خدمات فوريت هاي پزشكي
2
6
4
5
3
تعداد آمبولانس تخصيص داده شده به هر مركز
جدول 4-1نمونه اي از ايجاد جواب ابتدايي براي تخصيص آمبولانسها به مراكز
تابع هدف
به منظور ارزيابي جواب فعلي از الگوريتم SA2 استفاده مي كنيم. اين الگوريتم كه شرح آن در ادامه خواهدآمد سعي در يافتن بهترين تخصيص تقاضاها به مراكز خدمات فوري تهاي پزشكي و بيمارستان ها با توجه به توزيع فعلي آمبولان سها در بين مراكز خدمات فوري تهاي پزشكي را دارد به گونه ایی كه بخش اول تابع هدف مدل رياضي ارائه شده، كه مربوط به پوشش تقاضاها با بهترين كيفيت است، بيشينه شود. به عبارت ديگر الگوريتم هاي SA1 ، SA2 سعي در بيشينه سازي عبارت زير (F) را دارند.
(4-1)

4-4-2 الگوریتم SA2
اين الگوريتم سعي در يافتن بهترين تخصيص تقاضاها به مراكز خدمات فوري تهاي پزشكي و بيمارستان ها با توجه به توزيع فعلي آمبولانس ها در بين مراكز خدمات فوري تهاي پزشكي را دارد. مراحل اجراي اين الگوريتم در شكل 4-3 آمده است .
جواب اوليه
براي اجراي الگوريتمSA2 نياز به يافتن يك جواب اوليه از تخصيص تقاضاها وجود دارد. به اين منظور يك الگوريتم حريصانه طراحي گرديده است كه گام هاي اين الگوريتم به صورت زير است:
گام اول: يك ترتيب تصادفي از نقاط تقاضا مانند جدول 4-2 توليد مي كنيم و براساس آن اقدام به برآورده كردن تقاضاي هريك از نقاط در مراحل زير مي كنيم. براي نمونه در صورتي كه ترتيب تصادفي توليد شد همانند جدول زير باشد، ابتدا تقاضاي نقطه شماره 4 برآورده مي شود. سپس نوبت به نقط هي تقاضاي شماره 2 مي رسد و به همين شكل تا نقطه ي تقاضاي آخر ادامه مي يابد.
5
8
9
3
10
7
1
6
2
4
جدول4-2 يك ترتيب تصادفي از 10نقطه ي تقاضا
گام دوم را براي هر نقطه تقاضا تا زماني كه تمامي تقاضاي آن پاسخ داده شود يا هيچ مركزEMS در فاصله زماني r_2 از نقطه تقاضا و يا بيمارستاني در فاصله زمانيs_2 از آن با ظرفيت خالي وجود نداشته باشد و يا درصورت وجود با هم ارتباط نداشته باشند ادامه مي دهيم و سپس به نقطه ي تقاضاي بعدي مي پردازيم.
گام دوم: نزديك ترين مركز EMSرا كه داراي ظرفيت خالي مي باشد و در فاصله ي زماني r_2 از نقطه تقاضا قرار دارد انتخاب مي كنيم. سپس بين بيمارستان هايي كه با اين مركز ارتباط دارند و ظرفيت آنها تكميل نشده است، نزديك ترين بيمارستان به نقطه نقاضا را با شرط آنكه در فاصله زماني s_2 از آن قرار داشته باشد،تعيين مي كنيم. سپس تا آنجايي كه ظرفيت مركز EMSو بيمارستان اجازه مي دهند، تقاضاي نقطه تقاضاي مدنظر را توسط مركز و بيمارستان انتخاب شده پاسخ مي دهيم.

شکل 4-3 فلوچارت الگوریتم SA2
تابع هدف
به منظور ارزيابي جواب فعلي مانند الگوريتم SA2

پایان نامه
Previous Entries دانلود پایان نامه با موضوع جمع آوری اطلاعات، بحران مربوط، مکانیابی Next Entries دانلود پایان نامه با موضوع همسايگي، تخصيص، يافتن