Giới thiệu dự án

Trong bối cảnh đô thị hóa và sự bùng nổ của thương mại điện tử, dịch vụ dựa trên vị trí (Location-Based Services - LBS) đã trở thành hạ tầng thiết yếu trong đời sống số. Theo các báo cáo phân tích thị trường hệ thống thông tin địa lý (GIS), hơn 80% dữ liệu số hiện nay mang thuộc tính không gian và nhu cầu điều hướng tối ưu cho phương tiện giao thông liên tục tăng trưởng với tốc độ trên 15% mỗi năm. Tuy nhiên, việc phụ thuộc vào các dịch vụ bản đồ thương mại đóng kín (như Google Maps Platform) thường đi kèm với chi phí bản quyền API cao, giới hạn dung lượng truy vấn, và trải nghiệm người dùng đôi khi gặp khó khăn khi thao tác tùy biến điểm đầu/cuối trực tiếp trên bản đồ web.

Đồ án tốt nghiệp chuyên ngành Công nghệ Thông tin với đề 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 (Trường Đại học Quản lý và Công nghệ Hải Phòng, 2024) đã giải quyết bài toán cốt lõi này bằng việc làm chủ dữ liệu bản đồ mở OpenStreetMap (OSM) và triển khai thuật toán tìm đường tối ưu theo từng phương tiện di chuyển.

                  KIẾN TRÚC TỔNG THỂ HỆ THỐNG
+-------------------------------------------------------------+
|                      NGƯỜI DÙNG                             |
|  - Chọn phương tiện: Đi bộ / Xe máy / Ô tô                  |
|  - Chọn điểm xuất phát & đích: Click bản đồ / Tìm kiếm      |
+------------------------------+------------------------------+
                               |
                               v
+-------------------------------------------------------------+
|               GIAO DIỆN CLIENT (FRONTEND)                   |
|  - Leaflet.js v1.9.4 Render bản đồ & Layer đường đi         |
|  - HTML5, CSS3, JavaScript ES6+ xử lý sự kiện tương tác     |
+------------------------------+------------------------------+
                               | HTTP POST / API Request
                               v
+-------------------------------------------------------------+
|               MÁY CHỦ ỨNG DỤNG (BACKEND)                    |
|  - Node.js v20 LTS / Express.js v4.18 RESTful Router        |
|  - Bộ tiền xử lý & Lọc ràng buộc giao thông (Graph Filter)  |
|  - Thuật toán Dijkstra Engine (O((V + E) log V))            |
|  - Công thức Haversine tính toán trọng số hình học (km)     |
+------------------------------+------------------------------+
                               | Query / Caching
                               v
+-------------------------------------------------------------+
|                  NGUỒN DỮ LIỆU BẢN ĐỒ                       |
|  - Dữ liệu OpenStreetMap (OSM) qua Overpass Turbo API       |
|  - Graph Cache: 9.944 Nodes, 1.883 Ways, Ràng buộc 1 chiều |
+-------------------------------------------------------------+

Mục tiêu của dự án (Project Objectives)

  1. Khai thác và chuyển đổi dữ liệu không gian: Thu thập và tiền xử lý dữ liệu OpenStreetMap khu vực đô thị thông qua công cụ Overpass Turbo và ngôn ngữ Overpass QL, chuyển hóa thành cấu trúc đồ thị mạng lưới giao thông dạng JSON.
  2. Xây dựng mô hình đồ thị có ràng buộc đa phương thức: Thiết kế đồ thị gồm 9.944 đỉnh (nodes) và các cạnh (edges) mang thuộc tính trọng số khoảng cách (km) kết hợp các cờ logic (oneway, motorcar, motorcycle, foot).
  3. Hiện thực hóa và đánh giá hiệu năng thuật toán: Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất, thực nghiệm đối chuẩn (benchmark) với thuật toán Bellman-Ford và Floyd-Warshall trên cùng tập dữ liệu.
  4. Phát triển ứng dụng Web GIS tương tác hoàn chỉnh: Tích hợp thư viện Leaflet.js trên giao diện Frontend và xây dựng Backend với Node.js/Express.js, cho phép người dùng click trực tiếp trên bản đồ hoặc tìm kiếm thông minh.

Phạm vi và giới hạn (Scope & Limitations)

  • Phạm vi địa lý: Khu vực mạng lưới đường bộ đô thị thành phố Hải Phòng.
  • Công nghệ cốt lõi: Node.js, Express.js, Leaflet.js, OpenStreetMap, JSON Graph.
  • Giới hạn: Đồ án tập trung vào bài toán tối ưu khoảng cách tĩnh (Static Shortest Path) dựa trên dữ liệu hạ tầng giao thông OSM, chưa tích hợp dữ liệu mật độ giao thông theo thời gian thực (Live Traffic).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các nền tảng bản đồ trực tuyến hiện hành tuy hoàn chỉnh nhưng vẫn bộc lộ các hạn chế nhất định về quyền tự chủ dữ liệu, chi phí và mức độ linh hoạt tương tác:

Tiêu chí Google Maps OpenStreetMap (Gốc) Giải pháp Đồ án
Mã nguồn & Dữ liệu Đóng kín, tính phí theo lượt gọi API (Pay-as-you-go) Dữ liệu mở, giao diện mặc định chưa tối ưu cho từng vùng Mã nguồn mở hoàn toàn, làm chủ cấu trúc đồ thị nội bộ
Thao tác chọn điểm Phải kéo thả biểu tượng điểm mốc, dễ nhầm lẫn trên mobile Giao diện điều hướng chuẩn chưa thân thiện với người dùng phổ thông Click/chạm trực tiếp vào bất kỳ vị trí nào trên bản đồ để gán tọa độ
Ràng buộc phương tiện Phức tạp, khó can thiệp tùy biến thuật toán Cần công cụ thứ ba (OSRM, GraphHopper) Phân tầng trực tiếp theo cờ motorcar, motorcycle, foot
Khả năng tự triển khai (Self-hosted) Không hỗ trợ máy chủ riêng nội bộ Hỗ trợ nhưng cấu hình phức tạp Độc lập, chạy gọn nhẹ trên máy chủ Node.js cục bộ/on-premise

Phân loại yêu cầu hệ thống theo mô hình MoSCoW:

  • Must have: Tìm đường chính xác theo 3 loại phương tiện (ô tô, xe máy, đi bộ); xử lý đường một chiều (oneway); tính toán khoảng cách thực tế bằng công thức Haversine.
  • Should have: Gợi ý tìm kiếm địa điểm thông minh (Autocompletion); cho phép click trực tiếp trên bản đồ để chọn tọa độ xuất phát và đích.
  • Could have: Tích hợp danh mục địa điểm tiện ích (quán cafe, bệnh viện, cây xăng) trong khu vực.
  • Won't have: Mô phỏng định tuyến theo tín hiệu đèn giao thông và tắc đường thời gian thực trong giai đoạn 1.

Thiết kế hệ thống

Hệ thống được tổ chức theo kiến trúc 3 lớp (3-Tier Architecture):

  1. Lớp biểu diễn (Presentation Layer - Frontend):
    • HTML5 & CSS3: Xây dựng layout responsive, thân thiện trên trình duyệt máy tính và thiết bị di động.
    • Leaflet.js v1.9.4: Thư viện mã nguồn mở render các lớp bản đồ tương tác (Map Tiles từ OpenStreetMap), hiển thị marker điểm mốc và vẽ polyline hành trình dẫn đường.
  2. Lớp ứng dụng (Application Layer - Backend):
    • Node.js v20 LTS & Express.js v4.18.2: Khởi tạo máy chủ HTTP RESTful API, tiếp nhận yêu cầu định tuyến qua định dạng JSON.
    • Body-Parser v1.20.2: Middleware giải mã dữ liệu payload trong HTTP POST request.
    • Dijkstra Routing Engine: Module nạp đồ thị vào bộ nhớ RAM và thực thi giải thuật tìm đường với độ phức tạp $O((V + E)\log V)$.
  3. Lớp dữ liệu (Data Layer):
    • File data.json: Lưu trữ 20.104 điểm (nodes) và 1.883 đoạn đường (ways) trích xuất từ OSM.
    • File graph.json: Đồ thị giao thông đã tiền xử lý gồm 9.944 đỉnh và danh sách kề có trọng số.
// Cấu trúc mô tả một đoạn đường trong file data.json
{
  "type": "way",
  "id": 240515176,
  "nodes": [2482439165, 11747679934, 2482439159, 11747679935],
  "tags": {
    "highway": "residential",
    "name": "Ngõ 398 Vũ Chí Thắng",
    "oneway": "no",
    "motorcar": "yes",
    "motorcycle": "yes",
    "foot": "yes"
  }
}

// Cấu trúc đỉnh và danh sách kề trong graph.json
{
  "nodeId": "8730486582",
  "adjacentNodes": [
    {
      "node": "10095784904",
      "distance": 0.021872,
      "oneway": false,
      "motorcar": true,
      "motorcycle": true,
      "foot": true
    }
  ]
}

Phương pháp tính toán khoảng cách địa lý (Haversine Formula)

Khoảng cách thực tế giữa hai điểm $P_1(\text{lat}_1, \text{lon}_1)$ và $P_2(\text{lat}_2, \text{lon}_2)$ trên mặt cầu Trái Đất bán kính $R = 6371\text{ km}$ được tính toán bằng công thức:

$$\Delta\text{lat} = \text{lat}_2 - \text{lat}_1, \quad \Delta\text{lon} = \text{lon}_2 - \text{lon}_1$$

$$\text{haversin}(\theta) = \sin^2\left(\frac{\theta}{2}\right)$$

$$\text{Distance} = 2R \cdot \arcsin\left(\sqrt{\text{haversin}(\Delta\text{lat}) + \cos(\text{lat}_1)\cos(\text{lat}_2)\text{haversin}(\Delta\text{lon})}\right)$$

Tiến trình thực hiện và Quản trị rủi ro

Dự án áp dụng quy trình phát triển lặp (Iterative Development) với 4 mốc tiến độ:

  • Giai đoạn 1 (Tuần 1 - 3): Khảo sát lý thuyết đồ thị, xác định khu vực nghiên cứu tại Hải Phòng, xây dựng câu truy vấn Overpass QL để thu thập dữ liệu OSM.
  • Giai đoạn 2 (Tuần 4 - 6): Tiền xử lý dữ liệu không gian, xây dựng module tính toán Haversine và sinh đồ thị mạng lưới đường giao thông graph.json.
  • Giai đoạn 3 (Tuần 7 - 9): Hiện thực hóa thuật toán Dijkstra có ràng buộc phương tiện; benchmark thuật toán với Bellman-Ford và Floyd-Warshall.
  • Giai đoạn 4 (Tuần 10 - 12): Tích hợp Frontend Leaflet.js, kiểm thử các kịch bản cấm đường và hoàn thiện báo cáo đồ án.
Rủi ro kỹ thuật Mức độ Biện pháp giảm thiểu
Dữ liệu OSM bị phân mảnh, đứt đoạn đồ thị Trung bình Sử dụng thuật toán tìm kiếm nút kề gần nhất (Nearest Node Snapping) để nối các điểm đứt gãy
Kích thước file đồ thị lớn làm chậm khởi động Thấp Chuyển đổi định dạng sang JSON cấu trúc phẳng và nạp vào bộ nhớ (In-memory Graph) ngay khi server khởi động
Thời gian phản hồi tăng cao khi đồ thị mở rộng Trung bình Tối ưu hóa cấu trúc Priority Queue cho thuật toán Dijkstra

Implementation và kết quả

Quá trình phát triển và Code Snippets

Hệ thống được phát triển hoàn toàn bằng JavaScript/Node.js. Dưới đây là triển khai tính toán khoảng cách Haversine và cốt lõi thuật toán Dijkstra có xét đến các điều kiện giao thông:

// Module tính khoảng cách Haversine giữa 2 tọa độ (Node.js)
function calculateHaversineDistance(lat1, lon1, lat2, lon2) {
    const R = 6371; // Bán kính Trái Đất (km)
    const toRad = (angle) => (angle * Math.PI) / 180;

    const dLat = toRad(lat2 - lat1);
    const dLon = toRad(lon2 - lon1);
    const rLat1 = toRad(lat1);
    const rLat2 = toRad(lat2);

    const a = Math.sin(dLat / 2) * Math.sin(dLat / 2) +
              Math.sin(dLon / 2) * Math.sin(dLon / 2) * 
              Math.cos(rLat1) * Math.cos(rLat2);
    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    return R * c; // Trả về khoảng cách theo đơn vị km
}

// Cốt lõi thuật toán Dijkstra lọc theo phương tiện di chuyển
function findShortestPathDijkstra(graph, startNodeId, endNodeId, vehicleType) {
    const distances = {};
    const previous = {};
    const unvisited = new Set();

    // Khởi tạo bảng khoảng cách
    for (const node of graph) {
        distances[node.nodeId] = Infinity;
        previous[node.nodeId] = null;
        unvisited.add(node.nodeId);
    }
    distances[startNodeId] = 0;

    while (unvisited.size > 0) {
        // Tìm đỉnh có khoảng cách nhỏ nhất trong tập unvisited
        let currentNodeId = null;
        for (const nodeId of unvisited) {
            if (currentNodeId === null || distances[nodeId] < distances[currentNodeId]) {
                currentNodeId = nodeId;
            }
        }

        if (distances[currentNodeId] === Infinity || currentNodeId === endNodeId) {
            break;
        }

        unvisited.delete(currentNodeId);
        const currentNodeData = graph.find(n => n.nodeId === currentNodeId);
        if (!currentNodeData || !currentNodeData.adjacentNodes) continue;

        for (const edge of currentNodeData.adjacentNodes) {
            // Kiểm tra quyền lưu thông của phương tiện
            if (vehicleType === 'motorcar' && !edge.motorcar) continue;
            if (vehicleType === 'motorcycle' && !edge.motorcycle) continue;
            if (vehicleType === 'foot' && !edge.foot) continue;

            const alt = distances[currentNodeId] + edge.distance;
            if (alt < distances[edge.node]) {
                distances[edge.node] = alt;
                previous[edge.node] = currentNodeId;
            }
        }
    }

    // Tái cấu trúc lộ trình đường đi
    const path = [];
    let curr = endNodeId;
    while (curr) {
        path.unshift(curr);
        curr = previous[curr];
    }
    return { path, totalDistance: distances[endNodeId] };
}

// Endpoint điều hướng của Express.js
const express = require('express');
const app = express();
app.use(express.json());

app.post('/api/route/shortest-path', (req, res) => {
    const { startNode, endNode, vehicle } = req.body;
    if (!startNode || !endNode || !vehicle) {
        return res.status(400).json({ error: 'Thiếu tham số đầu vào hợp lệ.' });
    }
    const result = findShortestPathDijkstra(globalGraphData, startNode, endNode, vehicle);
    res.json({
        status: 'success',
        data: result
    });
});

Đánh giá hiệu năng và Thử nghiệm thực tế

Thử nghiệm được thực hiện trên môi trường phần cứng máy tính tiêu chuẩn (CPU đa nhân, 8GB RAM, hệ điều hành Windows/Linux, Node.js v20) với tập dữ liệu đồ thị giao thông thực tế gồm 9.944 đỉnh:

Tiêu chí đối chuẩn Dijkstra Bellman-Ford Floyd-Warshall
Độ phức tạp lý thuyết $O((V + E)\log V)$ $O(V \cdot E)$ $O(V^3)$
Thời gian thực thi (Dataset nhỏ) 2.1 ms 4.8 ms 12.6 ms
Thời gian thực thi (9.944 đỉnh) ~177 ms ~1 phút 56 giây (116.000 ms) ~1 giờ 46 phút 26 giây (6.386.000 ms)
Độ chính xác quãng đường Chuẩn xác 100% Chuẩn xác 100% Chuẩn xác 100%
Khả năng ứng dụng Web thời gian thực Xuất sắc (Khả thi) Không khả thi Hoàn toàn không khả thi 
                       THỜI GIAN THỰC THI (LOG-SCALE)
Dijkstra        | [177 ms]
Bellman-Ford    | [======================= 116.000 ms]
Floyd-Warshall  | [================================================== 6.386.000 ms]

Kết quả kiểm thử cho thấy: Thuật toán Dijkstra hoàn toàn áp đảo về hiệu năng trên đồ thị trọng số không âm, giảm thời gian xử lý tới 99,85% so với Bellman-Ford và 99,997% so với Floyd-Warshall. Thời gian phản hồi trung bình ~177 ms đảm bảo độ mượt mà tối đa cho trải nghiệm người dùng trên nền tảng web.

Hệ thống đã trải qua 4 kịch bản kiểm thử nghiệm ngặt:

  1. Tuyến đường thông thường (Hai 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 tương đồng.
  2. Tuyến đường một chiều (oneway = true): Ô tô và xe máy tuân thủ tuyệt đối chiều lưu thông, trong khi người đi bộ được thuật toán chỉ dẫn lộ trình linh hoạt ngắn hơn.
  3. Đường cấm xe máy và người đi bộ (Đoạn cao tốc/cầu vượt chuyên dụng): Hệ thống tự động chuyển hướng xe máy và người đi bộ sang đường nhánh an toàn.
  4. Đường ngõ nhỏ cấm ô tô (motorcar = false): Hệ thống dẫn đường ô tô đi vòng theo các trục đường chính, trong khi xe máy và người đi bộ được tối ưu qua ngõ tắt.

Đổi mới và đóng góp

  1. Làm chủ quy trình xây dựng Web GIS độc lập: Đồ án đã loại bỏ hoàn toàn sự phụ thuộc vào các dịch vụ định tuyến thương mại trả phí. Toàn bộ chu trình từ khai phá dữ liệu OpenStreetMap (Overpass QL), cấu trúc hóa đồ thị JSON, đến xây dựng API định tuyến đều được tự động hóa.
  2. Mô hình hóa linh hoạt luật giao thông đô thị Việt Nam: Bằng cách tích hợp trực tiếp các cờ logic (oneway, motorcar, motorcycle, foot) vào cấu trúc kề của từng đỉnh, giải thuật Dijkstra được tinh chỉnh để giải quyết triệt để bài toán cấm đường đặc thù tại các đô thị lớn.
  3. Tối ưu hóa trải nghiệm tương tác bản đồ: Ứng dụng khắc phục nhược điểm thao tác kéo thả phức tạp của các nền tảng cũ, cho phép người dùng click trực tiếp vào tọa độ bất kỳ trên nền bản đồ Leaflet.js để bắt đầu tìm kiếm.
  4. Đóng góp học thuật và thực tiễn: Cung cấp bộ benchmark chi tiết và mẫu kiến trúc tham chiếu cho sinh viên, kỹ sư phần mềm khi triển khai các hệ thống GIS, Logistics hoặc điều hướng nội bộ.

Ứng dụng thực tế và triển khai

Tình huống ứng dụng thực tế (Use Cases)

  • Logistics & Giao hàng nội đô: Hỗ trợ các đơn vị vận chuyển tối ưu hóa lộ trình cho đội ngũ shipper xe máy qua các mạng lưới ngõ hẹp tại đô thị Việt Nam.
  • Cổng thông tin du lịch thông minh: Tích hợp vào website của các thành phố (như Hải Phòng) để hỗ trợ du khách tìm kiếm lộ trình đi bộ hoặc di chuyển bằng phương tiện cá nhân qua các điểm danh lam thắng cảnh.
  • Hệ thống điều phối nội bộ cho khu công nghiệp, bệnh viện, trường đại học: Triển khai bản đồ cục bộ cho các khuôn viên rộng lớn mà Google Maps chưa cập nhật chi tiết các tuyến đường nội bộ.

Hướng dẫn triển khai hệ thống (Deployment Guide)

Yêu cầu hệ thống:

  • Node.js: Phiên bản 18.x hoặc 20.x LTS trở lên.
  • Phần cứng: Tối thiểu 2 CPU Cores, 2GB RAM, 500MB dung lượng ổ cứng khả dụng.
  • Mạng: Kết nối Internet để nạp Leaflet Tile Layers từ OpenStreetMap.

Các bước cài đặt và vận hành:

# Bước 1: Di chuyển vào thư mục dự án
cd web-shortest-path-osm

# Bước 2: Khởi tạo và cài đặt các package phụ thuộc
npm init -y
npm install express body-parser

# Bước 3: Khởi chạy máy chủ ứng dụng
node server.js

Sau khi khởi chạy thành công, truy cập trình duyệt tại địa chỉ: http://localhost:3000 hoặc cấu hình Reverse Proxy thông qua Nginx trên máy chủ đám mây.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Dữ liệu bản đồ được trích xuất dưới dạng tệp JSON tĩnh; chưa hỗ trợ cơ chế đồng bộ tự động (Hot-sync) khi OpenStreetMap cập nhật dữ liệu mới.
  • Thuật toán Dijkstra tiêu thụ bộ nhớ tỉ lệ thuận với số lượng đỉnh khi mở rộng phạm vi toàn quốc; chưa áp dụng cấu trúc dữ liệu nén phân tầng (Contraction Hierarchies).

Hướng phát triển trong tương lai

  • Nâng cấp thuật toán sang $A^*$ và Contraction Hierarchies (CH): Bổ sung hàm Heuristic (khoảng cách đường chim bay) để giảm không gian tìm kiếm, đẩy tốc độ phản hồi xuống dưới 10 ms đối với đồ thị hàng triệu đỉnh.
  • Tích hợp dữ liệu thời gian thực (Live Traffic): Kết nối dữ liệu GPS của đội xe thông qua giao thức MQTT/WebSocket để cập nhật trọng số cạnh theo tình trạng ùn tắc giao thông.
  • Hỗ trợ định vị GPS trực tiếp trên di động: Sử dụng HTML5 Geolocation API để tự động nhận diện vị trí thực tế của người dùng làm điểm bắt đầu.

Đối tượng hưởng lợi

  • Sinh viên & Giảng viên Công nghệ Thông tin: Tài liệu tham khảo toàn diện về ứng dụng cấu trúc dữ liệu và giải thuật vào bài toán GIS thực tế, kết hợp công nghệ Web hiện đại.
  • Kỹ sư phát triển phần mềm (Software Engineers): Mã nguồn mẫu sạch sẽ, chuẩn mực về việc bóc tách dữ liệu bản đồ OSM, tối ưu hóa thuật toán trên Node.js và render bản đồ tương tác với Leaflet.js.
  • Doanh nghiệp vừa và nhỏ (SMEs/Logistics): Giải pháp định tuyến không tốn chi phí bản quyền API, dễ dàng đóng gói và tùy biến triển khai on-premise an toàn, bảo mật.

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

1. Yêu cầu kỹ thuật tối thiểu để triển khai ứng dụng là gì?

Hệ thống chỉ yêu cầu máy chủ cài đặt Node.js v18+ và 2GB RAM. Do sử dụng cấu trúc đồ thị JSON tối ưu trong bộ nhớ, hệ thống không đòi hỏi cài đặt các hệ quản trị cơ sở dữ liệu cồng kềnh như PostgreSQL/PostGIS cho các đô thị vừa và nhỏ.

2. Tại sao đồ án chọn thuật toán Dijkstra thay vì Bellman-Ford hay Floyd-Warshall?

Vì trọng số khoảng cách trên đồ thị giao thông thực tế luôn là số dương ($\ge 0$). Dijkstra có độ phức tạp thời gian $O((V+E)\log V)$, đạt thời gian thực thi ~177 ms trên 9.944 đỉnh, vượt trội hoàn toàn so với Bellman-Ford (~1 phút 56 giây) và Floyd-Warshall (~1 giờ 46 phút).

3. Hệ thống xử lý đường một chiều và đường cấm theo phương tiện như thế nào?

Mỗi đoạn đường (way) trong OpenStreetMap chứa các thuộc tính (tags) như oneway, motorcar, motorcycle, foot. Khi xây dựng danh sách kề trong đồ thị, hệ thống chỉ tạo cung có hướng tương ứng và gán cờ điều kiện. Thuật toán Dijkstra sẽ lọc bỏ các cạnh không thỏa mãn loại phương tiện được chọn trước khi tính toán khoảng cách.

4. Dữ liệu bản đồ OpenStreetMap được cập nhật vào hệ thống như thế nào?

Dữ liệu được truy vấn thông qua công cụ Overpass Turbo bằng ngôn ngữ Overpass QL, xuất ra định dạng GeoJSON/JSON và được module xử lý backend chuyển đổi thành cấu trúc graph.json.

5. Khả năng mở rộng quy mô (Scalability) của hệ thống ra sao?

Với quy mô một thành phố (khoảng 10.000 đỉnh), hệ thống đáp ứng hàng nghìn truy vấn đồng thời với độ trễ thấp. Để mở rộng ra phạm vi toàn quốc (hàng triệu đỉnh), hệ thống có thể nâng cấp lên thuật toán Contraction Hierarchies (CH) kết hợp lưu trữ đồ thị phân tán trên Redis.

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 tác giả Đỗ Xuân Toàn đã hoàn thành xuất sắc toàn bộ các mục tiêu nghiên cứu và thực nghiệm đề ra. Dự án không chỉ chứng minh tính ưu việt vượt trội của giải thuật Dijkstra trên đồ thị giao thông thực tế (đạt tốc độ phản hồi ~177 ms trên gần 10.000 đỉnh) mà còn mang lại một giải pháp Web GIS hoàn chỉnh, độc lập và có tính ứng dụng cao. Đây là nền tảng kỹ thuật vững chắc để tiếp tục phát triển các hệ thống điều hướng thông minh, logistics đô thị và dịch vụ định vị mã nguồn mở trong tương lai.