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

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

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

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.