بکارگیری الگوریتم های تطبیق نقشه به‌منظور استخراج اطلاعات ترافیکی از خطوط سیر حاصل از GPS با نرخ نمونه‌برداری پایین

شکری, وحید; عباسپور, رحیم علی

بکارگیری الگوریتم های تطبیق نقشه به‌منظور استخراج اطلاعات ترافیکی از خطوط سیر حاصل از GPS با نرخ نمونه‌برداری پایین

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

نویسندگان

¹ دانشجوی کارشناسی ارشد، دانشکده مهندسی نقشه برداری و اطلاعات مکانی، پردیس دانشکده های فنی، دانشگاه تهران، تهران، ایران

² استادیار دانشکده مهندسی نقشه برداری و اطلاعات مکانی، پردیس دانشکده های فنی، دانشگاه تهران، تهران، ایران

چکیده

از میان روشهای مختلف جمعآوری اطلاعات ترافیکی،GPS به علت هزینه پایین‌تر، دسترسی و فراوانی بیشتر، از محبوبیت خاصی برخوردار است. عامل اصلی اطمینان از پارامترهای ترافیکی محاسبه‌شدهاز خطوط سیرGPS، اطلاع از مکان صحیح خودرو بر روی قطعات جاده است. این عمل کلیدی توسط الگوریتمهای تطبیق نقشه صورت میگیرد.درصد بالایی از خطوط سیر GPS تولید شده از GPS تلفن همراه،خودروهای مجهز به GPS،ناوگان حملونقل عمومی و شبکههای اجتماعی با نرخ نمونهبرداری پایین دو تا شش دقیقه تولید میشوند. بنابراین تعیین یک الگوریتم تطبیق نقشه مناسب برایکاهش خطای دادههای مذکور ضروری بنظر میرسد. در این مقاله هدف، معرفی، مقایسه و تحلیل نتایج تطبیق دادههای خطوط سیر GPS با دو الگوریتم ST-matching و IVMM برای دادههای با نرخ پایین و سپس تهیه نقشه سرعت ترافیکی از دادههای تطبیق شده است. از ویژگیهای بارز الگوریتم ST-matching در نظرگرفتن همزمان توپولوژی و ویژگیهای مکانی ویژگی زمانی است. درروش IVMM نه‌تنها از اطلاعات مکانی و زمانی بلکه از یک استراتژی رأیمبنا به‌منظور مدلکردن وزن تأثیرات متقابل بین نقاطGPS بهرهگرفتهمیشود. به‌منظور تست و ارزیابی این دو الگوریتم از دادههای ناوگان حملونقل عمومی اتوبوس‌رانی شهر تهران با نرخ نمونهبرداری دو دقیقه استفاده‌شده است.الگوریتم ST-matching برای تطبیق هر نقطه نمونه برداری فقط یک نقطه قبل از آن را در نظر میگیرد و برای نقطه اول نقطه ماقبل وجود ندارد، بنابراین الگوریتم به نقطه شروع وابستگی زیادی دارد. الگوریتم IVMM با مدل‌سازی تأثیرات متقابل نقاط نمونهبرداری نتایج مؤثرتر و مستحکمتری را ارائه میدهد. تابع وزن فاصله نقش مهمی در الگوریتم IVMM ایفا میکند. با افزایش مقدار پارامتر بتا در ابن تابع دقت تطبیق نقشه نیز افزایش مییابد. دقت بهدستآمده از روش IVMM 88 % و روش ST-matching 73% است. نتایج حاصل از این مقاله نشان میدهدالگوریتم IVVM درمقایسه با ST-matching به‌طور قابل‌توجهی بهتر عمل مینماید.هم چنین در مواجهه با گردشهای UشکلIVVM نتایج بهتری را ارائه میدهد.

کلیدواژه‌ها

20.1001.1.20086598.1396.8.4.4.3

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

Using Map Matching Algorithms to Extract Traffic Information from Low Sampling Rate GPS Trajectories

نویسندگان [English]

Vahid Shokri ¹
Rahim Ali Abbaspour ²

¹ MSc. Grad., School of Surveying and Geospatial Engineering, College of Engineering, University of Tehran, Tehran, Iran

² Assistant Professor, School of Surveying and Geospatial Engineering, College of Engineering, University of Tehran, Tehran, Iran

چکیده [English]

GPS, among the various methods of traffic data collection has special popularity due to the low cost and wide access. The primary factor for reliability of determined parameters extracted GPS trajectories is the correct calculation of a vehicle location on a road segment, which is realized by a map-matching algorithm. High percent of GPS trajectories is taken from a variety of sources including mobile GPS, GPS equipped vehicles the, fleet public transport, and social networks are in low sampling rate between 2 to 6 minutes. So determining a suitable map matching algorithm to reduce data errors seems necessary. This paper aims to implement ST-matching and IVVM algorithms to match the GPS tracking data and extract traffic parameters and traffic map by matched trajectories. A special characteristics of ST-matching algorithm is to employ simultaneous spatial, temporal and topology analysis. IVMM algorithm not only considers the spatial and temporal information of a GPS trajectory but also devise a voting-based strategy to model the weighted mutual influences between GPS points. To evaluate these algorithms GPS trajectories with 2 minutes sampling rate of public fleet transport related to bus lines are used. ST-matching algorithm use only one point before each sampling point to match it there for the first point has not any before point, there is no the previous point, so the algorithm is highly dependent on the starting point. IVMM algorithm by modeling mutual influences between GPS points provides more effective and strong result. Distance Weight Function plays an important role in IVMM algorithm. By increasing the value of the parameter beta in Distance Weight function increases map matching accuracy. The obtained accuracy of the method of IVMM and the ST-matching is 88% 73% respectively. The results of this study show the IVMM algorithm outperforms the ST-matching method. Also In the face of U-turn IVMM gives better results.

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

Traffic information
GPS trajectory
map matching
IVMM
St-matching

مراجع

- دوباش، الف. (1393) «تطبیق مشاهدات جی. پی. اس بر نقشه به صورت برونخط"، پایان نامه کارشناسیارشد، دانشکده مهندسی کامپیوتر، دانشگاه صنعتیشریف، تهران.

- شهرداری تهران. معاونت وسازمان حملونقل و ترافیک (1391) «گزارش عملکرد حمل و نقل همگانی»، فصل پنجم عملکرد سامانه اتوبوسرانی، تهران.

- Aung, S. S. and Naing, T. T. (2014) "Mining data for traffic detection system using GPS_Enable mobile phone in mobile cloud infrastructure ", International Journal on Cloud Computing: Services and Architecture (IJCCSA), Vol. 4, No. 3, p. 12.

- Brakatsoulas, S., Pfoser, D., Salas, R. and Wenk, C. (2005) "On map-matching vehicle tracking data", Proceedings of the 31st International Conference on Very Large Data- bases, VLDB Endowment, pp. 853-864.

- Greenfeld, J. S. (2002) "Matching GPS observations to locations on a digital map", Transportation Research Board 81st Annual Meeting, Washington D.C, p.13.

- Kim, S. and Kim, J. (2001) "Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system", Industrial Electronics, IEEE Transactions, Vol. 48, No, 2, pp. 432-441.

- Leduc, G. (2008) "Road traffic data: Collection methods and applications", European Commission, Joint Research Center, Institute of Prospective Technological Studies, JRC 47967.

- Li, H., Kulik, L. and Ramamohanarao, K. (2015) "Robust inferences of travel paths from GPS trajectories", International Journal of Geographical Information Science. Vol. 29, No.12, pp. 2194-2222.

- Lou, Y., Zhang, Ch. and Zheng, Y. (2009) "Map-matching for low-sampling-rate GPS trajectories", Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM. p. 352.

- Marchal, F., Hackney, J. and Axhausen, K. W. (2005) "Efficient map matching of large global positioning system data sets: Tests on speed-monitoring experiment in Zürich", Transportation Research Record: Journal of the Transportation Research Board. Vol. 1, No. 1935. pp. 93-100.

- Miwa, T., Kiuchi, D. and Yamamoto, T. (2012) "Development of map matching algorithm for low frequency probe data", Transportation Research Part C: Emerging Technologies, Vol. 22, pp. 132-145.

- Newson, P. and Krumm, J. (2009) "Hidden Markov map matching through noise and sparseness", Proceedings of the 17th ACM SIGSPATIAL International Conference On Advances In Geographic Information Systems, Washington, New York, ACM. pp. 336-343.

- Quddus, M. A., Ochieng, W. and Noland, R. B. (2007) "Current map-matching algorithms for transport applications: State-of-the art and future research directions", Transportation Research Part C: Emerging Technologies. Vol. 15, No. 5, pp. 312-328.

- Rauschert, I., Agrawal, P., Sharma, R., Fuhrmann, S., Brewer, I. and MacEachren, A. (2002) "Designing a human-centered, multimodal GIS interface to support emergency management", Proceedings of the 10th ACM international symposium on Advances in geographic information systems, McLean, Virginia, USA, ACM. pp. 119-124.

- Syed, S. and Cannon, M. E. (2004) "Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons", In Proceedings of the Institute of Navigation (ION) National Technical Meeting, 26-28 January, California, USA.

- Tao, S., Manolopoulos, V., Rodriguez, S. and Rusu, A. (2012) "Real-time urban traffic state estimation with A-GPS mobile phones as probes", Journal of Transportation Technologies. Vol. 2, No. 01, p. 22.

- Wang, D., Wang, Zh., Li, X. and XIAO, Zh. (2014) "A Map Matching Algorithm to Eliminate Miscalculation Based on Low-Sample-Rate Data", 3rd International Conference on Computer Science and Service System, Atlantis Press.

- Wu, D., Zhu, T., Lv, W. and Gao, X. (2007) "A heuristic map-matching algorithm by using vector-based recognition", Computing in the Global Information Technology, 2007. ICCGI 2007, International Multi-Conference on, IEEE. pp. 18-24.

- Yin, H. and Wolfson, O. (2004) "A weight-based map matching method in moving objects databases", Scientific and Statistical Database Management, 2004. Proceedings, 16th International Conference on, Washington, DC, USA, IEEE. pp. 437-438.

- Yuan, J., Zheng, Y., Zhang, C., Xie, X. and Sun, G-Z. (2010) "An interactive-voting based map matching algorithm", Proceedings of the 2010 Eleventh International Conference on Mobile Data Management, IEEE Computer Society. pp. 43-52.

- Zeng, Z., Zhang, T., Li, Q. and Wu, Z. (2015) "Curvedness feature constrained map matching for low-frequency probe vehicle data" , International Journal of Geographical Information Science, Vol. 30. No. 4, pp. 1-31.

- Zhou, P., Jiang, S. and Li, M .(2015) "Urban Traffic Monitoring with the Help of Bus Riders", Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on, Columbus, OH, USA, IEEE. p. 21-30.