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 và được ứng dụng sâu rộng vào đời sống, việc định vị và tìm kiếm lộ trình di chuyển đã chuyển dịch từ các phương thức truyền thống như bản đồ giấy, chỉ dẫn trực tiếp hoặc các thiết bị dẫn đường cố định sang các dịch vụ bản đồ trực tuyến. Các nền tảng phổ biến như Google Maps, Bing Maps và OpenStreetMap cung cấp dữ liệu phong phú, cập nhật liên tục, hỗ trợ người dùng lập kế hoạch di chuyển hiệu quả. Tuy nhiên, tác giả chỉ ra rằng trải nghiệm người dùng trên một số dịch vụ hiện nay vẫn còn những điểm bất tiện khi thực hiện thao tác thay đổi điểm xuất phát hoặc điểm đến. Thay vì cho phép chọn hoặc chạm trực tiếp trên bản đồ một cách linh hoạt, người dùng thường phải kéo thả biểu tượng vị trí hoặc thao tác qua nhiều bước phức tạp, gây khó khăn nhất định trên các thiết bị di động hoặc đối với người dùng phổ thông.
Đề tài "Xây dựng ứng dụng nền tảng web tìm đường đi ngắn nhất trên bản đồ" do sinh viên Đỗ Xuân Toàn thực hiện dưới sự hướng dẫn của TS. Lương Thanh Nhạn tại Trường Đại học Quản lý và Công nghệ Hải Phòng (2024) tập trung giải quyết bài toán tối ưu hóa tìm đường trên nền tảng web với giao diện tương tác trực tiếp.
Mục tiêu và các nhiệm vụ nghiên cứu được xác định theo văn bản bao gồm:
- Tìm hiểu hiện trạng và khảo sát bài toán tìm đường đi ngắn nhất trên bản đồ số.
- Nghiên cứu lý thuyết đồ thị, công thức tính khoảng cách địa lý và các thuật toán tìm đường đi ngắn nhất (Dijkstra, Bellman-Ford, Floyd-Warshall, A*,...).
- Thu thập, xử lý và chuyển đổi dữ liệu bản đồ mở từ nguồn OpenStreetMap (OSM) thành cấu trúc đồ thị phù hợp.
- Phân tích và thiết kế hệ thống: xây dựng các biểu đồ Use Case, biểu đồ tuần tự, biểu đồ lớp và cấu trúc cơ sở dữ liệu.
- Cài đặt ứng dụng web hoàn chỉnh gồm phía máy chủ (Backend) và giao diện người dùng (Frontend), tích hợp thư viện bản đồ tương tác.
- Thử nghiệm hệ thống trên các kịch bản thực tế (đường hai chiều, đường một chiều, đường cấm theo loại phương tiện) và đánh giá hiệu năng thuật toán.
Đối tượng và phạm vi nghiên cứu của đề tài:
- Đối tượng nghiên cứu: Các thuật toán tìm đường đi ngắn nhất trên đồ thị, cấu trúc dữ liệu không gian của OpenStreetMap và quy trình xây dựng ứng dụng web bản đồ tương tác.
- Đối tượng sử dụng: Người dùng thông thường, người di chuyển hàng ngày, khách du lịch, nhân viên giao hàng có nhu cầu tra cứu tuyến đường.
- Phạm vi không gian (địa lý): Một khu vực nhỏ thuộc địa bàn thành phố Hải Phòng, Việt Nam.
- Phạm vi công nghệ: Môi trường Node.js, Express.js, Body-Parser, JavaScript, HTML, CSS, thư viện bản đồ Leaflet, công cụ trích xuất dữ liệu Overpass Turbo và định dạng dữ liệu JSON.
Cơ sở lý thuyết và phương pháp
Khóa luận thiết lập nền tảng lý thuyết dựa trên lý thuyết đồ thị và biểu diễn dữ liệu không gian địa lý:
- Mô hình hóa dữ liệu OpenStreetMap: Dữ liệu OSM được cấu trúc thành các thực thể cơ bản gồm
node (điểm có tọa độ vĩ độ lat và kinh độ lon), way (tập hợp các node định hình đoạn đường hoặc ranh giới, kèm theo các nhãn tags mô tả thuộc tính như loại đường highway, đường một chiều oneway, quyền truy cập của phương tiện).
- Công thức tính khoảng cách mặt cầu (Haversine Formula): Để tính toán trọng số khoảng cách thực tế giữa hai điểm tọa độ địa lý $(lat_1, lon_1)$ và $(lat_2, lon_2)$ trên bề mặt Trái Đất bán kính $r$, tác giả sử dụng công thức:
$$\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 đó $\Delta lat = lat_2 - lat_1$, $\Delta lon = lon_2 - lon_1$, và hàm $\text{haversin}(\theta) = \sin^2(\theta / 2)$.
Tác giả đã tổng hợp và phân tích lý thuyết ưu - nhược điểm của 8 thuật toán tìm đường đi ngắn nhất phổ biến:
| Thuật toán |
Ưu điểm |
Nhược điểm |
| Dijkstra |
Dễ hiểu, dễ triển khai; hoạt động tốt trên đồ thị vô hướng/có hướng có trọng số dương; kết quả chính xác tuyệt đối. |
Không xử lý được đồ thị có trọng số âm; độ phức tạp $O((V+E)\log V)$. |
| Bellman-Ford |
Xử lý được trọng số âm; phát hiện chu trình âm; hoạt động tốt trên đồ thị có trọng số âm. |
Độ phức tạp thời gian lớn $O(VE)$; tốc độ chậm khi số cạnh nhiều. |
| A* |
Hiệu quả trên đồ thị lớn; sử dụng hàm heuristic để tối ưu không gian tìm kiếm; độ chính xác cao khi chọn đúng heuristic. |
Độ phức tạp và hiệu quả phụ thuộc nhiều vào chất lượng của hàm heuristic. |
| Floyd-Warshall |
Xử lý được trọng số âm; tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị. |
Độ phức tạp thời gian rất lớn $O(V^3)$; tốn bộ nhớ lưu trữ ma trận trọng số. |
| Contraction Hierarchies |
Rất hiệu quả trên đồ thị quy mô lớn; tối ưu thời gian tìm kiếm bằng kỹ thuật chia và trộn đỉnh. |
Tiền xử lý đồ thị phức tạp; kỹ thuật cài đặt khó. |
| Johnson |
Xử lý được trọng số âm; tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh. |
Độ phức tạp thời gian cao $O(VE + V^2 \log V)$. |
| Yen's K Shortest Paths |
Tìm được nhiều đường đi ngắn nhất thay thế ($K$ đường); phù hợp bài toán đa mục tiêu. |
Độ phức tạp thời gian cao $O(K(E + V^2 \log V))$ khi $K$ lớn. |
| SPFA |
Xử lý được trọng số âm; thời gian thực thi trung bình thấp hơn Bellman-Ford trong nhiều trường hợp. |
Dễ rơi vào vòng lặp vô hạn nếu có chu trình âm; hiệu suất không ổn định ở trường hợp xấu nhất. |
Phương pháp nghiên cứu thực tế được triển khai bao gồm:
- Phương pháp tiếp cận: Phân tích tài liệu chuyên ngành về thuật toán đồ thị, hệ thống thông tin địa lý (GIS) và lập trình web.
- Phương pháp thực nghiệm: Chạy thử nghiệm và đo lường thời gian thực thi của các thuật toán trên hai bộ dữ liệu thực tế (bộ dữ liệu kiểm tra nhỏ
graphtest và bộ dữ liệu dự án Hải Phòng).
- Phương pháp phân tích: Đánh giá số liệu hiệu năng, tính đúng đắn của lộ trình và khả năng đáp ứng yêu cầu ràng buộc giao thông.
- Nghiên cứu phát triển & Tư duy thiết kế: Thiết kế kiến trúc phần mềm, cấu trúc dữ liệu trung gian và giao diện tương tác trực tiếp trên bản đồ.
- Nguồn dữ liệu: Dữ liệu không gian trích xuất từ OpenStreetMap thông qua công cụ trực tuyến Overpass Turbo (
https://overpass-turbo.eu) bằng ngôn ngữ truy vấn Overpass QL.
Thiết kế và triển khai
Hệ thống được thiết kế theo mô hình phân tách rõ ràng giữa xử lý logic phía máy chủ và hiển thị tương tác phía máy khách:
[Người dùng / Trình duyệt]
[Frontend: HTML5, CSS3, JavaScript, Leaflet]
[Backend: Node.js, Express.js Web Server]
1. Kiến trúc dữ liệu và xử lý đồ thị
- Trích xuất dữ liệu: Sử dụng Overpass QL để truy vấn mạng lưới đường giao thông tại khu vực Hải Phòng, xuất ra tệp
data.json chứa 20.104 điểm (nodes) và 1.883 đoạn đường (ways), dung lượng khoảng 2,3 MB.
- Chuyển đổi đồ thị: Từ
data.json, hệ thống tính toán khoảng cách Haversine giữa các điểm kề nhau và ánh xạ các cờ thuộc tính giao thông (oneway, motorcar, motorcycle, foot) để tạo ra tệp graph.json. Tệp đồ thị gồm 9.944 đỉnh (nodes), dung lượng khoảng 2,6 MB, trong đó mỗi đỉnh lưu danh sách các đỉnh kề, cự ly (km) và điều kiện phương tiện được phép lưu thông.
2. Thiết kế mô hình hệ thống (UML)
- Đặc tả Use Case chính "Tìm đường đi ngắn nhất": Tác nhân chính là người dùng. Người dùng lựa chọn loại phương tiện (ô tô, xe máy, đi bộ), chọn điểm xuất phát và điểm đến (bằng cách gõ từ khóa gợi ý hoặc nhấp chọn trực tiếp trên bản đồ), sau đó nhấn lệnh tìm kiếm. Hệ thống kiểm tra tính hợp lệ, thực thi giải thuật và vẽ tuyến đường ngắn nhất lên bản đồ.
- Biểu đồ tuần tự (Sequence Diagrams): Xây dựng cho 4 quy trình nghiệp vụ: "Chọn phương tiện", "Chọn điểm bắt đầu", "Chọn điểm đến" và "Tìm đường đi ngắn nhất".
- Biểu đồ lớp (Class Diagram): Gồm các lớp chính:
F-Bando: Lớp giao diện quản lý các thành phần chọn phương tiện (Phuongtien), điểm bắt đầu (Diembatdau), loại điểm đến (Loaidiemden), ô nhập điểm đến (Diemden), nút tìm kiếm (Timduongdi) và các phương thức xử lý sự kiện tương ứng.data: Biểu diễn đối tượng dữ liệu OSM thô gồm id, type, lat, lon, nodes: Array<String>, tags: Map<String, String>.graph: Biểu diễn đồ thị mạng lưới gồm nodeId, node, distance, cùng các thuộc tính logic oneway, foot, motorcar, motorcycle.
3. Môi trường triển khai và công nghệ
- Phần cứng đề xuất: Bộ xử lý đa nhân, RAM tối thiểu 2 GB, kết nối Internet ổn định.
- Phần mềm và môi trường thực thi: Hệ điều hành Windows/Linux, môi trường Node.js (kiểm tra qua lệnh
node -v), trình quản lý gói npm, máy chủ chạy qua node server.js, trình duyệt web (Google Chrome, Mozilla Firefox, Microsoft Edge), trình soạn thảo mã nguồn Visual Studio Code.
- Công nghệ Frontend & Bản đồ: HTML5, CSS3, JavaScript thuần, thư viện Leaflet mã nguồn mở để dựng lớp bản đồ nền và hiển thị các đối tượng Marker/Polyline tuyến đường.
Nội dung chính theo từng chương
Mở đầu
Tác giả trình bày tính cấp thiết của đề tài trong bối cảnh số hóa giao thông; xác định mục đích xây dựng ứng dụng web tìm đường ngắn nhất nhằm nâng cao tiện ích di chuyển; đề ra 6 nhiệm vụ nghiên cứu cụ thể; lựa chọn 5 phương pháp nghiên cứu (tiếp cận, thực nghiệm, phân tích, R&D, tư duy thiết kế); giới hạn phạm vi nghiên cứu về địa lý tại một khu vực của thành phố Hải Phòng và phạm vi công nghệ xoay quanh JavaScript, Node.js, Leaflet và OpenStreetMap.
Chương 1. Tổng quan về đề tài
Chương này đánh giá chi tiết hiện trạng các dịch vụ bản đồ trực tuyến hiện có (Google Maps, Bing Maps, OpenStreetMap). Tác giả phân tích điểm hạn chế khi người dùng cần thay đổi điểm đầu/cuối lộ trình trên các nền tảng này và phát biểu bài toán xây dựng hệ thống mới. Các yêu cầu chức năng được xác định rõ: hỗ trợ 3 loại phương tiện (đi bộ, xe máy, ô tô), chọn điểm linh hoạt qua nhập liệu hoặc chạm trực tiếp trên bản đồ, cung cấp tính năng gợi ý tìm kiếm thông minh, và trực quan hóa tuyến đường tối ưu. Đồng thời, chương 1 giới thiệu chi tiết vai trò của các công cụ phát triển: Visual Studio Code, Node.js, Express.js, Body-Parser, OpenStreetMap, Overpass Turbo, định dạng JSON, 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 phương pháp luận xử lý dữ liệu và thuật toán:
- Thu thập và cấu trúc dữ liệu: Mô tả quy trình truy vấn dữ liệu từ Overpass Turbo bằng Overpass QL, xuất file
data.json (20.104 node, 1.883 way) và chuyển đổi thành graph.json (9.944 node). Trọng số khoảng cách giữa các node được tính toán chính xác bằng công thức Haversine.
- Khảo sát và thử nghiệm so sánh thuật toán: Tác giả tiến hành thử nghiệm đối sánh thời gian thực thi của 3 thuật toán tiêu biểu (Dijkstra, Bellman-Ford, Floyd-Warshall) trên cùng tập dữ liệu dự án:
| Tiêu chí so sánh |
Thuật toán Dijkstra |
Thuật toán Bellman-Ford |
Thuật toán Floyd-Warshall |
| Thời gian thực thi (Dữ liệu dự án Hải Phòng) |
Xấp xỉ 177 mili giây |
Xấp xỉ 1 phút 56 giây |
Xấp xỉ 1 giờ 46 phút 26 giây |
| Tính chính xác của lộ trình |
Trùng khớp hoàn toàn |
Trùng khớp hoàn toàn |
Trùng khớp hoàn toàn |
| Khả năng xử lý trọng số âm |
Không hỗ trợ |
Có hỗ trợ |
Có hỗ trợ |
| Độ phức tạp lý thuyết |
$O((V+E)\log V)$ |
$O(VE)$ |
$O(V^3)$ |
Kết quả chứng minh Dijkstra đạt tốc độ vượt trội trên mạng lưới giao thông thực tế (vốn không có trọng số âm), phù hợp để tích hợp vào ứng dụng web thời gian thực.
3. Mô phỏng từng bước thuật toán Dijkstra: Tác giả trình bày chi tiết bảng biến thiên qua đồ thị mẫu gồm 9 đỉnh (từ đỉnh 0 đến đỉnh 8), thể hiện rõ quá trình khởi tạo khoảng cách vô cùng ($+\infty$), cập nhật nhãn đỉnh kề và truy vết đỉnh cha qua từng bước lặp.
4. Thiết kế hệ thống: Trình bày chi tiết bảng đặc tả Use Case "Tìm đường đi ngắn nhất", sơ đồ hoạt động nghiệp vụ, 4 biểu đồ tuần tự và biểu đồ lớp.
Chương 3. Cài đặt chương trình và thử nghiệm
Chương 3 trình bày việc thiết lập môi trường máy chủ Node.js và giao diện web hoàn chỉnh. Tác giả thực hiện kiểm thử hệ thống qua các kịch bản thực tế:
- Thử nghiệm gợi ý tìm kiếm địa điểm: Khi người dùng nhập ký tự, hệ thống phản hồi danh sách gợi ý địa điểm tương ứng chính xác.
- Kịch bản đường hai chiều: Hệ thống tìm tuyến đường ngắn nhất bình thường cho cả 3 phương tiện khi không có ràng buộc một chiều.
- Kịch bản đường một chiều: Kiểm thử khi điểm xuất phát và đích yêu cầu đi qua đường một chiều; hệ thống dẫn đường đúng chiều cho ô tô, xe máy và chỉ dẫn hướng đi bộ thích hợp.
- Kịch bản đường cấm người đi bộ và xe máy: Thử nghiệm trên tuyến đường có biển cấm xe máy và người đi bộ; kết quả hệ thống chỉ cho phép ô tô đi qua tuyến đường này, trong khi xe máy và người đi bộ được điều hướng sang tuyến đường vòng hợp lệ.
- Kịch bản đường cấm ô tô: Thử nghiệm trên đoạn đường cấm ô tô; hệ thống tự động tìm đường vòng cho ô tô, trong khi xe máy và người đi bộ vẫn được chỉ dẫn đi qua đoạn đường ngắn nhất đó.
Kết luận và hướng phát triển
Đánh giá mức độ hoàn thành nhiệm vụ theo mục tiêu ban đầu; tổng kết các kết quả đạt được về mặt lý thuyết và sản phẩm ứng dụng; chỉ ra những hạn chế còn tồn tại và đề xuất các hướng nâng cấp mở rộng trong tương lai.
Kết quả và đóng góp
1. Kết quả thực nghiệm cụ thể
- Hiệu năng xử lý thuật toán: Trên tập dữ liệu đồ thị thực tế gồm 9.944 đỉnh của khu vực thành phố Hải Phòng, thuật toán Dijkstra hoàn thành tính toán đường đi ngắn nhất trong thời gian xấp xỉ 177 mili giây, nhanh hơn đáng kể so với Bellman-Ford (xấp xỉ 1 phút 56 giây) và Floyd-Warshall (xấp xỉ 1 giờ 46 phút 26 giây), trong khi kết quả quãng đường và tuyến đường tìm được là hoàn toàn đồng nhất giữa ba thuật toán.
- Xử lý dữ liệu không gian: Đã trích xuất và tiền xử lý thành công tệp dữ liệu
data.json gồm 20.104 node và 1.883 way (dung lượng 2,3 MB), chuyển đổi sang tệp đồ thị graph.json gồm 9.944 node (dung lượng 2,6 MB) phục vụ định tuyến.
- Sản phẩm ứng dụng web: Xây dựng thành công website hoạt động trên máy chủ Node.js, giao diện hiển thị bản đồ số thông qua thư viện Leaflet, cho phép:
- Chọn điểm xuất phát và điểm đích bằng cách nhập liệu có gợi ý từ khóa thông minh hoặc nhấp/chạm trực tiếp vào vị trí bất kỳ trên bản đồ.
- Lựa chọn linh hoạt giữa 3 loại phương tiện di chuyển: Ô tô, Xe máy, Đi bộ.
- Phân luồng chính xác theo luật giao thông: xử lý đúng các trường hợp đường một chiều, đường cấm ô tô, và đường cấm xe máy/người đi bộ.
2. Đóng góp của đề tài
- Làm rõ phương pháp chuyển đổi dữ liệu bản đồ mở OpenStreetMap (OSM) thành mô hình đồ thị có trọng số gắn kèm các thuộc tính ràng buộc luật giao thông thực tế.
- Đề xuất và hiện thực hóa giải pháp cải thiện tương tác người dùng trên web bản đồ bằng cách kết hợp gợi ý tìm kiếm với thao tác chọn điểm trực tiếp trên giao diện Leaflet, khắc phục sự bất tiện của thao tác kéo thả phức tạp trên một số dịch vụ bản đồ hiện hành.
Hạn chế và hướng nghiên cứu tiếp
- Hạn chế:
- Phạm vi dữ liệu địa lý mới chỉ bao phủ một khu vực nhỏ thuộc thành phố Hải Phòng, chưa mở rộng ra toàn thành phố hay phạm vi liên tỉnh.
- Dữ liệu mạng lưới đường được lưu trữ tĩnh dưới dạng tệp JSON (
data.json, graph.json), chưa kết nối cơ sở dữ liệu không gian động chuyên dụng.
- Hệ thống chưa tích hợp các yếu tố giao thông thời gian thực như tình trạng ùn tắc, thời tiết, công trường thi công hay vận tốc di chuyển thực tế để ước tính thời gian di chuyển (ETA).
- Hướng nghiên cứu và phát triển tiếp:
- Mở rộng phạm vi bản đồ ra toàn bộ thành phố Hải Phòng và các tỉnh thành lân cận.
- Cập nhật cơ chế đồng bộ và làm mới dữ liệu tự động từ máy chủ OpenStreetMap.
- Tích hợp dữ liệu giao thông thời gian thực nhằm tối ưu hóa đường đi theo tiêu chí thời gian thay vì chỉ thuần túy theo khoảng cách địa lý.
- Nghiên cứu áp dụng thêm các thuật toán định tuyến nâng cao cho mạng lưới quy mô lớn (như Contraction Hierarchies hoặc A* cải tiến) khi mở rộng tập dữ liệu.
Giá trị tham khảo
Đồ án là tài liệu tham khảo hữu ích cho:
- Sinh viên ngành Công nghệ thông tin, Hệ thống thông tin, Khoa học máy tính: Cung cấp tài liệu mẫu về việc áp dụng lý thuyết đồ thị và thuật toán tìm đường (Dijkstra) vào bài toán kỹ thuật phần mềm thực tế.
- Người phát triển ứng dụng GIS và Bản đồ số (WebGIS): Cung cấp quy trình từng bước từ truy vấn trích xuất dữ liệu OSM qua Overpass Turbo, tính toán cự ly tọa độ cầu bằng công thức Haversine, mô hình hóa file JSON thuộc tính giao thông, đến tích hợp giao diện tương tác bằng Leaflet trên nền tảng Node.js/Express.js.
- Nội dung đáng tham khảo nhất: Phần thực nghiệm đối sánh định lượng thời gian chạy giữa Dijkstra, Bellman-Ford, Floyd-Warshall ở Chương 2 và bộ kịch bản kiểm thử ràng buộc phân làn/đường cấm phương tiện ở Chương 3.
Câu hỏi thường gặp
1. Dữ liệu bản đồ trong đồ án được thu thập từ nguồn nào và qua công cụ gì?
Dữ liệu được thu thập từ dự án bản đồ mở OpenStreetMap (OSM) thông qua công cụ trực tuyến Overpass Turbo (https://overpass-turbo.eu) bằng ngôn ngữ truy vấn Overpass QL, sau đó xuất ra tệp dữ liệu định dạng JSON (data.json) chứa 20.104 điểm (nodes) và 1.883 đoạn đường (ways).
2. Khoảng cách giữa các điểm tọa độ trên bản đồ được tính toán bằng công thức nào?
Hệ thống sử dụng công thức Haversine để tính khoảng cách mặt cầu giữa hai điểm dựa trên tọa độ vĩ độ (lat) và kinh độ (lon):
$$\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)$$
với $r$ là bán kính Trái Đất.
3. Vì sao tác giả lựa chọn thuật toán Dijkstra thay vì Bellman-Ford hay Floyd-Warshall?
Qua thực nghiệm trên tập dữ liệu dự án gồm 9.944 đỉnh tại Hải Phòng, Dijkstra hoàn thành tính toán chỉ trong 177 ms, trong khi Bellman-Ford mất 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 và có mật độ cạnh phù hợp, Dijkstra vừa đảm bảo tính chính xác tuyệt đối, vừa đáp ứng yêu cầu phản hồi tức thì trên ứng dụng web.
4. Hệ thống xử lý các quy định giao thông (đường một chiều, đường cấm) như thế nào trong thuật toán?
Trong tệp đồ thị graph.json, mỗi liên kết giữa các đỉnh được gán các cờ giá trị Boolean: oneway (đường một chiều), motorcar (ô tô), motorcycle (xe máy), foot (đi bộ). Khi người dùng chọn loại phương tiện, thuật toán Dijkstra sẽ lọc các cạnh thỏa mãn điều kiện di chuyển của phương tiện đó trước khi tính toán đường đi ngắn nhất.
5. Tech stack chi tiết được sử dụng để xây dựng ứng dụng web là gì?
- Backend: Node.js, framework Express.js, middleware Body-Parser.
- Frontend: HTML5, CSS3, JavaScript.
- Thư viện bản đồ: Leaflet (hiển thị bản đồ nền, điểm đánh dấu và đường dẫn Polyline).
- Môi trường & Công cụ: Visual Studio Code, npm, trình duyệt web (Chrome, Firefox, Edge).
Kết luận
Đồ á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 đồ" của sinh viên Đỗ Xuân Toàn đã hoàn thành đầy đủ các nhiệm vụ phân tích, thiết kế và cài đặt một hệ thống web định tuyến giao thông hoàn chỉnh. Bằng việc kết hợp dữ liệu mở OpenStreetMap, công thức tính khoảng cách Haversine và thuật toán Dijkstra, hệ thống đã giải quyết hiệu quả bài toán tìm đường ngắn nhất theo cự ly cho ba loại phương tiện phổ biến. Kết quả thử nghiệm thực tế trên khu vực thành phố Hải Phòng chứng minh giải thuật đạt tốc độ phản hồi nhanh (177 ms) và xử lý chính xác các ràng buộc giao thông như đường một chiều hay đường cấm phương tiện.
