Khai thác thông tin tình trạng ùn tắc giao thông từ dữ liệu GPS - Trường hợp thành phố Hồ Chí Minh

  • 1 month ago
  • 1 lượt xem
  • 0 bình luận

  • Ít hơn 1 phút để đọc

Giới thiệu

Bài báo này đề xuất giải pháp trích xuất thông tin hữu ích về tình trạng giao thông từ dữ liệu GPS thu thập được từ các thiết bị giám sát hành trình của phương tiện giao thông. Giải thuật gom cụm dựa trên mật độ được tích hợp vào trong quy trình khai thác dữ liệu để lọc ra các vị trí thường xuyên ùn tắc trong mạng lưới giao thông đô thị. Chúng tôi tiến hành thực nghiệm trên bộ dữ liệu thật phạm vi Thành phố Hồ Chí Minh và thu được kết quả khá hứa hẹn về mặt ứng dụng.

Thông tin tài liệu

Loại file: PDF , dung lượng : 1.35 M, số trang : 5 ,tên

Xem mẫu

Chi tiết

  1. 36 Journal of Transportation Science and Technology, Vol 20, Aug 2016 KHAI THÁC THÔNG TIN TÌNH TRẠNG ÙN TẮC GIAO THÔNG TỪ DỮ LIỆU GPS - TRƯỜNG HỢP THÀNH PHỐ HỒ CHÍ MINH MINING INFORMATION ABOUT TRAFFIC CONGESTIONS FROM GPS DATA – CASE STUDY OF HO CHI MINH CITY Lê Văn Quốc Anh Khoa CNTT, ĐH GTVT TP.HCM, anh@ut.edu.vn Tóm tắt: Bài báo này đề xuất giải pháp trích xuất thông tin hữu ích về tình trạng giao thông từ dữ liệu GPS thu thập được từ các thiết bị giám sát hành trình của phương tiện giao thông. Giải thuật gom cụm dựa trên mật độ được tích hợp vào trong quy trình khai thác dữ liệu để lọc ra các vị trí thường xuyên ùn tắc trong mạng lưới giao thông đô thị. Chúng tôi tiến hành thực nghiệm trên bộ dữ liệu thật phạm vi Thành phố Hồ Chí Minh và thu được kết quả khá hứa hẹn về mặt ứng dụng. Từ khóa: Dữ liệu hành trình GPS; khai thác dữ liệu; phát hiện ùn tắc. Abstract: This paper presents an approach to the discovery of useful information about traffic condition from GPS data obtained from vehicle tracking devices. A density - based clustering approach is intergrated into the data mining process to figure out the most likely areas of congestions in urban traffic networks. We performed experiments on real - life datasets of Ho Chi Minh City and obtained very promissing results for developing applications. Keywords: Gps trajectory data; data mining; congestion detection. 1. Giới thiệu Mặc dù tính ứng dụng của bài toán này là Khai thác dữ liệu là quá trình tìm kiếm và khá đa dạng nhưng việc xử lý trên dữ liệu GPS rút trích những thông tin tiềm ẩn có giá trị, hữu và rút trích được những thông tin có giá trị gặp ích từ một khối lượng dữ liệu khá lớn ban đầu. nhiều thách thức. Thứ nhất, với sự ổn định và Những thông tin được rút trích được gọi là tri tính chính xác tương đối, bản thân dữ liệu thức, là yếu tố quyết định giúp phát triển các dạng này xuất hiện khá nhiều điểm dữ liệu ứng dụng thông minh. Trong lĩnh vực giao nhiễu và mất mát thông tin [5]. Thứ hai, dữ thông vận tải, việc sử dụng kết quả từ việc liệu thu thập theo thời gian nên khối lượng dữ phân tích dữ liệu từ các thiết bị giám sát hành liệu để phân tích là khá lớn, có thể xem như là trình, dữ liệu xe con di dộng (FCD) và dữ liệu một dạng “Big Data”. Điểm cuối cùng là vấn điện thoại trực tuyến (FPD) đã đem lại những đề biểu diễn những tri thức khai thác được từ hiệu quả rõ rệt trong vấn đề giám sát và quản dữ liệu GPS. Rất khó để mô tả hay diễn dịch lý giao thông [1]. nếu không sử dụng các công cụ trực quan hoá [6]. Bài báo này đề cập đến bài toán phân tích hay khai thác dữ liệu hành trình thu thập được Bài báo này trình bày giải pháp hiệu quả từ các thiết bị thu GPS, gọi tắt là dữ liệu GPS, cho bài toán trích xuất thông tin về tình trạng để trích xuất những thông tin có giá trị và hữu ùn tắc giao thông từ dữ liệu GPS với các đóng ích về tình trạng ùn tắc giao thông của mạng góp sau: lưới giao thông trong đô thị. Nguồn của dữ  Mô hình hoá điểm ùn tắc giao thông liệu GPS khá đa dạng và phổ biến, thông dụng dựa trên khái niệm Cluster. nhất là từ các thiết bị thu GPS gắn trên các  Giải quyết vấn đề nhiễu bằng cách tách phương tiện giao thông hay thu thập qua phần điểm dữ liệu và gom cụm dựa trên mật độ. mềm viết cho các điện thoại thông minh. Việc khai thác dữ liệu GPS mang lại khá nhiều ứng  Trực quan hoá các điểm ùn tắc trên dụng hữu ích, như: dự báo tắc nghẽn giao bản đồ. thông [2], khai thác địa điểm quan trọng và lộ 2. Các khái niệm và công trình liên trình thông dụng từ dữ liệu GPS [3], quy quan hoạch sử dụng các lộ trình tối ưu [4]. 2.1. Mô hình hoá dữ liệu GPS
  2. 37 TẠP CHÍ KHOA HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI, SỐ 20 - 08/2016 Dữ liệu thô thu thập từ các thiết bị thu GPS gọi là GPS Log tồn tại dưới khá nhiều định dạng, trong đó thông dụng là ở định dạng file (CSV, GPX, KML,…) hoặc dạng bảng trong một hệ quản trị cơ sở dữ liệu quan hệ (Oracle, MS SQL Server,…), tham khảo hình 1. Hình 1. Minh hoạ GPS Log thu thập từ một thiết bị giám sát hành trình phương tiện giao thông. Hình 2. Minh hoạ một quỹ đạo GPS trích xuất từ GPS Log, khu vực TP.HCM, xuất phát từ Quận 10, qua Để có sự chuẩn hoá dữ liệu đầu vào cho giải Quận 2, và dừng ở Quận 7. thuật khai thác dữ liệu sau này, chúng tôi mô 2.2. Gom cụm dữ liệu dựa trên mật độ hình hoá dữ liệu GPS qua các khái niệm sau - Giải thuật DBSCAN đây: Giải thuật DBSCAN [7] là giải thuật gom  Toạ độ GPS: Được biểu diễn bởi bộ cụm dữ liệu dựa trên mật độ được đánh giá là bốn , trong đó: id là mã khá hiệu quả trong việc gom cụm điểm dữ liệu định danh của đối tượng chuyển động có yếu tố nhiễu. Ngoài ra, những đặc tính khác (phương tiện giao thông hoặc một điện thoại của giải thuật này rất phù hợp để được lựa có hỗ trợ GPS); lat là vĩ độ, lon là kinh độ; và chọn trong bài toán phát hiện điểm ùn tắc giao time là thời gian ghi nhận vị trí của đối tượng. thông, như: Không yêu cầu cung cấp trước số  GPS Log: Là một tập hợp các toạ độ lượng cụm (trong trường hợp này là số điểm GPS, có dạng {p1, p2, …pn}, với mỗi pi là một ùn tắc); phát hiện được điểm ùn tắc với dạng toạ độ GPS . hình học bất kỳ và có thể kết hợp với các cấu  Quỹ đạo GPS: Là một chuỗi gồm các trúc dữ liệu (như R* Tree [8]) để tăng tốc quá toạ độ GPS thu thập không ngắt quãng của trình xử lý với dữ liệu lớn. cùng một đối tượng chuyển động, có dạng p1 Do giải thuật này khá thông dụng nên bài  p2  …  pn, trong đó: pi.id = pj.id , 1 báo sẽ không trình bày chi tiết giải thuật này.  i, j  n; và 0 < pi+1.time - pi.time < T,  0 < Độc giả quan tâm có thể tham khảo ở [7]. i < n, với T là ngưỡng thời gian ngắt quãng Với những tính chất đã nêu ở trên, giải cho phép giữa hai lần thu thập toạ độ liên tiếp. thuật gom cụm dựa trên mật độ DBSCAN Với các khái niệm mô tả như trên thì các được lựa chọn cho hướng tiếp cận được đề điểm dữ liệu trong dữ liệu thô sẽ được biểu xuất trong bài báo này. diễn bằng các điểm GPS và dữ liệu đầu vào 2.3. Tình hình nghiên cứu gần đây cho các giải thuật khai thác dữ liệu sẽ là các Một số công trình liên quan đến bài toán quỹ đạo GPS được trích xuất từ GPS Log. khai thác dữ liệu GPS được công bố gần đây, Khái niệm quỹ đạo GPS có thể hình dung từ với các mục tiêu khác nhau: Ước lượng tốc độ hình 2. Chi tiết của quá trình trích xuất sẽ được di chuyển trung bình của dòng giao thông từ trình bày trong mục 4.1. dữ liệu hành trình GPS [9], phát hiện các dạng tắc nghẽn từ dữ liệu xe con lưu động (FCD) [10] hay khám phá đường đi ít tốn thời gian nhất [11]. Các giải pháp này chủ yếu dựa trên thống kê để ước lượng vận tốc trung bình của dòng giao thông và nếu áp dụng trên dữ liệu
  3. 38 Journal of Transportation Science and Technology, Vol 20, Aug 2016 thực nghiệm giới thiệu phần sau thì kết quả Dữ liệu thô ban đầu ở dạng GPS Log sẽ không tốt. Ngoài kỹ thuật thống kê, bài báo được tách thành các tập toạ độ GPS theo định này đề xuất sử dụng giải thuật gom cụm dựa danh của thiết bị. Các toạ độ GPS trong mỗi trên mật độ để loại bỏ nhiễu và tăng chất lượng tập được sắp xếp theo thứ tự thời gian để tạo kết quả, như phần thực nghiệm sẽ trình bày. thành một chuỗi toạ độ GPS cho mỗi đối 3. Nguồn dữ liệu thực nghiệm tượng chuyển động. Để thực hiện việc kiểm nghiệm quy trình Với một giá trị ngưỡng thời gian ngắt khai thác thông tin vị trí ùn tắc đề xuất ở trên, quãng T cho trước, chuỗi toạ độ được quét chúng tôi sử dụng dữ liệu GPS Log thu thập tuần tự để tìm các điểm cắt (điểm cắt là điểm từ các phương tiện vận tải cung cấp bởi công có khoảng cách thời gian đến điểm kế tiếp ty OTS cung cấp dịch vụ giám sát hành trình vượt qua ngưỡng T). Các phân đoạn thu được xe ô tô. Số lượng xe được giám sát hành trình giữa các điểm cắt chính là các quỹ đạo GPS. trong nguồn dữ liệu này là 411, khu vực thành Trong trường hợp dữ liệu GPS Log thu thập phố Hồ Chí Minh (TP.HCM). Thời gian thu từ các phương tiện giao thông thì ngưỡng thời thập dữ liệu trong vòng một tuần, từ gian T có thể chọn là từ 30 phút đến 1 giờ, đây 01/06/2015 đến 07/06/2015. là thời gian các xe vận tải dừng đỗ tại trạm, bến, bãi. Tuy nhiên, rõ ràng là giá trị của Hình 3 minh hoạ dữ liệu GPS Log được ngưỡng thời gian này được chọn tuỳ thuộc vào hiển thị trên bản đồ nền của TP.HCM. Có khá đặc thù của từng loại dữ liệu thu thập được. nhiều điểm nhiễu trong dữ liệu cần làm sạch. Các phân đoạn thu được từ bước xử lý nêu trên là các chuỗi toạ độ GPS đảm bảo tính liên tục về thời gian giữa hai điểm liên tiếp. Trong thực tế, một số trường hợp thiết bị thu GPS ghi nhận toạ độ GPS không chính xác, dẫn đến mất tính liên tục về không gian trong chuỗi toạ độ GPS. Hình 5 minh hoạ một toạ độ GPS nhiễu được ghi nhận. Hình 5. Minh hoạ một toạ độ GPS nhiễu nằm cách xa quỹ đạo di chuyển. Hình 3. Dữ liệu thô chưa qua tiền xử lý và làm sạch dữ liệu. Xuất hiện một số đoạn nối các điểm không Do khoảng cách thời gian giữa các lần thu đúng thực tế. thập toạ độ thường là khá bé (vài giây) nên việc loại bỏ các toạ độ nhiễu này không ảnh hưởng đến tính liên tục về thời gian trong chuỗi quỹ đạo. Để thuận lợi trong các bước xử lý sau, giai đoạn tiền xử lý dữ liệu sẽ loại bỏ các toạ độ GPS nhiễu bằng cách sử dụng một ngưỡng khoảng cách d. Tuỳ thuộc vào tốc độ tối đa của phương tiện và khoảng cách thời gian giữa hai lần thu thập toạ độ GPS liên tiếp mà chọn giá trị ngưỡng khoảng cách d phù hợp. Với khoảng cách thời gian là 10s thì d có thể chọn là 280m, giả định phương tiện chạy Hình 4. Dữ liệu thực nghiệm sau khi tiền xử lý loại bỏ với tốc độ dưới 100km/h. Hình 4 trình bày dữ các điểm nhiễu và tách các đoạn quỹ đạo. liệu thô sau bước phân đoạn và làm sạch. 4. Khai thác thông tin địa điểm ùn tắc Bước tiền xử lý dữ liệu chuyển đổi dữ liệu từ dữ liệu GPS thô GPS Log sang các quỹ đạo GPS với sự 4.1. Tiền xử lý và làm sạch dữ liệu đảm bảo về tính liên tục thời gian và không gian. Đây chính là đầu vào cho quy trình trích
  4. 39 TẠP CHÍ KHOA HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI, SỐ 20 - 08/2016 xuất thông tin vận tốc tức thời và khai thác địa ứng cử viên cho việc nhận diện vị trí ùn tắc. điểm ùn tắc sẽ được trình bày tiếp theo đây. Thách thức bây giờ là làm sao lọc ra được các 4.2. Trích xuất thông tin vận tốc tức điểm ùn tắc thực sự từ danh sách các ứng cử thời từ quỹ đạo GPS viên này. Đa số trường hợp thiết bị giám sát hành trình cũng ghi nhận vận tốc tức thời của phương tiện tại thời điểm thu thập thông tin về vị trí và lưu trữ vào GPS Log. Tuy nhiên một số trường hợp dữ liệu GPS Log không có thông tin về vận tốc tức thời (phần lớn dữ liệu ở dạng các file GPX hay KML). Trong các trường hợp này, vận tốc tức thời có thể được tính thông qua khoảng cách thời gian và không gian giữa hai điểm liên tiếp trong quỹ đạo. Khoảng cách không gian giữa hai toạ độ GPS được tính bằng hàm sau (công thức Hình 6. Các vị trí ghi nhận tốc độ tức thời của đối Haversine): tượng chuyển động thấp hơn ngưỡng vận tốc 5km/h. function getDistanceFromLatLon (p1, p2) { R = 6371; // Bán kính Trái đất (km) 4.3. DBSCAN tìm khu vực ùn tắc dLat = (p2.lat-p1.lat)* PI/180; Từ tập hợp các vị trí ghi nhận có phương dLon = (p2.lon-p1.lon)* PI/180; a = sin(dLat/2)^2 + tiện đi chậm, chúng tôi đề xuất sử dụng cos(p1.lat*PI/180)*cos(p2.lat*PI/180)* phương pháp gom cụm dữ liệu theo mật độ, sin(dLon/2)^2; với giải thuật DBSCAN để loại bỏ các điểm c = 2 * arcsin(sqrt(a)); ngoại biên. Điểm ngoại biên ở đây được hiểu return R * c; là các vị trí mà có hiện tượng phương tiện đi } chậm là ngẫu nhiên (xe dừng hay đi chậm có Các vị trí điểm có tốc độ thấp hơn một chủ đích…). ngưỡng vận tốc cho trước (ví dụ 5km/h) sẽ được lọc ra để tìm các vị trí thường xuyên ùn tắc. Hình 6 minh hoạ các vị trí có tốc độ di chuyển của các phương tiện trong bộ dữ liệu nghiên cứu của khu vực nội thành Thành phố Hồ Chí Minh có vận tốc di chuyển bé hơn 5km/h. Nhận xét rằng mặc dù vẫn phát hiện một số địa điểm có khả năng ùn tắc cao như giữa các giao lộ, các trục đường chính, nhưng có khá nhiều địa điểm được đánh dấu khá rời rạc, không tập trung. Sử dụng ngưỡng vận tốc để xác định các Hình 7. Kết quả sau khi dùng DBSCAN loại bỏ các điểm ngoại biên. vị trí trên mạng lưới giao thông mà phương tiện di chuyển chậm. Cần lưu ý rằng không Hai tham số quan trọng trong giải thuật phải vị trí nào phương tiện đi chậm cũng phải DBSCAN là khoảng cách Epsilon và số điểm là vị trí ùn tắc. Có những vị trí mà phương tiện nhỏ nhất để xác định một vùng có mật độ dày di chuyển chậm là bình thường, ví dụ xe đi vào (MinPts). Các tham số này được chọn bằng bến, xe dừng đèn đỏ, hay xe đi vào các đường phương pháp thử và sai; giá trị để kết quả gom nội bộ của khu dân cư. Tuy nhiên, việc phát cụm là tốt nhất cho bộ dữ liệu thí nghiệm là hiện các vị trí mà phương tiện đi chậm lại vẫn Epsilon = 0.01 và MinPts = 5. rất hữu ích trong bài toán phát hiện điểm ùn Hình 7 minh hoạ các vị trí ùn tắc được ghi tắc. Rõ ràng là các vị trí này chính là những nhận sau khi chạy giải thuật DBSCAN. Nhận
  5. 40 Journal of Transportation Science and Technology, Vol 20, Aug 2016 xét rằng các vị trí ùn tắc phát hiện được phần Tài liệu tham khảo lớn là ở các vòng xoay, ngã giao của trục [1] M. R. Evans, D. Oliver, X. Zhou, and S. Shekhar, đường chính và đường nhánh. “Spatial Big Data: Volume, Velocity and Veracity,” Big Data Tech. Technol. 5. Kết quả và đánh giá Geoinformatics, pp. 149–176, 2010. Kết quả chạy giải thuật DBSCAN trên bộ [2] F. Maier, R. Braun, F. Busch, and P. Mathias, dữ liệu nghiên cứu trả về thông tin 412 cụm, “Pattern-based short-term prediction of urban congestion propagation and automatic response,” đó chính là các vị trí thường xuyên ùn tắc được Traffic Eng. Control, vol. 49, no. 6, pp. 227–232, phát hiện. Để đánh giá tính hợp lý của kết quả, 2008. chúng tôi sử dụng phần mềm Quantum GIS [3] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, (http://www.qgis.org) để trực quan hoá từng “Mining interesting locations and travel điểm ùn tắc trên bản đồ nền để kiểm tra. sequences from GPS trajectories,” Proc. 18th Int. Conf. World wide web - WWW ’09, 2009. Hình 7 cho thấy sự phân bố của các vị trí [4] F. Bastani, Y. Huang, X. Xie, and J. W. Powell, ùn tắc được phát hiện. Các vị trí ùn tắc được “A Greener Transportation Mode: Flexible phóng lớn để kiểm tra. Ví dụ trong hình 8, các Routes Discovery from GPS Trajectory Data,” vị trí ùn tắc được phát hiện gần vòng xoay Proc. 19th ACM SIGSPATIAL Int. Conf. Adv. Geogr. Inf. Syst., pp. 405–408, 2011. Lăng Cha Cả đều nằm trên các giao lộ và trên [5] H. Jeung, H. Lu, S. Sathe, and M. L. Yiu, thực tế thường xuyên xảy ra ùn tắc. “Managing evolving uncertainty in trajectory databases,” IEEE Trans. Knowl. Data Eng., vol. 26, no. 7, pp. 1692–1705, 2014. [6] D. Zhang, K. Lee, and I. Lee, “Periodic Pattern Mining for Spatio-Temporal Trajectories: A Survey,” 2015 10th Int. Conf. Intell. Syst. Knowl. Eng., pp. 306–313, 2015. [7] M. Ester, H. Kriegel, J. S, and X. Xu, “A density- based algorithm for discovering clusters in large spatial databases with noise,” in KDD-96, 1996, pp. 226–231. [8] M. Ester, H. Kriegel, J. Sander, M. Wimmer, and X. Xu, “Incremental Clustering for Mining in a Data Warehousing Environment,” in VLDB Conference, 1998, pp. 323–333. [9] I. Barbosa, M. A. Casanova, C. Renso, and J. A. Hình 8. Các điểm thường xuyên ùn tắc được phát hiện F. de Macedo, “Average Speed Estimation For tại khu vực vòng xoay Lăng Cha Cả. Road Networks Based On GPS Raw 6. Kết luận và hướng phát triển Trajectories,” Iceis 2013, p. 511, 2013. [10] L. Xu, Y. Yue, and Q. Li, “Identifying Urban Bài báo này đề xuất quy trình khai thác Traffic Congestion Pattern from Historical dữ liệu GPS để trích xuất thông tin về tình Floating Car Data,” Procedia - Soc. Behav. Sci., trạng ùn tắc giao thông. Dữ liệu thực nghiệm vol. 96, no. Cictp, pp. 2084–2095, 2013. được thu thập từ các xe thực tế chạy trên các [11] E.H.C. Lu, W.C.Lee, and V.S.Tseng, “Mining tuyến đường của Thành phố Hồ Chí Minh. Kết fastest path from trajectories with multiple destinations in road networks,” Knowl. Inf. Syst., quả đạt được là rất hứa hẹn và trở thành nền vol. 29, no. 1, pp. 25–53, 2011. tảng cho các ứng dụng tìm đường thông minh Ngày nhận bài: 18/07/2016 có tính đến tình trạng giao thông sau này. Đây Ngày chuyển phản biện: 22/07/2016 cũng là hướng phát triển trong tương lai của Ngày hoàn thành sửa bài: 08/08/2016 hướng tiếp cận vừa trình bày. Ngày chấp nhận đăng: 16/08/2016 Lời cảm ơn Nghiên cứu này được hỗ trợ từ nguồn kinh phí nghiên cứu khoa học của Trường Đại học Giao thông vận tải TP. HCM (MS KH1504) 

Download

Xem thêm
Thông tin phản hồi của bạn
Hủy bỏ