ارايه سرويس توصيه مسير بر اساس رتبه‌بندي خط سير كاربران محلي

Route recommendation based on local users’ trajectories

امروزه مجهز شدن دستگاه‌هاي همراه به فنّاوري‌هاي مدرن مكان‌يابي، باعث تحولي در عرصه‌ي فناوري اطلاعات مكاني-زماني و ظهور مجموعه داده‌ خطوط سير مكاني(Spatial Trajectory) شده است. وجود حجم زيادي از خطوط سير مكاني، فرصتي براي ارايه سرويس‌‌هاي متنوع مكان‌مبنا از طريق تجهيزات همراه فراهم مي‌كند. يكي از مهم‌ترين و كاربردي‌ترين سرويس‌هاي مكان‌مبنا، سرويس‌هاي توصيه مسير زمان‌‌مند به كاربران ناآشنا به منطقه هستند. يافتن بهترين مسير، يكي از مسايل رايج و مبتلابه زندگي كنوني براي هدايت كاربر جهت رسيدن به مقصد است. در تحقيق حاضر جهت يافتن مسير بهينه، ابتدا با رتبه‌بندي خط سير كاربران با استفاده از الگوريتم HITS، كاربران آشنا به منطقه يا به‌اصطلاح " كاربران محلي" و قطعه خيابان‌هاي مورد تردد اكثر كاربران محلي يا "قطعه خيابان‎‌هاي محلي" استخراج ‌شد. سپس با هدف ارايه يك مسيريابي تقريبي گرافي تحت عنوان گراف محلي ايجاد شد. مركز قطعه خيابان‌هاي محلي به‌عنوان گره‌هاي آن و يال‌هاي آن بر اساس دنباله‌ي ترتيبي قطعه خيابان‌هاي محلي از خط سير كاربران به دست مي‌آيد. پس‌ازآن با به‌كارگيري الگوريتم دايجسترا بر روي شبكه راه اصلي و مسير تقريبي به‌دست‌آمده، كوتاه‌ترين مسير بين بر اساس اين گراف از دو مرحله مسيريابي براي به دست آوردن مسير بهينه استفاده‌شده است. براي پياده‌سازي و آزمون، داده‌هاي مورداستفاده از خط سير 100 كاربر متحرك در منطقه شش شهر تهران به مدت سه ماه به‌صورت روزانه با استفاده از تلفن‌هاي همراه مجهز به GPS جمع‌آوري‌شده است. براي ارزيابي عملكرد مسيريابي دومرحله‌اي، ميزان زمان سفر در مسير پيشنهادي نسبت به كوتاه‌ترين مسير دايجسترا براي طول‌هاي مختلف و كاربراني با سطح آگاهي‌هاي مختلف از منطقه، به‌طور تجربي مقايسه شد. بر اين اساس زمان سفر در روش پيشنهادي نسبت به كوتاه‌ترين مسير حدود 62 درصد كاهش يافت.

Large amount of users’ 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’ 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 two-step routing, we experimentally compared the travel time in proposed route to Dijkstra’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.