مسیریابی بهینه بر اساس معیار زمان با توجه به شرایط متغیر ترافیکی

نوع مقاله : علمی - پژوهشی

چکیده

یکی از مهم ترین کاربردهای سیستمهای اطلاعات مکانی تسهیل و بهبود حمل و نقل است. در این زمینه قابلیتهای تجزیه و تحلیل شبکه در سیستمهای اطلاعات مکانی از جمله محاسبه کوتاه ترین مسیر می‌تواند بسیار مفید واقع شود. تا کنون معیارهای مختلفی برای انجام آنالیز کوتاه ترین مسیر در تجزیه و تحلیل شبکه در سیستمهای اطلاعات مکانی در نظر گرفته شده‌اند. معیارهایی از قبیل مسافت، زمان سفر، راحتی مسیر، زیبایی مسیر و غیره. معیار زمان سفر چون کاملا وابسته به ترافیک است، دارای تغییرات پیوسته و تا حدودی تصادفی است.. به همین دلیل مسیریابی بر اساس معیار زمان سفر با استفاده از الگوریتمهای رایج مسیریابی مثل دایجسترا که بر روی شبکه‌های استاتیک قابل اجرا هستند،  نمی‌تواند خروجی مناسبی ارائه دهد. بنابراین در این زمینه نیاز به توسعه الگوریتمهایی است که بر روی شبکه‌های پویا اجرا می‌شوند. در این مقاله یک روش جدید ارائه شده است که در آن از اطلاعات آماری زمان سفر در روزهای قبل به منظور پیش بینی زمان سفر یالها در آینده استفاده شده است. همچنین به منظور مدل کردن مساله تصادفی ترافیک به هر یک از یالهای شبکه ریسکی اختصاص یافته است که روش محاسبه آن نیز در این مقاله توضیح داده شده است. به منظور در نظر گرفتن زمان سفر لحظه‌ای و همچنین زمان سفر پیش بینی شده و ریسک هر یال،  از یک مدل تجزیه فضا- زمان استفاده شده است که چگونگی آن نیز در این مقاله توضیح داده شده است. در نهایت به منظور آزمون روش و بررسی نتایج آن، روش ارائه شده روی داده‌های یک نمونه موردی واقعی اجرا و مورد بحث قرار گرفته است آزمون  انجام شده به خوبی توانست تاثیر استفاده از این روش برای مسیریابی به جای روشهای استاتیک را  نشان دهد،  به نحوی که زمان سفر بین دو نقطه در شبکه مورد آزمون  از 35/71 دقیقه که مربوط به روشهای استاتیک بود  به 29/43 دقیقه کاهش یافت. بدون شک با افزایش فاصله بین دو نقطه میزان تاثیر و فواید روش ارائه شده نمایان تر خواهد بود.
.
 

کلیدواژه‌ها


عنوان مقاله [English]

Optimum Path Finding Based on Time Criterion under Traffic Variation

چکیده [English]

Facilitation of transportation is one of the most important applications of Geographic Information System (GIS). In this area the network capabilities of GIS such as shortest path computation, could be very useful. Different criteria have ever considered for shortest path analysis in GIS such as: Distance, travel time, path comfort, path beauty. Travel time criterion has some random continues variations, due to its relation to traffic. Therefore, path finding based on these criterions by current algorithms such as Dijkstra is not suitable. In this field a development of algorithms that can be used on dynamic networks is necessary. In this paper we have developed an algorithm for this purpose that used statistical information of travel time in previous days for prediction of travel time in future. Also for modeling of the randomness of traffic, we have used a risk parameter for each edge in network. We have used the model of space-time partitioning for consideration of observed travel time, predicted travel time and risk parameters together. Finally for testing the developed algorithm, a case study has been explained in this paper. The implemented case study showed the usefulness of represented method in finding shortest path beside current static methods where the total travel time between two points in tested network was reduced from 35.71 minutes by static methods to 29.43 minutes. Certainly, the usefulness of our represented method could be more apparent by increased distance between origin and destination in the network.

کلیدواژه‌ها [English]

  • Path finding
  • time
  • Dijkstra Algorithm
  • dynamic network
  • path risk