ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HÀ ĐỨC 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
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Giảng viên hướng dẫn: TS. Bùi Quang Hưng
Hà Nội, 09/2020
LỜI CẢM ƠN
Trước hết tôi xin bày tỏ lòng cảm ơn chân thành đến TS Bùi Quang Hưng đã tận
tình hướng dẫn tôi trong thời gian làm luận văn thạc sĩ này.
Tôi xin cảm ơn các thầy, cô ở Trung tâm Công nghệ tích hợp liên ngành Giám sát
hiện trường (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
1
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
2
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
3
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
4
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
5
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
6
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
7
DANH MỤC TỪ VIẾT TẮT
Ký hiệu
Ý nghĩa
Application
Programming
API
Interface – giao diện lập trình
ứng dụng
Cơ sở dữ liệu
CSDL
Đại học Quốc gia Hà Nội
ĐHQGHN
OGC
Tổ chức địa không gian Open
Geospatial Consortium
OpenStreetMap
OSM
Chuẩn Web Map Tile Service
WMTS
8
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
9
- 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.
10
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
11
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,
12
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.
13
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)
14
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:
15
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,
16
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.
.
17
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.
18
• 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.
19
• 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, nhược điểm của các phương
pháp đang được sử dụng phổ biến để tính toán tốc độ di chuyển trong thực thế. Trong khi
phương pháp thu thập thông tin chia sẻ từ người dung thường đem lại lượng dữ liệu tương
đối hạn chế, chưa đáp ứng được yêu cầu của VMap; các phương pháp đo trực tiếp yêu
cầu chi phí quá lớn về thiết bị, bảo trì, nhân sự và độ bao phủ của dữ liệu cũng gói gọn
trong một khu vực, để triển khai phương pháp này cho toàn bộ lãnh thổ Việt Nam cần
20
một lượng tài nguyên vô cùng lớn; trong khi đó, phương pháp tính toán từ dữ liệu vị trí
của phương tiện lại tỏ ra có những ưu điểm vượt trội như chi phí triển khai thấp (trong
trường hợp cụ thể là áp dụng cho VMap, dữ liệu vị trí có thể thu thập được trên chức
năng chỉ đường sẵn có), độ bao phủ dữ liệu tốt. Tuy độ tin cậy của dữ liệu thu thập được
từ phương pháp tính toán từ dữ liệu vị trí của phương tiện không được đảm bảo với lượng
dữ liệu thu được từ chức năng chỉ đường của VMap hiên tại nhưng điều này hoàn toàn
có thể cải thiện trong tương lai khi lượng người dung của VMap tăng lên.
2.2. Giới thiệu tổ chức Open Geospatial Consortium (OGC) và chuẩn Web Map Tile Service (WMTS)
2.2.1 Giới thiệu tổ chức Open Geospatial Consortium (OGC)
Tổ chức địa không gian (OGC) là tổ chức quốc tế chuyên đề ra các chuẩn trong lĩnh
vực hệ thống thông tin địa lý, với sự tham gia của trên 521 công ty, tổ chức chính phủ,
trường đại học và các viện nghiên cứu trên thế giới. Các thành viên sẽ tham gia vào quá
trình thống nhất các chuẩn mở toàn cầu cho các thông tin liên quan đến không gian địa
lý và các dịch vụ liên quan. Các chuẩn của OGC hỗ trợ các giải pháp về việc tương thích
các dịch vụ Web, không dây dựa trên vị trí và công nghệ thông tin chủ đạo. Các chuẩn
cho phép các nhà phát triển công nghệ tạo ra các thông tin và dịch vụ không gian phức
tạp có thể truy cập và hữu ích với tất cả các loại ứng dụng [9].
2.2.2 Giới thiệu chuẩn Web Map Tile Service (WMTS)
OGC đã tham gia vào việc phát triển các tiêu chuẩn cho lập bản đồ số sau khi một
bài báo được xuất bản năm 1997 bởi Allan Doyle, phác thảo một "WWW Mapping Bộ
thư viện" [10]. Tiêu chuẩn lâu đời nhất và phổ biến nhất để lập bản đồ số là WMS. Chuẩn
WMS hướng tới sự linh hoạt khi cho phép người dùng tùy biến chính xác ảnh bản đồ như
họ mong muốn. Tuy nhiên, WMS không phù hợp với các hệ thống đòi hỏi phản hồi nhanh
và nhiều. Đối với hầu hết các dịch vụ WMS, một yêu cầu sẽ cần vài giây để máy chủ có
thể tạo ra phản hồi. Đối với các hệ thống lớn, yêu cầu sự phản hồi nhanh thì đây là khó
khăn. Để khắc phục sự cố kết xuất trực tiếp đòi hỏi nhiều tài nguyên tính toán, các nhà
phát triển ứng dụng đã bắt đầu sử dụng các ô bản đồ được kết xuất trước. WMTS chia
bản đồ ra làm các mảnh (tile) tùy thuộc vào độ thu phóng theo chuẩn OGC Two
Dimensional Tile Matrix Set. Các mảnh bản đồ này sẽ được kết xuất trước để có thể ngay
lập tức gửi lại phản hồi khi có yêu cầu. Hiện nay, các dịch vụ bản đồ lớn đều sử dụng
chuẩn này [11].
21
Hình 2.1. WMTS chia bản đồ ra làm các mảnh
2.3. Giới thiệu về Google Map
Google Map là một dịch vụ bản đồ web được phát triển bởi Google [12]. Nó cung
cấp hình ảnh vệ tinh, chụp ảnh trên không, bản đồ đường phố, chế độ xem toàn cảnh
tương tác 360 ° của đường phố (Chế độ xem phố), điều kiện giao thông thời gian thực và
lập kế hoạch tuyến đường để đi bộ, xe hơi, xe đạp và máy bay (trong phiên bản beta)
hoặc giao thông công cộng. Vào năm 2020, Google Map đã được hơn 1 tỷ người sử dụng
mỗi tháng.
Google Map bắt đầu như một chương trình máy tính để bàn C++ tại Where 2
Technologies [13]. Vào tháng 10 năm 2004, công ty đã được Google mua lại, công ty đã
chuyển đổi nó thành một ứng dụng web. Sau khi mua thêm một công ty trực quan hóa
dữ liệu không gian địa lý và phân tích lưu lượng thời gian thực, Google Map đã được ra
mắt vào tháng 2 năm 2005. Giao diện người dùng của dịch vụ sử dụng JavaScript, XML
và Ajax. Google Map cung cấp API cho phép các bản đồ được nhúng trên các trang web
của bên thứ ba và cung cấp công cụ định vị cho các doanh nghiệp và các tổ chức khác ở
nhiều quốc gia trên thế giới. Google Map Maker cho phép người dùng cộng tác mở rộng
và cập nhật bản đồ của dịch vụ trên toàn thế giới nhưng đã bị ngừng từ tháng 3 năm 2017.
22
Tuy nhiên, các đóng góp của cộng đồng cho Google Map không bị ngừng vì công ty đã
thông báo các tính năng này sẽ được chuyển sang chương trình Google Local Guide.
Google Map, một dịch vụ bản đồ đáng tin cậy cung cấp thông tin vị trí thông qua
hình ảnh vệ tinh. Hiệu quả do công cụ trực tuyến này mang lại không thể phủ nhận vì nó
có khả năng kiểm tra các tuyến đường và cột mốc có thể để có thời gian di chuyển nhanh
hơn.
Google Map phát triển với mục đích thay thế các loại bản đồ giấy. Và nó đã trở
thành một trong những ứng dụng mạnh mẽ và phổ biến nhất hiện nay. Với nhiều tính
năng tiện ích, nên Google Map đã được nhiều người lựa chọn sử dụng để tìm hướng dẫn
chỉ đường. Nắm bắt xu thế đó, nên nhiều doanh nghiệp đã ứng dụng Google Map vào
trong kinh doanh trực tuyến. Phổ biến nhất là tích hợp Google Map vào trong trang mạng
để khách hàng dễ dàng tìm đến địa chỉ mua hàng. Ngoài ra người ta còn ứng dụng vào
việc tối ưu hóa địa điểm doanh nghiệp, nhờ đó làm tăng lượng truy cập đổ về trang mạng
của mình.
2.4. Giới thiệu về Graphhopper
GraphHopper là một thư viện và máy chủ định tuyến mã nguồn mở nhanh phát
triển bằng Java [14]. GraphHopper sử dụng các thuật toán khác nhau như Dijkstra, A *
và Contraction Hierarchies để tìm đường đi ngắn nhất dựa trên dữ liệu của
OpenStreetMap. Do Giấy phép Apache, nó là một giải pháp thay thế thân thiện với doanh
nghiệp cho các công cụ định tuyến hiện có và phần mềm điều hướng. GraphHopper được
phát triển bởi công ty GraphHopper GmbH, Đức, lần đầu được công bố mã nguồn mở
vào tháng 3 năm 2015. Phiên bản mới của GraphHopper là 2.0 được phát hành vào ngày
17/07/2020.
GraphHopper phát triển trên ngôn ngữ Java, sử dụng dữ liệu đường đầu vào là dữ
liệu OSM dưới định dạng .pbf ("Protocolbuffer Binary Format"). Từ dữ liệu đầu vào là
các way của OSM, GraphHopper tiến hành xây dựng một đồ thị và đánh trọng số cho
các cạnh phụ thuộc vào các đầu vào của dữ liệu như khoảng cách, số ngã rẽ, biển báo
giao thông,… GraphHopper cũng đồng thời hỗ trợ dữ liệu độ cao số (DEM - Digital
elevation model) để có thể tính chính xác khoảng cách giữa các vị trí trên bản đồ.
Các API mà GraphHopper cung cấp bao gồm:
23
- Tìm đường đi giữa 2 hoặc nhiều điểm (Routing API)
- Tìm đường đi giữa các ma trận điểm (Matrix API)
- Tìm địa điểm dựa trên tọa độ (Geocoding API)
- Tìm kiếm đường đi dựa trên dữ liệu GPX (Map Matching API)
Hình 2.2. Giao diện trình diễn của GraphHoper
2.5. Giới thiệu về Javascript và NodeJS
2.5.1. Giới thiệu, lịch sử phát triển Javascript
Cùng thời điểm Netscape bắt đầu sử dụng công nghệ Java trên trình duyệt Netscape,
LiveScript đã được đổi tên thành JavaScript để được chú ý hơn bởi ngôn ngữ lập trình
Java lúc đó đang được coi là một hiện tượng [15]. JavaScript được bổ sung vào trình
duyệt Netscape bắt đầu từ phiên bản 2.0b3 của trình duyệt này vào tháng 12 năm 1995.
Trên thực tế, hai ngôn ngữ lập trình Java và JavaScript không có liên quan gì đến nhau,
ngoại trừ việc cú pháp của cả hai ngôn ngữ cùng được phát triển dựa trên cú pháp của C.
JavaScript gồm 2 mảng là client-server thực hiện lệnh trên máy của end-user và web-
server.
Sau thành công của JavaScript, Microsoft bắt đầu phát triển JScript, một ngôn ngữ
có cùng ứng dụng và tương thích với JavaScript. JScript được bổ sung vào trình duyệt
Internet Explorer bắt đầu từ Internet Explorer phiên bản 3.0 được phát hành tháng 8 năm
24
1996. JavaScript là một ngôn ngữ lập trình website, được tích hợp và nhúng trong HTML
giúp website sống động. JavaScript cho phép kiểm soát các hành vi của trang web tốt
hơn so với khi chỉ sử dụng HTML. JavaScript là ngôn ngữ lập trình được hỗ trợ hầu như
trên tất cả các trình duyệt như Firefox, Chrome... thậm trí các trình duyệt trên thiết bị di
động.
2.5.2 Giới thiệu về NodeJS
NodeJS là một nền tảng mã nguồn mở được xây dựng trên nền tảng Javascript V8
Engine của Chrome, được sử dụng để phát triển các ứng dụng Web. NodeJS sử dụng cơ
chế hướng sự kiện , mô hình vào/ra không khóa, điều này làm cho NodeJS gọn nhẹ và
hiệu quả. Các ứng dụng NodeJS được viết bằng Javascript và có thể chạy trên nhiều nền
tảng khác nhau như OS X, Microsoft Windows và Linux. NodeJS cung cấp các thư viện
phong phú ở dạng các mô-đun khác nhau giúp đơn giản hóa việc lập trình và giảm thời
gian ở mức thấp nhất [16].
NodeJS được tạo bởi Ryan Dahl từ năm 2009, và phát triển dưới sự bảo trợ của
Joyent . NodeJS được tạo lần đầu cho hệ điều hành Linux sử dụng. Nó được phát triển
và bảo trì vởi Ryan Dahl và được tài trợ bởi Joyent Trong năm 2011, một bộ phần package
manager đã giới tiệu bộ thư viện cho NodeJS gọi là npm. Tháng 6 năm 2011, Microsoft
hợp tác với Joyent để tạo ra bản cho Windows. Tháng 12, Do xung đột nội bộ nên NodeJS
bị chia rẽ, IO.js được hình thành [16].
Những lý do để sử dụng NodeJS:
• Bất đồng bộ và hướng sự kiện: Tất cả API của các thư viện NodeJS đều bất
đồng bộ. Về cơ bản, nó có nghĩa là một máy chủ NodeJS không bao giờ chờ
một API trả về dữ liệu. Máy chủ sẽ chuyển sang API tiếp theo sau khi gọi
một API và cơ chế thông báo sự kiện của NodeJS giúp máy chủ nhận được
phản hồi từ cuộc gọi API trước đó.
• Rất nhanh: Được xây dựng trên V8 Javascript Engine của Google Chrome,
thư viện NodeJS chạy rất nhanh trong các quá trình thực hiện mã.
• Đơn luồng nhưng khả năng mở rộng cao: NodeJS sử dụng một mô hình
luồng duy nhất với vòng lặp sự kiện. Cơ chế sự kiện giúp máy chủ đáp ứng
một cách bất đồng bộ và làm cho máy chủ có khả năng mở rộng cao so với
các máy chủ kiểu truyền thống tạo các luồng hạn chế để xử lý các yêu cầu.
25
NodeJS sử dụng một chương trình luồng duy nhất và cùng một chương trình
có thể cung cấp dịch vụ cho một số lượng yêu cầu lớn hơn so với các máy
chủ kiểu truyền thống như Apache HTTP Server.
• Không đệm: Các ứng dụng NodeJS không bao giờ đệm dữ liệu.
• Thời gian thực: ở đây chính là xử lý giao tiếp từ máy khách tới máy chủ theo
thời gian thực.
2.6. Giới thiệu về Python và các thư viện, bộ thư viện sử dụng
2.6.1. Giới thiệu về Python
Python là ngôn ngữ lập trình bậc cao, dùng để phát triển website và nhiều ứng
dụng khác nhau. Python được ra bởi Guido van Rossum và được phát triển trong dự án
mã nguồn mở [17]. Python đã được hình thành vào cuối những năm 1980, và việc thực
hiện nó vào tháng 12 năm 1989 bởi Guido van Rossum tại Centrum Wiskunde &
Informatica (CWI) ở Hà Lan như là một kế thừa cho ngôn ngữ ABC (tự lấy cảm hứng từ
SETL) có khả năng xử lý ngoại lệ và giao tiếp với Hệ điều hành Amoeba. Van Rossum
là tác giả chính của Python, và vai trò trung tâm của ông trong việc quyết định hướng
phát triển của Python [17].
Python 2.0 đã được phát hành vào ngày 16 tháng 10 năm 2000 và có nhiều tính
năng mới, bao gồm bộ thu gom rác theo chu kỳ và hỗ trợ Unicode. Với việc phát hành
này quá trình phát triển đã được thay đổi và trở nên minh bạch hơn và cộng đồng hậu
thuẫn. Python 3.0 được phát hành năm 2008, sau một thời gian dài thử nghiệm. Cho tới
năm 2017, Python đang có phiên bản 3.7.
Đặc điểm nổi bật
• Ngữ pháp đơn giản, dễ đọc.
• Vừa hướng thủ tục, vừa hướng đối tượng.
• Hỗ trợ module và hỗ trợ gói (package).
• Xử lý lỗi bằng ngoại lệ (Exception).
• Kiểu dữ liệu động ở mức cao.
• Có các bộ thư viện chuẩn và các module ngoài, đáp ứng tất cả các nhu cầu lập
trình.
26
• Có khả năng tương tác với các module khác viết trên C/C++ (Hoặc Java cho
Jython, hoặc .Net cho IronPython).
2.6.2 Bộ thư viện Scikit-Learn (sklearn)
Dự án này đã được bắt đầu vào năm 2007 như là một dự án Google Summer of
Code của David Cournapeau. Cuối năm đó, Matthieu Brucher bắt đầu thực hiện dự án
này như một phần của luận án của mình.
Năm 2010, Fabian Pedregosa, Gael Varoquaux, Alexandre Gramfort và Vincent
Michel của INRIA đã lãnh đạo dự án và phát hành công khai lần đầu tiên vào ngày 1
tháng 2 năm 2010. Kể từ đó, một số bản phát hành đã xuất hiện sau chu kỳ ~ 3 tháng và
phát triển mạnh cộng đồng quốc tế đã và đang dẫn đầu sự phát triển [18].
Scikit-learn (viết tắt là sklearn) là một thư viện mã nguồn mở trong ngành học máy,
rất mạnh mẽ và thông dụng với cộng đồng Python, được thiết kế trên nền NumPy và
SciPy. Scikit-learn chứa hầu hết các thuật toán học máy hiện đại nhất, đi kèm với tài liệu
chi tiết. Điểm mạnh của thư viện này là nó được sử dụng phổ biến trong học thuật và
công nghiệp, do đó nó luôn được cập nhật và có một cộng đồng người dùng sử dụng lớn
[19].
Hiện nay có nhiều thư viện mã nguồn mở phục vụ cho nghiên cứu học máy. Bên
cạnh Scikit-learn, có 2 thư viện nổi bật khác là:
• LibSVM: Được viết trên C bởi Chih-Chung Chang và Chih-Jen Lin. Như tên gọi
của nó, thư viện này chứa các thuật toán SVM (Support Vector Machine), nhóm
thuật toán mạnh mẽ hỗ trợ cả regression và classification tasks [20].
• TensorFlows: Do các nhà khoa học của viện nghiên cứu Google Brain phát triển.
TensorFlows được viết trên Python và là thư viện mở [21].
Trong khi TensorFlows ở mức độ cấp thấp thì Scikit-learn cho phép ta sử dụng ngay
các thuật toán quan trọng một cách đơn giản và hiệu quả. Nói vậy không có nghĩa Scikit-
learn là một thư viện “nông cạn”, Scikit-learn là nền tảng để xây dựng các thuật toán học
máy khác (Nilearn, Pylearn2…). Scikit-learn còn là một trong những lựa chọn hàng đầu
của các nhà nghiên cứu và các nhà phát triển. Đứng sau Scikit-learn là các viện nghiên
cứu hàng đầu thế giới, gồm có Inria, Télécom Paristech, Paris-Saclay (Pháp), NYU
Moore-Sloan Data Science Environment và Columbia University.
27
2.6.3 Flask
Trong phát triển ứng dụng web, Python có nhiều bộ thư viện hỗ trợ lập trình viên
như Django, Tornado, Pyramid,… Trong đó, Flask là một bộ thư viện nhỏ gọn được viết
bằng Python. “Nhỏ gọn” không có nghĩa là thiếu chức năng mà “nhỏ gọn” theo triết lý
thiết kế là cung cấp một lõi chức năng cần thiết nhất cho ứng dụng web nhưng người
dùng có thể mở rộng bất cứ lúc nào. Flask luôn hỗ trợ các thành phần tiện ích mở rộng
cho ứng dụng như tích hợp cơ sở dữ liệu, xác thực biểu mẫu, xử lý tải lên, các công nghệ
xác thực, mẫu, email, RESTful..., chỉ khác là khi nào bạn muốn thì bạn mới đưa vào thôi
[22]. Người dùng có thể tập trung xây dựng ứng dụng web ngay từ đầu trong một khoảng
thời gian rất ngắn và có thể phát triển quy mô của ứng dụng tùy theo yêu cầu.
Sau khi cài đặt Python, để cài đặt Flask chỉ cần bạn gõ lệnh: pip install Flask Bây
giờ chúng ta thử tạo ứng dụng web với câu chào Hello World!. Thật đơn giản bạn sẽ tạo
một thư mục với tên thư mục là tên ứng dụng, sau đó, tạo một tập tin .py và viết mã. Ví
dụ như: hello.py như Hình 2.3.
Hình 2.3. Ví dụ ứng dụng Hello World trên bộ thư viện Flask
Sau đó chỉ cần run là trang web này sẽ hiển thị trên http://127.0.0.1:5000/
Kết quả như ở Hình 2.4. Như bạn thấy, Flask tập trung vào sự tối giản, cho phép
chúng ta ứng dụng Flask thật sự phù hợp cho việc xây dựng các ứng dụng web có quy
mô vừa và nhỏ, các API và dịch vụ web:
• Xây dựng ứng dụng web rất giống với việc viết các mô-đun Python chuẩn,
cấu trúc gọn gàng và rõ ràng.
28
• Thay vì cung cấp hết tất cả mọi thứ, Flask cung cấp cho người dùng các
thành phần cốt lõi thường được sử dụng nhất của khung ứng dụng web như
định tuyến trang, yêu cầu và phản hồi, các mẫu,...
• Với Flask, việc chọn các thành phần nào cho ứng dụng là việc của chúng ta.
Điều này thật tuyệt, vì mỗi ứng dụng web có những đặc điểm và tính năng
riêng, nó không phần phải chứa các thành phần mà nó không dùng.
• Flask có kiến trúc nhỏ gọn nên bạn hoàn toàn không bị bó buộc bởi bộ khung
cồng kềnh, không gặp bất cứ khó khăn nào khi cấu hình hay tổ chức ứng
dụng. Không những thế, Flask còn có các ưu điểm nổi bật như: cực kỳ linh
hoạt, tối giản, dễ tìm hiểu và sử dụng, định tuyến dễ dàng, rất dễ mở rộng.
Vì vậy, công việc chính của bạn là chỉ cần xác định ý tưởng, mục tiêu, tập
trung vào việc xây dựng ứng dụng web mà thôi.
• Flask cung cấp rất nhiều tài liệu từ cài đặt đến thực hiện và triển khai, từ
hướng dẫn nhanh đến hướng dẫn chi tiết. Bạn có thể dễ dàng tìm kiếm, tham
khảo, học tập về lập trình ứng dụng web với Flask bộ thư viện miễn phí trên
Internet.
• Cộng đồng Flask khá lớn. Bạn có thể dễ dàng, nhanh chóng tìm được giải
pháp từ cộng đồng người sử dụng Flask mỗi khi gặp vấn đề cần giúp đỡ ví
dụ như gặp lỗi, cách cài đặt thư viện, cách triển khai ứng dụng...
Hình 2.4. Ví dụ ứng dụng Hello World trên bộ thư viện Flask
2.7. Giới thiệu RNN
RNN (Recurrent Neural Network – Mạng nơ-ron hồi quy) là một trong những mô
hình học sâu trong công nghệ trí tuệ nhân tạo.Ý tưởng chính của RNN là sử dụng chuỗi
các thông tin. Trong các mạng nơ-ron truyền thống tất cả các đầu vào và cả đầu ra là độc
lập với nhau. Tức là chúng không liên kết thành chuỗi với nhau. Nhưng các mô hình này
không phù hợp trong rất nhiều bài toán. Ví dụ, nếu muốn đoán từ tiếp theo có thể xuất
hiện trong một câu thì ta cũng cần biết các từ trước đó xuất hiện lần lượt thế nào chứ nhỉ?
RNN được gọi là hồi quy bởi lẽ chúng thực hiện cùng một tác vụ cho tất cả các phần tử
29
của một chuỗi với đầu ra phụ thuộc vào cả các phép tính trước đó. Nói cách khác, RNN
có khả năng nhớ các thông tin được tính toán trước đó. Trên lý thuyết, RNN có thể sử
dụng được thông tin của một văn bản rất dài, tuy nhiên thực tế thì nó chỉ có thể nhớ được
một vài bước trước đó mà thôi. Trong lĩnh vực xử lý ngôn ngữ tự nhiên đã ghi nhận được
nhiều thành công của RNN cho nhiều vấn đề khác nhau.
Hình 2.5. Ví dụ về một mạng nơ-ron RNN
30
CHƯƠNG 3. ĐỀ XUẤT PHƯƠNG PHÁP
3.1 Thu thập dữ liệu Google Traffic Tiles
Hiện nay, dữ liệu giao thông được cung cấp bởi một số bên như: INRIX, Here,
TomTom, Waze, Uber,… Tuy nhiên, các dịch vụ này đều phải trả phí với phí dịch vụ
cao, không có khả năng sử dụng trên diện rộng
Google có thu thập dữ liệu của người dùng bằng nhiều phương pháp khác nhau.
Từ đó, Google đã công khai một bộ dữ liệu Google Traffic Tiles là dịch vụ theo chuẩn
WMTS của OGC thể hiện dữ liệu giao thông trực tiếp trên đường. Đường dẫn của Google
Traffic Tiles: https://mt1.google.com/vt/lyrs=transit,traffic&x={x}&y={y}&z={z}.
Chi tiết thông số về Google Traffic Tiles được trình bày ở Bảng 3.1.
Bảng 3.1. Thông số chi tiết Google Traffic Tiles
Tên Google Traffic Tiles
Địa chỉ Server mt1.google.com
/vt/lyrs=transit,traffic&x={x}&y={y}&z={z} Đường dẫn
Kích thước 256
Độ zoom lớn nhất 1
Độ zoom nhỏ nhất 18
Kích thước ảnh 256x256
31
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
Do dữ liệu giao thông thay đổi liên tục, Google Traffic thay đổi sau mỗi năm phút,
để tăng tốc thuật toán, chúng ta cần tải về bộ dữ liệu Google Traffic Tiles. Do số lượng
ảnh cả Việt Nam và Hà Nội là rất lớn, trong luận văn này tôi tiến hành thử nghiệm tại
12 quận bao gồm:
Ba Đình, Cầu Giấy, Đống Đa, Hà Đông, Hai Bà Trưng, Hoàn Kiếm, Hoàng Mai, Long
Biên, Bắc Từ Liêm, Nam Từ Liêm, Tây Hồ, Thanh Xuân.
Xây dựng một công cụ để tải về Google Traffic Tiles:
- Ngôn ngữ sử dụng: NodeJS
- Thư viện: request, polygon-lookup
- Thu thập tại 12 quận tại Hà Nội
- Độ zoom: 18 (Đây là độ zoom lớn nhất của bộ dữ liệu Google Traffic Tiles mà
Google cung cấp)
Từ khung nhìn chọn trước được miêu tả trong Bảng 3.2, công cụ sẽ tính toán ra
các thông số Xmax, Ymax, Xmin, Ymin (là tọa độ lớn nhất và nhỏ nhất của các mảnh bản đồ
cần tải về) tại độ Zoom 18 để tính toán tất cả các tile ảnh cần tải về. Sử dụng vòng lặp và
hàm PolygonLookup cửa thư viện polygon-lookup để lần lượt kiểm tra xem tọa độ các
Tile có thuộc 1 trong 12 quận thử nghiệm hay không, nếu có sẽ tải về tương ứng dữ liệu
32
ảnh đó bằng cách sử dụng thư viện request và lưu trữ dưới dạng cây thư mục {Độ
Zoom}/{X}/{Y}.png. Dữ liệu ranh giới hành chính được sử dụng ở đây là dữ liệu hành
chính 1:50.000 của Bộ Tài nguyên và Môi trường dưới định dạng GeoJSON.
Hình 3.2. Dữ liệu ranh giới hành chính
Bảng 3.2. Thông tin thử nghiệm tải về dữ liệu
Góc Bắc (vĩ độ) Góc Tây (kinh độ) Góc Nam (vĩ độ) Góc Đông (kinh độ)
21.379 105.281 20.554 106.027
Công thức tính X từ kinh độ:
𝑌 = 𝑙𝑜𝑛 + 180 360 ∗ 2𝑧𝑜𝑜𝑚
Công thức tính Y từ vĩ độ:
1 1 − log(tan ( ) + ) 𝑙𝑎𝑡 ∗ 𝜋 180 cos( )
𝑙𝑎𝑡 ∗ 𝜋 180 𝜋 𝑋 = 2 ∗ 2𝑧𝑜𝑜𝑚
Công thức tính kinh độ từ X:
𝑙𝑜𝑛 = 𝑥 2𝑧𝑜𝑜𝑚 ∗ 360 − 180
33
Công thức tính vĩ độ từ Y:
𝑙𝑎𝑡 = 180 𝜋 ∗ arctan(0.5 ∗ (exp(𝑛) − exp (−𝑛)))
- Trong đó n được tính theo công thức sau:
𝑛 = 𝜋 − 2 ∗ 𝜋 ∗ 𝑌 ∗ 𝑧𝑜𝑜𝑚 2𝑧𝑜𝑜𝑚
Kết quả chạy thử nghiệm:
- Tổng số tile: 15.128 tile
- Thời gian trung bình tải về: 133,46 giây
Hình 3.3. Một phần dữ liệu thu thập được
3.2 Xây dựng thuật toán tìm đường đi nhanh nhất theo thời gian
3.2.1 Đề xuất phương pháp tìm đường
Phương pháp mới được thể hiện trong Hình 3.4. Khi người dùng gửi yêu cầu đến
dịch vụ tìm đường mới, thông tin tọa độ của điểm đi và điểm đến sẽ được truyền đền
34
Thuật toán tìm đường đi nhanh nhất sẽ được trình bày ở phần sau của luận văn. Thuật
toán sẽ sử dụng dịch vụ tìm đường hiện tại của VMap (ở đây là GraphHopper) và bổ
sung thuật toán tìm đường đi nhanh nhất để đưa ra kết quả là đường đi nhanh nhất kèm
thời gian ước lượng thực tế cho người dùng.
Hình 3.4. Kiến trúc hệ thống tìm đường mới
Xây dựng API dẫn đường mới cho VMap:
- Ngôn ngữ sử dụng: python
- Thư viện: flask, json, requests, polyline, pickle, sklearn
API dẫn đường mới sẽ có đường dẫn và cấu trúc truy vấn tương tự với dịch vụ
hiện có của VMap. Các trường cụ thể được thể hiện ở Bảng 3.3. API khi có yêu cầu gửi
lên sẽ sử dụng thư viện request để lấy kết quả chỉ đường từ dịch vụ chỉ đường hiện có
của VMap. Dữ liệu đường đi của kết quả chỉ đường này sẽ được truyền vào mô hình sẽ
được trình bày bên dưới, đã được lưu lại bằng cách sử dụng thư viện pickle, để tính toán
lại ước lượng thời gian di chuyển. Để thay đổi giá trị ước lượng thời gian di chuyển của
kết quả trả về, ta cần quan tâm tới 2 thông số là points_encoded và instructions. Nếu
người dùng sử dụng thông số points_encoded=”true”, API sẽ sử dụng thư viện polyline
để giải mã dữ liệu đường đi đã được mã hóa, truyền dữ liệu đường đi vào mô hình. Nếu
người dùng sử dụng thông số instructions=”true”, thì thay vì ước lượng thời gian di
chuyển bằng cách truyền cả đường đi vào mô hình, ta sẽ phải ước lượng thời gian di
chuyển của từng bước trong chỉ dẫn. Sau đó thời gian di chuyển trên cả tuyến đường sẽ
bằng tổng thời gian di chuyển của các bước này. Cuối cùng ta sẽ trả lại kết quả là kết quả
35
tìm đường của dịch vụ chỉ đường VMap và thêm một thông số time_in_traffic tương ứng
với mỗi thông số time của kết quả.
Kết quả trả về dưới dạng JSON, có cấu trúc như ở Bảng 3.4.
Bảng 3.3. Các thông số truy vấn có thể gửi lên
Thông số Miêu tả
point (bắt buộc) Điểm đầu và điểm cuối mà người dung muốn tìm
đường. Định dạng [vĩ độ, kinh độ]
Phương tiện muốn tìm đường. Bao gồm: “car” (oto), vehicle
“motobike” (xe máy), “bike” (xe đạp) và “foot” (đi bộ)
Mặc định: “vn” locale
Ngôn ngữ hướng dẫn trong kết quả trả về. Ví dụ: “en”
ho tiếng Anh hoặc “de” cho tiếng Đức
elevation Mặc định: “false”
Nếu là “true”, thuật toán sẽ ước tính chiều dài của
quãng đường bằng cách sử dụng thêm mô hình độ cao
số.
details Tham số tùy chọn để truy xuất chi tiết đường dẫn. Bạn
có thể yêu cầu chi tiết bổ sung cho tuyến đường:
“street_name”, “time”, “distance”, “max_speed”,
“toll”, “road_class”, “road_class_link”, “road_access”,
“road_environment”, “lanes”, và “surface”
instructions Mặc định: “true”
Trả về các hướng dẫn đi trên tuyến đường
points_encoded Mặc định: “true”
Cho phép thay đổi mã hóa dữ liệu vị trí trong phản hồi.
Mặc định là mã hóa polyline, nhỏ gọn nhưng yêu cầu
mã máy khách đặc biệt để giải nén. Đặt tham số này
thành “false” để chuyển mã hóa sang các cặp tọa độ đơn
giản như [kinh độ, vĩ độ] hoặc [kinh độ, vĩ độ, độ cao].
36
ch.disable Mặc định: “false”
Sử dụng tham số này kết hợp với một hoặc nhiều tham
số từ bên dưới.
algorithm Mặc định: “round_trip”
Thay đổi thành “alternative_route” khi bạn muốn trả về
nhiều hơn 1 đường đi
alternative_route.max_paths Mặc định: “2”
Nếu algorithm = “alternative_route”, tham số này đặt
số lượng đường dẫn tối đa sẽ được tính toán. Tăng có
thể dẫn đến các lựa chọn thay thế kém hơn.
Bảng 3.4. Các thông số truy vấn có thể gửi lên
Thông tin
paths info Miêu tả Mảng đối tượng (RouteResponsePath) Thông tin bổ sung cho yêu cầu của bạn
37
Hình 3.5. Ví dụ một kết quả tìm đường được trả về bằng API mới
3.2.2 Đề xuất Thuật toán tìm đường đi nhanh nhất
Thuật toán tìm đường đi nhanh nhất có đầu vào là đường đi của người dùng dưới
dạng Polyline. Đường đi này là đầu ra của dịch vụ chỉ đường của VMap. Sau đó thuật
toán sẽ thực hiện các bước sau:
38
- Bước 1: Kết quả trả về của dịch vụ chỉ đường của VMap hiện tại bao gồm các
hướng dẫn di chuyển cũng như Polyline là tọa độ của các bước di chuyển đó. Mỗi
cách di chuyển này ta gọi là 1 Path.
- Bước 2: Từ các Path, ta có được thông tin Polyline bao gồm nhiều Point khác
nhau, mỗi 2 Point là một bước đi thẳng theo chỉ dẫn. Ta tách nhỏ Polyline trong
Path thành các Polyline lần lượt bao gồm 2 Point liền nhau, ta gọi là Line.
- Bước 3: Từ các Line, ta lần lượt cắt thành các mảnh nhỏ hơn, mỗi đoạn dài ~5.96m
(tương ứng 10 pixel trên 1 tile), ta được các Piece. Ta cần sử dụng thư viện shapely
để thực hiện việc này.
- Bước 4: Với mỗi Piece, ta tính toán tâm (Mid-point) và góc so với trục tọa độ.
Mục tiêu là ta cần tính toán cửa sổ cần lấy các điểm ảnh trên đó, từ đó xem được
đoạn đường đó đang có tình trạng giao thông như thế nào. Để tính toán được Mid-
point, em đã sử dụng hàm nội suy interpolate của thư viện shapely để nội suy ra
điểm trung tâm. Tuy nhiên, để sử dụng hảm này, ta cần chuyển hệ quy chiếu của
2 điểm của Piece sang hệ quy chiếu UTM. Em đã sử dụng hàm from_latlon và
to_latlon của thư viện utm, với Zone_number=”48” và Zone_letter=”Q”.
- Bước 5: Sử dụng thư viện OpenCV dựng cửa số trên Tile tương ứng với Mid-
Point để lấy tất cả các pixel ảnh thuộc của sổ đó, từ đo tính toán được tình trạng
giao thông tại Piece đó. Do hệ thống đường của VMap và Google là không trùng
khớp hoàn toàn, vì thế ta cần mở rộng của sổ theo chiều dọc để tăng khả năng có
dữ liệu. Sau khi thử nghiệm, em thấy độ chiều dọc của cửa sổ có giá trị 30 là hợp
lý.
39
Hình 3.6. Hệ thống đường của VMap và Google không hoàn toàn trùng khớp
Hình 3.7. Ví dụ trích xuất thông tin từ một Tile
- Bước 6: Chuẩn hóa dữ liệu thu được tại điểm đó bằng cách gán điểm trung bình
cho các điểm ảnh trong đó. Nếu điểm ảnh đó màu xanh hoặc không có giá trị, gán
giá trị bằng 1, nếu màu cam, gán giá trị bằng 2, lần lượt gán 3, 4 với các điểm ảnh
màu đỏ và nâu. Ta lấy trung bình và làm tròn để có giá trị của cửa sổ đó. Một vấn
40
đề gặp phải ở đây là ảnh Google Traffic Tile được kết xuất theo đường với màu
chủ đạo là Xanh, Cam, Đỏ và Nâu và được làm nhạt dần ở viền. Để có thể biết
chính xác một điểm ảnh là Xanh, Cam, Đỏ hay Nâu ở bảng mã màu RGB là rất
khó. Để giải quyết vấn đề này, em đã chuyển đổi ảnh sang bảng mã màu HSV
bằng cách sử dụng hàm cvtColor của thư viện OpenCV. Sau khi chuyển sáng mã
màu HSV, các pixel màu xanh sẽ có giá trị H (Hue) trong khoảng [57, 90], các
pixel màu cam có giá trị H trong khoảng [18, 40], pixel màu đỏ có giá trị H trong
khoảng [2, 10], pixel màu nấu có giá trị H trong khoảng [0, 1].
Hình 3.8. Các mức độ giao thông của Google Traffic
- Bước 7: Ta gom tất cả các giá trị của sổ sau khi chuẩn hóa để có đầu vào cho mô
hình học máy.
- Bước 8: Chạy mô hình để ước lượng thời gian di chuyển tương ứng với từng Path.
Từ đó, ta sắp xếp các Path theo thời gian di chuyển ngắn nhất thay vì đưa ra Path
có quãng đường ngắn nhất.
41
Hình 3.9. Quy trình của Thuật toán tìm đường đi nhanh nhất
42
CHƯƠNG 4. TRIỂN KHAI, THỰC NGHIỆM VÀ ĐÁNH GIÁ
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
4.1.1 Xây dựng bộ dữ liệu thử nghiệm
Xây dựng bộ dữ liệu thử nghiệm bằng cách chọn ngẫu nhiên 1200 điểm đầu và
1200 điểm cuối trong khu vực nội thành Hà Nội. Sử dụng thư viện request của NodeJS
để lấy hướng dẫn di chuyển của Dịch vụ tìm đường Google (Google Direction API) và
Dịch vụ tìm đường của VMap. Với kết quả trả về của dịch vụ tìm đường VMap, ta sẽ
trích xuất đặc trưng theo phương pháp trình bày ở phần trước làm đầu vào của thuật toán
học máy. Với kết quả của Dịch vụ tìm đường Google ta sẽ có được thời gian ước lượng
di chuyển trong tình trạng giao thông tương ứng với kết quả đầu ra của thuật toán. Kết
hợp hai thông tin này ta sẽ có được dữ liệu thử nghiệm. Bộ dữ liệu thử nghiệm được lưu
trữ trong cơ sở dữ liệu MongoDB và xuất ra dưới dạng file csv.
- Tổng số dữ liệu: 3401
- Dữ liệu tập train: 3000 dữ liệu
- Dữ liệu tập test: 401 dữ liệu
Hình 4.1. Quy trình xây dựng bộ dữ liệu thử nghiệm
4.1.2 Thử nghiệm và tìm mô hình hiệu quả nhất
Tiến hành thử nghiệm các thuật toán khác nhau để xây dựng mô hình tối ưu nhất
từ bộ dữ liệu thử nghiệm. Ở đây, em đã thử nghiệm với 2 thuật toán là Hồi quy tuyến
tính và RNN. Em sử dụng lần lượt 2 đối tượng LinearRegression và MLPRegressor của
thư viện sklearn để thực hiện với các thông số để mặc định. Cách thức thực hiện và so
sánh kết quả được thể hiện ở Hình 4.2 và Bảng 4.1.
43
Để đánh giá chất lượng dữ liệu, hệ số xác định R2 và sai số RMSE được sử dụng
để phân tích ước lượng thời gian di chuyển. Phân tích hồi qui là nghiên cứu sự phụ thuộc
của 1 biến (biến phụ thuộc) vào 1 hay nhiều biến khác (biến độc lập), nhằm mục đích
ước lượng (hay dự đoán) giá trị trung bình của biến phụ thuộc trên cơ sở các giá trị biết
trước của các biến độc lập.
Mô hình hồi qui tuyến tính k biến: Y = 1+ 2X2 + …+ kXk + U (1)
- Y: biến phụ thuộc X2 ,…,Xk : các biến độc lập
- U: sai số ngẫu nhiên
- 1 là hệ số tự do
- j là các hệ số hồi quy riêng, cho biết khi Xj tăng 1 đơn vị thì trung bình của Y sẽ
thay đổi j đơn vị trong trường hợp các yếu tố khác không đổi (j=2,…,k).
Hệ số xác định 0≤ R2 ≤1 Có thể nói R2 phản ánh tỷ lệ mô hình lý thuyết phản ánh
thực tế.
RMSE tính theo công thức sau:
44
Hình 4.2. Quy trình xây dựng bộ dữ liệu thử nghiệm
Kết quả thử nghiệm cho thấy với mô hình RNN có kết quả tốt hơn với chỉ số R2
không quá khác biệt (chênh lệch 0.0017), tuy nhiên RMSE thấp hơn 27%. Sau khi đã xây
dựng được mô hình, em sử dụng thư viện pickle để lưu mô hình xuống ổ cứng.
Bảng 4.1. Kết quả thử nghiệm
Thuật toán R2 RMSE MSE
Hồi quy tuyến tính 0.9175 87.80 7708.51
RNN 0.9192 64.361 4142.39
45
4.2 Triển khai công cụ thu thập bộ dữ liệu Google Traffic Tiles
Yêu cầu: NodeJS, NPM, PM2.
PM2 là một trình quản lý các tiến trình dành cho các ứng dụng NodeJS. Nó được
viết bằng chính NodeJS và Shell. PM2 cũng được tích hợp bộ cân bằng tải (load
balancer). Sử dụng lệnh npm i -g pm2 để cài đặt pm2 cho hệ thống.
Thực hiện sao chép tệp tin downloadImgGGTraffic.js vào thư mục /deployment.
Chạy lệnh npm i polygon-lookup request để cài đặt thư viện. Chạy lệnh pm2 start
downloadImgGGTraffic.js để chạy công cụ thu thập bộ dữ liệu Google Traffic Tiles. Để
tiến trình luôn chạy dù hệ thống có thể bị khởi động lại, ta sử dụng lệnh pm2 save để lưu
danh sách các tiến trình và pm2 startup để khai báo khởi động pm2 cùng hệ thống.
Hình 4.3. Tiến trình thu thập bộ dữ liệu Google Traffic Tiles được khởi tạo
Hình 4.4. PM2 được khai báo khởi động cùng hệ thống
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
Yêu cầu: Python, PIP, Flask, Waitress
Tương tự PM2, Waitress là một trình quản lý các tiến trình dành cho các ứng dụng
WSGI của Python. Sử dụng lệnh pip install waitress để cài đặt Waitress cho hệ thống.
Thực hiện sao chép tệp tin app.py vào thư mục /deployment. Chạy lệnh pip install flask
để cài đặt Flask. Tương tự với các thư viện cần thiết. Chạy lệnh waitress-serve –call
‘flaskr:VMap_direction’ để chạy ứng dụng web dưới dạng tiến trình. Lúc này, tiến trình
đã chạy ở cổng 8000.
Để có thể thay thế trực tiếp Dịch vụ tìm đường cũ của VMap, ta cần cấu hình
nginx (công cụ proxy hệ thống VMap đang sử dụng) đến cổng 8000. Vào thư mục
46
/etc/nginx/conf.d/ và tiến hành chỉnh sửa file VMap.conf. Thêm đoạn mã sau vào phần
proxy_pass http://10.101.3.215:8000;
proxy_cache VMap_cache; proxy_cache_revalidate on; proxy_cache_min_uses 3; proxy_cache_use_stale error timeout updating http_500
proxy_cache_lock on;
proxy_set_header X-Real-IP $remote_addr; proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; proxy_set_header Host $http_host; proxy_set_header X-NginX-Proxy true;
# Enables WS support proxy_http_version 1.1; proxy_set_header Upgrade $http_upgrade; proxy_set_header Connection "upgrade"; proxy_redirect off;
location /route { http_502 http_503 http_504; }
cấu hình tên miền VMap.vn để cập nhật dịch vụ tìm đường của VMap.
Sau khi triển khai thành công Dịch vụ tìm đường mới, chúng ta tiến hành thử
nghiệm trên ứng dụng nền tảng web và nền tảng di động của VMap. Kết quả di chuyển
thực tế được trình bày ở Bảng 4.2.
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
Bảng 4.2. Kết quả thử nghiệm thực tế
Google Map VMap cũ Vmap mới Thực tế
144 Xuân Thủy → 716 Láng 17 phút 10 phút 17 phút 17 phút
302 Láng → 275 Nguyễn 6 phút 7 phút 6 phút 6 phút
Trãi
144 Xuân Thủy → 10 Thụy 18 phút 15 phút 17 phút 18 phút
Khuê
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
Sau khi tiến hành thử nghiệm em nhận thấy thời gian phản hồi của dịch vụ còn
chậm. Cụ thể là khoảng 3 giây với yêu cầu tìm đường cho 1 tuyến đường và 8 giây cho
một yêu cầu. Chậm hơn rất nhiều so với chỉ khoảng 1 giây cho cả 2 yêu cầu trên khi sử
dụng dịch vụ cũ. Lý do của việc này là do quá trình tách đặc trưng từ ảnh Google Traffic
Tile tốn rất nhiều thời gian để xử lý. Ngoài ra, thời gian xử lý này còn phụ thuộc của
tuyến đường tìm được. Đây là một vấn đề cần giải quyết trong tương lai.
50
CHƯƠNG 5. KẾT LUẬN VÀ ĐỊNH HƯỚNG
Kết quả đạt được
Như vậy, trong luận văn này, em đã lần lượt trình bày các nghiên cứu của bản
thân để thực hiện các công việc: (i) Xây dựng công cụ thu thập bộ dữ liệu Google Traffic
Tiles, (ii) 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 và (iii) 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. Việc xây dựng công cụ
thu thập bộ dữ liệu Google Traffic Tiles đang ở mức thử nghiệm trong nội thành Hà Nội
với 15.128 tile, tự động cập nhật sau mỗi 5 phút. Tiếp theo đó, em đã lần lượt trình bày
cách tách các đặc trưng từ bộ dữ liệu này phụ thuộc tuyến đường tìm được bằng cách xử
dụng các kỹ thuật xử lý ảnh. Từ đó, em đã tiến hành xây dựng bộ dữ liệu thử nghiệm với
3401 dữ liệu bằng cách sử dụng Dịch vụ tìm đường của VMap và Dịch vụ tìm đường của
Google Map. Sau đó, em tiến hành xây dựng mô hình bằng cách thử nghiệm bằng cách
sử dụng Hồi quy tuyến tính và mạng nơ-ron RNN. Từ đó cho thấy RNN khá hiệu quả
trong việc ước lượng thời gian di chuyển với RMSE=64,361. Cuối cùng, em đã tiến hành
triển khai các công cụ, thuật toán này lên hệ thống của VMap đồng thời em cũng tiến
hành thử nghiệm trực tiếp trên ứng dụng nền tảng web và ứng dụng nền tảng di động của
VMap. Kết quả ban đầu cho thấy kết quả khá tương đồng so với kết quả thu được từ
Google Map.
Định hướng phát triển tương lai
Tuy đã triển khai dịch vụ vào thực tế, nhưng dịch vụ còn một số vấn đề còn tồn
tại và nổi bật nhất là thời gian xử lý quá chậm trong quá trình xử lý ảnh bóc tách feature.
Trong tương lai, em sẽ tìm cách giảm thời gian của quá trình này đến xuống mức có thể
chấp nhận được với người dùng. Ngoài ra các kỹ thuật bộ nhớ đệm để tăng tốc dịch vụ
cho toàn hệ thống. Ngoài ra, em cũng sẽ tiến hành tối ưu mô hình để đạt được hiệu quả
tốt hơn. Việc mở rộng phạm vi Google Traffic Tile sẽ được tính toán vì những dữ liệu
giao thông của Google hiện tại chỉ phủ tại các thành phố lớn trên cả nước. Vì vậy với
việc áp dụng một số kỹ thuật như chỉ tải về các hình ảnh có thay đổi thì việc cập nhật
hình ảnh trong khoảng thời gian 5 phút là khả thi.
51
TÀI LIỆU THAM KHẢO
“Đề án ‘Phát triển Hệ tri thức Việt số hóa.’” .
[1]
“VMap - Bản đồ Việt Nam.” https://vmap.vn/.
[2]
“OpenStreetMap.” https://www.openstreetmap.org/.
[3]
[4]
“OpenStreetMap Wiki.” https://wiki.openstreetmap.org/wiki/Main_Page.
[5] Nhóm phát triển VMap, “Tài liệu nội bộ,” 2020.
[6] Bộ Giao thông vận tải, “Quy chuẩn kỹ thuật quốc gia về Báo hiệu đường bộ.” 2019.
[7] R. Fairhurst, “Project-GraphHopper,” 2019.
[8] G. Leduc, “Road Traffic Data : Collection Methods and Applications,” EUR Number
Tech, pp. 2–10, 2008.
[9]
“About OGC | OGC.” https://www.ogc.org/about.
[10] A. Doyce, “WWW Mapping Bộ thư viện,” Open GIS Consort., 1997.
[11] “OpenGIS Web Map Tile Service
Implementation Standard
| OGC.”
https://www.ogc.org/standards/wmts.
[12] “Geo-location APIs
| Google Maps
Platform
| Google Cloud.”
https://cloud.google.com/maps-platform/.
[13] “Google Map.” https://sites.google.com/site/bestmapgogle/.
[14] “About us - GraphHopper Directions API.” https://www.graphhopper.com/about-us/.
[15] “JavaScript,” J. Inf. Process. Manag., 2001, doi: 10.1241/johokanri.44.584.
[16] R. Prediger, R. Winzinger, R. Prediger, and R. Winzinger, “Node.js,” in Node.js, 2015.
[17] T. E. Oliphant, “Python for scientific computing,” Comput. Sci. Eng., 2007, doi:
10.1109/MCSE.2007.58.
[18] F. Pedregosa et al., “Scikit-learn: Học máy in Python,” J. Mach. Learn. Res., 2011.
[19] A. C. Muller and S. Guido, Introduction to học máy with scikit-learn. 2017.
[20] C.-C. Chang and C.-J. Lin, “LIBSVM,” ACM Trans. Intell. Syst. Technol., 2011, doi:
10.1145/1961189.1961199.
[21] “TensorFlow.” https://www.tensorflow.org/.
[22] M. Grinberg, “Flask Web Developement,” O’Reilly, 2014, doi: 10.1007/s13398-014-
0173-7.2.
52
