Luận văn Phát triển thuật toán tìm đường cho Nền tảng cung cấp dịch vụ địa chỉ Việt Nam

FIMO), khoa Công nghệ thông tin, trường Đại học Công nghệ - ĐHQGHN đã tạo điều kiện giúp đỡ tôi hoàn thành luận văn. Cuối cùng, tôi muốn gửi lời cảm ơn sâu sắc nhất đến bố mẹ và những người thân trong gia đình, những người luôn ủng hộ con đường tôi đã lựa chọn, giúp đỡ và động viên tôi vượt qua những khó khăn trong cuộc sống. Tuy đã có những cố gắng nhất định nhưng do kiến thức và thời gian có hạn nên chắc chắn luận văn này còn nhiều thiếu sót và hạn chế nhất định. Kính mong nhận được sự góp ý của thầy cô. Khóa luận này được hỗ trợ bởi đề tài nghiên cứu ứng dụng và phát triển công nghệ cấp quốc gia: "Nghiên cứu xây dựng Nền tảng cung cấp dịch vụ dữ liệu địa chỉ Việt Nam phục vụ phát triển các ứng dụng dân sinh”, Mã số: ĐTCT-KC-4.0-03/19/25. Hà Nội, ngày tháng năm 2020 Học viên Hà Đức Văn 2 TÓM TẮT Tóm tắt: Trong thời đại chứng kiến những sự phát triển vượt bậc của các hệ thống công nghệ thông tin, các hệ thống bản đồ số cũng có những bước tiến lớn, đóng góp một vai trò quan trọng trong cuộc sống hiện đại. Nắm bắt thực trạng và nhu cầu sử dụng bản đồ số ở Việt Nam cho mục đích tìm kiếm thông tin địa chỉ, tìm đường,.. Nền tảng bản đồ số VMap ra đời với vai trò tiên phong trong lĩnh vực bản đồ sô tại Việt Nam. Một trong những thách thức trong việc phát triển chức năng chỉ đường của VMap đó chính là ước tính tốc độ di chuyển thực tế. Thực trạng về việc sử dụng phương tiện cá nhân và vấn đề đô thị hóa đã dẫn đến tình trạng giao thông tại các thành phố lớn trở nên vô cùng phức tạp khi thường xuyên xảy ra ùn tắc, mật độ phương tiện cao. Điều này dẫn đến tốc độ di chuyển trên từng đoạn đường vào những thời điểm khác nhau có sự khác biệt rõ rệt. Tuy chức năng chỉ đường của VMap đã đưa ra tốc độ di chuyển bằng những tính chất không đổi của đoạn đường như loại đường, các biển báo hạn chế tốc độ nhưng như thế là chưa đủ để đảm bảo độ chính xác. Luận văn này thực hiện nghiên cứu, phát triển công cụ ước tính tốc độ di chuyển trong thực tế dựa trên dữ liệu giao thông cho VMap. Luận văn bao gồm các thành phần chính là: (1) tìm hiểu những công nghệ, nghiên cứu về tính toán tốc độ di chuyển trên thực tế, (2) Đề xuất quy trình xây dựng thuật toán sử dụng Google Traffic Tiles để ước lượng thời gian di chuyển thực tế,(3) Xây dựng bộ dữ liệu thử nghiệm và đánh giá thử nghiệm các mô hình, (4) Triển khai và đánh giá hiệu quả của thuật toán. Từ khóa: VMap, tốc độ di chuyển, tìm đường 3 LỜI CAM ĐOAN Tôi xin cam đoan luận văn “PHÁT TRIỂN THUẬT TOÁN TÌM ĐƯỜNG CHO NỀN TẢNG CUNG CẤP DỊCH VỤ ĐỊA CHỈ VIỆT NAM” là công trình nghiên cứu của bản thân dưới sự hướng dẫn của TS. Bùi Quang Hưng. Tất cả những tham khảo từ nghiên cứu liên quan đều được trích dẫn một cách rõ ràng trong danh mục tài liệu tham khảo. Không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Hà Nội, ngày tháng năm 2020 Học viên Hà Đức Văn 4 MỤC LỤC TÓM TẮT ............................................................................................................. 2 DANH MỤC BẢNG BIỂU .................................................................................. 6 DANH MỤC HÌNH ẢNH ................................................................................... 7 DANH MỤC TỪ VIẾT TẮT .............................................................................. 8 MỞ ĐẦU ............................................................................................................... 9 CHƯƠNG 1. GIỚI THIỆU CHUNG ............................................................. 11 1.1 Giới thiệu chung về VMap và chức năng chỉ đường của VMap. ........ 11 1.1.1 Giới thiệu VMap ............................................................................... 11 1.1.2 Chức năng chỉ đường của VMap .................................................... 12 1.2 Vấn đề gặp phải với chức năng chỉ đường của VMap ......................... 12 1.2.1 Vấn đề gặp phải do thiếu dữ liệu tín hiệu giao thông .................... 13 1.2.2 Vấn đề gặp phải do thiếu dữ liệu lưu lượng giao thông ................ 15 CHƯƠNG 2. CÁC NGHIÊN CỨU, CÔNG NGHỆ LIÊN QUAN .............. 18 2.1 Một số phương pháp tính toán tốc độ di chuyển thực tế. .................... 18 2.1.1 Thu thập thông tin chia sẻ từ người dùng ...................................... 18 2.1.2 Tính toán dựa trên công nghệ đo trực tiếp .................................... 18 2.1.3 Tính toán từ dữ liệu vị trí của phương tiện .................................... 20 2.2. Giới thiệu tổ chức Open Geospatial Consortium (OGC) và chuẩn Web Map Tile Service (WMTS) .............................................................................. 21 2.2.1 Giới thiệu tổ chức Open Geospatial Consortium (OGC).............. 21 2.2.2 Giới thiệu chuẩn Web Map Tile Service (WMTS) ........................ 21 2.3. Giới thiệu về Google Map ................................................................. 22 2.4. Giới thiệu về Graphhopper ............................................................... 23 2.5. Giới thiệu về Javascript và NodeJS ................................................. 24 2.5.1. Giới thiệu, lịch sử phát triển Javascript ........................................ 24 2.5.2 Giới thiệu về NodeJS ........................................................................ 25 5 2.6. Giới thiệu về Python và các thư viện, bộ thư viện sử dụng ........... 26 2.6.1. Giới thiệu về Python ........................................................................ 26 2.6.2 Bộ thư viện Scikit-Learn (sklearn) .................................................. 27 2.6.3 Flask ................................................................................................... 28 2.7. Giới thiệu RNN .................................................................................. 29 CHƯƠNG 3. ĐỀ XUẤT PHƯƠNG PHÁP .................................................... 31 3.1 Thu thập dữ liệu Google Traffic Tiles ................................................... 31 3.2 Xây dựng thuật toán tìm đường đi nhanh nhất theo thời gian ........... 34 3.2.1 Đề xuất phương pháp tìm đường .................................................... 34 3.2.2 Đề xuất Thuật toán tìm đường đi nhanh nhất ............................... 38 CHƯƠNG 4. TRIỂN KHAI, THỰC NGHIỆM VÀ ĐÁNH GIÁ ................ 43 4.1 Xây dựng mô hình ước lượng thời gian di chuyển theo tình trạng giao thông ........................................................................................................................... 43 4.1.1 Xây dựng bộ dữ liệu thử nghiệm ..................................................... 43 4.1.2 Thử nghiệm và tìm mô hình hiệu quả nhất .................................... 43 4.2 Triển khai công cụ thu thập bộ dữ liệu Google Traffic Tiles .............. 46 4.3 Triển khai thuật toán cho Nền tảng cung cấp dịch vụ địa chỉ Việt Nam VMap .......................................................................................................................... 46 CHƯƠNG 5. KẾT LUẬN VÀ ĐỊNH HƯỚNG .............................................. 51 Kết quả đạt được ........................................................................................... 51 Định hướng phát triển tương lai .................................................................. 51 Tài liệu tham khảo ............................................................................................. 52 6 DANH MỤC BẢNG BIỂU Bảng 3.1. Thông số chi tiết Google Traffic Tiles ................................................ 31 Bảng 3.3. Thông tin thử nghiệm tải về dữ liệu .................................................... 33 Bảng 3.4. Các thông số truy vấn có thể gửi lên ................................................... 36 Bảng 3.5. Các thông số truy vấn có thể gửi lên ................................................... 37 Bảng 4.1. Kết quả thử nghiệm ............................................................................. 45 Bảng 4.2. Kết quả thử nghiệm thực tế ................................................................. 48 7 DANH MỤC HÌNH ẢNH Hình 1.1. Ví dụ chức năng chỉ đường của VMap ................................................ 12 Hình 1.2. Ví dụ về việc quản lý, chỉnh sửa biển báo hiệu giao thông trên VMap ............................................................................................................................. 14 Hình 1.3. Vấn đề gặp phải với chức năng tìm đường của VMap ........................ 14 Hình 1.4. Tối ưu đồ thị định tuyến của chức năng chỉ đường VMap [6] ............ 16 Hình 2.1. WMTS chia bản đồ ra làm các mảnh .................................................. 22 Hình 2.2. Giao diện trình diễn của GraphHoper ................................................ 24 Hình 2.3. Ví dụ ứng dụng Hello World trên bộ thư viện Flask ........................... 28 Hình 2.4. Ví dụ ứng dụng Hello World trên bộ thư viện Flask ........................... 29 Hình 2.5. Ví dụ về một mạng nơ-ron RNN .......................................................... 30 Hình 3.1. Dữ liệu giao thông của Google hiển thị trên nền tảng dữ liệu VMap . 32 Hình 3.2. Dữ liệu ranh giới hành chính .............................................................. 33 Hình 3.3. Một phần dữ liệu thu thập được .......................................................... 34 Hình 3.4. Kiến trúc hệ thống tìm đường mới ....................................................... 35 Hình 3.5. Ví dụ một kết quả tìm đường được trả về bằng API mới ..................... 38 Hình 3.6. Hệ thống đường của VMap và Google không hoàn toàn trùng khớp . 40 Hình 3.7. Ví dụ trích xuất thông tin từ một Tile .................................................. 40 Hình 3.8. Các mức độ giao thông của Google Traffic ........................................ 41 Hình 3.9. Quy trình của Thuật toán tìm đường đi nhanh nhất ............................ 42 Hình 4.1. Quy trình xây dựng bộ dữ liệu thử nghiệm .......................................... 43 Hình 4.2. Quy trình xây dựng bộ dữ liệu thử nghiệm .......................................... 45 Hình 4.3. Tiến trình thu thập bộ dữ liệu Google Traffic Tiles được khởi tạo ..... 46 Hình 4.4. PM2 được khai báo khởi động cùng hệ thống ..................................... 46 Hình 4.5. Thử nghiệm dịch vụ tìm đường mới trên ứng dụng nền tảng web VMap tại VMap.vn .......................................................................................................... 47 Hình 4.6. Thử nghiệm tìm đường tương tự trên nền tảng Google Map .............. 48 Hình 4.7. Thử nghiệm dịch vụ tìm đường mới trên ứng dụng nền tảng di động Android ................................................................................................................ 49 8 DANH MỤC TỪ VIẾT TẮT Ký hiệu Ý nghĩa API Application Programming Interface – giao diện lập trình ứng dụng CSDL Cơ sở dữ liệu ĐHQGHN Đại học Quốc gia Hà Nội OGC Tổ chức địa không gian Open Geospatial Consortium OSM OpenStreetMap WMTS Chuẩn Web Map Tile Service 9 MỞ ĐẦU Hệ tri thức Việt số hóa [1] là đề án của Chính phủ Việt Nam với mục tiêu xây dựng một hệ tri thức tổng hợp trong mọi lĩnh vực, góp phần thúc đẩy, tạo điều kiện để mọi người dân học tập suốt đời, làm chủ tri thức, tăng cường nghiên cứu sáng tạo, ứng dụng tiến bộ khoa học công nghệ, thúc đẩy phát triển đất nước. Đề án được xây dựng và cập nhật theo hình thức xã hội hóa, thu hút và khuyến khích mọi người dân và doanh nghiệp tham gia, với vai trò vừa khai thác vừa đóng góp để làm giàu các tài nguyên tri thức số hóa của Việt Nam. Góp phần khơi dậy, lan toả niềm đam mê khoa học và công nghệ, khát vọng sáng tạo, cống hiến của mọi người trong việc tạo lập và phổ biến tri thức. Đề án hướng tới phổ cập thông tin khoa học và công nghệ cho mọi tầng lớp người dân trong xã hội, nhất là các vùng nông thôn, vùng sâu, vùng xa; học sinh, sinh viên, người lao động. Một trong những nội dung quan trọng của Đề án là Xây dựng nền tảng Bản đồ số Việt Nam do Đại học Quốc gia Hà Nội chủ trì. Bản đồ số Việt Nam sẽ là nền tảng cơ bản để trên đó các nhà phát triển xây dựng các ứng dụng dân sinh phục vụ các nhu cầu khác nhau của cộng đồng như tìm kiếm vị trí, địa điểm, địa chỉ, du lịch, văn hóa, giáo dục, y tế, Một trong những dịch vụ được sử dụng nhiều nhất và cũng là quan trọng nhất của VMap là dịch vụ tìm đường. Người dùng thường muốn tìm đường đi có khoảng thời gian di chuyển ngắn nhất thay vì tìm đường đi ngắn nhất. Đây là xu thế chung của tất cả các dịch vụ chỉ đường hiện có trên thị trường như Google Map, Bing Map, Here Map, TomTom, Việc ước lượng thời gian di chuyển của người dùng của VMap đang rất không chính xác nên chưa thế áp dụng để tìm đường đi ngắn nhất theo thời gian. Tuy nhiên, do thiếu dữ liệu tín hiệu giao thông và chưa có dữ liệu lưu lượng giao thông thực tế để xây dựng thuật toán, kết quả đầu ra của dịch vụ tìm đường đang cho ra ước lượng thời gian di chuyển rất không chính xác. Luận văn này tập trung vào việc Phát triển thuật toán tìm đường đi nhanh nhất theo thời gian cho Nền tảng cung cấp dịch vụ địa chỉ Việt Nam VMap bằng cách sử dụng dữ liệu lưu lượng giao thông từ ảnh Google Traffic Tiles với các mục tiêu cụ thể sau: - Xây dựng công cụ thu thập bộ dữ liệu Google Traffic Tiles - Xây dựng thuật toán tìm đường đi nhanh nhất theo thời gian cho Nền tảng cung cấp dịch vụ địa chỉ Việt Nam VMap 10 - Triển khai thuật toán cho Nền tảng cung cấp dịch vụ địa chỉ Việt Nam VMap và đánh giá hiệu quả sử dụng Nội dung trình bày của luận văn gồm các phần sau: - Chương 1: Giới thiệu chung. Giới thiệu khái quát về Nền tảng dữ liệu Bản đồ số Việt Nam, cũng như các vấn đề còn tồn đọng trong hệ thống chỉ đường, dẫn của VMap. - Chương 2: Các nghiên cứu và công nghệ liên quan. Giới thiệu về các kiến thức, công cụ liên quan đến khóa luận. - Chương 3: Đề xuất phương pháp. Nghiên cứu, phát triển quy trình tìm đường đi ngắn nhất theo thời gian. - Chương 4: Triển khai thực nghiệm và đánh giá. Tiến hành triển khai quy trình và đánh giá kết quả thu được. - Chương 5: Kết luận và định hướng. Tổng kết lại các nội dung đã trình bày trong chương trước, kết quả đã được và định hướng phát triển tiếp theo. 11 CHƯƠNG 1. GIỚI THIỆU CHUNG 1.1 Giới thiệu chung về VMap và chức năng chỉ đường của VMap. 1.1.1 Giới thiệu VMap VMap[2] - Nền tảng dữ liệu Bản đồ số Việt Nam được ra mắt vào ngày 01/10/2019. Hiện VMap có hơn 23,4 triệu dữ liệu địa chỉ trên cả nước. Bên cạnh các tính năng cơ bản như: tìm kiếm địa chỉ, tìm đường, VMap sẽ đi theo một hướng đi khác biệt, đó là hiển thị lớp bản đồ riêng của các lĩnh vực trong cuộc sống và hiển thị địa chỉ chi tiết tới từng số nhà, dù ở thành thị hay miền núi, vùng sâu, vùng xa. Để thu thập dữ liệu bản đồ, trong hơn 3 tháng, hơn 120.000 nhân viên Bưu điện và đoàn viên, thanh niên trên cả nước đã tích cực tới từng khu phố, thôn bản để thu thập thông tin. Các dữ liệu gồm địa chỉ chi tiết của địa điểm (số nhà, đường phố, hẻm, xóm) và ghi chú về loại đối tượng (nhà hàng, nhà dân, ngân hàng, chợ,) đều được ghi lại[1]. Ngoài ra còn có một lượng dữ liệu rất lớn được đóng góp bởi người dùng thông qua nền tảng OpenStressMap và ứng dụng VMap Contributor. Sau khi xác nhận thông tin chuẩn, dữ liệu sẽ được tích hợp và đưa lên bản đồ số VMap. Một trong những lớp dữ liệu quan trọng của nền tảng bản đồ số VMap là lớp dữ liệu đường. Dữ liệu đường của VMap được lưu trữ theo phương pháp tổ chức dữ liệu của OpenStreetMap [3] gồm 4 thành phần chính là tag, node, way, relation cụ thể như sau: Tag: Tag có cấu trúc gồm khóa (key) và giá trị (value) thể hiện đặc điểm của các đôi tượng. Không có giới hạn về hình dạng của tag, vì vậy chúng có thể được sử dụng để đại diện cho bất kỳ thông tin gì. Việc sử dụng thành phần này là hoàn toàn dễ dàng khi không có bất kỳ quy định nào cho khóa và giá trị [4]. Node: Một node là thể hiện của một vị trí trong thế giới thực đến bản đồ số. Nó được xác định bởi một vĩ độ và một kinh độ kèm một định danh duy nhất. Các nút là các thực thể duy nhất có nghĩa là lưu trữ các vị trí địa lý, do đó nó được sử dụng để xây dựng nên các yếu tố khác như way hay relation. Đặc điểm của các node có thể được thể hiện bằng các tag của nó. Như là biển báo, đèn tín hiệu, các địa điểm công cộng như trạm xăng, nhà hàng,... [4] Way: Một way kết nối giữa các node gần nhau để biểu diễn một cấu trúc đơn giản. Một way có thể có cấu trúc mở hoặc khép kín . Một way khép kín là way có node đầu 12 tiên cũng là node cuối cùng trên way đó. Một way khép kín có thể là một khu vực được xác định phần lãnh thổ là phần bên trong của way khép kín. Một way mở là một way được mô tả tuyến tính không chia sẻ node đầu tiên và node cuối cùng thường để biểu thị những con đường bộ, sông suối hoặc đường sắt. [4] Relation: Một relation được sử dụng để xác định mối quan hệ giữa các node, way và các relation khác. Một thành viên của một mối quan hệ có thể tùy ý có một vai trò mô tả phần mà một tính năng cụ thể đóng trong một mối quan hệ. [4] 1.1.2 Chức năng chỉ đường của VMap Một trong những tính năng quan trọng nhất của VMap đó là chức năng chỉ đường. Đầu vào của hệ thống là tọa độ điểm đầu, điểm đích và phương tiện di chuyển. Hệ thống sẽ đưa ra kết quả là tuyến đường tối ưu theo tiêu chí khoảng cách di chuyển ngắn nhất hoặc thời gian di chuyển nhanh nhất. Ví dụ về giao diện của chức năng tìm kiếm trên VMap được thể hiện trong Hình 1.1. Hình 1.1. Ví dụ chức năng chỉ đường của VMap 1.2 Vấn đề gặp phải với chức năng chỉ đường của VMap Hiện tại thì chức năng chỉ đường của VMap sử dụng phương pháp tìm đường đi theo khoảng cách ngắn nhất [5]. Ngoài ra, việc ước lượng thời gian di chuyển của người dùng trên quãng đường đó gặp hai vấn đề chính là thiết dữ liệu tín hiệu giao thông và thiếu dữ liệu lưu lượng giao thông. Đây là những yếu tố quan trọng quyết định tới thời gian di chuyển của người dùng. Người dùng thường muốn tìm đường đi có khoảng thời gian di chuyển ngắn nhất thay vì tìm đường đi ngắn nhất. Đây là xu thế chung của tất cả các dịch vụ chỉ đường hiện có trên thị trường như Google Map, Bing Map, Here Map, 13 TomTom, Việc ước lượng thời gian di chuyển của người dùng của VMap đang rất không chính xác nên chưa thế áp dụng để tìm đường đi ngắn nhất theo thời gian. 1.2.1 Vấn đề gặp phải do thiếu dữ liệu tín hiệu giao thông Cùng với người điều khiển giao thông (Cảnh sát giao thông) thì tín hiệu giao thông đường bộ Việt Nam đứng vị trí rất quan trọng, không quá khi ta nói rằng chúng là cần nhất, không thể thiếu để duy trì trật tự, an toàn giao thông, giúp xe và phương tiện, người tham giao thông được lưu hành. Tín hiệu giao thông bao gồm: • Đèn tín hiệu điều khiển giao thông đặt ở các ngã ba, ngã tư đường phố đông đúc, phức tạp là dùng để báo hiệu, điều khiển sự đi lại của các loại xe cộ người đi đường, nhằm đảm bảo trật tự giao thông, ngăn ngừa tai nạn, làm cho sự giao lưu trong thành thị được dễ dàng, thuận lợi [6]. • Còn về biển báo hiệu đường bộ được chia thành 5 nhóm cơ bản sau đây: biển báo cấm; biển hiệu lệnh; biển báo nguy hiểm và cảnh báo; biển chỉ dẫn; biển phụ, biển viết bằng chữ [6]. Biển báo hiệu giao thông cung cấp chính xác quy định về giao thông đường bộ cho người tham gia giao thông. Dữ liệu tín hiệu giao thông khu vực Dịch Vọng Hậu, Cầu Giấy, Hà Nội: ● Dữ liệu của VMap: ~ 95 bản ghi ● Dữ liệu thực tế: ~ 200 bản ghi Với một lượng dữ liệu lớn và địa chỉ chi tiết tới từng ngõ, ngách như vậy thì VMap cũng phải có một hệ thống dẫn đường, chỉ đường đúng, nhanh và phù hợp với giao thông tại Việt Nam. Cùng với phản hồi từ người dùng cho thấy chức năng tìm đường của VMap vẫn chưa có độ chính xác cao. Đặc biệt là thiếu chính xác trong việc tìm đường dựa trên thông tin giao thông. Hiện tại, cách thi hành hiệu lực của biển báo lên mạng lưới đường của VMap vẫn đang thực hiện hoàn toàn thủ công. Do vậy, cần nhiều nhân lực, công sức để thi hành hiệu lực của biển báo. Với loại dữ liệu phức tạp đó, việc thu thập không hề dễ dàng vì các địa điểm về thông tin tín hiệu giao thông dễ dàng bị thay đổi, số lượng lại rất lớn. 14 Hình 1.2. Ví dụ về việc quản lý, chỉnh sửa biển báo hiệu giao thông trên VMap Cùng với đó có thể thấy dữ liệu về tín hiệu giao thông trên VMap còn thiếu nên chức năng tìm đường tối ưu thời gian theo tín hiệu giao thông hoạt động chưa có độ chính xác cao. Hình 1.3 có thể thấy rằng quãng đường đi qua khá nhiều đèn tín hiệu giao thông gây chậm trễ, tốn thời gian di chuyển của người dùng. Hình 1.3. Vấn đề gặp phải với chức năng tìm đường của VMap (Vùng khoanh đỏ là địa điểm thiếu hoặc không có dữ liệu về đèn tín hiệu giao thông) 15 Vấn đề này đã được đề xuất giải quyết trong khóa luận Nghiên cứu, phát triển phương pháp tìm đường đi giữa 2 địa điểm tối ưu theo thời gian dựa trên tín hiệu giao thông cho VMap, sinh viên Bùi Quang Huy, K61 – trường Đại học Công nghệ, ĐHQGHN giải quyết. 1.2.2 Vấn đề gặp phải do thiếu dữ liệu lưu lượng giao thông Phương thức hoạt động của hệ thống chỉ đường VMap [7]: Dữ liệu đường của VMap được chuyển đổi thành đồ thị có đỉnh là các node giao nhau giữa các way, các tag như loại đường, giới hạn tốc độ. được sử dụng để tính tốc độ di chuyển. Mỗi một loại phương tiện sẽ có một đồ thị riêng với mục đích thể hiện đặc trưng của từng phương tiện về thời gian di chuyển. Một khi đồ thị được thiết lập với tất cả dữ liệu, việc tìm kiếm tuyến đường giữa 2 điểm chủ yếu là vấn đề chọn 2 đỉnh trên đồ thị, sau đó chạy thuật toán Dijkstra để tìm tuyến đường có thời gian ngắn nhất. Đỉnh của đồ thị: Các đỉnh của đồ thị biểu thị một hướng cụ thể của way. Mỗi node là giao điểm của các way có thể có trọng số tính theo giây cho thời gian di chuyển qua way đó. Cạnh của đồ thị: Cạnh của đồ thị kết nối các đỉnh của đồ thị, tốc độ di chuyển trên cạnh được tính theo các thẻ thông tin (tag) như loại đường, giới hạn tốc độ di chuyển,.. Trọng số thời gian di chuyển trên cạnh theo giây sẽ được tính bằng tốc độ di chuyển và độ dài cạnh. Trong quá trình định tuyến, một số cạnh đơn giản (nối 2 đỉnh không phải giao điểm) được lược bỏ để tăng tốc độ xử lý. Hình 1.4 cho thấy các bước đưa dữ liệu đường VMap trở thành đồ thị định tuyến: 16 Hình 1.4. Tối ưu đồ thị định tuyến của chức năng chỉ đường VMap [6] Vấn đề đặt ra: chức năng chỉ đường của VMap đưa ra kết quả dựa trên tốc độ di chuyển được đặt mặc định theo loại đường, giới hạn tốc độ,.. dẫn đến kết quả tuyến đường tối ưu theo thời gian giữa 2 địa điểm cố định là như nhau trong mọi khoảng thời gian. Điều này chưa chính xác so với thực tế khi tốc độ di chuyển ảnh bị ảnh hưởng bởi rất nhiều yếu tố như thời tiết, mật độ giao thông,.. và thay đổi liên tục. Như vậy, chức năng chỉ đường của VMap chưa có một phương pháp ước tính thời gian di chuyển phù hợp so với thực tế. Vấn đề này đã được đề xuất giải quyết trong khóa luận Nghiên cứu, phát triển công cụ ước tính tốc độ di chuyển trong thực tế dựa trên dữ liệu giao thông cho VMap, 17 sinh viên Phùng Quang Minh, K61 – trường Đại học Công nghệ, ĐHQGHN giải quyết. Trong khóa luận này, Phùng Quang Minh đã đề xuất xây dựng một hệ thống thu thập dữ liệu giao thông của người dùng để cải thiện thuật toán tìm đường cho Nền tảng VMap. Tuy nhiên, để có dữ liệu thực tế có thể sử dụng được, chúng ta cần rất nhiều người dùng. Mà muốn có thêm người sử dụng, chúng ta cần có dịch vụ tìm đường cung cấp kết quả chính xác hơn. Vì vậy, để giải quyết vấn đề này, trong luận văn này, em sẽ trình bày phương pháp xây dựng thuật toán ước lượng thời gian di chuyển thực tế sử dụng Google Traffic Tiles, từ đó đưa kết quả tìm đường cho người dùng theo thời gian ngắn nhất. . 18 CHƯƠNG 2. CÁC NGHIÊN CỨU, CÔNG NGHỆ LIÊN QUAN 2.1 Một số phương pháp tính toán tốc độ di chuyển thực tế. 2.1.1 Thu thập thông tin chia sẻ từ người dùng Phương pháp này dựa trên việc thu thập dữ liệu từ trải nghiệm thực tế của người dùng. Nó thường yêu cầu người dùng điền vào một mẫu với những thông tin cố định như vị trí, thời gian, phương tiện di chuyển, tốc độ hiện tại,...Dữ liệu sau khi tổng hợp sẽ được chia sẻ lại cho người dùng. Ưu điểm: chi phí triển khai thấp, không bị ảnh hưởng bởi các yếu tố bên ngoài như thời tiết, mật độ giao thông,.. Nhược điểm: Lượng dữ liệu thu thập được có độ bao phủ kém, không được kiểm soát do người dùng là nguồn cung cấp dữ liệu duy nhất. Phương pháp này thường được sử dụng như một kênh phụ để bổ sung thông tin trong trường hợp thiếu sót, sai lệch của những phương pháp khác. 2.1.2 Tính toán dựa trên công nghệ đo trực tiếp Một cách tổng quan, công nghệ đo trực tiếp [8] đề cập đến dữ liệu giao thông được đo bằng các thiết bị được đặt trực tiếp dọc các tuyến đường. Công nghệ đo trực tiếp được chia thành hai loại: đo xâm nhập và đo không xâm nhập: Phương pháp đo xâm nhập. Các phương pháp đo xâm nhập về cơ bản bao gồm một máy ghi dữ liệu và một cảm biến đặt trên lề hoặc mặt đường. Phương pháp này đã được sử dụng và kiểm chứng về độ chính xác trong nhiều năm. Những công nghệ cốt lõi của phương pháp được mô tả ngắn gọn sau đây: • Cảm biến khí nén: ống cao su được đặt trên các làn đường để phát hiện phương tiện từ thay đổi áp suất được tạo ra khi lốp xe đi qua ống. Xung của không khí được tạo ra được ghi lại và xử lý bởi một bộ đếm nằm ở bên đường. Hạn chế chính của công nghệ này là nó có phạm vi bao phủ dữ liệu hạn chế và hiệu quả của nó phụ thuộc vào điều kiện thời tiết, nhiệt độ và tình trạng giao thông. Hệ thống này cũng có thể không hiệu quả trong tình trạng phương tiện di chuyển với tốc độ thấp. 19 • Cảm biến áp điện: các cảm biến được đặt trong một rãnh dọc theo bề mặt đường của các làn đường. Nguyên tắc là chuyển đổi năng lượng cơ học thành năng lượng điện. Thật vậy, biến dạng cơ học của vật liệu áp điện làm thay đổi mật độ điện tích bề mặt của vật liệu để và sự khác biệt sẽ xuất hiện giữa các điện cực. Biên độ và tần số của tín hiệu tỷ lệ thuận với mức độ biến dạng. Hệ thống này có thể được sử dụng để đo trọng lượng và tốc độ. • Vòng từ: Đây là công nghệ thông thường nhất được sử dụng để thu thập dữ liệu giao thông. Các vòng được đặt trong các con đường theo hình vuông tạo ra từ trường. Thông tin sau đó được truyền đến một thiết bị đếm được đặt bên đường. Vòng đời sử dụng của thiết bị này thường ngắn vì nó có thể bị hư hại bởi xe hạng nặng, nhưng không bị ảnh hưởng bởi điều kiện thời tiết xấu. Công nghệ này đã được triển khai rộng rãi ở châu Âu (và các nơi khác) trong một vài thập kỷ qua. Tuy nhiên, chi phí thực hiện và bảo trì của phương pháp này tương đối lớn. Phương pháp đo không xâm nhập: Các kỹ thuật không xâm nhập được dựa trên các quan sát từ xa. Ngay cả khi đếm thủ công là phương pháp được sử dụng nhiều nhất, các công nghệ mới đã xuất hiện gần đây có vẻ rất hứa hẹn: • Đếm thủ công: đây là phương pháp truyền thống nhất. Trong trường hợp này, các các thiết bị đo được vận hành một cách thủ công bởi con người và không thể có được một cách hiệu quả bởi kết quả đạt được của phương pháp chỉ là một con số, ví dụ: mật độ giao thông, phân loại xe. Các thiết bị phổ biến nhất được sử dụng là hệ thống bảng đếm cơ học và hệ thống bảng đếm điện tử. • Năng lượng hồng ngoại: sự hiện diện, tốc độ và loại phương tiện được phát hiện dựa trên năng lượng hồng ngoại tỏa ra từ khu vực phát hiện. Hạn chế chính là hiệu suất trong thời tiết xấu và phạm vi bao phủ dữ liệu. • Từ tính thụ động: cảm biến từ được cố định dưới hoặc trên mặt đường. Nó đếm số lượng xe, loại và tốc độ. Tuy nhiên, trong điều kiện vận hành, các cảm biến gặp khó khăn trong việc phân biệt giữa các phương tiện có khoảng cách gần nhau. 20 • Radar vi sóng: công nghệ này có thể phát hiện các phương tiện di chuyển và tốc độ. Nó ghi lại dữ liệu đếm, tốc độ và phân loại xe đơn giản và không bị ảnh hưởng bởi điều kiện thời tiết. • Siêu âm: các thiết bị này phát ra sóng âm thanh để phát hiện các phương tiện bằng cách đo thời gian để tín hiệu quay trở lại thiết bị. Các cảm biến siêu âm được đặt trên làn đường và có thể bị ảnh hưởng bởi nhiệt độ hoặc thời tiết xấu. Các thiết bị âm thanh thụ động được đặt dọc theo đường và có thể thu thập số lượng xe, tốc độ và dữ liệu phân loại. Chúng cũng có thể bị ảnh hưởng bởi các điều kiện thời tiết xấu (ví dụ: nhiệt độ thấp, tuyết). • Phát hiện hình ảnh video: máy quay video ghi lại số xe, loại và tốc độ bằng các kỹ thuật xử lý video khác nhau. Hệ thống có thể nhạy cảm với điều kiện khí tượng. 2.1.3 Tính toán từ dữ liệu vị trí của phương tiện Nguyên tắc của phương pháp tính toán từ dữ liệu vị trí của phương tiện là thu thập dữ liệu giao thông bằng cách định vị phương tiện qua điện thoại di động hoặc GPS trên toàn bộ mạng lưới đường bộ. Điều này về cơ bản có nghĩa là mọi chiếc xe đều được trang bị điện thoại di động hoặc GPS hoạt động như một bộ cảm biến cho mạng lưới đường bộ. Dữ liệu như vị trí xe, tốc độ và hướng di chuyển được gửi ẩn danh đến một trung tâm xử lý trung tâm. Sau khi được thu thập và trích xuất, thông tin hữu ích (ví dụ: trạng thái giao thông,tốc độ di chuyển, tuyến đường thay thế) có thể được phân phối lại cho các tài xế trên đường. Độ tin cậy của dữ liệu thu thập được từ phương pháp này thường gây ra nhiều nghi vấn đối với số lượng mẫu nhỏ nhưng được tăng lên đáng kể đối với lượng mẫu lớn thu thập được. Cách thức tính toán dựa trên dữ liệu vị trí cũng tương đối đơn giản khi thời gian và đoạn đường di chuyển của từng phương tiện được thể hiện một cách rõ ràng. Kết luận: Mục 2.1 đã giới thiệu và chỉ ra những ưu,