Giới thiệu dự án

Trong bối cảnh đô thị hóa và sự phát triển vượt bậc của các dịch vụ định vị địa lý (GIS - Geographic Information System), bài toán tìm đường đi tối ưu (Shortest Path Problem) đóng vai trò then chốt trong việc giải quyết ùn tắc giao thông, tối ưu hóa chuỗi cung ứng logistics và nâng cao trải nghiệm di chuyển cá nhân. Theo các báo cáo thống kê ngành giao thông thông minh, việc ứng dụng các thuật toán định tuyến chính xác có thể giảm tới 15-20% thời gian di chuyển và tiết kiệm hàng triệu lít nhiên liệu tiêu hao mỗi năm tại các đô thị lớn.

Tuy nhiên, các hệ thống điều hướng trực tuyến hiện nay như Google Maps, Bing Maps hay OpenStreetMap (OSM) dù sở hữu kho dữ liệu khổng lồ nhưng vẫn tồn tại những rào cản tương tác đối với người dùng bản địa. Cụ thể, thao tác đổi điểm đi/đến đòi hỏi nhiều bước kéo thả biểu tượng phức tạp, khó tương tác trên thiết bị di động màn hình nhỏ, và chưa tối ưu hóa triệt để cho các quy chuẩn giao thông đặc thù tại Việt Nam (như hệ thống ngõ ngách hẹp cấm ô tô, cầu vượt phân luồng cấm xe máy và người đi bộ).

Đề 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 (Trường Đại học Quản lý và Công nghệ Hải Phòng) thực hiện dưới sự hướng dẫn của TS. Lương Thanh Nhạn tập trung giải quyết bài toán định tuyến đường bộ có ràng buộc không gian và phương tiện tại khu vực thành phố Hải Phòng.

graph LR
    A[Người dùng tương tác Web UI] --> B[Gửi tọa độ Điểm đi/đến & Phương tiện]
    B --> C[Node.js / Express Server]
    C --> D[Xử lý Đồ thị Trọng số từ OSM Data]
    D --> E[Thực thi Thuật toán Dijkstra có ràng buộc]
    E --> F[Trả về Polyline Tuyến đường tối ưu]
    F --> G[Render trực quan trên Leaflet.js Map]

Mục tiêu dự án

  1. Thu thập và mô hình hóa dữ liệu địa lý: Khai thác dữ liệu bản đồ mở OpenStreetMap khu vực nội thành Hải Phòng bằng công cụ Overpass Turbo, chuyển đổi thành cấu trúc đồ thị trọng số (Spatial Graph) lưu trữ dưới định dạng JSON.
  2. Nghiên cứu và hiện thực hóa thuật toán định tuyến: Phân tích, so sánh hiệu năng các thuật toán đường đi ngắn nhất (Dijkstra, Bellman-Ford, Floyd-Warshall) và lập trình thuật toán tối ưu có tích hợp ràng buộc giao thông (đường một chiều, loại phương tiện).
  3. Phát triển ứng dụng Web GIS tương tác cao: Xây dựng giao diện web thân thiện với khả năng click/chạm trực tiếp trên bản đồ để chọn tọa độ, tự động gợi ý tìm kiếm địa điểm và trực quan hóa tuyến đường.

Phương pháp tiếp cận và kết quả kỳ vọng

Dự án áp dụng phương pháp phân tích thực nghiệm và mô hình hóa dữ liệu không gian. Dữ liệu thô gồm 20.104 điểm (nodes) và 1.883 đoạn đường (ways) được tiền xử lý thành đồ thị 9.944 đỉnh với ma trận kề tính toán bằng công thức Haversine. Hệ thống kỳ vọng đạt thời gian phản hồi định tuyến dưới 200ms trên môi trường máy chủ Node.js cục bộ, đảm bảo tính chính xác 100% về mặt khoảng cách và tuân thủ các quy tắc phân luồng giao thông.

Phạm vi và giới hạn

  • Phạm vi địa lý: Khu vực nội thành thành phố Hải Phòng, Việt Nam.
  • Phương tiện hỗ trợ: Ô tô (motorcar), Xe máy (motorcycle), Đi bộ (foot).
  • Giới hạn kỹ thuật: Đồ thị tĩnh (chưa tích hợp luồng dữ liệu giao thông thời gian thực - Real-time Traffic Jam).

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

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

Hiện nay, các giải pháp bản đồ trực tuyến thương mại thống trị thị trường nhưng bộc lộ nhiều điểm hạn chế về khả năng tùy biến cục bộ:

Tiêu chí Google Maps Bing Maps Ứng dụng đề tài (HPU Web Map)
Nguồn dữ liệu Độc quyền (Dữ liệu đóng, có phí API) Độc quyền (Microsoft, có phí API) Dữ liệu mở OpenStreetMap (Mã nguồn mở, miễn phí)
Tương tác chọn điểm Kéo thả pin / Nhập text form Kéo thả pin / Nhập text form Chạm/Click trực tiếp tại tọa độ bất kỳ trên Map
Phân luồng chi tiết Có (tổng quát theo quốc lộ/phố lớn) Có (tổng quát) Ràng buộc sâu theo ngõ hẹp, cấm xe máy, cấm đi bộ
Khả năng tự triển khai Không thể tự host máy chủ riêng Không thể tự host máy chủ riêng Toàn quyền kiểm soát Server nội bộ (Node.js backend)
Chi phí vận hành Tăng theo số lượng request API Tăng theo số lượng request API $0 chi phí bản quyền dữ liệu

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

  • Must have (Bắt buộc): Tìm đường đi ngắn nhất giữa 2 điểm; Tùy chọn 3 phương tiện (ô tô, xe máy, đi bộ); Kiểm soát đường 1 chiều (oneway); Giao diện bản đồ tương tác Leaflet.js.
  • Should have (Nên có): Gợi ý địa điểm thông minh (Autocomplete); Hiển thị bảng thông tin chi tiết tên đường và tổng khoảng cách (km).
  • Could have (Có thể có): Lọc tìm kiếm theo danh mục địa điểm (trạm xăng, bệnh viện, trường học).
  • Won't have (Chưa phát triển): Định vị GPS động theo thời gian thực và dẫn đường bằng giọng nói.

Thiết kế hệ thống

Kiến trúc tổng thể và Công nghệ sử dụng

Hệ thống được thiết kế theo mô hình Client-Server phi trạng thái (Stateless Web Architecture):

  • Frontend Stack: HTML5, CSS3, JavaScript (ES6+), Thư viện bản đồ Leaflet.js v1.9.4.
  • Backend Stack: Node.js LTS v18.x/v20.x, Web Framework Express.js v4.18.2, Middleware Body-Parser v1.20.2.
  • Nguồn dữ liệu & Công cụ: OpenStreetMap (OSM), Overpass Turbo QL Engine, Định dạng dữ liệu JSON.
+-------------------------------------------------------------+
|                      CLIENT BROWSER                         |
|   +-----------------------------------------------------+   |
|   |         Leaflet.js (Map Tiles OSM Rendering)        |   |
|   |   Autocomplete Search UI  |  Map Click Listener     |   |
|   +-----------------------------------------------------+   |
+------------------------------|------------------------------+
                               | HTTP POST /api/find-path
                               v
+-------------------------------------------------------------+
|                     NODE.JS WEB SERVER                      |
|   +-----------------------------------------------------+   |
|   |         Express Router & Body-Parser Middleware      |   |
|   +-----------------------------------------------------+   |
|   |                  Dijkstra Engine                    |   |
|   | - Constraints Filter (Vehicle type, oneway rules)   |   |
|   | - Haversine Distance Calculator                     |   |
|   +-----------------------------------------------------+   |
|   |         In-Memory Graph Data (9,944 Nodes JSON)     |   |
|   +-----------------------------------------------------+   |
+-------------------------------------------------------------+

Thiết kế mô hình dữ liệu không gian

Dữ liệu đồ thị không gian graph.json được trích xuất và biến đổi từ tập dữ liệu thô data.json của OpenStreetMap:

  1. Cấu trúc thực thể Node (Đỉnh):
{
  "type": "node",
  "id": 8730486582,
  "lat": 20.8492341,
  "lon": 106.6789123
}
  1. Cấu trúc thực thể Graph (Danh sách kề kèm trọng số và ràng buộc):
{
  "nodeId": "8730486582",
  "adjacentNodes": [
    {
      "node": "10095784904",
      "distance": 0.021872,
      "oneway": false,
      "motorcar": true,
      "motorcycle": true,
      "foot": true
    },
    {
      "node": "8730486581",
      "distance": 0.015430,
      "oneway": true,
      "motorcar": false,
      "motorcycle": true,
      "foot": true
    }
  ]
}

Phương pháp luận (Methodology)

Quy trình phát triển phần mềm tuân thủ theo mô hình lặp kết hợp kiểm thử thực nghiệm:

  1. Giai đoạn 1 - Khai phá dữ liệu: Viết truy vấn Overpass QL để quét hộp giới hạn (Bounding Box) tọa độ Hải Phòng, trích xuất 20.104 nodes và 1.883 ways.
  2. Giai đoạn 2 - Tiền xử lý đồ thị: Tính toán khoảng cách cạnh bằng công thức lượng giác mặt cầu và lọc các đỉnh cô lập, giảm tải tập dữ liệu xuống còn 9.944 đỉnh hợp lệ.
  3. Giai đoạn 3 - Xây dựng lõi thuật toán & Backend: Hiện thực hóa các thuật toán đường đi ngắn nhất trên Node.js.
  4. Giai đoạn 4 - Tích hợp Frontend & Kiểm thử nghiệm thu: Ráp nối API với giao diện Leaflet, thử nghiệm đa kịch bản phân luồng.

Implementation và kết quả

Development Process

1. Thuật toán tính khoảng cách địa lý (Haversine Formula)

Để tính độ dài cạnh (trọng số khoảng cách giữa hai đỉnh trên mặt cầu Trái Đất dựa vào kinh độ $\lambda$ và vĩ độ $\varphi$), công thức Haversine được triển khai với bán kính trung bình Trái Đất $R = 6371\text{ km}$:

$$\Delta \varphi = \varphi_2 - \varphi_1, \quad \Delta \lambda = \lambda_2 - \lambda_1$$ $$a = \sin^2\left(\frac{\Delta \varphi}{2}\right) + \cos(\varphi_1) \cdot \cos(\varphi_2) \cdot \sin^2\left(\frac{\Delta \lambda}{2}\right)$$ $$d = 2 \cdot R \cdot \arcsin(\sqrt{a})$$

2. Cài đặt thuật toán Dijkstra có ràng buộc phương tiện

Mã nguồn xử lý định tuyến phía Server Node.js duyệt đồ thị với hàng đợi ưu tiên và áp dụng bộ lọc thuộc tính phương tiện:

function findShortestPathDijkstra(graph, startNodeId, endNodeId, vehicleType) {
    let distances = {};
    let previous = {};
    let unvisited = new Set();

    // Khởi tạo bảng khoảng cách ban đầu
    for (let node in graph) {
        distances[node] = Infinity;
        previous[node] = null;
        unvisited.add(node);
    }
    distances[startNodeId] = 0;

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

        if (distances[currentNode] === Infinity || currentNode === endNodeId) {
            break; // Đã đến đích hoặc các đỉnh còn lại không thể chạm tới
        }

        unvisited.delete(currentNode);

        // Duyệt các đỉnh kề thỏa mãn điều kiện phương tiện
        let neighbors = graph[currentNode].adjacentNodes || [];
        for (let edge of neighbors) {
            if (!unvisited.has(edge.node)) continue;

            // Kiểm tra ràng buộc phân luồng theo phương tiện di chuyển
            let isAccessible = true;
            if (vehicleType === 'car' && !edge.motorcar) isAccessible = false;
            if (vehicleType === 'motorcycle' && !edge.motorcycle) isAccessible = false;
            if (vehicleType === 'foot' && !edge.foot) isAccessible = false;

            if (isAccessible) {
                let alt = distances[currentNode] + edge.distance;
                if (alt < distances[edge.node]) {
                    distances[edge.node] = alt;
                    previous[edge.node] = currentNode;
                }
            }
        }
    }

    // Truy vết đường đi từ đích về nguồn
    let path = [];
    let curr = endNodeId;
    while (curr) {
        path.unshift(curr);
        curr = previous[curr];
    }
    return { path, totalDistance: distances[endNodeId] };
}

Testing và validation

Đánh giá Benchmark hiệu năng thuật toán

Nghiên cứu tiến hành chạy thử nghiệm so sánh 3 thuật toán tìm đường kinh điển trên cùng một tập dữ liệu đồ thị thực tế của dự án (9.944 đỉnh):

Thuật toán Độ phức tạp thời gian Bộ nhớ yêu cầu Thời gian thực thi (Dataset 9.944 Nodes) Tỷ lệ chênh lệch thời gian so với Dijkstra
Dijkstra $O((V + E) \log V)$ Thấp ($O(V)$) ~177 mili-giây (0.177s) Gốc (Chuẩn tối ưu)
Bellman-Ford $O(V \cdot E)$ Thấp ($O(V)$) ~1 phút 56 giây (116s) Chậm hơn 655 lần
Floyd-Warshall $O(V^3)$ Rất cao ($O(V^2)$) ~1 giờ 46 phút 26 giây (6386s) Chậm hơn 36.079 lần

[!IMPORTANT] Kết quả đo lường thực nghiệm chứng minh thuật toán Dijkstra tối ưu vượt trội (nhanh hơn Bellman-Ford 99.85% về thời gian phản hồi) khi giải quyết bài toán tìm đường đơn cặp nguồn - đích trên đồ thị trọng số không âm của mạng lưới giao thông đô thị.

Kết quả thử nghiệm kịch bản phân luồng giao thông

Hệ thống đã trải qua các bài kiểm thử biên với các kịch bản thực địa tại Hải Phòng:

  1. Kịch bản 1: Tuyến đường không có đường một chiều: Tất cả phương tiện (ô tô, xe máy, đi bộ) đều tìm được lộ trình ngắn nhất tương đồng về hình học.
  2. Kịch bản 2: Tuyến đường có đường một chiều (oneway: true): Ô tô và xe máy được định tuyến đi vòng qua các nút giao hợp lệ, trong khi người đi bộ vẫn được phép đi tuyến ngắn nhất theo vỉa hè hai chiều.
  3. Kịch bản 3: Đoạn đường cấm xe máy và người đi bộ (Cầu vượt cao tốc/đường gom chuyên dụng): Hệ thống chỉ mở đường cho ô tô đi thẳng; xe máy và người đi bộ tự động chuyển hướng qua đường nhánh dân sinh.
  4. Kịch bản 4: Tuyến đường cấm ô tô (Ngõ hẹp dưới 2m): Ô tô được định tuyến đi vòng đường lớn; xe máy và người đi bộ đi qua ngõ ngách để rút ngắn quãng đường.

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

  1. Tương tác bản đồ cảm ứng trực tiếp (Direct Map Interaction): Khắc phục triệt để nhược điểm thao tác kéo thả phức tạp trên Google Maps; người dùng chỉ cần nhấp điểm bắt đầu và điểm đến trực tiếp trên nền Leaflet, giảm thời gian thao tác từ 15 giây xuống dưới 3 giây.
  2. Tích hợp sâu thuộc tính OSM vào định tuyến đa phương tiện: Thay vì chỉ tính khoảng cách đơn thuần, hệ thống bóc tách các thẻ tag OSM (highway=residential, motorcar=no, oneway=yes) trực tiếp vào cấu trúc đồ thị JSON, giải quyết bài toán giao thông ngõ xóm đặc thù của Việt Nam.
  3. Tối ưu hóa tài nguyên máy chủ cục bộ: Chuyển đổi dữ liệu bản đồ cồng kềnh (hàng chục MB XML) thành cấu trúc danh sách kề tinh gọn (2.4MB JSON), cho phép chạy toàn bộ thuật toán trong bộ nhớ RAM (In-memory computation) với thời gian phản hồi cực nhanh ~177ms mà không cần hệ thống máy chủ đắt tiền.

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

Kịch bản ứng dụng

  • Dịch vụ giao hàng chặng cuối (Last-Mile Delivery): Hỗ trợ shipper xe máy tìm kiếm lối đi tắt qua hệ thống ngõ ngách nhỏ hẹp mà các ứng dụng điều hướng ô tô thông thường không nhận diện được.
  • Hệ thống điều phối cứu hộ nội bộ đô thị: Triển khai độc lập cho các bệnh viện, trạm cứu hỏa tại địa phương để định tuyến xe cấp cứu trong tình trạng mất kết nối Internet toàn cầu (Offline GIS Server).
# Hướng dẫn khởi chạy hệ thống trên môi trường Linux/Windows Server:
# Bước 1: Clone repository và cài đặt thư viện phụ thuộc
npm init -y
npm install express body-parser leaflet

# Bước 2: Khởi động Web Server
node server.js

# Server chạy mặc định tại cổng HTTP Port: http://localhost:3000

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

Hạn chế kỹ thuật

  • Đồ thị tĩnh: Trọng số khoảng cách giữa các đỉnh là cố định theo độ dài vật lý, chưa thể cập nhật biến động theo thời gian thực (như kẹt xe giờ cao điểm hay ngập lụt).
  • Bộ nhớ mở rộng: Việc lưu trữ toàn bộ đồ thị trên bộ nhớ RAM của một Node.js process đơn lẻ sẽ gặp khó khăn khi mở rộng phạm vi ra toàn bộ lãnh thổ quốc gia.

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

  • Ứng dụng cấu trúc dữ liệu đồ thị nâng cao Contraction Hierarchies (CH) hoặc thuật toán A* (A-Star) kết hợp Heuristic để tăng tốc độ tìm kiếm khi mở rộng quy mô đồ thị lên hàng triệu đỉnh.
  • Tích hợp cơ sở dữ liệu không gian chuyên dụng PostGIS / PostgreSQL để tối ưu hóa truy vấn không gian phức tạp.

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

  • Sinh viên & Giảng viên Công nghệ Thông tin: Nguồn tài liệu tham khảo trực quan, đầy đủ từ khâu toán học giải thuật đến hiện thực hóa mã nguồn ứng dụng Web GIS hoàn chỉnh.
  • Lập trình viên phát triển Web: Nắm bắt kỹ thuật tích hợp bản đồ Leaflet.js, trích xuất dữ liệu bản đồ mở OpenStreetMap bằng Overpass Turbo API và xử lý bất đồng bộ trong Node.js.
  • Doanh nghiệp vận tải & Chuyển phát nhanh địa phương: Một giải pháp định tuyến độc lập, miễn phí bản quyền API bản đồ, dễ dàng tích hợp vào hệ thống ERP quản lý đội xe nội bộ.

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

1. Ứng dụng yêu cầu cấu hình phần cứng tối thiểu như thế nào để triển khai?

Hệ thống yêu cầu CPU tối thiểu 2 lõi (Dual-core), 2GB RAM và 500MB dung lượng ổ cứng khả dụng. Ứng dụng chạy trên mọi nền tảng hỗ trợ Node.js (Windows, Ubuntu Linux, macOS) và tương thích hoàn toàn với các trình duyệt web hiện đại (Chrome, Edge, Firefox, Safari).

2. Vì sao đồ án chọn thuật toán Dijkstra thay vì thuật toán A* hoặc Floyd-Warshall?

Thuật toán Floyd-Warshall có độ phức tạp quá lớn ($O(V^3)$), mất hơn 1.7 giờ trên đồ thị gần 10.000 đỉnh. Thuật toán Dijkstra với độ phức tạp $O((V+E)\log V)$ đem lại thời gian chạy chỉ ~177ms, đảm bảo tìm ra đường đi ngắn nhất tuyệt đối mà không cần thiết lập hàm Heuristic ước lượng phức tạp như thuật toán A*.

3. Dữ liệu bản đồ OpenStreetMap có thể tự động cập nhật khi đường sá thay đổi không?

Dữ liệu hiện tại được xuất định kỳ từ Overpass Turbo thành tệp JSON. Để cập nhật tự động, hệ thống có thể thiết lập một Cron Job định kỳ truy vấn Overpass API theo chu kỳ tuần/tháng để đồng bộ các thay đổi về đường sá mới mở hoặc phân luồng giao thông.

4. Hệ thống có thể tích hợp vào ứng dụng di động (Android / iOS) không?

Có. Do Backend Node.js được thiết kế dưới dạng RESTful API cung cấp kết quả định tuyến định dạng JSON (danh sách tọa độ Polyline), các ứng dụng di động React Native, Flutter hoặc Swift/Kotlin đều có thể dễ dàng gọi API và hiển thị tuyến đường lên bản đồ.

5. Chi phí vận hành và bảo trì hệ thống ước tính như thế nào?

Chi phí vận hành gần như bằng 0 do sử dụng hoàn toàn mã nguồn mở và nền tảng dữ liệu mở OpenStreetMap, loại bỏ hoàn toàn chi phí bản quyền API đắt đỏ của Google Maps Platform khi có lượng truy cập cao.

Kết luận

Đồ án "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 xuất sắc các mục tiêu nghiên cứu và thực tiễn đề ra. Dự án không chỉ chứng minh tính đúng đắn và hiệu năng vượt trội của thuật toán Dijkstra trên dữ liệu thực tế tại thành phố Hải Phòng (~177ms phản hồi trên 9.944 đỉnh) mà còn mang lại một giải pháp Web GIS tiện ích, đáp ứng chính xác các quy chuẩn phân luồng giao thông đô thị đặc thù. Đây là nền tảng vững chắc để tiếp tục mở rộng phát triển thành các hệ thống điều hướng thông minh đa chức năng phục vụ cộng đồng và doanh nghiệp trong tương lai.