ارائه سرویس توصیه مسیر بر اساس رتبه‌بندی خط سیر کاربران محلی

امروزه مجهز شدن دستگاه های همراه به فنّاوری های مدرن مکان یابی، باعث تحولی در عرصه ی فناوری اطلاعات مکانیزمانی و ظهور مجموعه داده خطوط سیر مکانی(spatial trajectory) شده است. وجود حجم زیادی از خطوط سیر مکانی، فرصتی برای ارائه سرویس های متنوع مکان مبنا از طریق تجهیزات همراه فراهم می کند. یکی از مهم ترین و کاربردی ترین سرویس های مکان مبنا، سرویس های توصیه مسیر زمان مند به کاربران ناآشنا به منطقه هستند. یافتن بهترین مسیر، یکی از مسائل رایج و مبتلابه زندگی کنونی برای هدایت کاربر جهت رسیدن به مقصد است. در تحقیق حاضر جهت یافتن مسیر بهینه، ابتدا با رتبه بندی خط سیر کاربران با استفاده از الگوریتم hits، کاربران آشنا به منطقه یا به اصطلاح کاربران محلی و قطعه خیابان های مورد تردد اکثر کاربران محلی یا قطعه خیابان های محلی استخراج شد. سپس با هدف ارائه یک مسیریابی تقریبی گرافی تحت عنوان گراف محلی ایجاد شد. مرکز قطعه خیابان های محلی به عنوان گره های آن و یال های آن بر اساس دنباله ی ترتیبی قطعه خیابان های محلی از خط سیر کاربران به دست می آید. پس ازآن با به کارگیری الگوریتم دایجسترا بر روی شبکه راه اصلی و مسیر تقریبی به دست آمده، کوتاه ترین مسیر بین بر اساس این گراف از دو مرحله مسیریابی برای به دست آوردن مسیر بهینه استفاده شده است. برای پیاده سازی و آزمون، داده های مورداستفاده از خط سیر 100 کاربر متحرک در منطقه شش شهر تهران به مدت سه ماه به صورت روزانه با استفاده از تلفن های همراه مجهز به gps جمع آوری شده است. برای ارزیابی عملکرد مسیریابی دومرحله ای، میزان زمان سفر در مسیر پیشنهادی نسبت به کوتاه ترین مسیر دایجسترا برای طول های مختلف و کاربرانی با سطح آگاهی های مختلف از منطقه، به طور تجربی مقایسه شد. بر این اساس زمان سفر در روش پیشنهادی نسبت به کوتاه ترین مسیر حدود 62 درصد کاهش یافت.

Route recommendation based on local users’ trajectories

Large amount of users rsquo; trajectories, is an emerging source of inexpensive data that can be used to provide an opportunity to present route recommendation service to the unfamiliar users within the area. In this study, with the aim of finding the optimal route, we first extract both local users and local road segments data sets by ranking them via HITS algorithm. In this model, a hub is a user who many time has crossed many road segments of a region, and an authority is a road segment that has been crossed by many users. Therefore, users rsquo; travel experiences (hub scores) and the interests of road segments (authority scores) have a mutual reinforcement relation. We also propose a novel approach in which the basic unit of routing is separate road segment instead of GPS trajectory segment. Moreover, to provide the approximate routing, we create a local graph. The center of the local road segments are considered as nodes and are based on local streets sequence arrange the pieces obtained from the trajectory of the user as edges of local graph. According to this graph, two steps of routing are used to obtain the optimal path. Then using Dijkstra's algorithm on the main road network and obtained an approximate route, shortest route between two local road segments based on this graph is used to obtain the optimal route. To implement and test, used data, from the trajectories of moving users in Tehran, has been gathered for 3 months on daily basis. To evaluate performance of the twostep routing, we experimentally compared the travel time in proposed route to Dijkstra rsquo;s shortest path for different lengths and users with different levels of regional knowledge. The travel time in the proposed method was decreased 60 percent compare to shortest route.