ارایه طبقه بندی از انواع گراف دوگان و بکارگیری آنها در بهبود آنالیزهای مسیریابی

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

چکیده

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

کلیدواژه‌ها


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

Providing a Classification of Dual Graph Types to Improve the Routing Analysis

چکیده [English]

Management of transportation is one of the most important GIS applications. In this filed the network capabilities of GIS such as shortest path computation is very useful. Graph theories play an important role in GIS network analysis. Various theories such as the algorithms of computing shortest path have ever been used in different cases of graph problems. But for some important cases, there is not a good solution in primal graph. For using of dual spaces, at first the problem will be sent to a proper dual space and then after solving, the answers will come back to the primal space. In this paper, different types of dual graphs used in different sciences such as GIS, have been explained by authors. The dual graph concept for two particular problems in route specification: modeling the different costs of turns in crosses and shortest path finding between non-point origin and destination, have been used. As known, the travel time on crosses in right turning is less than left turning. In this paper it is propounded that linear dual graph can be used for modeling the left turn and right turn in a city network. A solution for finding the shortest path between non-point origin and destination was proposed. In many cases the destination or origin of the trip is not a specific point. It was shown that by changing the structure of the primal graph and its adjacent matrix, the linear or polygonal destination could be converted to a specific point. The proposed approach was implemented on the street map of a municipal district in City of Tehran. The developed application illustrated the usefulness and positive effect of discussed approach in transportation network routing.

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

  • Graph
  • Dual graph
  • Best path
  • Transportation network
  • GIS