کنفرانس مهندسی برق ایران

صفحه اصلی / بیست و نهمین کنفرانس مهندسی برق ایران

ارائه روشی مبتنی بر دایجسترای پویا جهت مسیریابی بهینه در شبکه ترافیک شهری

نویسندگان :

طه واجدسمیعی¹ منیره عبدوس²

1- دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی 2- دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی

کلمات کلیدی :

الگوریتم دایجسترای ایستا، الگوریتم دایجسترای پویا، الگوریتم‌های مسیریابی، حمل و نقل هوشمند، مسیریابی بهینه

چکیده :

امروزه با توجه به گسترش روزافزون جمعیت، مسئله پیشنهاد مسیر بهینه برای جابه‌جایی بین نقاط مختلف شهر از اهمیت ویژه‌ای برخوردار شده‌است. در راستای حل این مسئله برنامه‌ها و الگوریتم‌های متنوعی ارائه شده‌اند که البته غالبا بر پایه اطلاعات آماری بوده، وابسته به جمع‌آوری مقدار زیادی داده از سطح شهر و همچنین نیازمند محاسبات نسبتا زیادی هستند. در این مقاله روشی بر پایه الگوریتم دایجسترا ارائه شده‌است که در آن پویایی و تغییرات ترافیکی در طول زمان نیز در نظر گرفته شده‌است. همچنین در این روش به کمک استفاده از ابزارهای نگاشت نقشه شهر بر روی گراف، مقدار قابل توجهی از محاسبات مسیریابی کاهش داده شده‌است. در نهایت نیز با انجام آزمایشات متعدد بر روی بخشی از نقشه شهر تهران و مقایسه الگوریتم پیشنهادی با سایر الگوریتم‌ها می‌توان گفت روشی ارائه شده‌است که توانسته از الگوریتم دایجسترا و موارد مشابه آن عملکرد بهتری داشته باشد، و همین‌طور با توجه به ساختار الگوریتمی این روش می‌توان اشاره داشت که از حالت کاملا آماری خارج بوده و بخش عمده‌ای از آن بر پایه پیاده‌سازی‌های الگوریتمی است که این مسئله خود نیز منجر به کاهش نیاز به استفاده از داده‌های زیاد آماری از سطح شهر می‌شود.