Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, các dịch vụ bản đồ số và điều hướng trực tuyến như Google Maps, Bing Maps và OpenStreetMap đã trở thành công cụ thiết yếu hỗ trợ việc di chuyển hàng ngày. Mặc dù các nền tảng thương mại hiện nay sở hữu kho dữ liệu khổng lồ cùng nhiều tính năng đa dạng, tác giả Đỗ Xuân Toàn (ngành Công nghệ thông tin, Trường Đại học Quản lý và Công nghệ Hải Phòng) nhận thấy vẫn tồn tại một số hạn chế nhất định về mặt trải nghiệm thao tác người dùng. Điển hình là khi cần thay đổi điểm xuất phát hoặc điểm đến, người dùng trên một số nền tảng thường phải kéo thả biểu tượng vị trí một cách thủ công thay vì có thể tương tác chạm/chọn trực tiếp tại điểm mong muốn trên bản đồ. Thao tác này gây tốn thời gian, đặc biệt là trên các thiết bị di động hoặc đối với nhóm người dùng ít am hiểu công nghệ.

Xuất phát từ thực tế đó, đồ án tốt nghiệp "Xây dựng ứng dụng nền tảng web tìm đường đi ngắn nhất trên bản đồ" (hướng dẫn bởi TS. Lương Thanh Nhàn, năm 2024) được thực hiện nhằm giải quyết các nhiệm vụ và mục tiêu cụ thể:

  1. Mục tiêu nghiên cứu: Nghiên cứu bài toán tìm đường đi ngắn nhất trên mạng lưới giao thông; phân tích, thiết kế và xây dựng một ứng dụng nền tảng web có khả năng tìm kiếm tuyến đường tối ưu giữa hai địa điểm dựa trên thuật toán định tuyến và hiển thị trực quan trên bản đồ số.
  2. Nhiệm vụ nghiên cứu (theo phân công đề tài):
    • Tìm hiểu hiện trạng và cơ sở lý thuyết của bài toán tìm đường đi ngắn nhất trên bản đồ.
    • Thu thập, xử lý và thiết kế cấu trúc dữ liệu bản đồ từ nguồn dữ liệu mở.
    • Phân tích và thiết kế hệ thống thông tin (xây dựng các biểu đồ Use Case, biểu đồ tuần tự, biểu đồ lớp).
    • Lập trình, cài đặt ứng dụng nền tảng web và tiến hành thử nghiệm các kịch bản định tuyến theo từng loại phương tiện giao thông.
    • Đánh giá hiệu năng thuật toán, nhận xét kết quả và đề xuất hướng hoàn thiện.
  3. Đối tượng và phạm vi nghiên cứu:
    • Đối tượng sử dụng: Người dùng thông thường tham gia giao thông, người có nhu cầu di chuyển hàng ngày, du khách và nhân viên giao hàng.
    • Phạm vi không gian/địa lý: Dữ liệu bản đồ được giới hạn thử nghiệm tại một khu vực nhỏ thuộc thành phố Hải Phòng, Việt Nam.
    • Phạm vi công nghệ: Ngôn ngữ lập trình JavaScript, HTML, CSS; môi trường Node.js kết hợp Express.js và Body-Parser; thư viện bản đồ tương tác Leaflet; nguồn dữ liệu địa lý mở OpenStreetMap (OSM) và công cụ Overpass Turbo.

Cơ sở lý thuyết và phương pháp

Đồ án kết hợp các nền tảng lý thuyết về lý thuyết đồ thị, mô hình dữ liệu địa lý không gian và phương pháp kỹ nghệ phần mềm để giải quyết bài toán tìm đường.

1. Khung lý thuyết và mô hình toán học

  • Mô hình hóa mạng lưới giao thông thành đồ thị: Không gian địa lý được biểu diễn dưới dạng đồ thị $G = (V, E)$, trong đó tập đỉnh $V$ đại diện cho các điểm nút giao thông (nodes) và tập cạnh $E$ đại diện cho các đoạn đường kết nối (ways) có hướng hoặc vô hướng kèm theo trọng số khoảng cách địa lý và các thuộc tính lưu thông.
  • Công thức tính khoảng cách Haversine: Để xác định trọng số khoảng cách thực tế giữa hai điểm nút trên bề mặt cong của Trái Đất dựa trên kinh độ (longitude) và vĩ độ (latitude), tác giả sử dụng công thức Haversine:

$$\text{Distance} = 2 \cdot r \cdot \arcsin\left(\sqrt{\text{haversin}(\Delta lat) + \cos(lat_1) \cdot \cos(lat_2) \cdot \text{haversin}(\Delta lon)}\right)$$

Trong đó:

  • $r$ là bán kính Trái Đất.

  • $\Delta lat = lat_2 - lat_1$ và $\Delta lon = lon_2 - lon_1$.

  • Hàm $\text{haversin}(\theta) = \sin^2\left(\frac{\theta}{2}\right)$.

  • $(lat_1, lon_1)$ và $(lat_2, lon_2)$ lần lượt là tọa độ địa lý của điểm thứ nhất và điểm thứ hai.

  • Thuật toán định tuyến: Tác giả tiến hành khảo cứu và so sánh tổng quan các thuật toán tìm đường kinh điển và hiện đại: Dijkstra, Bellman-Ford, $A^*$ (A-Star), Floyd-Warshall, Contraction Hierarchies, Johnson, Yen's K Shortest Paths và SPFA (Shortest Path Faster Algorithm).

Thuật toán Ưu điểm Nhược điểm Độ phức tạp thời gian
Dijkstra Dễ hiểu, dễ triển khai; hoạt động chính xác trên đồ thị có trọng số dương. Không xử lý được trọng số âm. $O((V+E)\log V)$
Bellman-Ford Xử lý được trọng số âm và phát hiện chu trình âm. Chạy chậm khi số cạnh lớn. $O(VE)$
$A^*$ (A Star) Hiệu quả trên đồ thị lớn; sử dụng hàm heuristic tối ưu hóa tìm kiếm. Phụ thuộc nhiều vào chất lượng chọn hàm heuristic. Phụ thuộc heuristic
Floyd-Warshall Xử lý được trọng số âm; tìm đường ngắn nhất giữa tất cả các cặp đỉnh. Chi phí tính toán lớn; tốn bộ nhớ lưu ma trận trọng số. $O(V^3)$
Contraction Hierarchies Tốc độ tìm kiếm nhanh trên mạng lưới giao thông lớn. Tiền xử lý phức tạp, khó triển khai. Đòi hỏi tiền xử lý cao
Johnson Tìm đường ngắn nhất giữa mọi cặp đỉnh trên đồ thị có trọng số âm. Độ phức tạp tính toán còn cao trên đồ thị lớn. $O(VE + V^2 \log V)$
Yen's K Shortest Paths Tìm được nhiều lựa chọn đường đi thay thế ($K$ đường ngắn nhất). Độ phức tạp tăng cao khi giá trị $K$ lớn. $O(K(E + V^2 \log V))$
SPFA Xử lý trọng số âm; thời gian thực tế nhanh trong một số trường hợp. Hiệu suất không ổn định; dễ lặp vô hạn khi có chu trình âm. Kém ổn định ở trường hợp xấu

2. Phương pháp nghiên cứu và thu thập dữ liệu

Tác giả áp dụng phối hợp các phương pháp nghiên cứu kỹ thuật:

  • Phương pháp tiếp cận tài liệu: Tổng hợp lý thuyết về cấu trúc dữ liệu, thuật toán đồ thị và các chuẩn định dạng bản đồ số.
  • Phương pháp thực nghiệm và phân tích định lượng: Tiến hành cài đặt song song ba thuật toán (Dijkstra, Bellman-Ford, Floyd-Warshall) để chạy thử nghiệm trên hai bộ dữ liệu kiểm thử (tập đồ thị mẫu graphtest và tập dữ liệu thực tế của dự án), từ đó đo lường chính xác thời gian thực thi (mili-giây, giây, phút) và đánh giá độ chính xác của đường đi.
  • Nguồn dữ liệu thực tế: Dữ liệu bản đồ được truy vấn trực tiếp từ hệ thống OpenStreetMap (OSM) thông qua công cụ Overpass Turbo (https://overpass-turbo.eu) bằng ngôn ngữ truy vấn Overpass QL. Dữ liệu tải về lưu trữ dưới dạng JSON, bao gồm 20.104 điểm nút (node) và 1.883 đoạn đường (way), với dung lượng tệp là 2,0 MB. Sau quá trình tính toán khoảng cách Haversine và trích xuất quan hệ láng giềng, tập đồ thị graph hoàn chỉnh thu được gồm 9.944 đỉnh với dung lượng 2,0 MB.

Thiết kế và triển khai

Hệ thống được thiết kế theo kiến trúc ứng dụng web hướng dịch vụ với sự phân tách rõ ràng giữa tầng hiển thị phía máy khách (Frontend) và tầng xử lý nghiệp vụ phía máy chủ (Backend).

1. Kiến trúc công nghệ

  • Frontend: Xây dựng bằng HTML5, CSS3 và JavaScript thuần. Tích hợp thư viện Leaflet mã nguồn mở để dựng bản đồ tương tác, hiển thị các lớp bản đồ nền OSM, quản lý các điểm đánh dấu (marker), bắt sự kiện click trực tiếp trên bản đồ để chọn tọa độ và vẽ đường tuyến (polyline) kết quả.
  • Backend: Xây dựng trên môi trường Node.js kết hợp framework Express.js. Sử dụng middleware Body-Parser để bóc tách và xử lý các yêu cầu HTTP POST chứa thông số định tuyến gửi lên từ giao diện người dùng.
  • Cấu trúc lưu trữ dữ liệu:
    • Tệp data.json: Chứa thông tin gốc của các node (thuộc tính id, lat, lon) và các way (thuộc tính id, mảng nodes, và các tags như "highway": "residential", tên đường).
    • Tệp graph.json: Cấu trúc danh sách kề đại diện cho 9.944 đỉnh giao thông. Mỗi phần tử chứa nodeId, danh sách đỉnh kề kèm thuộc tính distance (tính bằng kilomet qua công thức Haversine) và các cờ ràng buộc kiểu Boolean: oneway (đường một chiều), motorcar (cho phép ô tô), motorcycle (cho phép xe máy), foot (cho phép người đi bộ).

2. Thiết kế hệ thống (UML)

Hệ thống được mô hình hóa chi tiết qua các sơ đồ:

  • Biểu đồ Use Case: Mô tả ca sử dụng trọng tâm "Tìm đường đi ngắn nhất". Người dùng tương tác cung cấp thông tin gồm loại phương tiện (ô tô, xe máy, đi bộ), điểm bắt đầu và điểm đến (nhập văn bản có gợi ý tự động hoặc chọn trực tiếp trên bản đồ), sau đó kích hoạt chức năng tìm đường để hệ thống tính toán và trả kết quả.
  • Biểu đồ tuần tự (Sequence Diagram): Đặc tả 4 luồng tương tác:
    1. Chọn phương tiện: Người dùng chọn phương thức di chuyển trên giao diện.
    2. Chọn điểm bắt đầu: Bắt sự kiện chọn trên bản đồ hoặc gợi ý văn bản.
    3. Chọn điểm đến: Xác định tọa độ đích đến.
    4. Tìm đường đi ngắn nhất: Gửi yêu cầu tọa độ đến máy chủ Node.js, máy chủ duyệt đồ thị qua thuật toán Dijkstra, tính toán tuyến đường ngắn nhất thỏa mãn các cờ ràng buộc phương tiện và trả dữ liệu tọa độ chuỗi điểm về cho Leaflet hiển thị.
  • Biểu đồ lớp (Class Diagram): Bao gồm lớp giao diện F-Bando (chứa các thuộc tính Phuongtien, Diembatdau, Loaidiemden, Diemden, Timduongdi và các phương thức điều khiển tương ứng), liên kết với cấu trúc dữ liệu bản đồ data (id, type, lat, lon, nodes, tags) và cấu trúc đồ thị graph (nodeId, node, distance, oneway, foot, motorcar, motorcycle).

3. Thực nghiệm và đo kiểm hiệu năng thuật toán

Để lựa chọn thuật toán tối ưu cho hệ thống, tác giả đã tiến hành đo đạc thời gian thực thi giữa Dijkstra, Bellman-Ford và Floyd-Warshall trên cùng bộ dữ liệu đồ thị dự án gồm 9.944 đỉnh:

Thuật toán Thời gian thực thi trên dữ liệu dự án Tính chính xác của tuyến đường Khả năng ứng dụng vào website
Dijkstra ~177 mili-giây Tuyến đường tìm được trùng khớp hoàn toàn Phù hợp nhất (đáp ứng thời gian thực)
Bellman-Ford ~1 phút 56 giây Tuyến đường tìm được trùng khớp hoàn toàn Không phù hợp cho ứng dụng web (quá chậm)
Floyd-Warshall ~1 giờ 46 phút 26 giây Tuyến đường tìm được trùng khớp hoàn toàn Không khả thi cho tương tác trực tuyến

Kết quả thực nghiệm khẳng định việc lựa chọn thuật toán Dijkstra giúp ứng dụng phản hồi kết quả gần như tức thì (~0,177 giây), đáp ứng tốt yêu cầu tương tác thời gian thực trên nền tảng web đối với đồ thị mạng lưới đường bộ có trọng số không âm.

Nội dung chính theo từng chương

Chương 1. Tổng quan về đề tài

Chương 1 trình bày tổng quan về bối cảnh thực tiễn, phân tích hiện trạng các hệ thống tìm đường hiện có và chỉ ra các hạn chế trong thao tác người dùng. Tác giả tiến hành phát biểu bài toán tìm đường đi ngắn nhất trên bản đồ số, xác định rõ các yêu cầu phi chức năng (tích hợp đa dịch vụ, giao diện thân thiện, vận hành ổn định) và yêu cầu chức năng (tùy chọn 3 loại phương tiện di chuyển, hỗ trợ gợi ý tìm kiếm thông minh, cho phép nhấp chọn trực tiếp điểm xuất phát và đích đến trên bản đồ, hiển thị chi tiết lộ trình). Đồng thời, chương này giới thiệu tổng quan bộ công cụ và công nghệ xây dựng chương trình, bao gồm Visual Studio Code, nền tảng máy chủ Node.js, Express.js, Body-Parser, hệ thống dữ liệu OpenStreetMap (OSM), công cụ Overpass Turbo, định dạng dữ liệu JSON, cùng các công nghệ giao diện HTML, CSS, JavaScript và thư viện Leaflet.

Chương 2. Phân tích thiết kế hệ thống

Chương 2 tập trung giải quyết bài toán kỹ thuật thông qua việc phân tích yêu cầu xử lý dữ liệu và thiết kế kiến trúc hệ thống:

  • Mô tả quy trình 4 bước thu thập và xuất dữ liệu từ OpenStreetMap bằng Overpass QL trên công cụ Overpass Turbo.
  • Xây dựng cấu trúc dữ liệu cho tệp data.json (20.104 node, 1.883 way) và chuẩn hóa thành tệp graph.json (9.944 đỉnh kề). Trọng số các cạnh được tính toán dựa trên tọa độ địa lý thông qua công thức Haversine.
  • Trình bày chi tiết lý thuyết và thuật toán từng bước của Dijkstra, minh họa quá trình duyệt đồ thị qua bảng trạng thái qua từng bước lặp từ đỉnh gốc 0 đến đỉnh 8.
  • Trình bày kết quả so sánh hiệu năng giữa Dijkstra, Bellman-Ford và Floyd-Warshall.
  • Xây dựng bảng đặc tả Use Case "Tìm đường đi ngắn nhất", vẽ sơ đồ nghiệp vụ, biểu đồ Use Case, 4 biểu đồ tuần tự cho các luồng thao tác và biểu đồ lớp chi tiết.

Chương 3. Cài đặt chương trình và thử nghiệm

Chương 3 mô tả quá trình cài đặt môi trường và kiểm thử thực tế các chức năng của website:

  • Môi trường hệ thống: Cấu hình máy tính chạy hệ điều hành tương thích (Windows/Linux), bộ xử lý đa nhân, khuyến nghị RAM tối thiểu 2 GB, kết nối Internet ổn định, cài đặt Node.js và npm. Quy trình khởi chạy thông qua các lệnh node -v, npm init --y và node server.js (hoặc node sever.js theo văn bản) để mở cổng dịch vụ trên trình duyệt.
  • Giao diện ứng dụng: Thiết kế trực quan với thanh điều khiển chọn phương tiện, ô tìm kiếm địa điểm hỗ trợ gợi ý từ khóa và khung hiển thị bản đồ Leaflet.
  • Kiểm thử thực nghiệm: Tiến hành kiểm thử toàn diện trên 4 kịch bản giao thông thực tế:
    1. Tuyến đường không có đường một chiều: Cả 3 phương tiện (ô tô, xe máy, đi bộ) đều tìm được lộ trình ngắn nhất thẳng và tối ưu.
    2. Tuyến đường có đường một chiều: Tuyến đường của ô tô và xe máy tự động đổi hướng đi vòng theo đúng quy định chiều lưu thông, trong khi người đi bộ vẫn có thể đi tuyến ngắn nhất nếu đoạn đường đó cho phép đi bộ hai chiều.
    3. Tuyến đường cấm người đi bộ và xe máy: Hệ thống dẫn đường cho ô tô đi vào tuyến đường đó, nhưng tự động chuyển hướng tìm lộ trình khác an toàn hơn cho xe máy và người đi bộ.
    4. Tuyến đường cấm xe ô tô: Hệ thống điều hướng xe máy và người đi bộ đi qua bình thường, trong khi ô tô được điều hướng đi đường vòng thay thế.

Kết quả và đóng góp

  • Kết quả kỹ thuật đạt được:
    • Xây dựng hoàn chỉnh một ứng dụng web tìm đường đi ngắn nhất trên bản đồ với đầy đủ giao diện người dùng và máy chủ xử lý dữ liệu.
    • Xử lý thành công tập dữ liệu địa lý OSM thực tế với 20.104 điểm nút, 1.883 đoạn đường và chuyển đổi thành đồ thị 9.944 đỉnh giao thông.
    • Tích hợp thành công công thức Haversine để tính khoảng cách cung tròn trên mặt cầu và cài đặt thuật toán Dijkstra đạt thời gian xử lý nhanh vượt trội (~177 ms trên 9.944 đỉnh), đảm bảo khả năng phản hồi tức thì.
    • Hệ thống xử lý chính xác các điều kiện ràng buộc luật giao thông đường bộ: đường một chiều (oneway), đường cấm xe máy (motorcycle), đường cấm ô tô (motorcar) và đường cấm người đi bộ (foot).
  • Giải pháp và đóng góp thực tế:
    • Cải tiến phương thức tương tác người dùng: Thay vì phải kéo thả biểu tượng vị trí phức tạp như một số ứng dụng hiện có, người dùng có thể nhấp trực tiếp vào bất kỳ vị trí nào trên bản đồ số để chọn điểm xuất phát và điểm đích, kết hợp cùng tính năng gợi ý tìm kiếm địa điểm thông minh.
    • Cung cấp giải pháp định tuyến tùy biến theo từng loại phương tiện giao thông riêng biệt, nâng cao tính an toàn và tiện lợi khi di chuyển.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế:
    • Dữ liệu địa lý thử nghiệm mới chỉ giới hạn trong phạm vi một khu vực nhỏ của thành phố Hải Phòng.
    • Nguồn dữ liệu đồ thị là dữ liệu tĩnh trích xuất từ OpenStreetMap, chưa tích hợp dữ liệu tình trạng giao thông theo thời gian thực (như cảnh báo ùn tắc, tai nạn, ngập lụt hoặc công trình đang thi công).
  • Hướng phát triển tiếp theo:
    • Mở rộng phạm vi dữ liệu bản đồ cho toàn bộ khu vực thành phố Hải Phòng và các tỉnh, thành phố lân cận.
    • Nghiên cứu tích hợp các nguồn cấp dữ liệu giao thông thời gian thực để cập nhật trọng số cạnh động theo tình hình ùn tắc.
    • Tối ưu hóa thuật toán định tuyến cho các mạng lưới đồ thị quy mô lớn (nghiên cứu áp dụng thêm các kỹ thuật heuristic như $A^*$ hoặc cấu trúc phân cấp Contraction Hierarchies).

Giá trị tham khảo

Đồ án là tài liệu tham khảo có giá trị ứng dụng thực hành cao cho sinh viên ngành Công nghệ thông tin, Kỹ thuật phần mềm và Hệ thống thông tin:

  • Cung cấp quy trình rõ ràng về cách tích hợp và xử lý dữ liệu bản đồ nguồn mở OpenStreetMap qua công cụ Overpass Turbo và ngôn ngữ truy vấn Overpass QL.
  • Tài liệu mẫu cho việc áp dụng công thức toán học Haversine vào việc tính toán khoảng cách tọa độ GPS thực tế trên mô hình đồ thị.
  • Hướng dẫn chi tiết cách xây dựng ứng dụng Web GIS mini kết hợp Node.js, Express.js và thư viện Leaflet, cũng như phương pháp mô hình hóa hướng đối tượng thông qua hệ thống biểu đồ UML.

Câu hỏi thường gặp

1. Đồ án sử dụng công thức toán học nào để tính khoảng cách giữa hai tọa độ địa lý trên bản đồ?
Tác giả sử dụng công thức Haversine để tính khoảng cách dựa trên vĩ độ và kinh độ của hai điểm trên mặt cầu Trái Đất, với công thức: $\text{Distance} = 2 \cdot r \cdot \arcsin(\sqrt{\text{haversin}(\Delta lat) + \cos(lat_1) \cdot \cos(lat_2) \cdot \text{haversin}(\Delta lon)})$.

2. Dữ liệu bản đồ được lấy từ nguồn nào và có quy mô bao nhiêu?
Dữ liệu được trích xuất từ OpenStreetMap (OSM) thông qua công cụ Overpass Turbo tại địa chỉ https://overpass-turbo.eu. Tệp dữ liệu ban đầu data.json bao gồm 20.104 điểm (node) và 1.883 đoạn đường (way) với dung lượng 2,0 MB. Sau khi xử lý thành đồ thị graph.json, tập dữ liệu bao gồm 9.944 đỉnh.

3. Tại sao tác giả lại lựa chọn thuật toán Dijkstra thay vì Bellman-Ford hay Floyd-Warshall cho ứng dụng web?
Dựa trên kết quả đo kiểm thực nghiệm trên tập dữ liệu dự án gồm 9.944 đỉnh, thuật toán Dijkstra hoàn thành tính toán trong khoảng 177 mili-giây, trong khi Bellman-Ford mất xấp xỉ 1 phút 56 giây và Floyd-Warshall mất tới 1 giờ 46 phút 26 giây. Do đồ thị giao thông thực tế không có trọng số âm, Dijkstra đảm bảo tính chính xác tuyệt đối với tốc độ xử lý nhanh nhất, đáp ứng yêu cầu tương tác thời gian thực trên web.

4. Hệ thống xử lý các điều kiện giao thông đặc thù như thế nào đối với từng loại phương tiện?
Trong cấu trúc đồ thị graph.json, mỗi cạnh kết nối được gán các thuộc tính Boolean gồm oneway, motorcar, motorcycle, foot. Khi người dùng chọn phương tiện (ô tô, xe máy, đi bộ), thuật toán sẽ lọc các cạnh thỏa mãn điều kiện lưu thông tương ứng để tìm đường đi hợp lệ, đảm bảo không dẫn xe vào đường cấm hoặc đường ngược chiều.

Kết luận

Đồ án tốt nghiệp của sinh viên Đỗ Xuân Toàn đã hoàn thành tốt các mục tiêu nghiên cứu và kỹ thuật đề ra thông qua việc xây dựng thành công ứng dụng nền tảng web tìm đường đi ngắn nhất trên bản đồ. Bằng việc kết hợp dữ liệu mở OpenStreetMap, công thức Haversine và thuật toán định tuyến Dijkstra trên nền tảng Node.js và Leaflet, hệ thống mang lại giải pháp tìm đường nhanh chóng (~177 ms), chính xác và linh hoạt theo từng loại phương tiện giao thông. Đồ án có tính thực tiễn cao, đóng vai trò là tài liệu tham khảo bổ ích cho việc phát triển các ứng dụng hệ thống thông tin địa lý và kỹ thuật phần mềm web.