مروري بر روش هاي مسيريابي قطعي و ابتكاري مورد استفاده در GIS

Survey on Certain and Heuristic Route Finding Algorithms in GIS

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

Traffic condition is one of the most important issues in urban transportation system of large cities, because it affects other important areas directly and indirectly. For example, water and air pollution as an environmental issue and physical or mental health of citizens as a health issue. Suggesting best routes based on different criteria such as traffic condition is one of the ways to reduce urban traffic, implicitly. In GIS, best routes can be suggested to users based on different algorithms that have been developed so far, to move in urban road network, and consider different costs, travel time, traffic, distance and other factors. Aim of this paper is reviewing route finding algorithms in GIS. For this purpose, algorithms are investigated in two categories, deterministic and heuristic algorithms. Advanced route finding problems which are closer to the real world problems are also described. Finally, a comparison between algorithms are done based on different parameters so that researchers can find the best suited algorithm based on their requirement.