الگوریتمی سریع برای مسیریابی بهینه در مساله اسکان موقت

گذشته ازکاربردهای متعدد مسیریابی بهینه در شبکه های شهری، این مقاله به ارائه الگوریتمی سریع مبتنی بر Dijkstra برای تعیین مسیر بهینه بین نقاط متعدد در شبکه های شهری می پردازد. مهمترین ویژگی این الگوریتم سرعت بالای آن است که با افزودن تعدادی قید به الگوریتم Dijkstra حاصل آمده است. نیاز به سرعت بالای جستجو به علت استفاده از این الگوریتم در فرایند اسکان موقت زلزله زدگان بوده است. در این کاربرد بایستی به دفعات بسیار زیاد (برابر حاصلضرب تعداد بلوکهای ساختمانی در تعداد نواحی امن مربوطه) مسیرهای بهینه بین نواحی امن و بلوکهای ساختمانی در شهر جستجو شده تا نتایج آن در مرحله بعد برای تعیین بهترین ناحیه امن مربوطه به هر بلوک ساختمانی بکار گرفته شود. آزمایشات مولفین نشا ن داد برای تعیین حدود پنجاه هزار مسیر بهینه در یک شبکه شبیه سازی شده با ده هزار بلوک ساختمانی و پنج ناحیه امن مجاور برای هر یک ، در کل به زمان پردازشی در کمتر از یک شبانه روز با کامپیوتر دارای پردازنده P4-2GB نیاز است.

Keywords:

مسیر یابی بهینه , گراف , اسکان موقت , زلزله